克服硬性速率限制：使用令牌桶和 Redis 实现高效速率限制

作为开发人员，处理外部集成经常会面临挑战，尤其是当这些集成施加严格的速率限制时。

最近，我遇到了一个重大问题，我们的应用程序反复受到外部 API 的严格速率限制，导致请求频繁失败，并破坏了我们的数据摄取管道。

最初尝试的管理方法，例如简单的重试机制和手动速率限制，都无法有效应对这种情况。这促使我探索更复杂的解决方案：令牌桶算法和指数退避算法，并利用 Redis 来确保分布式系统的可扩展性。

挑战：速率限制和请求失败

在与第三方 API 交互时，您经常会遇到速率限制——即在给定时间范围内可以发出的请求数量受到限制。超出这些限制可能会导致请求被拒绝、服务中断，最终影响用户体验。

就我们而言，流量特性和系统的分布式特性加剧了这一挑战。这个问题出现在我们的一位客户将其全部 400 个代码库与我们的开发者生产力分析平台Middleware进行同步时。

举例来说，需要同步的数据包含超过 5 万个拉取请求，每个请求大约需要 4 次请求，总计 20 万次请求。然而，该账户的速率限制仅为每小时 2000 次请求。
诸如固定延迟和单服务器速率限制之类的简单解决方案不足以应对，因此需要一种更稳健的方法。

高级解决方案：基于令牌分桶和指数退避的流量整形

为了有效解决速率限制问题，我计划实施一种流量整形策略，该策略结合了令牌桶算法和指数退避算法。以下是这些概念的概要：

流量整形：管理请求流，以确保与外部 API 的交互顺畅，且不超出速率限制。
- 令牌桶：一种限速算法，允许流量突发，同时在一段时间内强制执行稳定的速率。
指数退避：一种重试机制，它以指数级速度增加重试之间的等待时间，从而降低外部 API 过载的可能性。

了解交通流向塑造

流量整形是指控制向外部服务发送请求的速率。通过实施令牌桶系统，我们可以在保持请求速率长期稳定的同时，允许短时间内出现流量突发。这可以防止外部服务过载，并降低触及速率限制的风险。

令牌桶算法

来源：GeeksforGeeks

令牌桶算法是一种简单而有效的速率限制方法。其工作原理如下：

一个桶可以保存一定数量的令牌，每个令牌代表发出一个请求的权限。
代币以固定速率添加到桶中。
当发出请求时，会从存储桶中移除一个令牌。如果存储桶为空，则请求将被拒绝或延迟。
存储桶有最大容量限制，因此无法容纳超过预设限制的代币数量。

找到合适的最大代币数量和充值率

确定最大令牌数和充值速率的最佳值需要了解应用程序的流量模式和外部 API 的速率限制。例如，如果 API 允许每分钟 100 个请求：

最大令牌数：设置为 100，允许最多一次性发送 100 个请求。
补充速度：设置为每秒约 1.67 个代币（100 个代币/60 秒）。

指数退避算法

指数退避是一种重试策略，其中重试之间的等待时间呈指数级增长。这种方法通过拉开重试间隔，避免在初始失败后出现大量请求，从而降低外部 API 的负载。

以下是一个简单的伪代码实现：

initial_delay = 1 second
max_delay = 32 seconds
attempts = 0

while (attempts < max_attempts) {
    result = make_request()
    if (result.success) {
        break
    }
    delay = min(initial_delay * 2^attempts, max_delay)
    sleep(delay)
    attempts += 1
}

将令牌桶和指数退避与 Redis 集成

Redis 是一种内存数据结构存储，由于其速度快且支持原子操作，因此是分布式系统中实现速率限制的绝佳选择。

为什么选择 Redis？

之所以选择 Redis，是因为它拥有强大的功能集，能够完美地满足分布式速率限制解决方案的需求：

可扩展性：能够处理高吞吐量和低延迟，使其适用于分布式系统。
原子操作：确保跨多个实例可靠地执行令牌桶更新和检查。
持久化：可选择将数据持久化到磁盘，以确保速率限制状态在重启后仍然存在。

使用 Redis 实现令牌桶

import redis
import time

redis_client = redis.StrictRedis(host='localhost', port=6379, db=0)

def get_tokens(bucket_key, refill_rate, max_tokens):
    current_time = time.time()
    last_refill_time = redis_client.hget(bucket_key, 'last_refill_time') or current_time
    tokens = int(redis_client.hget(bucket_key, 'tokens') or max_tokens)
    
    elapsed_time = current_time - float(last_refill_time)
    new_tokens = int(elapsed_time * refill_rate)
    
    tokens = min(tokens + new_tokens, max_tokens)
    redis_client.hset(bucket_key, 'tokens', tokens)
    redis_client.hset(bucket_key, 'last_refill_time', current_time)
    
    return tokens

def consume_token(bucket_key, refill_rate, max_tokens):
    tokens = get_tokens(bucket_key, refill_rate, max_tokens)
    if tokens > 0:
        redis_client.hincrby(bucket_key, 'tokens', -1)
        return True
    else:
        return False