令牌桶算法

综述

往一个桶中，不断补充令牌。每次的访问都会消耗一定量的令牌；

• 如果令牌数够，则执行访问
• 如果令牌数量不够，则拒绝访问

特性 ——

• 平均速率约束：长期平均吞吐受限于 rate。
• 突发能力：桶容量 capacity 决定允许的最大突发请求数。

是一种比较均衡的算法，同时考虑到了平均速率和突发的大型访问

按需填充

如果维护一个定时器来按照 rate 的速率往桶中放入令牌，比较消耗资源。所以可以在每次访问请求的时候，通过计算时间差来判断桶中令牌的数量（利用 $\mathrm{\Delta }t$ 来计算令牌增量），最终判断是否允许此次访问。