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

2023-05-22 17:54:47 系统 设计

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

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

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

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

令牌桶算法

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 main
import ( "fmt" "math" "time")
const ( MAX_BUCKET_SIZE float64 = 3 REFILL_RATE int = 1)
type TokenBucket struct { currentBucketSize float64 lastRefillTimestamp int}
func (tb *TokenBucket) allowRequest(tokens float64) bool { tb.refill() //refill of bucket happening at constant REFILL_RATE
if tb.currentBucketSize >= tokens { tb.currentBucketSize -= tokens return true }
return false}
func getCurrentTimeInNanoseconds() int { return time.Now().Nanosecond()}
func (tb *TokenBucket) refill() { nowTime := getCurrentTimeInNanoseconds()
tokensToAdd := (nowTime - tb.lastRefillTimestamp) * REFILL_RATE / 1e9
tb.currentBucketSize = math.Min(tb.currentBucketSize+float64(tokensToAdd), MAX_BUCKET_SIZE) tb.lastRefillTimestamp = nowTime}
func main() { obj := TokenBucket{ currentBucketSize: 3, lastRefillTimestamp: , }
fmt.Printf("Request processed: %v\n", obj.allowRequest(1)) //true fmt.Printf("Request processed: %v\n", obj.allowRequest(1)) //true fmt.Printf("Request processed: %v\n", obj.allowRequest(1)) //true fmt.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/

相关文章