限流算法

1、计数器

  采用计数器是一种比较简单的限流算法，一般我们会限制一秒钟能够通过的请求数。比如限流QPS为100，算法的实现思路就是从第一个请求进来开始计时，在接下来的1秒内没来一个请求就把计数加1，如果累加的数字达到了100，后续的请求就会被全部拒绝。等到1秒结束后，把计数恢复成0，重新开始计数。如果在单位时间1秒内的前10毫秒处理了100个请求，那么后面的990毫秒会拒绝所有的请求，我们把这种现象称为“突刺现象”。

2、漏桶算法

  漏桶算法的思路很简单，一个固定容量的漏桶按照常量固定速率流出水滴。如果桶是空的，流入的水滴就会溢出(被丢弃)，而漏桶容量是不变的。漏桶算法的大致原理如下所示。

3、令牌桶算法

  令牌桶算法是比较常见的限流算法之一，可以使用它进行接口限流，其大致原理图如下所示。

  令牌按固定的速率被放入令牌桶中，例如tokens/s。桶中最多存放b个令牌(Token),当桶装满时，新添加的令牌会被丢弃或拒绝。当请求到达时，将从桶中删除1个令牌。令牌桶中的令牌不仅可以被移除，还可以往里添加，所以为了保证接口随时有数据通过，必须不停的往桶里加令牌。由此可见，往桶里加令牌的速度决定了数据通过接口的速度。我们通过控制往令牌桶里加令牌的速度来控制接口的流量。

4、漏桶算法和令牌桶算法的区别

• 漏桶算法是按照常量固定速率流出请求的，流入请求速率任意，当流入的请求数累积到漏桶容量时，新流入的请求会被拒绝。
• 令牌桶算法是按照固定速率往桶中添加令牌的，请求是否被处理需要看桶中的令牌是否足够，当令牌数减为零时，拒绝新的请求。
• 令牌桶算法允许突发情况，只要有令牌就可以处理，允许一定程度的突发容量。
• 漏桶算法限制的是常量流出速率，从而使突发流入速率平滑。