# 限流算法

在保证可用的情况下尽可能多增加进入的人数,其余的人在排队等待,或者返回友好提示,保证里面的进行系统的用户可以正常使用，防止系统雪崩。

### 计数器
在一段时间间隔内(时间窗/时间区间)，处理请求的最大数量固定，超过部分不做处理。

##### 实际应用
线程池大小，指定数据库连接池大小、nginx连接数等

##### 临界问题
假设我们系统中现在只有一个用户，这个用户在59秒的时候发送了100次请求，然后在一分零一秒的时候又发送了100次请求，这个时候实际上在系统当中，一分钟之内就接收了200次请求，可能会导致我们的服务蹦掉。限流算法在这个临界点没有发挥作用

##### 如何解决临界问题——滑动窗口
之所以计数器算法会造成临界值的问题，是因为我们在统计Counter的时候精度太低了。而滑动窗口算法则是在此基础之上，进行了优化

在使用滑动时间窗口，我们可以把1分钟分成6格，每格时间长度是10s，每一格又各自管理一个计数器，单位时间用一个长度为60s的窗口描述。一个请求进入系统，对应的时间格子的计数器便会+1，而每过10s，这个窗口便会向右滑动一格。只要窗口包括的所有格子的计数器总和超过限流上限，便会拒绝后面的请求。

### 漏斗算法
漏斗算法限流的基本原理为：水(对应请求)从进水口进入到漏桶里，漏桶以一定的速度出水(请求放行)，当水流入速度过大，桶内的总水量大于桶容量会直接溢出，请求被拒绝

在系统看来，请求永远是以平滑的传输速率过来，从而起到了保护系统的作用。

##### 漏斗算法的应用
Nginx漏斗限流 `limit_req_zone`

##### 漏斗算法存在的问题
漏桶出口的速度固定，不能灵活的应对后端能力提升。比如，通过动态扩容，后端流量从1000QPS提升到1WQPS，漏桶没有办法。必须调整算法才行

### 令牌桶
令牌桶算法是对漏斗算法的一种改进，除了能够起到限流的作用外，还允许一定程度的流量突发,因为处理完后,立马就可以取令牌,而漏斗算法就不行,出水口就那么大。

令牌桶算法以一个设定的速率产生令牌并放入令牌桶，每次用户请求都得申请令牌，如果令牌不足，则拒绝请求。
令牌桶算法中新请求到来时**会从桶里拿走一个令牌**，如果桶内没有令牌可拿，就拒绝服务。当然，令牌的数量也是有上限的。令牌的数量与时间和发放速率强相关，时间流逝的时间越长，会不断往桶里加入越多的令牌，如果令牌发放的速度比申请速度快，令牌桶会放满令牌，直到令牌占满整个令牌桶，

削峰:有大量流量进入时,会发生溢出,从而限流保护服务可用

缓冲:不至于直接请求到服务器, 缓冲压力

##### 令牌桶的实现
Guava的 RateLimiter提供了令牌桶算法实现：平滑突发限流(SmoothBursty)和平滑预热限流(SmoothWarmingUp)实现。