J005-流控方案整理

status

Published

slug

j005

type

Post

流控

流控，即流量控制，是指通过一系列手段和技术，对网络、交通、物流等系统中的流量进行调节和管理，以确保系统的稳定运行、提高资源利用效率、保障服务质量等。

常见的流控使用场景为：保护下游有限的资源不被流量冲垮，保证服务的可用性。参考TCP协议中的拥塞控制，流控通常有一个阈值，指设定的一个特定数值或范围，用于决定何时启动流控措施以及采取何种程度的流控。

流控接口：

单机流控

1. 简单窗口/固定窗口

概念：

基于一个给定的时间窗口，维护一个计数器用于统计访问的次数

规则：

如果访问次数小于阈值，允许访问，访问次数+1

如果访问次数超出阈值，限制访问，访问次数不变

如果超出了时间窗口，计数器清零，并重置清零后的首次成功访问时间为当前时间，确保计数器统计的是最近一个窗口的访问量

代码示例：

简单窗口的常用使用场景，会根据不同的key进行流控

每个key有单独的时间窗口、阈值配置，因此每个key都需要维护一个单独的限流器实例。

多线程场景下，可以使用synchronized，修改读写变量为volatile，使用原子操作来实现线程安全

存在问题：

临界突变：以1分钟100次访问为例，当流量不均匀时，极有可能出现窗口的临界区出现2倍流量冲击的情况，可能会导致系统的崩溃。

在临界的 20 秒内（0:50~1:10）系统承受的实际访问量是 200 次

2. 滑动窗口

概念：

为了解决简单窗口的临界突变问题，将大的时间窗口切分成更细粒度的子窗口

每个子窗口维护一个独立的计数器用于统计窗口范围内的访问量

规则：

每过一个子窗口大小的时间，就右滑一个子窗口

每一次统计当前窗口往前若干个窗口的访问量总和，总量超过阈值就会拒绝后续请求

代码示例：Sentinel，https://github.com/alibaba/Sentinel/wiki/Sentinel工作主流程

StatisticSlot 是 Sentinel 的核心功能插槽之一，用于统计实时的调用数据。

clusterNode：资源唯一标识的 ClusterNode 的实时统计

origin：根据来自不同调用者的统计信息

defaultnode: 根据入口上下文区分的资源 ID 的 runtime 统计

入口流量的统计

Sentinel 底层采用高性能的滑动窗口数据结构 LeapArray 来统计实时的秒级指标数据，可以很好地支撑写多于读的高并发场景。

问题：

精度问题：滑动窗口算法并不能精准控制任意给定时间窗口T内的访问量不大于N

举例：1分钟划分为10秒的6个滑动窗口，请求速率为20次/秒时

假设0:05~0:10内有100个请求，接下来的请求都会被限流
1:00时刻窗口滑动，并在1:00~1:05时刻继续放入100个请求
0:05~1:05的1分钟时间窗口中，请求量超出了给定阈值

解决方法：设定更高的精度，划分更细的滑动窗口

平滑度问题：滑动窗口的流量曲线通常如下，面对大流量滑动窗口很容易导致限流阈值快速打满，剩余窗口中的后续请求无法通过。

期望的限流效果：流量平滑地进入系统中

3. 漏桶

概念：

追求平滑性，流控并不是切断流量，而该是将流量控制在系统能承受的速度范围内，实现流速控制

漏桶算法的思路，把请求看做往桶里注水

桶底漏出的水：离开缓冲区被服务器处理的请求
桶口溢出的水：被丢弃的请求

规则：

最大允许请求数 N：桶的大小

时间窗口大小 T：一整桶水漏完的时间

最大访问速率 V：一整桶水漏完的速度，即 N/T

请求被限流：桶注水的速度比漏水的速度快，最终导致桶内水溢出

代码示例：

存在问题：

漏桶优势在于平滑流量，但与滑动窗口算法一样，极端情况下，漏桶算法也存在在时间窗口T内放入2倍阈值N的流量的问题。

如果访问量相比窗口大小 N 大很多，在窗口（0~T）一开始的 0 时刻就直接涌进来，使得漏桶在时间 t（ 0≈t<T ）时刻溢出，然后在剩余的 T - t 时间内按照 N / T 的速度流入，在总的窗口内的访问量 = N+(T−t)∗N/T，只要 t 够小，访问量就接近 2N。

存在计算误差：因此漏桶漏水的速度最好是一个整数值，否则在计算剩余水量时会有些许误差。

4. 令牌桶

概念：与漏桶法类似

简单来说，就是把注水看成放令牌，一个桶可以承受的流量（令牌数）是有限的，放入令牌就是注水，取出令牌就是处理请求。

规则：

系统以恒定的速率产生令牌，然后把令牌放到令牌桶中

令牌桶有一个容量，当令牌桶满了的时候，再向其中放令牌，那么多余的令牌会被丢弃；

当想要处理一个请求的时候，需要从令牌桶中取出一个令牌，如果此时令牌桶中没有令牌，那么则拒绝该请求。

代码示例：

Guava 中提供的 RateLimiter实现了多线程的令牌桶

支持 SmoothBursty 策略、SmoothWarmingUp 策略
仅支持QPS级别

漏桶、令牌桶的区别

适用场景：

漏桶：用于控制网络的请求速率，输入速率可以变化，但输出速率保持恒定；

令牌桶：按照固定速率往桶中添加令牌，允许输出速率根据突发大小调整

5. 滑动日志

概念：

用于实现流量的精确控制，通过日志式记录实现

对当前时间t，只需要考虑t-T时间段内是否有大于等于N个请求被放行

可以通过维护队列q实现，节点记录每个请求的时间
只关心当前时间之前最长 T 时间内的记录，且队列最大长度为N

规则：

记录每一次用户请求日志，当每次流控判断时，取出最近时间窗口内的日志数，看是否大于流控阈值。这就是滑动日志的算法思路。

伪代码示例：

存在问题：

复杂度很高

空间复杂度达到 O(N)
在队列中确定时间窗口，采用二分查找进行，时间复杂度为O(logN)

分布式流控

分布式系统中的CAP定理

指在分布式系统中，如下的三个特性无法同时满足，最多只能实现其中的两项。（不可能三角）

Consistency（一致性）

Availability（可用性）

Partition Tolerance（分区容错性）

对于分布式部署的应用服务，当共用资源or依赖的下游服务出现流量限制时，分布式流控可以给每台应用服务器分配流量。

平均策略：平均分配流控配额，将问题转换为单机流控。

存在问题：流量不均匀、机器宕机或临时扩缩容场景不适用

中心化策略：配额由一个中心系统统一管控，应用进程通过请求中心系统获取流控配额

状态统一由中心系统维护，实现简单
中心系统节点出错or不可用，会影响全局的流控，需要额外保护

去中心化策略：应用进程独立保存和维护流控配额状态，集群内周期性异步通讯保持状态一直

降低中心化单点的低可靠性，但实现上比较复杂，状态的一致性难以保证

中心化和去中心化的区别

去中心化倾向CAP中的A
中心化倾向CAP中的C
目前生产环境中均使用中心化流控，去中心化方案没有出现过

中心化流控的实现

接入层入口流控

在应用服务的统一入口，如LVS或Nginx，进行入口的流控

举例：Nginx 提供了 ngx_http_limit_req_module 模块用于流控，底层使用的是漏桶算法

TokenServer流控

使用一个专用的TokenServer来管理流控配额，统计总调用量，判断单个请求是否允许等

应用服务器与TokenServer通信来获取配额
Sentinel就是通过TokenServer实现的流控

TokenServer需要实现的功能

自动管理，调度（分配/选举）
高可用

实现成本高

需要采用分布式一致性协议来做集群选举
需要monitor来监控状态

存储式流控

通过存储系统来保存流控的计数值等统计信息

应用从存储中获取统计信息，再将最新的请求写入存储中

存储系统的选择

MySQL等数据库
Redis/Tair缓存（性能更好）

Tair流控

基于其API，用incr实现简单窗口

Redis流控（具体看原文）

简单窗口：INCR类似Tair流控
令牌/漏桶：Hash，使用key来记录
滑动窗口：Sorted Set
并发控制

Lua脚本
Redis事务
RedLock

总结

一个很简单的概念，但是有很多不同的实现方法，摸透原理还是需要花费很多时间的。例如流控的突发情况，故障发生时的可用性，总之生产环境中多为分布式服务，需要考虑到方方面面，做好兜底策略。