详解5种Java中常见限流算法

目录
  • 01固定窗口
  • 02滑动窗口
  • 03漏桶算法
  • 04令牌桶
  • 05滑动日志
  • 06分布式限流
  • 07总结

1.瞬时流量过高,服务被压垮?

2.恶意用户高频光顾,导致服务器宕机?

3.消息消费过快,导致数据库压力过大,性能下降甚至崩溃?

......

在高并发系统中,出于系统保护角度考虑,通常会对流量进行限流;不但在工作中要频繁使用,而且也是面试中的高频考点。

今天我们将图文并茂地对常见的限流算法分别进行介绍,通过各个算法的特点,给出限流算法选型的一些建议,并给出Java语言实现的代码示例。

01固定窗口

固定窗口又称固定窗口(又称计数器算法,Fixed Window)限流算法,是最简单的限流算法,通过在单位时间内维护的计数器来控制该时间单位内的最大访问量。

假设限制每分钟请求量不超过60,设置一个计数器,当请求到达时如果计数器到达阈值,则拒绝请求,否则计数器加1;每分钟重置计数器为0。代码实现如下:

public class CounterRateLimiter extends MyRateLimiter {
    /**
     * 每秒限制请求数
     */
    private final long permitsPerSecond;
    /**
     * 上一个窗口的开始时间
     */
    public long timestamp = System.currentTimeMillis();
    /**
     * 计数器
     */
    private int counter;

    public CounterRateLimiter(long permitsPerSecond) {
        this.permitsPerSecond = permitsPerSecond;
    }

    @Override
    public synchronized boolean tryAcquire() {
        long now = System.currentTimeMillis();
        // 窗口内请求数量小于阈值,更新计数放行,否则拒绝请求
        if (now - timestamp < 1000) {
            if (counter < permitsPerSecond) {
                counter++;
                return true;
            } else {
                return false;
            }
        }
        // 时间窗口过期,重置计数器和时间戳
        counter = 0;
        timestamp = now;
        return true;
    }
}

固定窗口最大的优点在于易于实现;并且内存占用小,我们只需要存储时间窗口中的计数即可;它能够确保处理更多的最新请求,不会因为旧请求的堆积导致新请求被饿死。当然也面临着临界问题,当两个窗口交界处,瞬时流量可能为2n。

02滑动窗口

为了防止瞬时流量,可以把固定窗口近一步划分成多个格子,每次向后移动一小格,而不是固定窗口大小,这就是滑动窗口(Sliding Window)。

比如每分钟可以分为6个10秒中的单元格,每个格子中分别维护一个计数器,窗口每次向前滑动一个单元格。每当请求到达时,只要窗口中所有单元格的计数总和不超过阈值都可以放行。TCP协议中数据包的传输,同样也是采用滑动窗口来进行流量控制。

实现如下:

public class SlidingWindowRateLimiter extends MyRateLimiter {
    /**
     * 每分钟限制请求数
     */
    private final long permitsPerMinute;
    /**
     * 计数器, k-为当前窗口的开始时间值秒,value为当前窗口的计数
     */
    private final TreeMap<Long, Integer> counters;

    public SlidingWindowRateLimiter(long permitsPerMinute) {
        this.permitsPerMinute = permitsPerMinute;
        this.counters = new TreeMap<>();
    }

    @Override
    public synchronized boolean tryAcquire() {
        // 获取当前时间的所在的子窗口值; 10s一个窗口
        long currentWindowTime = LocalDateTime.now().toEpochSecond(ZoneOffset.UTC) / 10 * 10;
        // 获取当前窗口的请求总量
        int currentWindowCount = getCurrentWindowCount(currentWindowTime);
        if (currentWindowCount >= permitsPerMinute) {
            return false;
        }
        // 计数器 + 1
        counters.merge(currentWindowTime, 1, Integer::sum);
        return true;
    }
    /**
     * 获取当前窗口中的所有请求数(并删除所有无效的子窗口计数器)
     *
     * @param currentWindowTime 当前子窗口时间
     * @return 当前窗口中的计数
     */
    private int getCurrentWindowCount(long currentWindowTime) {
        // 计算出窗口的开始位置时间
        long startTime = currentWindowTime - 50;
        int result = 0;

        // 遍历当前存储的计数器,删除无效的子窗口计数器,并累加当前窗口中的所有计数器之和
        Iterator<Map.Entry<Long, Integer>> iterator = counters.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<Long, Integer> entry = iterator.next();
            if (entry.getKey() < startTime) {
                iterator.remove();
            } else {
                result += entry.getValue();
            }
        }
        return result;
    }
}

滑动窗口解决了计数器中的瞬时流量高峰问题,其实计数器算法也是滑动窗口的一种,只不过窗口没有进行更细粒度单元的划分。对比计数器可见,当窗口划分的粒度越细,则流量控制更加精准和严格。

不过当窗口中流量到达阈值时,流量会瞬间切断,在实际应用中我们要的限流效果往往不是把流量一下子掐断,而是让流量平滑地进入系统当中。

03漏桶算法

如何更加平滑的限流?不妨看看漏桶算法(Leaky Bucket),请求就像水一样以任意速度注入漏桶,而桶会按照固定的速率将水漏掉;当注入速度持续大于漏出的速度时,漏桶会变满,此时新进入的请求将会被丢弃。限流和整形是漏桶算法的两个核心能力。

实现如下:

public class LeakyBucketRateLimiter extends MyRateLimiter {
    // 桶的容量
    private final int capacity;
    // 漏出速率
    private final int permitsPerSecond;
    // 剩余水量
    private long leftWater;
    // 上次注入时间
    private long timeStamp = System.currentTimeMillis();

    public LeakyBucketRateLimiter(int permitsPerSecond, int capacity) {
        this.capacity = capacity;
        this.permitsPerSecond = permitsPerSecond;
    }

    @Override
    public synchronized boolean tryAcquire() {
        //1. 计算剩余水量
        long now = System.currentTimeMillis();
        long timeGap = (now - timeStamp) / 1000;
        leftWater = Math.max(0, leftWater - timeGap * permitsPerSecond);
        timeStamp = now;

        // 如果未满,则放行;否则限流
        if (leftWater < capacity) {
            leftWater += 1;
            return true;
        }
        return false;
    }
}

这并不是一个完整的漏桶算法的实现,以上代码中只是对流量是否会被抛弃进行校验,即tryAcquire返回true表示漏桶未满,否则表示漏桶已满丢弃请求。

想要以恒定的速率漏出流量,通常还应配合一个FIFO队列来实现,当tryAcquire返回true时,将请求入队,然后再以固定频率从队列中取出请求进行处理。示例代码如下:

@Test
public void testLeakyBucketRateLimiter() throws InterruptedException {
    ScheduledExecutorService scheduledExecutorService = Executors.newSingleThreadScheduledExecutor();
    ExecutorService singleThread = Executors.newSingleThreadExecutor();

    LeakyBucketRateLimiter rateLimiter = new LeakyBucketRateLimiter(20, 20);
    // 存储流量的队列
    Queue<Integer> queue = new LinkedList<>();
    // 模拟请求  不确定速率注水
    singleThread.execute(() -> {
        int count = 0;
        while (true) {
            count++;
            boolean flag = rateLimiter.tryAcquire();
            if (flag) {
                queue.offer(count);
                System.out.println(count + "--------流量被放行--------");
            } else {
                System.out.println(count + "流量被限制");
            }
            try {
                Thread.sleep((long) (Math.random() * 1000));
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    });

    // 模拟处理请求 固定速率漏水
    scheduledExecutorService.scheduleAtFixedRate(() -> {
        if (!queue.isEmpty()) {
            System.out.println(queue.poll() + "被处理");
        }
    }, 0, 100, TimeUnit.MILLISECONDS);

    // 保证主线程不会退出
    while (true) {
        Thread.sleep(10000);
    }
}

漏桶算法存在目的主要是用来平滑突发的流量,提供一种机制来确保网络中的突发流量被整合成平滑稳定的额流量。

不过由于漏桶对流量的控制过于严格,在有些场景下不能充分使用系统资源,因为漏桶的漏出速率是固定的,即使在某一时刻下游能够处理更大的流量,漏桶也不允许突发流量通过。

04令牌桶

如何在够限制流量速率的前提下,又能够允许突发流量呢?令牌桶算法了解一下!令牌桶算法是以恒定速率向令牌桶发送令牌,请求到达时,尝试从令牌桶中拿令牌,只有拿到令牌才能够放行,否则将会被拒绝。

令牌桶具有以下特点:

1.以恒定的速率发放令牌,假设限流速率为v/s,则表示每1/v秒发放一个令牌

2.假设令牌桶容量是b,如果令牌桶已满,则新的令牌会被丢弃

3.请求能够通过限流器的前提是令牌桶中有令牌

令牌桶算法中值得关注的参数有两个,即限流速率v/s,和令牌桶容量b;速率a表示限流器一般情况下的限流速率,而b则是burst的简写,表示限流器允许的最大突发流量。

比如b=10,当令牌桶满的时候有10个可用令牌,此时允许10个请求同时通过限流器(允许流量一定程度的突发),这10个请求瞬间消耗完令牌后,后续的流量只能按照速率r通过限流器。

实现如下:

public class TokenBucketRateLimiter extends MyRateLimiter {
    /**
     * 令牌桶的容量「限流器允许的最大突发流量」
     */
    private final long capacity;
    /**
     * 令牌发放速率
     */
    private final long generatedPerSeconds;
    /**
     * 最后一个令牌发放的时间
     */
    long lastTokenTime = System.currentTimeMillis();
    /**
     * 当前令牌数量
     */
    private long currentTokens;

    public TokenBucketRateLimiter(long generatedPerSeconds, int capacity) {
        this.generatedPerSeconds = generatedPerSeconds;
        this.capacity = capacity;
    }

    /**
     * 尝试获取令牌
     *
     * @return true表示获取到令牌,放行;否则为限流
     */
    @Override
    public synchronized boolean tryAcquire() {
          /**
           * 计算令牌当前数量
           * 请求时间在最后令牌是产生时间相差大于等于额1s(为啥时1s?因为生成令牌的最小时间单位时s),则
           * 1. 重新计算令牌桶中的令牌数
           * 2. 将最后一个令牌发放时间重置为当前时间
           */
        long now = System.currentTimeMillis();
        if (now - lastTokenTime >= 1000) {
            long newPermits = (now - lastTokenTime) / 1000 * generatedPerSeconds;
            currentTokens = Math.min(currentTokens + newPermits, capacity);
            lastTokenTime = now;
        }
        if (currentTokens > 0) {
            currentTokens--;
            return true;
        }
        return false;
    }
}

需要主意的是,非常容易被想到的实现是生产者消费者模式;用一个生产者线程定时向阻塞队列中添加令牌,而试图通过限流器的线程则作为消费者线程,只有从阻塞队列中获取到令牌,才允许通过限流器。

由于线程调度的不确定性,在高并发场景时,定时器误差非常大,同时定时器本身会创建调度线程,也会对系统的性能产生影响。

05滑动日志

滑动日志是一个比较“冷门”,但是确实好用的限流算法。滑动日志限速算法需要记录请求的时间戳,通常使用有序集合来存储,我们可以在单个有序集合中跟踪用户在一个时间段内所有的请求。

假设我们要限制给定T时间内的请求不超过N,我们只需要存储最近T时间之内的请求日志,每当请求到来时判断最近T时间内的请求总数是否超过阈值。

实现如下:

public class SlidingLogRateLimiter extends MyRateLimiter {
    /**
     * 每分钟限制请求数
     */
    private static final long PERMITS_PER_MINUTE = 60;
    /**
     * 请求日志计数器, k-为请求的时间(秒),value当前时间的请求数量
     */
    private final TreeMap<Long, Integer> requestLogCountMap = new TreeMap<>();

    @Override
    public synchronized boolean tryAcquire() {
        // 最小时间粒度为s
        long currentTimestamp = LocalDateTime.now().toEpochSecond(ZoneOffset.UTC);
        // 获取当前窗口的请求总数
        int currentWindowCount = getCurrentWindowCount(currentTimestamp);
        if (currentWindowCount >= PERMITS_PER_MINUTE) {
            return false;
        }
        // 请求成功,将当前请求日志加入到日志中
        requestLogCountMap.merge(currentTimestamp, 1, Integer::sum);
        return true;
    }

    /**
     * 统计当前时间窗口内的请求数
     *
     * @param currentTime 当前时间
     * @return -
     */
    private int getCurrentWindowCount(long currentTime) {
        // 计算出窗口的开始位置时间
        long startTime = currentTime - 59;
        // 遍历当前存储的计数器,删除无效的子窗口计数器,并累加当前窗口中的所有计数器之和
        return requestLogCountMap.entrySet()
                .stream()
                .filter(entry -> entry.getKey() >= startTime)
                .mapToInt(Map.Entry::getValue)
                .sum();
    }
}

滑动日志能够避免突发流量,实现较为精准的限流;同样更加灵活,能够支持更加复杂的限流策略,如多级限流,每分钟不超过100次,每小时不超过300次,每天不超过1000次,我们只需要保存最近24小时所有的请求日志即可实现。

灵活并不是没有代价的,带来的缺点就是占用存储空间要高于其他限流算法。

06分布式限流

以上几种限流算法的实现都仅适合单机限流。虽然给每台机器平均分配限流配额可以达到限流的目的,但是由于机器性能,流量分布不均以及计算数量动态变化等问题,单机限流在分布式场景中的效果总是差强人意。

分布式限流最简单的实现就是利用中心化存储,即将单机限流存储在本地的数据存储到同一个存储空间中,如常见的Redis等。

当然也可以从上层流量入口进行限流,Nginx代理服务就提供了限流模块,同样能够实现高性能,精准的限流,其底层是漏桶算法。

07总结

1.固定窗口算法实现简单,性能高,但是会有临界突发流量问题,瞬时流量最大可以达到阈值的2倍。

2.为了解决临界突发流量,可以将窗口划分为多个更细粒度的单元,每次窗口向右移动一个单元,于是便有了滑动窗口算法。

滑动窗口当流量到达阈值时会瞬间掐断流量,所以导致流量不够平滑。

3.想要达到限流的目的,又不会掐断流量,使得流量更加平滑?可以考虑漏桶算法!需要注意的是,漏桶算法通常配置一个FIFO的队列使用以达到允许限流的作用。

由于速率固定,即使在某个时刻下游处理能力过剩,也不能得到很好的利用,这是漏桶算法的一个短板。

4.限流和瞬时流量其实并不矛盾,在大多数场景中,短时间突发流量系统是完全可以接受的。令牌桶算法就是不二之选了,令牌桶以固定的速率v产生令牌放入一个固定容量为n的桶中,当请求到达时尝试从桶中获取令牌。

当桶满时,允许最大瞬时流量为n;当桶中没有剩余流量时则限流速率最低,为令牌生成的速率v。

5.如何实现更加灵活的多级限流呢?滑动日志限流算法了解一下!这里的日志则是请求的时间戳,通过计算制定时间段内请求总数来实现灵活的限流。

当然,由于需要存储时间戳信息,其占用的存储空间要比其他限流算法要大得多。

不管黑猫白猫,能抓到老鼠的就是好猫。限流算法并没有绝对的好劣之分,如何选择合适的限流算法呢?不妨从性能,是否允许超出阈值,落地成本,流量平滑度,是否允许突发流量以及系统资源大小限制多方面考虑。

当然,市面上也有比较成熟的限流工具和框架。如Google出品的Guava中基于令牌桶实现的限流组件,拿来即用;以及alibaba开源的面向分布式服务架构的流量控制框架Sentinel更会让你爱不释手,它是基于滑动窗口实现的。

以上就是详解5种Java中常见限流算法的详细内容,更多关于Java限流算法的资料请关注我们其它相关文章!

(0)

相关推荐

  • Java中4种经典限流算法讲解

    目录 限流是什么? 常见的限流算法 固定窗口限流算法 滑动窗口限流算法 漏桶算法 令牌桶算法 最近,我们的业务系统引入了Guava的RateLimiter限流组件,它是基于令牌桶算法实现的,而令牌桶是非常经典的限流算法.本文将跟大家一起学习几种经典的限流算法. 限流是什么? 维基百科的概念如下: In computer networks, rate limiting is used to control the rate of requests sent or received by a net

  • java限流算法详细

    目录 1.场景 2.算法详解 2.1 计数算法 2.1.1 说明 2.1.2 适用场景 2.1.3 代码 2.2 漏桶算法 2.2.1 说明 2.2.2 漏桶算法图示 2.2.3 适用场景 2.2.4 代码 2.3 令牌桶算法 2.3.1 说明 2.3.2 令牌桶算法图示 2.3.3 适用场景 2.3.4 代码 2.3.5 第三方工具类 1.场景 程序中经常需要对接口进行限流,防止访问量太大,导致程序崩溃. 常用的算法有:计数算法.漏桶算法.令牌桶算法,最常用的算法是后面两种. 2.算法详解 2

  • Java 常见的限流算法详细分析并实现

    目录 为什么要限流 限流算法 计数器限流 漏桶限流 令牌桶限流 为什么要限流 在保证可用的情况下尽可能多增加进入的人数,其余的人在排队等待,或者返回友好提示,保证里面的进行系统的用户可以正常使用,防止系统雪崩. 限流算法 限流算法很多,常见的有三类,分别是 计数器算法 .漏桶算法.令牌桶算法 . (1)计数器:           在一段时间间隔内,处理请求的最大数量固定,超过部分不做处理. (2)漏桶:           漏桶大小固定,处理速度固定,但请求进入速度不固定(在突发情况请求过多时

  • Java实现5种限流算法及7种限流方式

    目录 前言 1. 限流 2. 固定窗口算法 2.1. 代码实现 3. 滑动窗口算法 3.1. 代码实现 4. 滑动日志算法 4.1. 代码实现 5. 漏桶算法 6. 令牌桶算法 6.1. 代码实现 6.2. 思考 7. Redis 分布式限流 7.1. 固定窗口限流 7.3. 滑动窗口限流 8. 总结 参考 前言 最近几年,随着微服务的流行,服务和服务之间的依赖越来越强,调用关系越来越复杂,服务和服务之间的稳定性越来越重要.在遇到突发的请求量激增,恶意的用户访问,亦或请求频率过高给下游服务带来较

  • 详解5种Java中常见限流算法

    目录 01固定窗口 02滑动窗口 03漏桶算法 04令牌桶 05滑动日志 06分布式限流 07总结 1.瞬时流量过高,服务被压垮? 2.恶意用户高频光顾,导致服务器宕机? 3.消息消费过快,导致数据库压力过大,性能下降甚至崩溃? ...... 在高并发系统中,出于系统保护角度考虑,通常会对流量进行限流:不但在工作中要频繁使用,而且也是面试中的高频考点. 今天我们将图文并茂地对常见的限流算法分别进行介绍,通过各个算法的特点,给出限流算法选型的一些建议,并给出Java语言实现的代码示例. 01固定窗

  • 详解如何把Java中if-else代码重构成高质量代码

    为什么我们写的代码都是if-else? 程序员想必都经历过这样的场景:刚开始自己写的代码很简洁,逻辑清晰,函数精简,没有一个if-else, 可随着代码逻辑不断完善和业务的瞬息万变:比如需要对入参进行类型和值进行判断:这里要判断下对象是否为null:不同类型执行不同的流程. 落地到具体实现只能不停地加if-else来处理,渐渐地,代码变得越来越庞大,函数越来越长,文件行数也迅速突破上千行,维护难度也越来越大,到后期基本达到一种难以维护的状态. 虽然我们都很不情愿写出满屏if-else的代码,可逻

  • 详解如何在Java中调用Python程序

    Java中调用Python程序 1.新建一个Maven工程,导入如下依赖 <dependency> <groupId>org.python</groupId> <artifactId>jython-standalone</artifactId> <version>2.7.0</version> </dependency> 2.在java中直接执行python代码片段 import org.python.util

  • 详解如何在Java中实现堆排序算法

    目录 算法描述 实现代码 测试代码 算法描述 堆排序算法的描述如下: 将待排序的数组调整为最大堆,此时未排序的长度 N 为数组的长度,调整的过程就是倒序将数组的前 N/2 个元素下沉的过程,每次下沉都会将较大的元素带到上面,最终将数组变为最大堆: 弹出最大堆的堆顶元素并将其移动到数组的最后面,将原本最后面的元素放到堆顶,然后将未排序的长度 N - 1,调整数组的前 N 个元素为最大堆: 重复步骤 2 直到未排序的长度为 0. 实现代码 package com.zhiyiyo.collection

  • 详解如何在Java中加密和解密zip文件

    目录 依赖 压缩一个文件 压缩多个文件 压缩一个目录 创建一个分割的压缩文件 提取所有文件 提取单个文件 总结 依赖 让我们先把 zip4j 依赖关系添加到我们的 pom.xml 文件中. <dependency>     <groupId>net.lingala.zip4j</groupId>     <artifactId>zip4j</artifactId>     <version>2.9.0</version>

  • Redis常见限流算法原理及实现

    目录 前言 简介 固定时间窗口 原理 示例说明 优缺点 相关实现 限流脚本 具体实现 测试 滑动时间窗口 实现原理 示例说明 具体实现 漏桶算法 原理 具体实现 令牌桶算法 原理 具体实现 小结 总结 前言 在高并发系统中,我们通常需要通过各种手段来提供系统的可以用性,例如缓存.降级和限流等,本文将针对应用中常用的限流算法进行详细的讲解. 简介 限流简称流量限速(Rate Limit)是指只允许指定的事件进入系统,超过的部分将被拒绝服务.排队或等待.降级等处理. 常见的限流方案如下: 固定时间窗

  • Go+Redis实现常见限流算法的示例代码

    目录 固定窗口 滑动窗口 hash实现 list实现 漏桶算法 令牌桶 滑动日志 总结 限流是项目中经常需要使用到的一种工具,一般用于限制用户的请求的频率,也可以避免瞬间流量过大导致系统崩溃,或者稳定消息处理速率.并且有时候我们还需要使用到分布式限流,常见的实现方式是使用Redis作为中心存储. 这个文章主要是使用Go+Redis实现常见的限流算法,如果需要了解每种限流算法的原理可以阅读文章 Go实现常见的限流算法 下面的代码使用到了go-redis客户端 固定窗口 使用Redis实现固定窗口比

  • 详解Springboot集成sentinel实现接口限流入门

    Sentinel是阿里巴巴开源的限流器熔断器,并且带有可视化操作界面. 在日常开发中,限流功能时常被使用,用于对某些接口进行限流熔断,譬如限制单位时间内接口访问次数:或者按照某种规则进行限流,如限制ip的单位时间访问次数等. 之前我们已经讲过接口限流的工具类ratelimter可以实现令牌桶的限流,很明显sentinel的功能更为全面和完善.来看一下sentinel的简介: https://github.com/spring-cloud-incubator/spring-cloud-alibab

  • 详解三种java实现多线程的方式

    java中实现多线程的方法有两种:继承Thread类和实现runnable接口. 1.继承Thread类,重写父类run()方法 public class thread1 extends Thread { public void run() { for (int i = 0; i < 10000; i++) { System.out.println("我是线程"+this.getId()); } } public static void main(String[] args) {

随机推荐