【转】流量控制算法——什么是漏桶算法和令牌桶算法？

令牌桶（TokenBucket）简介

1.令牌桶实现的基本思想

令牌桶，顾名思义，是一种通过让请求被处理前先行获取令牌，只有获取到令牌的请求才能被放行处理的一种限流方式。令牌桶的实现包含两个方面：

一方面是按固定的速率来产生令牌并存入桶中，如果令牌数量超过桶的最大容量则直接丢弃掉。

一方面当有请求时先从桶中获取令牌，获取到令牌后才能通过进行处理，否则被直接丢弃或等待获取令牌。

2.令牌桶与漏桶（LeakyBucket）的区别

令牌桶与漏桶的区别在于漏桶控制的是请求被处理的速率。即当有请求的时候，先进入桶中进行排队，按固定的速率流出被处理；而令牌桶控制的是令牌产生的速率。即当有请求的时候，先从令牌桶中获取令牌，只要能获取到令牌就能立即通过被处理，不限制请求被处理的速度，所以也就可以应对一定程度的突发流量。如图所示二者的区别：

区别

比如有100个请求同时进入。现在假设漏桶的速率是每10ms处理一个请求，那么要处理完这100个请求需要1秒钟，因为每处理完1个请求，都需要等待10ms才能处理下一个请求。

如果是令牌桶，假设令牌桶产生令牌的速率也是每10ms产生一个，那么1秒钟就是产生100个令牌。所以，一种极端的情况就是当这100个请求进入的时候，桶中正好有100个令牌，那么这100个请求就能瞬间被处理掉。

3.如何应对突发流量

所谓突发流量，就是在某个时刻的流量突然比平时的流量要高。光有突发流量还不够，得系统能够应对才行，即能够正常处理，否则就不叫应对突发流量了。那令牌桶是如何应对突发流量的呢？就是通过令牌桶缓存到的令牌来应对的，再加上令牌桶的最大容量约束，不会无限制的让流量通过。

突发流量