常用的限流方案思路和实现

限流方案

1、计数器(固定窗口)

1.1、简介

计数器固定窗口算法是最基础也是最简单的一种限流算法。原理就是对一段固定时间窗口内的请求进行计数,如果请求数超过了阈值,则舍弃该请求;如果没有达到设定的阈值,则接受该请求,且计数加1。当时间窗口结束时,重置计数器为0。
在这里插入图片描述

1.2、代码实现

import java.util.concurrent.atomic.AtomicInteger;public class CountLimiter {/*** 窗口大小,单位为毫秒*/private int window;/*** 窗口内允许的请求次数*/private int limit;/*** 当前窗口内的请求次数*/private AtomicInteger count;/*** 窗口是否正在运行*/private volatile boolean isRunning = true;public CountLimiter() {this(60, 10);}/*** 构造函数* @param window 窗口大小,单位为毫秒* @param limit 窗口内允许的请求次数*/public CountLimiter(int window, int limit) {this.window = window;this.limit = limit;count = new AtomicInteger(0);}/*** 尝试获取令牌* @return 获取成功返回true,失败返回false*/public boolean tryAcquire() {int current = count.incrementAndGet();if (current > limit) {return false;} else {return true;}}/*** 启动窗口线程*/public void start() {// 启动一个线程,每过window毫秒将count置为0new Thread(new Runnable() {@Overridepublic void run() {while (isRunning) {try {Thread.sleep(window);count.set(0);} catch (InterruptedException e) {e.printStackTrace();}}}}).start();}/*** 关闭窗口线程*/public void stop() {isRunning = false;System.out.println("限流关闭,关闭时间" + System.currentTimeMillis());}public static void main(String[] args) {CountLimiter limiter = new CountLimiter(100, 3);limiter.start();int count = 0;for (int i = 0; i < 10; ++i) {if (limiter.tryAcquire()) {count++;System.out.println("请求通过, 当前时间" + System.currentTimeMillis());}}limiter.stop();System.out.println("请求通过:" + count);}
}

运行结果:

请求通过, 当前时间1709273340687
请求通过, 当前时间1709273340693
请求通过, 当前时间1709273340693
限流关闭,关闭时间1709273340693
请求通过:3

1.3、特点分析

  • 实现简单,容易理解
  • 窗口界限处可能会出现两倍于阈值的流量
  • 窗口时间内可能会出现服务不可用,流量不够平滑

2、计数器(滑动窗口)

2.1、简介

计数器滑动窗口算法是计数器固定窗口算法的改进,解决了固定窗口切换时可能会产生两倍于阈值流量请求的缺点。
滑动窗口算法在固定窗口的基础上,将一个计时窗口分成了若干个小窗口,然后每个小窗口维护一个独立的计数器。当请求的时间大于当前窗口的最大时间时,则将计时窗口向前平移一个小窗口。平移时,将第一个小窗口的数据丢弃,然后将第二个小窗口设置为第一个小窗口,同时在最后面新增一个小窗口,将新的请求放在新增的小窗口中。同时要保证整个窗口中所有小窗口的请求数目之和不能超过设定的阈值。
在这里插入图片描述

滑动窗口算法其实就是对请求数进行了更细粒度的限流,窗口划分得越多,则限流越精准。

2.2、代码实现

public class CountSlideLimiter {// 窗口大小private int window;// 窗口内允许的请求次数private int limit;// 滑动窗口的个数private int splitNum;// 计数器private int[] counter;// 计数器索引private int index;// 开始时间private long startTime;public CountSlideLimiter() {this(1000, 20, 10);}public CountSlideLimiter(int window, int limit, int splitNum) {this.window = window;this.limit = limit;this.splitNum = splitNum;counter = new int[splitNum];index = 0;startTime = System.currentTimeMillis();}/*** 尝试获取令牌* @return 获取成功返回true,否则返回false*/public synchronized boolean tryAcquire() {long curTime = System.currentTimeMillis();long windowNum = Math.max(curTime - window - startTime, 0) / (window / splitNum);slide(windowNum);int count = 0;for (int i = 0; i < splitNum; ++i) {count += counter[i];}if (count >= limit) {return false;} else {counter[index]++;return true;}}/*** 滑动窗口* @param windowNum 滑动窗口距离*/private synchronized void slide(long windowNum) {if (windowNum == 0) {return;}long slideNum = Math.min(windowNum, splitNum);for (int i = 0; i < slideNum; ++i) {index = (index + 1) % splitNum;counter[index] = 0;}startTime = startTime + windowNum * (window / splitNum);}public static void main(String[] args) throws InterruptedException {int limit = 3;CountSlideLimiter limiter = new CountSlideLimiter(100, limit, 5);int count = 0;for (int i = 0; i < 10; ++i) {count = 0;for (int j = 0; j < 50; ++j) {if (limiter.tryAcquire()) {count++;System.out.println("请求通过, 当前时间" + System.currentTimeMillis());}}Thread.sleep(10);for (int j = 0; j < 50; ++j) {if (limiter.tryAcquire()) {count++;System.out.println("请求通过, 当前时间" + System.currentTimeMillis());}}if (count > limit) {System.out.println("限流失败,当前请求数:" + count);}}}
}

运行结果:

请求通过, 当前时间1709278379478
请求通过, 当前时间1709278379484
请求通过, 当前时间1709278379484

2.2、特点分析:

  • 避免了计数器固定窗口算法在固定窗口切换时可能产生两倍于阈值流量的请求问题;
  • 和漏斗算法相比,新来的请求也能够被处理到,避免了漏斗算法的饥饿问题。

3、漏桶算法

3.1、简介

漏桶算法中的漏桶是一个形象的比喻,这里可以用生产者消费者模式进行说明,请求是一个生产者,每一个请求都如一滴水,请求到来后放到一个队列(漏桶)中,而桶底有一个孔,不断地漏出水滴,就如消费者不断地在消费队列中的内容,消费的速率(漏出的速度)等于限流阈值。即假如 QPS 为 2,则每 1s / 2= 500ms 消费一次。漏桶的桶有大小,就如队列的容量,当请求堆积超过指定容量时,会触发拒绝策略。
在这里插入图片描述

3.2、代码实现

import java.util.LinkedList;
import java.util.List;public class LeakyBucketLimiter {// 容量private int capacity;// 速率private int rate;// 剩余容量private int left;// 请求队列private List<Request> requests;// 是否运行private volatile boolean isRunning = true;public LeakyBucketLimiter(int capacity, int rate) {this.capacity = capacity;this.rate = rate;this.left = capacity;this.requests = new LinkedList<>();}public void handelRequest(Request request) {request.setHandleTime(System.currentTimeMillis());left++;if (left > capacity) {left = capacity;}System.out.println(request.toString());}public synchronized boolean tryAcquire(Request request) {if (left <= 0) {return false;} else {left--;requests.add(request);return true;}}public void start() {new Thread(new Runnable() {@Overridepublic void run() {while(isRunning) {if(!requests.isEmpty()) {Request request = requests.remove(0);handelRequest(request);}try {Thread.sleep(1000 / rate);} catch (Exception e) {e.printStackTrace();}}}}).start();;}public void stop() {isRunning = false;}public static void main(String[] args) throws InterruptedException {LeakyBucketLimiter limiter = new LeakyBucketLimiter(3, 5);limiter.start();int count = 0;for(int i = 0; i < 10; i++) {Thread.sleep(50);Request request = new Request(i, System.currentTimeMillis(), 0L);if(limiter.tryAcquire(request)) {count++;System.out.println("请求被接受");} else {System.out.println("请求被拒绝");}}System.out.println("请求通过数:" + count);Thread.sleep(10000);limiter.stop();}public static class Request {private int code;private long lanchTime;private long handleTime;public Request() {}public Request(int code, long lanchTime, long handleTime) {this.code = code;this.lanchTime = lanchTime;this.handleTime = handleTime;}public int getCode() {return code;}public void setCode(int code) {this.code = code;}public long getLanchTime() {return lanchTime;}public void setLanchTime(long lanchTime) {this.lanchTime = lanchTime;}public long getHandleTime() {return handleTime;}public void setHandleTime(long handleTime) {this.handleTime = handleTime;}@Overridepublic String toString() {return "Request{" +"code=" + code +", lanchTime=" + lanchTime +", handleTime=" + handleTime +'}';}}
}

运行结果:

请求被接受
请求被接受
请求被接受
请求被接受
Request{code=0, lanchTime=1709280004490, handleTime=1709280004640}
请求被拒绝
请求被拒绝
请求被拒绝
Request{code=1, lanchTime=1709280004546, handleTime=1709280004861}
请求被接受
请求被拒绝
请求被拒绝
请求通过数:5
Request{code=2, lanchTime=1709280004596, handleTime=1709280005066}
Request{code=3, lanchTime=1709280004651, handleTime=1709280005267}
Request{code=7, lanchTime=1709280004867, handleTime=1709280005471}

3.3、特点分析:

  • 漏桶的漏出速率是固定的,对下游系统起到了保护的作用
  • 不能解决流量突发情况。

4、令牌桶

4.1、简介

令牌桶算法同样是实现限流是一种常见的思路,最为常用的 Google 的 Java 开发工具包 Guava 中的限流工具类 RateLimiter 就是令牌桶的一个实现。令牌桶的实现思路类似于生产者和消费之间的关系。
系统服务作为生产者,按照指定频率向桶(容器)中添加令牌,如 QPS 为 2,每 500ms 向桶中添加一个令牌,如果桶中令牌数量达到阈值,则不再添加。
请求执行作为消费者,每个请求都需要去桶中拿取一个令牌,取到令牌则继续执行;如果桶中无令牌可取,就触发拒绝策略,可以是超时等待,也可以是直接拒绝本次请求,由此达到限流目的。
在这里插入图片描述

4.2、代码实现:

public class TokenBucketLimiter {private int capacity;private int rate;private int tokens;private volatile boolean isRunning = true;private static final int DEFAULT_CAPACITY = 10;private static final int DEFAULT_RATE = 5;public TokenBucketLimiter() {this(DEFAULT_CAPACITY, DEFAULT_RATE);}public TokenBucketLimiter(int capacity, int rate) {this.capacity = capacity;this.rate = rate;this.tokens = capacity;}public synchronized boolean tryAcquire(Request request) {if (tokens > 0) {tokens--;handelRequest(request);return true;} else {return false;}}public void start() {new Thread(new Runnable() {@Overridepublic void run() {while (isRunning) {synchronized(this) {tokens++;if (tokens > capacity) {tokens = capacity;}}try {Thread.sleep(1000 / rate);} catch (InterruptedException e) {e.printStackTrace();}}}}).start();;}public void stop() {isRunning = false;}public void handelRequest(Request request) {request.setHandleTime(System.currentTimeMillis());System.out.println(request.toString());}public static void main(String[] args) throws InterruptedException {TokenBucketLimiter limiter = new TokenBucketLimiter(3, 5);limiter.start();int count = 0;for(int i = 0; i < 10; i++) {Thread.sleep(50);Request request = new Request(i, System.currentTimeMillis(), 0L);if(limiter.tryAcquire(request)) {count++;System.out.println("请求被接受,当前时间:" + System.currentTimeMillis());} else {System.out.println("请求被拒绝,当前时间:" + System.currentTimeMillis());}}System.out.println("请求通过数:" + count);limiter.stop();}public static class Request {private int code;private long lanchTime;private long handleTime;public Request() {}public Request(int code, long lanchTime, long handleTime) {this.code = code;this.lanchTime = lanchTime;this.handleTime = handleTime;}public int getCode() {return code;}public void setCode(int code) {this.code = code;}public long getLanchTime() {return lanchTime;}public void setLanchTime(long lanchTime) {this.lanchTime = lanchTime;}public long getHandleTime() {return handleTime;}public void setHandleTime(long handleTime) {this.handleTime = handleTime;}@Overridepublic String toString() {return "Request{" +"code=" + code +", lanchTime=" + lanchTime +", handleTime=" + handleTime +'}';}}
}

运行结果:

Request{code=0, lanchTime=1709279960998, handleTime=1709279960998}
请求被接受,当前时间:1709279961008
Request{code=1, lanchTime=1709279961061, handleTime=1709279961061}
请求被接受,当前时间:1709279961061
Request{code=2, lanchTime=1709279961111, handleTime=1709279961111}
请求被接受,当前时间:1709279961111
Request{code=3, lanchTime=1709279961162, handleTime=1709279961162}
请求被接受,当前时间:1709279961162
请求被拒绝,当前时间:1709279961214
请求被拒绝,当前时间:1709279961268
请求被拒绝,当前时间:1709279961323
Request{code=7, lanchTime=1709279961378, handleTime=1709279961378}
请求被接受,当前时间:1709279961378
请求被拒绝,当前时间:1709279961433
请求被拒绝,当前时间:1709279961485
请求通过数:5

4.3、特点分析:

  • 令牌桶算法是对漏桶算法的一种改进,除了能够在限制调用的平均速率的同时还允许一定程度的流量突发

参考

分布式限流
https://blog.51cto.com/u_15905482/6237162
参考:
https://www.wdbyte.com/java/rate-limiter/
https://juejin.cn/post/6870396751178629127

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

【单点登录SSO,Auth2,jwt-过程分析】

目录 单点登录简介 SSO&CAS是什么 单点登录适合什么场景 单点登录的三种实现方式 CAS的几个重要知识点 CAS的实现过程 单点登录简介 单点登录(SingleSignOn&#xff0c;SSO)&#xff0c;就是通过用户的一次性鉴别登录。当用户在身份认证服务器上登录一次以后&#xff0c;即…

C++ //练习 11.12 编写程序,读入string和int的序列,将每个string和int存入一个pair中,pair保存在一个vector中。

C Primer&#xff08;第5版&#xff09; 练习 11.12 练习 11.12 编写程序&#xff0c;读入string和int的序列&#xff0c;将每个string和int存入一个pair中&#xff0c;pair保存在一个vector中。 环境&#xff1a;Linux Ubuntu&#xff08;云服务器&#xff09; 工具&#x…

【JavaWeb】Day32.MySQL概述

什么是数据库 数据库&#xff1a;英文为 DataBase&#xff0c;简称DB&#xff0c;它是存储和管理数据的仓库。 像我们日常访问的电商网站京东&#xff0c;企业内部的管理系统OA、ERP、CRM这类的系统&#xff0c;以及大家每天都会刷的头条、抖音类的app&#xff0c;那这些大家所…

苍穹外卖Day04套餐管理部分总结

写给像我一样完完全全的小白的。本人代码水平一塌糊涂&#xff0c;前几天就是机械地跟着视频敲代码。对于Day04的作业本来感觉代码抓瞎一点不会写&#xff0c;尽力去理解业务逻辑后发现好像也没那么难&#xff0c;整体代码可以仿照Day03新增菜品来进行实现&#xff01; 一、功…

面试复盘1 - 测试相关(实习)

写在前&#xff1a;hello&#xff0c;大家早中晚上好~这里是西西&#xff0c;最近有在准备测试相关的面试&#xff0c;特此开设了新的篇章&#xff0c;针对于面试中的问题来做一下复盘&#xff0c;会把我自己遇到的问题进行整理&#xff0c;除此之外还会进行对一些常见面试题的…

6.S081的Lab学习——Lab2: system calls

文章目录 前言一、System call tracing&#xff08;moderate&#xff09;解析&#xff1a; 二、Sysinfo&#xff08;moderate&#xff09;解析&#xff1a; 前言 一个本硕双非的小菜鸡&#xff0c;备战24年秋招。打算尝试6.S081&#xff0c;将它的Lab逐一实现&#xff0c;并记…

人工智能上手 Pytorch

人工智能上手 Pytorch 1、人工智能框架历史走向 2015年&#xff0c; caffe&#xff0c;优势配置简单&#xff0c;缺点安装麻烦&#xff0c;且不更新维护 2016年&#xff0c;tensorflow 1.x&#xff0c;定义太严格&#xff0c;很复杂。开发成本高。简单的任务&#xff0c;也很…

今客CRM客户管理系统 v17.3

简介&#xff1a; 今客CRM客户管理系统主要是为了帮助企业解决在日常工作中遇到的客户管理等难题而开发&#xff0c;通过今客CRM客户管理系统可以对企业事务中的不同功能进行操作&#xff0c;用户通过自定义字段类型可以达到适合不同企业的需求。在今客客户关系管理系统中管理…

来个自定义的电子木鱼吧

<!DOCTYPE html> <html><head><meta charset"utf-8"><meta name"viewport" content"widthdevice-width, initial-scale1"><title>自定义木鱼</title> </head> <body style"background-…

Rredis缓存常见面试题

文章目录 1.什么是缓存穿透&#xff0c;怎么解决2.什么是缓存击穿&#xff0c;怎么解决3.什么是缓存雪崩&#xff0c;怎么解决4.双写一致性问题5.redisson添加的排他锁是如何保证读写、读读互斥的6.为什么不使用延迟双删7.redis做为缓存&#xff0c;数据的持久化是怎么做的8.re…

MVCC详细总结

简介 MVCC&#xff08;Multi-Version Concurrency Control&#xff09;是一种多版本并发控制机制&#xff0c;主要用于数据库管理系统中&#xff0c;实现对数据库的并发访问。在编程语言中&#xff0c;MVCC可以实现事务内存。 MVCC的特点是读不加锁&#xff0c;读写不冲突。MVC…

LeetCode 第二题:冒泡排序详解 【2/1000】含imagemagick动态效果图

&#x1f464;作者介绍&#xff1a;10年大厂数据\经营分析经验&#xff0c;现任大厂数据部门负责人。 会一些的技术&#xff1a;数据分析、算法、SQL、大数据相关、python 作者专栏每日更新&#xff1a; LeetCode解锁1000题: 打怪升级之旅 LeetCode解锁1000题: 打怪升级之旅htt…

【重学C语言】三、C语言最简单的程序

【重学C语言】三、C语言最简单的程序 最简单的程序头文件使用尖括号 < >使用双引号 ""区别与注意事项示例 主函数认识三个错误 常量和变量常量ASCII 码表转义字符 关键字数据类型关键字存储类关键字修饰符关键字控制流程关键字函数相关关键字其他关键字 变量变…

公众号爆文策略与实践:揭秘千万阅读量的秘密

1. 引言 介绍公众号爆文的重要性&#xff0c;以及分享个人通过每天投入半小时赚到30倍门票的经验。强调跟上大佬步伐&#xff0c;提升认知的重要性。 2. 爆文的底层逻辑 2.1 推荐的底层逻辑 内容分发机制的变化&#xff0c;从仅限于直接关注到通过搜索、浏览推荐等多种方式…

【Qt】Ubuntu20.04.6+Qt5.15.2+QtCreator10.0.1无法输入中文

1、前提条件 1)已经安装了fcitx sudo apt install fcitx sudo apt install fcitx-pinyin sudo apt install fcitx-bin fcitx-table-all sudo apt install fcitx-qt52)系统已经配置fcitx 3)将系统下 /usr/lib/x86_64-linux-gnu/qt5/plugins/platforminputcontexts/libfcitx…

基于YOLOv8车牌识别算法支持12种中文车牌类型(源码+图片+说明文档)

yolov8车牌识别算法&#xff0c;支持12种中文车牌类型 支持如下&#xff1a; 1.单行蓝牌 2.单行黄牌 3.新能源车牌 4.白色警用车牌 5.教练车牌 6.武警车牌 7.双层黄牌 8.双层白牌 9.使馆车牌 10.港澳粤Z牌 11.双层绿牌 12.民航车牌 图片测试demo: 直接运行detect_plate.py 或者…

文件操作详解(二)

目录 一.文件的顺序读写1.顺序读写函数&#xff08;适合于所有的流&#xff09;1.1 fgetc(读字符)1.2 fputc(写字符)1.3 fgets(读字符串)1.4 fput(写字符串)1.5 fscanf(格式化地读)1.6 fprintf(格式化地写) 2.顺序读写函数&#xff08;只适用于文件流&#xff09;2.1 fread(二进…

智慧能源管理解决方案应用与作用

智慧能源管理解决方案作为新一代的能源管理体系&#xff0c;依托于高度发展的信息技术和物联网技术&#xff0c;为企业和家庭提供了全面、智能的能源使用和节能减排方案。其目的在于通过智能化手段优化能源配置&#xff0c;提高能源使用效率&#xff0c;促进环保和可持续发展。…

QuartusII联合Modelsim仿真中最好不要将tb文件设置为顶层,以避免compile错误

QuartusII联合Modelsim仿真中最好不要将tb文件设置为顶层&#xff0c;以避免compiler错误 1&#xff0c;QuartusII下的rtl文件、sim文件如下显示。2&#xff0c;将rtl文件中任一个置于顶层&#xff0c;都不会影响sim仿真输出。3&#xff0c;将tb.v文件置于顶层&#xff0c;comp…

【芯片验证】通关寄存器与ral_model —— 寄存器生成流程中加入backdoor后门配置

前言 【芯片验证】通关寄存器与ral_model —— backdoor后门访问实操测试-CSDN博客 上一篇文章中,我们通过在环境中配置后门路径的方式来实现了寄存器的后门访问,但是在实际应用中,无论寄存器RTL文件、例化还是寄存器模型大概率都是工具生成的,比如在本专栏中实现的gen_r…