序
在高并发系统中，我们通常需要通过缓存、降级和限流等多种方式来提供系统的可用性。本文将详细解释应用中常用的限流算法。
简介
流量限制(flow rate limit)的简称，流量限制是指只允许指定的事件进入系统，超出部分将被拒绝服务、排队或等待、降级等处理。常见的流量限制方案如下:
固定时间窗口
固定时间窗是最常见的限流算法之一。窗口的概念对应的是限流场景中的限流时间单位。
原则
时间线被分成多个大小固定独立窗口；
落在每个时间窗口内的请求使计数器增加1；
如果计数器超过当前限制阈值，则落入该窗口的后续请求将被拒绝。但是当时间到达下一个时间窗口时，计数器将被重置为0。
说明
注意:在上面显示的场景中，电流被限制为每秒10次，窗口大小为1秒。每个方块代表一个请求，绿色方块代表一个正常的请求，红色方法代表一个受限的请求。在每秒10次的场景下，从左向右看，输入10个请求后，后面的请求会受到限制。
优点和缺点
优势
逻辑简单，维护成本低；
劣势
切换车窗时，不能保证电流限值。
相关实施
固定时间窗的具体实现可以通过Redis调用lua限流脚本来实现。
限流脚本
具体实现
试验
注意:该测试每3秒访问一次，超过时会提示错误。
滑动时间窗口
滑动窗口算法是固定窗口算法的改进。在滑动窗口算法中，还需要根据当前请求动态查询窗口。但是窗口中的每个元素都是子窗口。子窗口的概念类似于第一种方案中的固定窗口，子窗口的大小可以动态调整。
实现原则
单位时间分为几个区间，一般分为几个小时间段；
每个区间都有一个计数器。如果请求落在此间隔内，此间隔内的计数器将增加1。
在每个时间段之后，时间窗口将向右滑动一个网格，丢弃最老的间隔并将其带入新的间隔；
在计算整个时间窗口内的请求总数时，所有时间段内的计数器都将累加。如果总计数超过限制数，此窗口中的所有请求都将被丢弃。
说明
注意:比如上图中的场景是每分钟限流100次。每个子窗口的时间维度设置为1秒，因此一分钟的窗口有60个子窗口。每当这样的请求到来，我们动态计算这个窗口的时候，最多需要寻找60次。时间的复杂度从线性变成了常数，时间的复杂度会相对低一些。
具体实现
至于滑动时间窗的实现，可以使用sentinel，后面会详细讲解sentinel的使用方法。
漏桶
漏桶水首先进入漏桶，然后漏桶以一定的速度流出。当进水大于出水时，多余的水直接溢出。当请求替换为水时，漏桶相当于服务器队列，但当请求量大于当前限制阈值时，多余的请求将被拒绝服务。通过使用漏桶队列，可以将业务的访问速度控制在一个固定的速率上，并且可以对业务进行分级。
原则
描述:
将每个请求放在固定大小的队列中等待处理。
队列以固定的速率流出请求，如果队列为空，则停止流出。
如果队列已满，多余的请求将被直接拒绝。
具体实现
令牌桶算法
令牌桶算法是基于漏桶的改进版本。在令牌桶中，令牌代表当前系统允许的请求上限，令牌将以统一的速度放入桶中。当桶满时，新令牌被丢弃。
原则
令牌以固定速率生成，并放入令牌桶；
如果令牌桶已满，多余的令牌将被直接丢弃。当请求到达时，将从令牌桶中提取令牌，并且可以执行已经获得令牌的请求。
如果bucket 空用完了，请求就会被拒绝。
具体实现
执行结果:
解释:接口被限制为每2秒一个请求，需要10个线程20秒来完成处理。但是，rateLimiter.tryAcquire限制在10秒钟内没有获得令牌的情况下抛出异常，因此5个结果将被频繁请求。
总结
固定窗口:实现简单，适用于流量分布比较均匀，限流精度要求不高的场景。
滑动窗口:适用于对精度和性能有一定要求的场景，可以调整子窗口数量来权衡性能和精度。
漏桶:适用于交通绝对畅通的场景。
令牌桶:适用于整体流畅的流量，也可以满足一定的突发流程场景。
摘要
本文详细阐述了几种限流算法的原理和实现。如果您有任何问题，请随时反馈。
作者:大剑师无痕
链接:file/tupian/20220813/p
免责声明：本平台仅供信息发布交流之途，请谨慎判断信息真伪。如遇虚假诈骗信息，请立即举报
举报
