限速之令牌桶和漏桶算法

限速是大型服务里面必备的功能，目的是对并发控制和请求进行限速来保护系统，让系统不会因为单位时间内的请求数量太大，被打爆。对于超过了限速的那些请求，处理方法往往是：直接拒绝服务，排队等待，或者降级处理。

对于限速来说，最常用的两个算法是：令牌桶算法和漏桶算法，下面我们便来看下它们是怎么回事。

一、令牌桶：

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

https://baike.baidu.com/item/token%20bucket/4315253

令牌桶的工作过程： 1.令牌根据时间匀速的产生令牌数量，这里假设是r，存入到令牌桶中.

2.令牌桶在初始化的时候，会分配一定数量的令牌数capicity。

3.消息到来之后，会从令牌桶里面取出令牌消费掉，这里假设是d，如果获取不到令牌的话，就直接触发限速保护策略，往往是直接丢弃。

当前时间t内可以消费的令牌数量为：

当前令牌桶剩余的令牌数(这里最大是capicity) + r*t

二、漏桶

漏桶可以看作是一个带有常量服务时间的单服务器队列，如果漏桶（包缓存）溢出，那么数据包会被丢弃。

漏桶算法强制一个常量的输出速率而不管输入数据流的突发性。当输入空闲时，该算法不执行任何动作。

https://baike.baidu.com/item/%E6%BC%8F%E6%A1%B6%E7%AE%97%E6%B3%95

漏斗有一个入水口，一个出水口，出水口按照一定的速率出水，并且有一个最大出水速率。

1.入水速率小于等于出水速率的时候，漏斗内不会积水；

2.入水速率大于出水速率的时候，漏斗内会存在积水。

在漏斗内有水的情况下：

1. 出水口按照最大速率出水；
2. 漏斗未满的情况下，多出来的水会存在漏斗中；
3. 漏斗满了的话，还有水进入漏斗，水会溢出。

三、两种算法的区别

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