Learn Cybersecurity令牌桶
到目前为止讲过的算法,都把突发流量当成一个问题来处理。可实际上,很多突发都是再正常不过的事:一个页面同时加载六个资源,或者一个闲置了一分钟的客户端突然有活要干。
令牌桶算法允许这种突发存在,而且是有意为之。令牌以恒定速率累积,每次请求消耗一个,一个安静了一阵子的客户端手头就会攒下一些令牌。
树叶与毛毛虫
一株植物最多能长五片叶子,每天长三片。每来一只毛毛虫就吃掉一片叶子,如果没叶子可吃,这只毛毛虫就活不下去了。
| 天数 | 长出的叶子 | 毛毛虫数量 | 结果 | 剩余叶子 |
|---|---|---|---|---|
| 1 | 3 | 2 | 两只都吃到了 | 1 |
| 2 | 3,累计4片 | 5 | 4只吃到,1只没吃到 | 0 |
| 3 | 3 | 0 | 什么都没发生 | 3 |
| 4 | 长2片,封顶5片 | 0 | 什么都没发生 | 5 |
这张表里藏着三个要点:
- 一片叶子就是一个令牌,一次请求消耗一个。
- 令牌按固定速率产生,不管有没有人在申请。
- 植物容量有上限,所以第四天只长了两片而不是三片。
正是这个容量上限,才允许了突发的存在。一个满的令牌桶可以一次性花光,所以一个安静了很久的客户端能瞬间发出五个请求,然后就得等新令牌长出来。
补充速率决定了长期的平均水平,容量决定了你能容忍多大的突发。
正是这个上限,决定了突发流量的规模是有限的。要是没有这个上限,一个闲置了一小时的客户端回来时,就能一口气把攒了一小时的量全部发出去。
搭建令牌桶
状态只有两个数字,逻辑只有两个判断。
class TokenBucket {
constructor(capacity, refillRate, refillInterval) {
this.capacity = capacity
this.refillRate = refillRate
this.refillInterval = refillInterval
this.tokens = capacity // 初始为满
this.secondsSinceLastRefill = 0
}
processRequests(numRequests) {
this.secondsSinceLastRefill += 1
if (this.secondsSinceLastRefill >= this.refillInterval) {
this.tokens = Math.min(this.capacity, this.tokens + this.refillRate)
this.secondsSinceLastRefill = 0
}
const accepted = Math.min(numRequests, this.tokens)
const rejected = numRequests - accepted
this.tokens -= accepted
return { accepted, rejected }
}
}真正干活的是这两处 Math.min。
第一处把补充量限制在容量以内,确保令牌数永远不会超过上限。第二处把接受数量限制在现有令牌数以内,所以一个想要九个令牌、而桶里只剩一个的请求,会接受一个、拒绝八个。
补充检查用的是 >= 而不是 ==,这是刻意的设计。如果某一次计时被漏掉了,精确匹配的判断就会跳过这次补充,桶就再也补不满了。
如果一开始是空的,规则会更严格,而且会让任何人第一次访问都感觉像出了故障。
参数决定一切
同一个算法,两套不同的配置。
容量10,每3秒补充6个。 大约每秒稳定处理两个,还能一次性容纳十个。按秒逐轮推演:
| 轮次 | 请求数 | 接受数 | 拒绝数 | 剩余令牌 |
|---|---|---|---|---|
| 1 | 3 | 3 | 0 | 7 |
| 2 | 5 | 5 | 0 | 2 |
| 3 | 7 | 7 | 0 | 补充到8后剩1 |
| 4 | 9 | 1 | 8 | 0 |
比较宽松。突发流量能被吸收,想把桶用干得费点功夫。
容量8,每10秒补充2个。 现在前八个请求是免费的,之后基本就没什么余量了。发五个,再发五个,桶就空了,还得等八秒才能等来两个令牌。
同样的算法,体验却截然不同。第二种配置下的客户端不得不琢磨什么时候该花令牌,因为令牌稀缺,补充又慢。
这已经不是一个用来"塑形"流量的限流规则了,而是一个逼着客户端精打细算每次请求的规则——而算法本身其实完全没变。
动手试一试
一个容量为5、每2秒补充2个令牌、初始为满的桶。
- 一个客户端一次性发送5个请求。有多少被接受?还剩多少?
- 两秒后它又发送3个请求。会发生什么?
- 这之后客户端等了10秒。此时它有多少令牌?
- 这个桶允许的持续速率是多少?最大突发量又是多少?
核对你的答案
1. 全部5个都被接受,剩0个。 桶一开始是满的,每次请求消耗一个令牌。瞬间把它花光,正是容量存在的意义所在。
2. 接受两个,拒绝一个。 过去了两秒,桶补充了2个令牌。三个请求对着2个令牌,Math.min(3, 2) 接受两个,第三个被拒绝。
3. 是五个,不是十个。 十秒本该累积10个令牌,但容量把它封顶在5。这就是"第四天规则":闲置时间不会无限累积,这也正是防止一个长期安静的客户端回来时发起超大突发的机制。
4. 持续速率每秒1个,一次性突发最多5个。 每两秒补两个令牌,是长期的平均速率;容量5,则是瞬时能承受的最大突发量。
第四题的两个答案值得记住。补充速率和容量回答的是两个不同的问题,如果只用一个数字来描述令牌桶,就会丢失其中一个信息。
接下来去哪儿
令牌桶把"何时花令牌"的决定权交给了客户端,所以到达服务器的流量仍然是不均匀的——有边界,但不均匀。
漏桶采用了另一种思路:先接受突发流量,再以恒定速率释放出去,这样不管流量来的时候多不均匀,服务器看到的都是平滑的。