实施速率限制器的位置主要取决于我们的应用程序、技术栈、技术团队等因素。通常有三个位置可供选择:客户端、服务器端或中间件。
客户端是不可靠的地方来执行速率限制,因为恶意行为者可以轻易伪造客户端请求。
比将速率限制器放在服务器端更好的方法是使用速率限制器中间件,它甚至可以对我们的服务器端进行限流。因此,如果您正在使用微服务架构,并且已经使用类似身份验证中间件的功能,则可以在其旁边实现速率限制器中间件。
有许多速率限制算法可供选择:我们将介绍一些算法,包括“令牌桶”、“漏桶”、“滑动窗口计数器”等。
令牌桶算法
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: 0,
}
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/
原创文章,作者:小技术君,如若转载,请注明出处:https://www.sudun.com/ask/33880.html