【环球速看料】高并发面试必问,常见四大限流算法实现原理
时间 : 2023-05-16 10:39:23   来源 : 一灯架构

在分布式系统中,高并发场景下,为了防止系统因突然的流量激增而导致的崩溃,同时保证服务的高可用性和稳定性,限流是最常用的手段。

限流算法也是面试中必考题,今天一灯带大家一块学习一下常见的四种限流算法,分别是:固定窗口算法滑动窗口算法漏桶算法令牌桶算法


【资料图】

1. 固定窗口算法1.1 实现原理

固定窗口限流算法,也叫计数器限流算法,是最简单的一种限流算法。

实现原理是:在一个固定长度的时间窗口内限制请求数量,每来一个请求,请求次数加一,如果请求数量超过最大限制,就拒绝该请求。

下面使用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;    }}
1.3 优缺点

优点:实现简单,容易理解。

缺点:

限流不够平滑。例如:限流是每秒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);    }}
2.3 优缺点

优点:解决了固定窗口算法的窗口边界问题,避免突发流量压垮服务器。

缺点:还是存在限流不够平滑的问题。例如:限流是每秒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;    }}
3.3 优缺点

优点:

平滑流量。由于漏桶算法以固定的速率处理请求,可以有效地平滑和整形流量,避免流量的突发和波动(类似于消息队列的削峰填谷的作用)。防止过载。当流入的请求超过桶的容量时,可以直接丢弃请求,防止系统过载。

缺点:

无法处理突发流量:由于漏桶的出口速度是固定的,无法处理突发流量。例如,即使在流量较小的时候,也无法以更快的速度处理请求。可能会丢失数据:如果入口流量过大,超过了桶的容量,那么就需要丢弃部分请求。在一些不能接受丢失请求的场景中,这可能是一个问题。不适合速率变化大的场景:如果速率变化大,或者需要动态调整速率,那么漏桶算法就无法满足需求。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;    }}
4.3 优缺点

优点:

可以处理突发流量:令牌桶算法可以处理突发流量。当桶满时,能够以最大速度处理请求。这对于需要处理突发流量的应用场景非常有用。限制平均速率:在长期运行中,数据的传输率会被限制在预定义的平均速率(即生成令牌的速率)。灵活性:与漏桶算法相比,令牌桶算法提供了更大的灵活性。例如,可以动态地调整生成令牌的速率。

缺点:

可能导致过载:如果令牌产生的速度过快,可能会导致大量的突发流量,这可能会使网络或服务过载。需要存储空间:令牌桶需要一定的存储空间来保存令牌,可能会导致内存资源的浪费。实现稍复杂:相比于计数器算法,令牌桶算法的实现稍微复杂一些。5. 总结

这篇文章我们介绍了四种常用的限流算法:固定窗口算法、滑动窗口算法、漏桶算法和令牌桶算法。每种算法都有其特点和适用场景,下面我们来对它们进行简单的总结和比较。

固定窗口算法实现简单,但是限流不够平滑,存在窗口边界问题,适用于需要简单实现限流的场景。

滑动窗口算法解决了窗口边界问题,但是还是存在限流不够平滑的问题,适用于需要控制平均请求速率的场景。

漏桶算法的优点是流量处理更平滑,但是无法应对突发流量,适用于需要平滑流量的场景。

令牌桶算法既能平滑流量,又能处理突发流量,适用于需要处理突发流量的场景。

标签:

相关文章

X 关闭

X 关闭