令牌算法是以固定速度往一个桶内增加令牌,当桶内令牌满了后,就停止增加令牌。上游请求时,先从桶里拿一个令牌,后端只服务有令牌的请求,所以后端处理速度不一定是匀速的。当有突发请求过来时,如果令牌桶是满的,则会瞬间消耗桶中存量的令牌。如果令牌还不够,那么再等待发放令牌(固定速度),这样就导致处理请求的速度超过发放令牌的速度。
令牌桶算法和漏桶算法不同的是,有时后端能够处理一定的突发情况,只是为了系统稳定,一般不会让请求超过正常情况的60%,给容灾留有余地。但漏桶算法中后端处理速度是固定的,对于短时的突发情况,后端不能及时处理,和实际处理能力不匹配。
1 有一个固定容量的桶存放令牌(Token)。
2 桶初始化是空的,以固定的速度(rate)向桶里填充 Token,当达到桶的容量时,多余的令牌被丢弃。
3 当请求到来时,从桶里移除一个令牌,如果没有令牌,则拒绝该请求。
令牌桶控制的是令牌入桶的速度,对于拿到令牌的速度没有限制,允许一定的突发流量被瞬间处理。
漏桶的出水速度是恒定的,那么意味着如果瞬时大流量的话,将有大部分请求被丢弃掉(也就是所谓的溢出)。不应对突发流量。
生成令牌的速度是恒定的,而请求去拿令牌是没有速度限制的。这意味,面对瞬时大流量,该算法可以在短时间内请求拿到大量令牌,而且拿令牌的过程并不是消耗很大的事情。所以令牌桶具备漏桶的一定特点(固定时间放入固定令牌)但是也具备一定突发性能兼容(一瞬间爆发,桶里有就能抗)
Google开源项目Guava中的RateLimiter使用的就是令牌桶控制算法。为单机JVM算法,不支持分布式
spring cloud gateway 默认使用redis的RateLimter限流算法来实现
https://blog.csdn.net/chengqiuming/article/details/122397654
https://www.cnblogs.com/cjsblog/p/9379516.html
https://juejin.cn/post/6895201419805392909
http://www.javashuo.com/article/p-mnvmnpxq-bb.html