限流算法（计数器、滑动时间窗口、漏斗、令牌）原理以及代码实现

您所在的位置：网站首页 › 错误代码431表示高速计数器计数值超过上限 › 限流算法（计数器、滑动时间窗口、漏斗、令牌）原理以及代码实现

限流算法（计数器、滑动时间窗口、漏斗、令牌）原理以及代码实现

2024-03-22 08:21| 来源: 网络整理| 查看: 265

文章目录前言 1、计数器（固定时间窗口）算法原理代码实现存在的问题 2、滑动时间窗口算法原理代码实现存在的问题 3、漏桶算法原理代码实现存在的问题 4、令牌桶算法原理代码实现最后

本文会对这4个限流算法进行详细说明，并输出实现限流算法的代码示例。代码是按照自己的理解写的，很简单的实现了功能，还请大佬们多多交流找bug。下面还有投票，帮忙投个票👍

前言

什么是限流？限流限流就是限制流量。在高并发、高流量的场景中我们需要把限流做好，防止突发的流量、恶意的攻击等大量请求的冲击带来不必要的影响，保证业务系统的正常运行。

如何限流？首先我们需要知道限流的基本思路，其次需要知道限流的几种实现方式（这里我们叫限流算法）。

限流的基本思路就是在一个单位时间内流量超过某个阈值后被拒绝或限制。

目前常见的限流算法有计数器（固定时间窗口）算法、滑动时间窗口算法、漏斗算法、令牌算法。

1、计数器（固定时间窗口）算法

计数器（固定时间窗口）算法是最简单的限流算法，实现方式也比较简单。

原理

其原理是：通过维护一个单位时间内的计数值，每当一个请求通过时，就将计数值加1，当计数值超过预先设定的阈值时，就拒绝单位时间内的其他请求。如果单位时间已经结束，则将计数器清零，开启下一轮的计数。

在这里插入图片描述

代码实现 import java.util.Random; public class Counter { //时间窗口 private final int interval = 1000; //时间窗口内的阈值 private final int limit = 5; private long lastTime = System.currentTimeMillis(); private int counter = 0; public boolean tryAcquire() { if (System.currentTimeMillis() < lastTime + interval) { // 在时间窗口内 counter++; } else { //超过时间窗口充值重置counter lastTime = System.currentTimeMillis(); counter = 1; } return counter { while (true) { // 每过200毫秒，就将窗口向前移动一格 if (slot.size() == slotCount) { slot.poll(); } slot.offer(new Node(System.currentTimeMillis())); try { Thread.sleep(interval / slotCount); } catch (InterruptedException e) { e.printStackTrace(); } } }).start(); } public boolean tryAcquire() { Node currWindow = getCurrWindow(); currWindow.setCount(currWindow.getCount() + 1); return getCounter() System.out.print(node.getTime() + ":" + node.getCount() + "|")); if (counter.tryAcquire()) { System.out.println("进行请求"); } else { System.out.println("限流了。。。。"); } Thread.sleep(100 * new Random().nextInt(5)); } } } 存在的问题

那么滑动窗口限流法是完美的吗？细心观察我们应该能马上发现问题，如下图：

在这里插入图片描述

0ms-1000ms、200ms-1200ms的请求在我们设置的阈值内，但是100ms-1100ms的请求一共是220，超过了我们所设置的阈值。

滑动时间窗口限流法其实就是计数器算法的一个变种，依然存在临界值的问题。并且流量的过渡是否平滑依赖于我们设置的窗口格数，格数越多，统计越精确，但是具体要分多少格呢？

3、漏桶算法

上面所介绍的两种算法存在流量不能平滑的过渡，下面介绍下漏桶算法。

原理

漏桶算法以一个常量限制了出口流量速率，因此漏桶算法可以平滑突发的流量。其中漏桶作为流量容器我们可以看做一个FIFO的队列，当入口流量速率大于出口流量速率时，因为流量容器是有限的，超出的流量会被丢弃。

下图比较形象的说明了漏桶算法的原理，其中水滴是入口流量，漏桶是流量容器，匀速流出的水是出口流量。

代码实现

这里我用了 ArrayBlockingQueue 作为漏桶，可以快速的实现功能。

import java.util.Random; import java.util.concurrent.ArrayBlockingQueue; public class Funnel { //出口流量速率 1s 10个 private int rate = 10; //漏桶 private ArrayBlockingQueue bucket; public Funnel(int rate, int capacity) { this.rate = rate; this.bucket = new ArrayBlockingQueue(capacity); int speed = 1000 / this.rate; //固定速率滴水 new Thread(() -> { while (true) { bucket.poll(); try { Thread.sleep(speed); } catch (InterruptedException e) { e.printStackTrace(); } } }).start(); } public boolean tryAcquire() { // 漏桶里面放水 return bucket.offer(this); } public static void main(String[] args) throws InterruptedException { Funnel funnel = new Funnel(10, 100); while (true) { if (funnel.tryAcquire()) { System.out.println("进行请求"); } else { System.out.println("限流了。。。。"); } Thread.sleep(20 * new Random().nextInt(5)); } } } 存在的问题

因为漏桶算法的流出速率是固定的，所以漏桶算法不支持出现突发流出流量。但是在实际情况下，流量往往是突发的。

4、令牌桶算法

令牌桶算法是漏桶算法的改进版，可以支持突发流量。不过与漏桶算法不同的是，令牌桶算法的漏桶中存放的是令牌而不是流量。

原理

令牌桶算法是如何支持突发流量的呢？最开始，令牌桶是空的，我们以恒定速率往令牌桶里加入令牌，令牌桶被装满时，多余的令牌会被丢弃。当请求到来时，会先尝试从令牌桶获取令牌（相当于从令牌桶移除一个令牌），获取成功则请求被放行，获取失败则阻塞或拒绝请求。那么当突发流量来临时，只要令牌桶有足够的令牌，就不会被限流。

代码实现 import java.util.Random; import java.util.concurrent.ArrayBlockingQueue; public class Token { //添加令牌速率 1s 10个 private int rate = 10; //漏桶 private ArrayBlockingQueue bucket; public Token(int rate, int capacity) { this.rate = rate; this.bucket = new ArrayBlockingQueue(capacity); //恒定速率往漏桶里面添加令牌 int speed = 1000 / this.rate; new Thread(() -> { while (true) { bucket.offer(this); try { Thread.sleep(speed); } catch (InterruptedException e) { e.printStackTrace(); } } }).start(); } public boolean tryAcquire() { // 漏桶里面取令牌 return null != bucket.poll(); } public static void main(String[] args) throws InterruptedException { Token funnel = new Token(10, 100); //8s后突发流量 Thread.sleep(8000); while (true) { if (funnel.tryAcquire()) { System.out.println("进行请求"); } else { System.out.println("限流了。。。。"); } Thread.sleep(20 * new Random().nextInt(5)); } } } 最后

或许大家在工作中会用现成的一些限流组件比如：Spring Cloud 的 Hystrix 、Spring Cloud Alibaba 的 Sentinel 或者是 Google 的 Guava 限流器。其实现原理离不开上述所说的4种限流算法，我们开发人员还是要知其然，知其所以然。

【本文地址】

限流算法（计数器、滑动时间窗口、漏斗、令牌）原理以及代码实现

限流算法（计数器、滑动时间窗口、漏斗、令牌）原理以及代码实现

今日新闻

推荐新闻