Java中常见的限流算法有哪些

这篇“Java中常见的限流算法有哪些”文章的知识点大部分人都不太理解，所以小编给大家总结了以下内容，内容详细，步骤清晰，具有一定的借鉴价值，希望大家阅读完这篇文章能有所收获，下面我们一起来看看这篇“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;        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;    }        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时，将请求入队，然后再以固定频率从队列中取出请求进行处理。示例代码如下：

@Testpublic 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令牌桶

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

令牌桶具有以下特点：

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

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

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

令牌桶算法中值得关注的参数有两个，即限流速率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;    }        @Override    public synchronized boolean tryAcquire() {                  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;        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;    }        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代理服务就提供了限流模块，同样能够实现高性能，精准的限流，其底层是漏桶算法。

以上就是关于“Java中常见的限流算法有哪些”这篇文章的内容，相信大家都有了一定的了解，希望小编分享的内容对大家有帮助，若想了解更多相关的知识内容，请关注编程网精选频道。