前言
流控的含义：
- 限制单位时间内的请求量
流控的作用：
- 高并发场景下，保证服务的可用性
算法
实现流控的算法包括：固定窗口、滑动窗口、漏桶、令牌桶、滑动日志
固定窗口
最简单的流控算法，核心思想是：给定时间窗口，维护一个计数器用于统计访问次数，并实现以下规则：
- 如果访问次数小于阈值，则允许访问，访问次数+1；
- 如果访问次数超出阈值，则限制访问，访问次数不增；
- 如果超过了时间窗口，计数器清零，并重置清零后的首次成功访问时间为当前时间
分布式环境下，可以使用tair缓存来统计访问次数
固定窗口算法的问题：
- 存在
临界突变问题，导致极端情况下单位时间内的请求量double于设置的阈值，达不到限流的效果- 假设1分钟内仅允许100个请求，时间窗口为0:00-1:00和1:00-2:00，若从0:50开始以10次/秒的速度请求，则在临界0:50-1:00的20秒内系统承受了200次请求，没有实现限流的效果
滑动窗口
固定窗口存在临界突变问题的核心是统计调用次数的粒度太粗。滑动窗口为解决这个问题，把大的时间窗口拆分成若干粒度更细的子窗口，每个子窗口独立统计调用次数，按子窗口维度滑动来统计整体窗口内的调用次数
滑动窗口这样解决临界突变问题：
1 | 滑动窗口将一分钟的时间窗口切分成6个子窗口，每个子窗口维护一个独立的计数器用于统计10秒内的访问量，每经过10s，时间窗口向右滑动一格。如果0:50到1:00进来了100次请求，由于算法统计的是6个子窗口的访问量总和，接下来1:00~1:10的请求就会被拒绝 |
滑动窗口的问题：
- 精度问题。滑动窗口无法控制任意给定时间内的请求量都小于阈值，无法保障系统的可靠性
- 平滑度问题。滑动窗口无法控制任意子时间窗口内流量的相对均匀性，导致流量超过一定范围后，流量被切断，无法保障系统的可用性
漏桶算法
核心思想：基于出口流速来做流控，可以很好地解决平滑度问题，在网络通信中常用于流量整形
漏桶算法描述如下：
- 漏桶具有固定容量和固定出水的速率，其中出水速率表示流控的qps阈值
- 请求qps速率以流入桶中的水的流速表示
- 如果桶满了，则流入的水滴溢出，表现为新请求被拒绝
由此可知，漏桶算法对流量激增有一定容忍度，靠桶内容量兜住。除非qps持续激增，桶满了才会拒绝请求，否则当调用方qps低于阈值后，桶内的水不断流出，系统在流量激增和下降阶段依然能正常提供服务，这就解决了平滑度问题，调用方的请求不会突然间全部拒绝
令牌桶算法
和漏桶算法我认为没区别。基于入口流速来做流控，qps阈值表示往桶中放令牌的速度。外部请求表示从桶中拿令牌，只有当拿不到令牌时才拒绝请求。
滑动日志
核心思想：记录每一次用户请求日志，当每次流控判断时，取出最近时间窗口内的日志数，看是否大于流控阈值。
滑动日志的问题
- 时间复杂度&空间复杂度较大。
- 首先，我们要保存一个长度最大为
N=qps*t的队列，这意味着空间复杂度达到O(N) - 其次，我们需要在队列中寻找t时间范围内的请求总数。以二分查找为例，时间复杂度是O(logN)。
- 首先，我们要保存一个长度最大为
流控算法对比
| 算法 | 原理 | 时间复杂度 | 空间复杂度 | 问题 | 适用场景 |
|---|---|---|---|---|---|
| 固定窗口 | 固定时间窗口计数 | O(1) | O(1) | 临界突变 | 容易实现，适用于一些简单的流控场景，流量比较均匀，或者允许临界突变 |
| 滑动窗口 | 窗口拆分，子窗口独立统计，按窗口时间滑动，统一限流。 | O(1) | O(M) - M为子窗口数 | 精度&平滑度 | 适用大多数场景，可以通过调节采样子窗口数来平衡开销 |
| 漏桶/令牌桶算法 | 基于（出口/入口）流速来做流控 | O(1) | O(1) | 精度 | 可做流量整形，容忍一定程度的突发流量 |
| 滑动日志 | 基于请求日志做流控 | O(log(N)) | O(N)-最大日志数 | 精度高，时间&空间复杂度高 | 要求完全精确的控制，保证任意T时刻内流量不超过N，高时间和空间复杂度，性能最差 |
成熟产品
Guava RateLimiter
基于令牌桶算法实现，有平滑突发限流（SmoothBursty）和平滑预热限流（SmoothWarmingUp）两种实现
RateLimiter是采用令牌桶算法，但是如果单独起一个线程去发放令牌肯定不优雅，所以RateLimiter采用了一个很巧妙的方法：将一个时间段视作一个令牌（时间段的长度 = 1/限流值）。时间的匀速推进，就相当于在匀速的发放令牌，每次请求都会根据当前时间重新计算桶内令牌数
SmoothBursty
当桶内有剩余令牌时，突然来一波流量，默认配置的SmoothBursty会放过去2倍限流值的流量
SmoothBursty类型的RateLimiter，会匀速的往桶里放入令牌，默认会存储1s的令牌，取令牌的时候优先消耗存储令牌，如果没有令牌则返回false（或者等待）。所以对于一波突发的流量，可能会出现2倍限流值的情况
SmoothWarmingUp
当桶内有剩余令牌时，突然来一波流量，SmoothWarmingUp的流量会呈爬坡型逐渐升高到限流值
取令牌的时候，会取令牌桶中的令牌，但是取走之后会设置一个等待时间tw（tw内不允许流量通过），这个等待时间tw是根据桶内的令牌来计算的，桶内存储的令牌越多，等待时间越长。所以这对突刺流量，真正通过的流量会是一个爬坡线。
预热区间决定了斜线的斜率，预热区间越大，斜率越小。（预热区间：创建限流器时的入参）