系统设计 - 设计一个速率限制器

实施速率限制器的位置主要取决于我们的应用程序、技术栈、技术团队等因素。通常有三个位置可供选择：客户端、服务器端或中间件。

客户端是不可靠的地方来执行速率限制，因为恶意行为者可以轻易伪造客户端请求。

比将速率限制器放在服务器端更好的方法是使用速率限制器中间件，它甚至可以对我们的服务器端进行限流。因此，如果您正在使用微服务架构，并且已经使用类似身份验证中间件的功能，则可以在其旁边实现速率限制器中间件。

有许多速率限制算法可供选择：我们将介绍一些算法，包括“令牌桶”、“漏桶”、“滑动窗口计数器”等。

令牌桶算法

Stripe (点击此处阅读)^[1] 使用令牌桶算法来限制他们的 API 请求。

根据 Stripe 技术博客：

我们使用令牌桶算法来执行速率限制。这个算法有一个中央的桶主机，你每次请求时都从中取出令牌，并慢慢地向桶中滴入更多令牌。如果桶是空的，就拒绝请求。在我们的情况下，每个 Stripe 用户都有一个桶，每次他们发出请求时，我们就从那个桶中删除一个令牌。我们使用 Redis 实现我们的速率限制器。

桶中有预定义容量的令牌。当请求到达时，它从桶中取出一个令牌并进一步处理。如果没有令牌可供获取，则请求将被丢弃，用户将不得不重试。

示例用例：

•我们将速率限制规则设置为每个用户每分钟 3 个请求。•用户1在 00 时间间隔发出请求，当前桶已满，有 3 个令牌，因此请求将被处理。现在桶中的令牌数量更新为 2。•用户1在第 10 秒发出第二个请求，桶中有 2 个令牌，所以请求将进一步处理。现在桶中的令牌数量更新为 1。•用户1在第 30 秒发出第三个请求，桶中有 1 个令牌，所以请求将进一步处理。现在整整 1 分钟内桶都为空。•用户1在第 55 秒发出第四个请求，桶中没有令牌，因此请求被限制，用户将收到 429 状态码 - 请求太多，并被要求稍后重试。HTTP 429 Too Many Requests 响应状态码表示用户在给定的时间内发送了太多请求。•在那 1 分钟的完成时，令牌计数以固定速率刷新，并且桶再次装满了 3 个令牌，可以再次为该特定用户处理请求。

简单来说：

在令牌桶算法中，我们每次请求都会从桶中处理一个令牌。新令牌以速率 r 放入桶中。桶最多可以容纳 b 个令牌。如果请求到来时桶已满，则该请求将被丢弃。

令牌桶算法需要两个参数：

令牌桶算法代码示例

package mainimport ("fmt""math""time"
)const (MAX_BUCKET_SIZE float64 = 3REFILL_RATE     int     = 1
)type TokenBucket struct {currentBucketSize   float64lastRefillTimestamp int
}func (tb *TokenBucket) allowRequest(tokens float64) bool {tb.refill() //refill of bucket happening at constant REFILL_RATEif tb.currentBucketSize >= tokens {tb.currentBucketSize -= tokensreturn true}return false
}func getCurrentTimeInNanoseconds() int {return time.Now().Nanosecond()
}func (tb *TokenBucket) refill() {nowTime := getCurrentTimeInNanoseconds()tokensToAdd := (nowTime - tb.lastRefillTimestamp) * REFILL_RATE / 1e9tb.currentBucketSize = math.Min(tb.currentBucketSize+float64(tokensToAdd), MAX_BUCKET_SIZE)tb.lastRefillTimestamp = nowTime
}func main() {obj := TokenBucket{currentBucketSize:   3,lastRefillTimestamp: 0,}fmt.Printf("Request processed: %v\n", obj.allowRequest(1)) //truefmt.Printf("Request processed: %v\n", obj.allowRequest(1)) //truefmt.Printf("Request processed: %v\n", obj.allowRequest(1)) //truefmt.Printf("Request processed: %v\n", obj.allowRequest(1)) //false, request dropped
}

Leaky Bucket Algorithm

Leaky Bucket是使用队列实现速率限制的一种简单直观的方式。它是一个先进先出的队列（FIFO）。进来的请求被附加到队列中，如果没有足够的空间容纳新的请求，则会被丢弃（泄漏）。

•当一个请求到达时，系统检查队列是否已满。如果没有满，则将请求添加到队列中。•否则，请求将被丢弃。•请求以固定的间隔从队列中提取并处理。

算法的工作原理：

泄漏桶算法接受以下两个参数：

•桶大小：等于队列大小。队列保存要以固定速率处理的请求。•流出速率：定义在固定速率内可以处理多少请求，通常以秒为单位。

该算法的优点是，它平滑处理请求的突发，并以大致平均的速率处理它们。

Sliding Window Algorithm

•该算法跟踪请求的时间戳。时间戳数据通常保存在缓存中，例如 Redis 的有序集合。•当一个新请求到来时，删除所有过期的时间戳。过期的时间戳被定义为早于当前时间窗口的开始时间。•将新请求的时间戳添加到日志中。•如果日志大小与允许的请求数相同或更低，则接受请求。否则，拒绝该请求。

在下面的示例中，速率限制器允许我们每分钟2个请求。窗口内超出此限制的请求将被丢弃。

注意： 为了便于理解，我们使用了hh:mm:ss格式，但在redis中，我们将推送UNIX时间戳。

•当一个新请求在1:00:01到达时，日志为空。因此，请求被允许。•一个新请求在1:00:30到达，时间戳1:00:30被插入日志中。插入后，日志大小为2，不大于允许的请求数。因此，请求被允许。•一个新请求在1:00:50到达，时间戳被插入到日志中。插入后，日志大小为3，大于允许的大小2。因此，该请求被拒绝，即使时间戳仍然存在于日志中。•一个新请求在1:01:40到达。在[1:00:40,1:01:40)范围内的请求在最新时间范围内，但在1:00:40之前发送的请求已过时。两个过时的时间戳1:00:01和1:00:30从日志中删除。删除操作后，日志大小变为2；因此，该请求被接受。

速率限制器的详细设计：

我们将使用以下组件：

•配置和数据存储来存储速率限制器规则。•工作进程经常从磁盘中获取规则并将其存储在缓存中。•速率限制器中间件从缓存中获取规则。它还从Redis中获取时间戳、计数器等数据。当请求到来时，它进行计算并决定是处理该请求还是对其进行速率限制。•如果需要对请求进行速率限制，这里有两个选项•选项1：拒绝请求并向客户端发送状态代码429: too many requests。•选项2：将请求推送到消息队列以稍后处理该请求。

现在，我们可能需要将以上系统扩展到分布式环境中，以支持多个服务器和并发线程。这里可能会出现两个挑战：

竞争条件

如上所述：

从Redis中读取计数器值，检查(计数器+1)是否超过阈值。如果没有，将计数器值在Redis中增加1。

假设Redis中的计数器值为3（如上图所示）。如果两个请求并发读取计数器值，而在任一请求写回值之前，都不检查另一个线程。它们都会将计数器增加1并写回，而不会检查其他线程。两个请求（线程）都认为它们有正确的计数器值4。但是，正确的计数器值应该是5。

锁可以在这里使用，但这可能会影响性能。因此，我们可以使用Redis Lua脚本^[2]。

•这可能会导致更好的性能。•此外，脚本中的所有步骤都以原子方式执行。在脚本执行时，没有其他Redis命令可以运行。

同步

在分布式环境中，同步是另一个需要考虑的重要因素。为了支持数百万用户，一个速率限制服务器可能无法处理流量。当使用多个速率限制服务器时，需要同步。

一种可能的解决方案是使用黏性会话，允许客户端将流量发送到相同的速率限制器。这种解决方案既不可扩展也不灵活。更好的方法是使用像Redis这样的集中式数据存储。

在所有事情都就绪之后，我们还可以监视我们的速率限制器以获取性能、规则、算法有效性等指标。例如，如果速率限制规则过于严格，会丢弃许多有效请求。在这种情况下，我们希望稍微放松一下规则。在另一个例子中，我们注意到当有突然增加的流量，如抢购时，我们的速率限制器变得无效。在这种情况下，我们可以更改算法以支持突发流量。令牌桶在这里非常合适。

引用链接

[1] (点击此处阅读): https://stripe.com/blog/rate-limiters
[2] Redis Lua脚本: https://www.freecodecamp.org/news/a-quick-guide-to-redis-lua-scripting/