常用的限流算法

在开发高并发系统时有三把利器用来保护系统：缓存、降级和限流。今天我们要聊的就是限流（Rate Limit），限流的目的很简单，就是为了保护系统不被瞬时大流量冲垮.

限流这个概念我其实很早之前就有去了解过，不过无奈之前工作所接触业务的并发量实在是谈不上限流。目前公司大促峰值QPS在2w往上，自然而然需要用到限流，特别是类似秒杀这种瞬时流量非常大但实际成单率低的业务场景。

目前比较常用的限流算法有三种 

* 计数器固定窗口算法
* 计数器滑动窗口算法
* 漏桶算法
* 令牌桶算法

  1. 计数器法
    用一个计数器在单位时间周期内最多多少次，然后下一个周期清零。
    有一个明显问题，就是可能在周期最后和周期开始的短时间段之内，涌入大量请求，导致系统压力过大，甚至崩溃，限流作用有限。

  2. 计数器滑动窗口算法
    将周期分为N个小周期，每个小周期分别有自己的访问次数，根据时间滑动删除过期的小周期。 假设周期为5分钟（300秒），将5分钟分为10个小周期，每个小周期的访问次数为30次。第一个周期内访问次数为30次，超过30就会禁止访问。 当滑动窗口的格子划分的越多，那么滑动窗口的滚动就越平滑，限流的统计就会越精确。
    此算法可以很好的解决固定窗口算法的临界问题。

  3. 漏桶算法
    漏桶算法，漏桶作为一个容器有固定的容量，出口流量速率是一个固定的值，因此漏桶的流出流量肯定是平滑的，对于流入流量是不设限的。
    当漏桶容量满了以后，流入流量将被丢弃（拒绝访问）。 漏桶算法限制了流出流量是一个固定的值，无法支持突发流出流量，如果瞬间流量增量，会导致大部分请求被拒绝。

  4. 令牌桶算法

以恒定的速度（单位时间/限流值）向桶里面放令牌。如果桶已经满了，那么无法放入的令牌就会被丢弃。
请求到来的时候，从桶里面获取令牌，如果令牌非空（或者指定一个阈值），就可以获取令牌（并从桶中删除），请求也就可以执行，否则阻塞或者拒绝。
算法允许最大b(令牌桶大小)个请求的突发，所以桶的大小应该设置为小于系统并发数。
因为有桶做缓冲，只要瞬间流量不大于桶大小，将不会有请求被拒绝，所以桶容量大小必须设置合适。

参考：

  1. 常用4种限流算法介绍及比较
  2. 常用限流算法
Flag Counter