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

文章目录

  • 前言
  • 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 <= limit;
    }


    public static void main(String[] args) throws InterruptedException {
        Counter counter = new Counter();
        while (true) {
            if (counter.tryAcquire()) {
                System.out.println("进行请求");
            } else {
                System.out.println("限流了。。。。");
            }
            Thread.sleep(100 * new Random().nextInt(5));
        }

    }
}


存在的问题

但是这种实现会有一个问题,举个例子:

假设我们设定1s内允许通过的请求阈值是100,如果在时间窗口的最后几毫秒发送了99个请求,紧接着又在下一个时间窗口开始时发送了99个请求,那么这个用户其实在一秒显然超过了阈值但并不会被限流。其实这就是临界值问题,那么临界值问题要怎么解决呢?

在这里插入图片描述

2、滑动时间窗口算法

原理

滑动时间窗口算法就是为了解决上述固定时间窗口存在的临界值问题而诞生。要解决这种临界值问题,显然只用一个窗口是解决不了问题的。假设我们仍然设定1秒内允许通过的请求是200个,但是在这里我们需要把1秒的时间分成多格,假设分成5格(格数越多,流量过渡越平滑),每格窗口的时间大小是200毫秒,每过200毫秒,就将窗口向前移动一格。为了便于理解,可以看下图

在这里插入图片描述

图中将窗口划为5份,每个小窗口中的数字表示在这个窗口中请求数,所以通过观察上图,可知在当前窗口(200毫秒)只要超过110就会被限流。

代码实现

这里我用了 LinkedList 作为分割窗口,可以快速的实现功能。

import java.util.LinkedList;
import java.util.Random;

public class MovingWindow {

    //时间窗口/ms
    private final int interval = 1000;

    //时间窗口内的阈值
    private final int limit = 5;

    //分割窗口个数
    private int slotCount = 5;

    private LinkedList<Node> slot = new LinkedList<Node>();

    public MovingWindow() {
        new Thread(() -> {
            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() <= limit;
    }

    private int getCounter() {
        return slot.stream().mapToInt(Node::getCount).sum();
    }

    private Node getCurrWindow() {
        if (slot.isEmpty()) {
            while (true) {
                if (slot.isEmpty()) {
                    try {
                        Thread.sleep(10);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                } else break;
            }
        }
        return slot.getLast();
    }


    private class Node {

        private int count;

        private long time;

        public Node(long time) {
            this.time = time;
        }

        public int getCount() {
            return count;
        }

        public void setCount(int count) {
            this.count = count;
        }

        public long getTime() {
            return time;
        }

        public void setTime(long time) {
            this.time = time;
        }
    }


    public static void main(String[] args) throws InterruptedException {
        MovingWindow counter = new MovingWindow();
        while (true) {
            counter.slot.stream().forEach(node -> 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的队列,当入口流量速率大于出口流量速率时,因为流量容器是有限的,超出的流量会被丢弃。

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

image.png

代码实现

这里我用了 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、令牌桶算法

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

原理

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

image.png

代码实现

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种限流算法,我们开发人员还是要知其然,知其所以然。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/11794.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【Redis笔记03】Redis运行环境之Cluster集群模式

这篇文章&#xff0c;主要介绍Redis运行环境之Cluster集群模式。 目录 一、Cluster集群模式 1.1、集群模式原理 &#xff08;1&#xff09;普通集群 &#xff08;2&#xff09;什么是分片&#xff1f;&#xff1f;&#xff1f; &#xff08;3&#xff09;如何分片存储&…

【操作系统复习】第4章 进程同步

进程同步的概念 主要任务 ➢ 使并发执行的诸进程之间能有效地共享资源和相互合作&#xff0c;从而使程序的执行具有可再现性。 进程间的制约关系 ➢ 间接相互制约关系(互斥关系) • 进程互斥使用临界资源 ➢ 直接相互制约关系&#xff08;同步关系&#xff09; •…

在线绘制思维导图

思维导图是一种可视化的思维工具&#xff0c;它可以将放射性思考具体化为可视的图像和图表。 思维导图利用图文并重的技巧&#xff0c;把各级主题的关系用相互隶属与相关的层级图表现出来&#xff0c;把主题关键词与图像、颜色等建立记忆链接。 它运用图像和颜色等多种元素&…

真题详解(Flynn分类)-软件设计(四十六)

真题详解&#xff08;计算机总线&#xff09;-软件设计&#xff08;四十五)https://blog.csdn.net/ke1ying/article/details/130046829 Flynn分类将计算机分为四类。 单指令流单数据流机器&#xff08;SISD&#xff09;&#xff1a;早期的机器&#xff0c;在某个时钟周期&…

某程序员哀叹:月薪四五万,却每天极度焦虑痛苦,已有生理性不适,又不敢裸辞,怎么办?...

高薪能买来快乐吗&#xff1f;来看看这位程序员的哀叹&#xff1a;实在是扛不住了&#xff0c;每天都在极度焦虑和痛苦中度过&#xff0c;早上起来要挣扎着做心理建设去上班&#xff0c;已经产生生理性的头晕恶心食欲不振。有工作本身的原因&#xff0c;更多是自己心态的问题&a…

商务接待广州考斯特商务租车详解!

进入四月份以来&#xff0c;全国各个地区都有很多商务活动举办&#xff0c;广州也不例外&#xff0c;广州很多地区都有商务活动的需求。因此不少主办方都需要商务租车来接待客户&#xff0c;而丰田考斯特是市面上常见的一款高端中巴车&#xff0c;主要是因为考斯特的可靠性、安…

CentOs的环境和配置

centos如果我们想要登录怎么办&#xff1f; 我们可以使用Xshell的远程登录 就像这样 这个就是Xshell远程登录&#xff0c;我们可以ssh root你的主机ip 然后输入密码就可以登录 就像这样 然后输入你的密码 就登录上来了&#xff0c;然后就可以进行你的操作 但是我们还可以直…

Flink 优化 (一) --------- 资源配置调优

目录一、内存设置1. TaskManager 内存模型2. 生产资源配置示例二、合理利用 cpu 资源1. 使用 DefaultResourceCalculator 策略2. 使用 DominantResourceCalculator 策略3 使用 DominantResourceCalculator 策略并指定容器 vcore 数三、并行度设置1. 全局并行度计算2. Source 端…

谷歌云服务器centos9的docker部署chat-web,实现自己的ChatGPT

谷歌云服务器centos9的docker部署chat-web&#xff0c;实现自己的ChatGPT 前提条件&#xff1a;准备一个境外服务器和chatgpt的key。&#xff08;网上教程很多&#xff09; 1.更新yum yum update2.下载docker-ce的repo curl https://download.docker.com/linux/centos/dock…

【iOS开发-响应者链Responder Chain】

文章目录0.0 前言1 响应者链&#xff08;Responder Chain1.1 响应者1.2 响应链事件1.3 响应者对象1.3.1 常见的响应者对象1.3.3 UIResponder1.3 UITouch1.3.1 UITouch的属性1.3.2 UITouch的方法1.4 UIEvent1.4.2 获取touch1.5 完整的响应者链1.5.1寻找响应者的hitTest方法1.5.2…

excel在文本的固定位置插入字符、进行日期和时间的合并

1.excel在文本的固定位置插入字符 如上图&#xff0c;现在想要将其转化为日期格式&#xff08;比如2017/1/1&#xff09;&#xff0c;但是当设置单元格格式为日期时却显示出很多&#xff03;。我们可以通过在20170101中添加两个斜杠“/”来将其转化为2017/1/1。可以用replace函…

【分享】如何移除PDF密码?

相信不少小伙伴在工作的时候&#xff0c;经常会为了保证PDF文档的安全和私密而给文件设置“打开密码”&#xff0c;但如果后续需要频繁使用该文件&#xff0c;每次打开都要查找输入密码&#xff0c;就会使得工作效率大大降低耽误工作时间。那后续不需要设置保护了&#xff0c;要…

如何用ChatGPT写文章?只需要这3步,10倍提升写作效率

随着技术的不断进步和创新&#xff0c;我们的生活方式和工作方式也在不断变化。在日常工作中&#xff0c;越来越多的人使用人工智能和机器学习等技术提高效率减少时间成本。最近ChatGPT火出圈了&#xff0c;很多人通过使用ChatGPT提高了工作效率。那么&#xff0c;在写作领域&a…

【C++ 三】一维数组、二维数组

数组概述、一维数组、二维数组 文章目录数组概述、一维数组、二维数组前言1 数组1.1 概述2 一维数组2.1 一维数组定义方式2.2 一维数组数组名2.3 冒泡排序3 二维数组3.1 二维数组定义方式3.2 二维数组数组名总结前言 本文包含数组概述、一维数组、二维数组。 1 数组 1.1 概述…

Jina AI 创始人肖涵博士:揭秘 Auto-GPT 喧嚣背后的残酷真相

Auto-GPT 究竟是一个开创性的项目&#xff0c;还是一个被过度炒作的 AI 实验&#xff1f;本文为我们揭开了喧嚣背后的真相&#xff0c;并揭示了 Auto-GPT 不适合实际应用的生产局限性。 背景介绍 这两天&#xff0c;Auto-GPT&#xff0c;一款让最强语言模型 GPT-4 能够自主完成…

口令暴力破解--Ftp协议暴力破解与Ssh协议暴力破解

Ftp协议暴力破解 FTP服务检测 FTP服务 FTP是一种文件传输协议&#xff0c; FTP服务默认端口为21。利用FTP服务器可以在本地主机和远程主机间进行文件传输。当FTP没有配置好安全控制&#xff0c;如对登录的源地址及密码尝试次数做限制&#xff0c;那么就会存在暴力破解可能。…

计算机网络

文章目录数据传输过程及接收过程应用层传输层TCP/IP4层网络模型 1.应用层 2.传输层 3.网络层 4.数据链路层 数据传输过程及接收过程 用户A在聊天软件上输入hello world按下发送,发送给B 一: 传输 1.应用层:构建一个应用层的数据报文交给传输层 ** 2.传输层: 根据刚才传过来的…

java虚拟机反射机制

&#xff08;1&#xff09;Java虚拟机反射机制的定义&#xff1f; Java反射机制是在运行状态中&#xff0c;对于任意一个类&#xff0c;都能够知道这个类的所有属性和方法;对于任意一个对象&#xff0c;都能够调用它的任意方法和属性;这种动态获取信息以及动态调用对象方法的功…

MySQL事务隔离级别

一、概念说明 脏读&#xff1a;指的是读到了其他事务未提交的数据&#xff0c;未提交意味着这些数据可能会回滚&#xff0c;也就是可能最终不会存到数据库中&#xff0c;也就是不存在的数据。读到了并不一定最终存在的数据&#xff0c;这就是脏读。 可重复读&#xff1a;在一个…

【GPT4】微软 GPT-4 测试报告(3)GPT4 的编程能力

欢迎关注【youcans的GPT学习笔记】原创作品&#xff0c;火热更新中 微软 GPT-4 测试报告&#xff08;1&#xff09;总体介绍 微软 GPT-4 测试报告&#xff08;2&#xff09;多模态与跨学科能力 微软 GPT-4 测试报告&#xff08;3&#xff09;GPT4 的编程能力 【GPT4】微软 GPT-…
最新文章