浅析限流算法

计数器

计数器算法的思想很简单，每当一个请求到来时，我们就将计数器加一，当计数器数值超过阈值后，就拒绝余下请求。一秒钟后，我们将计数器清零，开始新一轮的计数。计数器算法简单粗暴，易于实现。但是缺点也是有的，也就是所谓的"突刺现象"。举例说明一下，假如我们给计数器设置的阈值为100。系统瞬间内（比如10毫秒内）有200个请求到来，这个时候计数器只能放过其中的100个请求，余下的100个请求全部被拒绝掉。如果第二秒内没有请求到来，那么系统就处于空闲状态。也就是上一秒忙的要死，这一秒又闲的要死。如果我们能用一个容器将剩余的100个请求缓存起来，待计数器重置后再将这些请求放出来。这样系统在这两秒内的吞吐量就由100变成了200，提升了一倍

漏桶算法

漏桶算法由流量容器、流量入口和出口组成。其中流量出口流速即为我们期望的限速值，比如 100 QPS。漏桶算法除了具备限流能力，还具备流量整型功能。下面我们通过一张图来了解漏桶算法。

如上图，流入漏桶流量的流速是不恒定的，经过漏桶限速后，流出流量的速度是恒定的。需要说明的是，漏桶的容量是有限的，一旦流入流量超出漏桶容量，这部分流量只能被丢弃了。

令牌桶算法

令牌桶和漏桶颇有几分相似，只不过令牌通里存放的是令牌。它的运行过程是这样的，一个令牌工厂按照设定值定期向令牌桶发放令牌。当令牌桶满了后，多出的令牌会被丢弃掉。每当一个请求到来时，该请求对应的线程会从令牌桶中取令牌。初期由于令牌桶中存放了很多个令牌，因此允许多个请求同时取令牌。当桶中没有令牌后，无法获取到令牌的请求可以丢弃，或者重试。下面我们来看一下的令牌桶示意图：