漏桶算法和令牌桶算法

Google开源工具包Guava提供了限流工具类RateLimiter，该类基于令牌桶算法来完成限流，非常易于使用

 

常用的限流算法有两种：漏桶算法和令牌桶算法。

      漏桶算法思路很简单，水（请求）先进入到漏桶里，漏桶以一定的速度出水，当水流入速度过大会直接溢出，可以看出漏桶算法能强行限制数据的传输速率。

图1 漏桶算法示意图

      对于很多应用场景来说，除了要求能够限制数据的平均传输速率外，还要求允许某种程度的突发传输。这时候漏桶算法可能就不合适了，令牌桶算法更为适合。如图2所示，令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌，而如果请求需要被处理，则需要先从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务。

图2 令牌桶算法示意图

 

 

在网络中传输数据时，为了防止网络拥塞，需限制流出网络的流量，使流量以比较均匀的速度向外发送。令牌桶算法就实现了这个功能，可控制发送到网络上数据的数目，并允许突发数据的发送。

 

令牌桶算法是 网络流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一种算法。典型情况下，令牌桶算法用来控制发送到网络上的数据的数目，并允许突发数据的发送。

 

大小固定的令牌桶可自行以恒定的速率源源不断地产生令牌。如果令牌不被消耗，或者被消耗的速度小于产生的速度，令牌就会不断地增多，直到把桶填满。后面再产生的令牌就会从桶中溢出。最后桶中可以保存的最大令牌数永远不会超过桶的大小。

 

传送到令牌桶的数据包需要消耗令牌。不同大小的数据包，消耗的令牌数量不一样。

 

令牌桶这种控制机制基于令牌桶中是否存在令牌来指示什么时候可以发送流量。令牌桶中的每一个令牌都代表一个字节。如果令牌桶中存在令牌，则允许发送流量；而如果令牌桶中不存在令牌，则不允许发送流量。因此，如果突发门限被合理地配置并且令牌桶中有足够的令牌，那么流量就可以以峰值速率发送。

 

令牌桶算法的基本过程如下：

 

假如用户配置的平均发送速率为r，则每隔1/r秒一个令牌被加入到桶中；

 

假设桶最多可以存发b个令牌。如果令牌到达时令牌桶已经满了，那么这个令牌会被丢弃；

 

当一个n个字节的 数据包到达时，就从令牌桶中删除n个令牌，并且 数据包被发送到网络；

 

如果令牌桶中少于n个令牌，那么不会删除令牌，并且认为这个数据包在 流量限制之外；

 

算法允许最长b个字节的突发，但从长期运行结果看， 数据包的速率被限制成常量r。对于在 流量限制外的 数据包可以以不同的方式处理：

 

它们可以被丢弃；

 

它们可以排放在 队列中以便当令牌桶中累积了足够多的令牌时再传输；

 

它们可以继续发送，但需要做特殊标记，网络过载的时候将这些特殊标记的包丢弃。

 

注意：令牌桶算法不能与另外一种常见算法“ 漏桶算法（Leaky Bucket）”相混淆。这两种算法的主要区别在于“ 漏桶算法”能够强行限制数据的传输速率，而“令牌桶算法”在能够限制数据的平均传输速率外，还允许某种程度的突发传输。在“令牌桶算法”中，只要令牌桶中存在令牌，那么就允许突发地传输数据直到达到用户配置的门限，因此它适合于具有突发特性的流量。