在分布式系统中，高并发场景下，为了防止系统因突然的流量激增而导致的崩溃，同时保证服务的高可用性和稳定性，限流是最常用的手段。
限流算法也是面试中必考题，今天一灯带大家一块学习一下常见的四种限流算法，分别是：固定窗口算法、滑动窗口算法、漏桶算法、令牌桶算法。
【资料图】
固定窗口限流算法，也叫计数器限流算法，是最简单的一种限流算法。
实现原理是：在一个固定长度的时间窗口内限制请求数量，每来一个请求，请求次数加一，如果请求数量超过最大限制，就拒绝该请求。
下面使用Java伪代码实现一下固定窗口限流算法，注意以下算法没有考虑并发情况，在并发环境下，可以使用Synchronized、Reentrantlock或者AtomicLong等并发工具来保证数据安全性。
1.2 代码实现/** * @author 一灯架构 * @apiNote 固定窗口限流算法 **/public class FixWindowLimiter { /** * 每个窗口的最大请求数量 */ public static long threshold = 10; /** * 窗口大小，1000ms */ public static long windowUnit = 1000; /** * 窗口内的当前请求数量 */ public static long count = 0; /** * 窗口的开始时间 */ public static long lastTime = 0; /** * 限流方法，返回true表示通过 */ public boolean limit() { // 获取系统当前时间 long currentTime = System.currentTimeMillis(); // 判断是否在当前时间窗口内，如果不在就开启一个新的时间窗口 if (currentTime - lastTime > windowUnit) { // 计数器清零 count = 0; // 开启新的时间窗口 lastTime = currentTime; } // 判断是否超过最大请求量 if (count < threshold) { count++; return true; } return false; }}优点：实现简单，容易理解。
缺点：
限流不够平滑。例如：限流是每秒3个，在第一毫秒发送了3个请求，达到限流，窗口剩余时间的请求都将会被拒绝，体验不好。无法处理窗口边界问题。因为是在某个时间窗口内进行流量控制，所以可能会出现窗口边界效应，即在时间窗口的边界处可能会有大量的请求被允许通过，从而导致突发流量。例如：限流是每秒3个，在第一秒的最后一毫秒发送了3个请求，在第二秒的第一毫秒又发送了3个请求。在这两毫米内处理了6个请求，但是并没有触发限流。如果出现突发流量，可能会压垮服务器。
2. 滑动窗口算法2.1 实现原理滑动窗口算法是对固定窗口算法的一种改进。在滑动窗口算法中，窗口的起止时间是动态的，窗口的大小固定。这种算法能够较好地处理窗口边界问题，但是实现相对复杂，需要记录每个请求的时间戳。
实现原理是：每来一个请求，就向后推一个时间窗口，计算这个窗口内的请求数量。如果请求数量超过限制就拒绝请求，否则就处理请求，并记录请求的时间戳。另外还需要一个任务清理过期的时间戳。
2.2 代码实现/** * @author 一灯架构 * @apiNote 固定窗口限流算法 **/public class SlidingWindowLimiter { /** * 每个窗口的最大请求数量 */ public static long threshold = 10; /** * 窗口大小，1000ms */ public static long windowUnit = 1000; /** * 请求集合，用来存储窗口内的请求数量 */ public static List requestList = new ArrayList<>(); /** * 限流方法，返回true表示通过 */ public boolean limit() { // 获取系统当前时间 long currentTime = System.currentTimeMillis(); // 统计当前窗口内，有效的请求数量 int sizeOfValid = this.sizeOfValid(currentTime); // 判断是否超过最大请求数量 if (sizeOfValid < threshold) { // 把当前请求添加到请求集合里 requestList.add(currentTime); return true; } return false; } /** * 统计当前窗口内，有效的请求数量 */ private int sizeOfValid(long currentTime) { int sizeOfValid = 0; for (Long requestTime : requestList) { // 判断是否在当前时间窗口内 if (currentTime - requestTime <= windowUnit) { sizeOfValid++; } } return sizeOfValid; } /** * 清理过期的请求（单独启动一个线程处理） */ private void clean() { // 判断是否超出当前时间窗口内 requestList.removeIf(requestTime -> System.currentTimeMillis() - requestTime > windowUnit); }} 优点：解决了固定窗口算法的窗口边界问题，避免突发流量压垮服务器。
缺点：还是存在限流不够平滑的问题。例如：限流是每秒3个，在第一毫秒发送了3个请求，达到限流，剩余窗口时间的请求都将会被拒绝，体验不好。
3. 漏桶算法3.1 实现原理漏桶限流算法是一种常用的流量整形（Traffic Shaping）和流量控制（Traffic Policing）的算法，它可以有效地控制数据的传输速率以及防止网络拥塞。
实现原理是：
一个固定容量的漏桶，按照固定速率出水（处理请求）；当流入水（请求数量）的速度过大会直接溢出（请求数量超过限制则直接拒绝）。桶里的水（请求）不够则无法出水（桶内没有请求则不处理）。当请求流量正常或者较小的时候，请求能够得到正常的处理。当请求流量过大时，漏桶限流算法可以通过丢弃部分请求来防止系统过载。
这种算法的一个重要特性是，输出数据的速率始终是稳定的，无论输入的数据流量如何变化。这就确保了系统的负载不会超过预设的阈值。但是，由于漏桶的出口速度是固定的，所以无法处理突发流量。此外，如果入口流量过大，漏桶可能会溢出，导致数据丢失。
3.2 代码实现/** * @author 一灯架构 * @apiNote 漏桶限流算法 **/public class LeakyBucketLimiter { /** * 桶的最大容量 */ public static long threshold = 10; /** * 桶内当前水量 */ public static long count = 0; /** * 漏水速率（每秒5次） */ public static long leakRate = 5; /** * 上次漏水时间 */ public static long lastLeakTime = System.currentTimeMillis(); /** * 限流方法，返回true表示通过 */ public boolean limit() { // 调用漏水方法 this.leak(); // 判断是否超过最大请求数量 if (count < threshold) { count++; return true; } return false; } /** * 漏水方法，计算并更新这段时间内漏水量 */ private void leak() { // 获取系统当前时间 long currentTime = System.currentTimeMillis(); // 计算这段时间内，需要流出的水量 long leakWater = (currentTime - lastLeakTime) * leakRate / 1000; count = Math.max(count - leakWater, 0); lastLeakTime = currentTime; }}优点：
平滑流量。由于漏桶算法以固定的速率处理请求，可以有效地平滑和整形流量，避免流量的突发和波动（类似于消息队列的削峰填谷的作用）。防止过载。当流入的请求超过桶的容量时，可以直接丢弃请求，防止系统过载。缺点：
无法处理突发流量：由于漏桶的出口速度是固定的，无法处理突发流量。例如，即使在流量较小的时候，也无法以更快的速度处理请求。可能会丢失数据：如果入口流量过大，超过了桶的容量，那么就需要丢弃部分请求。在一些不能接受丢失请求的场景中，这可能是一个问题。不适合速率变化大的场景：如果速率变化大，或者需要动态调整速率，那么漏桶算法就无法满足需求。4. 令牌桶算法4.1 实现原理令牌桶限流算法是一种常用的流量整形和速率限制算法。与漏桶算法一样，令牌桶算法也是用来控制发送到网络上的数据的数量。
实现原理：
系统以固定的速率向桶中添加令牌；当有请求到来时，会尝试从桶中移除一个令牌，如果桶中有足够的令牌，则请求可以被处理或数据包可以被发送；如果桶中没有令牌，那么请求将被拒绝；桶中的令牌数不能超过桶的容量，如果新生成的令牌超过了桶的容量，那么新的令牌会被丢弃。令牌桶算法的一个重要特性是，它能够应对突发流量。当桶中有足够的令牌时，可以一次性处理多个请求，这对于需要处理突发流量的应用场景非常有用。但是又不会无限制的增加处理速率导致压垮服务器，因为桶内令牌数量是有限制的。
4.2 代码实现/** * @author 一灯架构 * @apiNote 漏桶限流算法 **/public class TokenBucketLimiter { /** * 桶的最大容量 */ public static long threshold = 10; /** * 桶内当前的令牌数量 */ public static long count = 0; /** * 令牌生成速率（每秒5次） */ public static long tokenRate = 5; /** * 上次生成令牌的时间 */ public static long lastRefillTime = System.currentTimeMillis(); /** * 限流方法，返回true表示通过 */ public boolean limit() { // 调用生成令牌方法 this.refillTokens(); // 判断桶内是否还有令牌 if (count > 0) { count--; return true; } return false; } /** * 生成令牌方法，计算并更新这段时间内生成的令牌数量 */ private void refillTokens() { long currentTime = System.currentTimeMillis(); // 计算这段时间内，需要生成的令牌数量 long refillTokens = (currentTime - lastRefillTime) * tokenRate / 1000; count = Math.min(count + refillTokens, threshold); lastRefillTime = currentTime; }}优点：
可以处理突发流量：令牌桶算法可以处理突发流量。当桶满时，能够以最大速度处理请求。这对于需要处理突发流量的应用场景非常有用。限制平均速率：在长期运行中，数据的传输率会被限制在预定义的平均速率（即生成令牌的速率）。灵活性：与漏桶算法相比，令牌桶算法提供了更大的灵活性。例如，可以动态地调整生成令牌的速率。缺点：
可能导致过载：如果令牌产生的速度过快，可能会导致大量的突发流量，这可能会使网络或服务过载。需要存储空间：令牌桶需要一定的存储空间来保存令牌，可能会导致内存资源的浪费。实现稍复杂：相比于计数器算法，令牌桶算法的实现稍微复杂一些。5. 总结这篇文章我们介绍了四种常用的限流算法：固定窗口算法、滑动窗口算法、漏桶算法和令牌桶算法。每种算法都有其特点和适用场景，下面我们来对它们进行简单的总结和比较。
固定窗口算法实现简单，但是限流不够平滑，存在窗口边界问题，适用于需要简单实现限流的场景。
滑动窗口算法解决了窗口边界问题，但是还是存在限流不够平滑的问题，适用于需要控制平均请求速率的场景。
漏桶算法的优点是流量处理更平滑，但是无法应对突发流量，适用于需要平滑流量的场景。
令牌桶算法既能平滑流量，又能处理突发流量，适用于需要处理突发流量的场景。
标签：
