限流
限流的目的是通过对并发访问/请求进行限速，或者对一个时间窗口内的请求进行限速来保护系统，一旦达到限制速率则可以拒绝服务、排队或等待、降级等处理
限流一词常用于计算机网络之中，定义如下：
In computer networks, rate limiting is used to control the rate of traffic sent or received by a network interface controller and is used to prevent DoS attacks.
- 通过控制数据的网络数据的发送或接收速率来防止可能出现的DOS攻击。而实际的软件服务过程中，限流也可用于API服务的保护。
- 由于提供服务的计算机资源(包括CPU、内存、磁盘及网络带宽等)是有限的，则其提供的API服务的QPS也是有限的，限流工具就是通过限流算法对API访问进行限制，保证服务不会超过其能承受的负载压力。
主要内容：
常用限流算法的简单介绍及比较
常用限流算法
常用的限流算法主要包括：
- Token bucket-令牌桶
- Leaky bucket-漏桶
- Fixed window counter-固定窗口计数
- Sliding window log-滑动窗口日志
- Sliding window counter-滑动窗口计数
- 以上几种方式其实可以简单的分为计数算法、漏桶算法和令牌桶算法。
计数限流算法
无论固定窗口还是滑动窗口核心均是对请求进行计数，区别仅仅在于对于计数时间区间的处理。
固定窗口计数
实现原理
- 固定窗口计数法思想比较简单，只需要确定两个参数：计数周期T及周期内最大访问（调用）数N。请求到达时使用以下流程进行操作：
算法优点
- 固定窗口计数实现简单，并且只需要记录上一个周期起始时间与周期内访问总数，几乎不消耗额外的存储空间。
算法缺陷
固定窗口计数缺点也非常明显，在进行周期切换时，上一个周期的访问总数会立即置为0，这可能导致在进行周期切换时可能出现流量突发，
如图所示
简化模型
- 两个周期T0中a时刻有n1个访问同时到达;
- 周期T1中b时刻有n2个访问同时到达;
- n1和n2均小于设定的最高访问次数N（否则会触发限流）。
在发生时间间隔切换的时候，在切换的过程中发生并发突变，所以在实际使用过程中，固定窗口计数器存在突破限额N的可能。
- 举例，限制QPS为10，某用户在周期切换的前后的0.1秒内，分两次发送10次请求，根据算法规则此20次请求可通过限流器，则0.1面秒请求数20，超过每秒最多10次请求的限制。
滑动窗口计数
为解决固定窗口计数带来的周期切换处流量突发问题，可以使用滑动窗口计数。滑动窗口计算本质上也是固定窗口计数，区别在于将计数周期进行细化。
实现原理
滑动窗口计数法与固定窗口计数法相比较，除了计数周期T及周期内最大访问（调用）数N两个参数，增加一个参数M，用于设置周期T内的滑动窗口数。
限流流程如下：
滑动窗口计数在固定窗口计数记录数据基础上，需要增加一个长度为M的计数数组，用于记录在窗口滑动过程中各窗口访问数据。其流程示例如下：
周期切换问题
滑动窗口针对周期进行了细分，不存在周期到后计数直接重置为0的情况，故不会出现跨周期的流量限制问题。
非计数限流法
常用的限流算法有两种：漏桶算法和令牌桶算法
- 漏桶算法思路很简单，水（请求）先进入到漏桶里，漏桶以一定的速度出水，当水流入速度过大会直接溢出，可以看出漏桶算法能强行限制数据的传输速率。
漏桶限流
实现原理
漏桶限流算法的实现原理图：
- 设定漏桶流出速度及漏桶的总容量，在请求到达时判断当前漏桶容量是否已满，不满则可将请求存入桶中，否则抛弃请求。
- 采用一个线程以设定的速率取出请求进行处理。
- 需要确定参数为漏桶流出速度r及漏桶容量N
流程如下：
算法特点
- 漏桶算法主要特点在于可以保证无论收到请求的速率如何，真正抵达服务方接口的请求速率最大为r，能够对输入的请求进行平滑处理。
- 漏桶算法的缺点也非常明显，由于其只能以特定速率处理请求，则如何确定该速率就是核心问题，如果速率设置太小则会浪费性能资源，设置太大则会造成资源不足。
- 并且由于速率的设置，无论输入速率如何波动，均不会体现在服务端，即使资源有空余，对于突发请求也无法及时处理，故对有突发请求处理需求时，不宜选择该方法。
令牌桶限流
- 对于很多应用场景来说，除了要求能够限制数据的平均传输速率外，还要求允许某种程度的突发传输。这时候漏桶算法可能就不合适了，令牌桶算法更为适合。
- 令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌，而如果请求需要被处理，则需要先从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务。
实现原理
设定令牌桶中添加令牌的速率，并且设置桶中最大可存储的令牌，当请求到达时，向桶中请求令牌（根据应用需求，可能为1个或多个），若令牌数量满足要求，则删除对应数量的令牌并通过当前请求，若桶中令牌数不足则触发限流规则。
根据描述需要设置的参数为，令牌添加速率r，令牌桶中最大容量N，流程如下：
算法特点
令牌桶算法通过设置令牌放入速率可以控制请求通过的平均速度，且由于设置的容量为N的桶对令牌进行缓存，可以容忍一定流量的突发。
限流算法比较
以上提到四种算法，本小节主要对四种算法做简单比较算法进行对比。
