1.常见限流算法1. 固定时间窗口算法Fixed Window Counter这是最简单粗暴的算法。原理将时间划分为固定的窗口比如从0点到1点。在每个窗口内维护一个计数器每来一个请求就加1。如果计数器超过了阈值比如1000则拒绝后续请求。当时间进入下一个窗口比如1点到2点计数器清零重置。致命缺点临界突发问题。假设窗口大小为1秒限流100QPS。如果在第1秒的后100ms来了100个请求第2秒的前100ms又来了100个请求那么在这200ms内系统承受了200个请求但每个窗口内的计数都刚好是100并没有触发限流。这就导致了流量“突刺”系统可能会被瞬间冲垮。2. 滑动时间窗口算法Sliding Window Counter这是对固定窗口算法的改进也是Sentinel默认统计流量的方式。原理它不再有固定的、生硬的窗口边界而是将时间窗口划分成更小的格子比如把1秒分成2个500ms的格子。每当有请求到来窗口会随着时间滑动窗口内统计的数据是当前时刻往前推一个完整窗口周期比如1秒内所有格子的数据总和。优点因为窗口是平滑滑动的所以解决了固定窗口的临界突发问题。在上面的例子中第2秒前100ms的请求会滑动到包含第1秒后100ms的窗口内此时总和是200超过了阈值就会被限流。代价因为需要记录每个小格子的数据所以内存和性能开销比固定窗口要大。3. 漏桶算法Leaky Bucket这个算法强调“整形”让流量输出变得非常均匀。原理可以想象成一个底部有一个小洞的水桶。水请求可以以任意速度流入桶中但水会以固定的速率从洞中流出被处理。如果桶满了新流入的水请求就会溢出被拒绝。核心特点无论流入流量多大流出速率都是恒定的。这能很好地保护后端系统避免瞬时高峰。适用场景适合需要绝对平滑流量的场景比如数据库批量写入、文件导出等可以防止瞬间流量压垮数据库。局限性因为它强制匀速所以无法应对突发流量。即使系统当前完全空闲也无法处理突然涌来的一波请求它们只能在桶里排队实时性稍差。4. 令牌桶算法Token Bucket这是最常用、也最灵活的算法Sentinel的预热功能就是基于它实现的。原理有一个桶里面放着令牌。系统会以固定的速率往桶里添加令牌。当请求到来时必须从桶里获取一个令牌如果拿到令牌就通过否则就被拒绝。如果桶里的令牌积攒满了多余的令牌就会被丢弃。核心特点它允许一定程度的突发流量。因为如果系统空闲了一段时间桶里会积攒很多令牌。当突发流量到来时请求可以一次性拿走所有积攒的令牌从而快速处理峰值流量之后再回归到正常的令牌生成速率。适用场景非常通用。既能通过速率限制保护系统又能利用令牌积攒的特性应对业务高峰是实际工程中使用最广泛的算法之一。算法流量是否均匀能否应对突发流量实现复杂度典型应用固定时间窗口否不能有临界问题极低简单计数场景不推荐滑动时间窗口否不能精确计数但无缓冲较高Sentinel默认限流统计精确控制QPS漏桶算法是绝对均匀不能只能排队中等流量整形平滑输出如消息队列消费令牌桶算法否允许瞬时突发能积攒令牌应对中等通用限流如Guava RateLimiter、Sentinel预热2.Sentinel限流机制1.总体介绍阿里的sentinelsentinel基于滑动时间窗口算法统计调用数据提供了如下限流实现快速失败DefaultController基于滑动时间窗口的统计数据如果当前QPS已达到阈值则立即限流严格保证流量小于限流阈值属于 “滑动时间窗口限流算法”的特点。排队等待RateLimiterController根据限流阈值计算请求放行的时间间隔如果过两个请求之间的间隔时间过短则计算第二个请求需要等待的时间并通过Thread.sleep让第二请求线程进行等待。如果第N请求的等待时间大于最大等待时间则该请求被限流。这种以固定速率释放请求且允许一定数量的请求堆积属于“漏桶限流算法”的特点。WarmUpWarmUpController、WarmUpRateLimiterController内部实现参考了guava的RateLimiter但是逻辑比guava更加复杂功能也更加强大。可以确定的是WarmUp使用的是“令牌桶限流算法”。Sentinel 的滑动窗口没有用 Redis ZSet 的ZREMRANGEBYSCORE这类操作因为那是分布式环境下的解决方案比如配合 Redis 做集群限流。而 Sentinel 本质上是本地限流组件运行在应用进程内的 JVM 中它的设计原则就是极致的高性能绝不会依赖远程 Redis 的网络 IO 或复杂数据结构。Sentinel 的滑动窗口实现正是“分成了很多个小窗口”专业术语叫LeapArray即“跳跃数组”。它通过空间换时间和数组时间戳取模的方式把性能开销降到了极低。拆解一下它的核心原理1. 核心数据结构环形数组Sentinel 没有用链表或树而是使用了一个固定长度的环形数组。假设你设置的统计时长是 1 秒采样窗口数量sampleCount默认为 2。那么数组长度就是 2每个格子代表 500 毫秒。数组在初始化时就创建好了不会频繁创建和销毁对象避免了 GC垃圾回收压力。2. 定位算法时间戳取模无锁竞争当请求进来时Sentinel 会计算当前时间属于哪个格子定位逻辑极其轻量计算当前时间的Bucket ID窗口索引(当前时间戳 / 窗口长度) % 数组长度。由于是环形数组后面的时间可能会覆盖前面的格子比如第 3 个 500ms 会覆盖第 1 个 500ms 的位置。3. 解决“覆盖”问题复用而非删除旧数据怎么处理它不会去删除旧数据而是直接复用Reset。当请求定位到某个数组格子时它会检查该格子里的时间戳如果格子的时间戳和当前时间属于同一个窗口期 -直接在该格子上累加计数原子 CAS 操作。如果格子的时间戳已经过期属于上一个周期 -直接重置该格子的所有数据将计数置为 0时间戳更新为当前时间然后写入新数据。关键点整个过程只有数组下标访问和CAS比较并交换原子操作完全没有ZSet那种排序、插入、删除的 O(logN) 或 O(N) 开销也没有任何网络 IO。为什么说“分成小窗口”远比“ZSet”高效对比维度Redis ZSet (分布式方案)Sentinel 本地环形数组依赖依赖网络、Redis 内存、序列化纯本地内存无外部依赖时间复杂度ZREMRANGEBYSCORE复杂度 O(logNM)数据量大了有性能损耗数组下标访问O(1)极快内存开销每个请求都要存一个 member数据量大会膨胀只有固定 2 个或少量对象内存恒定不变GC 压力频繁创建/销毁 ZSet 元素触发 GC对象复用几乎没有 GC 压力2.滑动窗口工作原理LeapArray 统计数据的基本思路创建一个长度为 n 的数组数组元素就是窗口每个窗口包装了 1 个指标桶桶中存放了该窗口时间范围内对应的请求统计数据可以想象成一个环形数组在时间轴上向右滚动请求到达时会命中数组中的一个窗口该请求的数据就会存到命中的这个窗口包含的指标桶中当数组转满一圈时会回到数组的开头此时下标为 0 的元素需要重复使用它里面的窗口数据过期了需要重置然后再使用。总结Sentinel 就是分成了固定数量的小窗口默认 2 个通过环形数组复用的方式替代了删除操作。这样做的好处是毫秒级响应计算过程就是几次整数运算。无 GC 干扰数组长度固定对象不增不减。精度可控如果你需要更精确的统计比如想统计到 100ms 精度可以通过sampleCount调大数组长度比如设为 10但这会稍微增加内存默认的 2 个500ms 精度在性能和精度上达到了最好的平衡。2.StatisticNode简单来说StatisticNode就是 Sentinel 进行实时流量统计的“数据收集器”和“仓库”。为了让你更直观地理解可以把它看作是一个高性能的“仪表盘”——每一个请求的到来、通过、拒绝、耗时等信息都会实时上报并记录在StatisticNode里。当限流规则比如 QPS 不能超过 100需要判断时Sentinel 就会直接从这个节点里查询“过去 1 秒内有多少个请求”然后决定是否放行。它在 Sentinel 的架构中承担了两个最核心的职能1. 它是“滑动窗口”的载体我们刚才聊到的滑动窗口LeapArray其实就是StatisticNode里的核心成员变量。StatisticNode内部维护了两个滑动窗口数组rollingCounterInSecond用于秒级统计QPS、响应时间等。它默认将 1 秒分成 2 个 500ms 的格子。rollingCounterInMinute用于分钟级统计用于判断是否达到熔断降级的慢调用比例等。它将 1 分钟分成 60 个格子每个格子 1 秒。所以当你问“基于 QPS 限流的数据结构是什么”时本质上就是StatisticNode里的rollingCounterInSecond这个滑动窗口。2. 它是“多维度指标”的统计中枢StatisticNode不仅仅统计总请求数它会将请求分类统计。在它的代码逻辑里每次请求进来都会调用addPassRequest记录通过数或addBlockRequest记录拒绝数等方法。它主要维护了以下几类计数器通过滑动窗口中的MetricBucket存储pass通过的请求数用于计算 QPS。block被限流/降级拦截的请求数。success业务逻辑执行成功的请求数用于计算异常比例。rtResponse Time请求的响应耗时用于计算平均 RT。exception业务异常数。它在架构中的位置便于理解你可以把 Sentinel 的工作流想象成这样请求进入- 2.StatisticNode记录请求1- 3.查询StatisticNode过去 1 秒的总数- 4.判断是否超过阈值- 5.放行或拒绝。而StatisticNode通常不会单独存在它会被另一个概念ProcessorSlotChain处理器插槽链所持有。在默认的调用链中StatisticNode属于StatisticSlot这个插槽来管理。总结一句话StatisticNode就是 Sentinel 用来承载“滑动窗口算法”并对 QPS、RT、异常率等所有实时指标进行线程安全统计的“本地内存数据节点”。如果没有它Sentinel 就无法知道当前的流量到底有多大限流也就无从谈起。StatisticNode数据结构public class StatisticNode implements Node { /** * 保存最近 1 秒内的统计数据 * 每个桶bucket500ms共 2 个桶 */ private transient volatile Metric rollingCounterInSecond new ArrayMetric(SampleCountProperty.SAMPLE_COUNT, IntervalProperty.INTERVAL); /** * 保存最近 60 秒的统计数据 * windowLengthInMs 被特意设置为 1000 毫秒即每个桶代表 1 秒 * 共 60 个桶这样可以获得每秒精确的统计信息 */ private transient Metric rollingCounterInMinute new ArrayMetric(60, 60 * 1000, false); // 省略其他字段和方法... } 作者得物技术 链接https://juejin.cn/post/7610636104946270227 来源稀土掘金 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。2.ArrayMetric是StatisticNode的“底层引擎”或“数据管家”。如果用一个比喻来理解StatisticNode是“前台接待员”负责告诉外界“我能提供 QPS、RT 等数据”。ArrayMetric是“后台数据库引擎”负责真正地执行“数据写到哪里”和“从哪个格子读取数据”。StatisticNode持有包含ArrayMetric的引用而ArrayMetric持有包含我们上一轮讨论的核心数据结构——滑动窗口LeapArray。数据结构public class ArrayMetric implements Metric { /** * 滑动窗口数组 */ private final LeapArrayMetricBucket data; public ArrayMetric(int sampleCount, int intervalInMs) { this.data new OccupiableBucketLeapArray(sampleCount, intervalInMs); } public ArrayMetric(int sampleCount, int intervalInMs, boolean enableOccupy) { if (enableOccupy) { // 可抢占的滑动窗口支持借用未来窗口的配额 this.data new OccupiableBucketLeapArray(sampleCount, intervalInMs); } else { // 普通滑动窗口 this.data new BucketLeapArray(sampleCount, intervalInMs); } } }1. 它们的核心区别与职责组件核心职责面向对象StatisticNode指标分类与业务逻辑。它定义了我们有哪些指标pass、block、rt、success等并提供addPassRequest()、successQps()这类业务含义明确的 API。给 Sentinel 限流规则判断时调用面向业务。ArrayMetric数据读写实现。它屏蔽了底层滑动窗口操作的复杂性比如数组下标计算、CAS 更新、过期数据重置。它提供的 API 是通用的比如add(MetricEvent, int)。给StatisticNode调用执行具体的存储与统计面向技术实现。LeapArray存储实体。它是一个抽象父类真正存放数据的是其子类如OccupiableBucketLeapArray。它负责维护环形数组和每个格子MetricBucket。被ArrayMetric调用操作底层的数组和对象。2. 为什么要设计成StatisticNode-ArrayMetric-LeapArray三层这是典型的单一职责原则设计好处很明显StatisticNode不用关心“数据怎么存”它只关心“存什么数据”和“对外提供什么数据”。这使得它很“轻”业务语义清晰。ArrayMetric作为中间层封装了所有对滑动窗口的增删改查操作。它让上层StatisticNode可以像操作一个普通的Map一样存取数据而无需关心底层是数组还是链表。LeapArray专注于最底层、最高性能的环形数组复用算法。如果未来要换一种存储结构虽然不太可能也只需要修改ArrayMetric中的实现而完全不影响StatisticNode。