精确掌控并发:漏桶算法在分布式环境下并发流量控制的设计与实现

news/2024/2/25 20:14:38/文章来源:https://blog.csdn.net/yinmo_sc/article/details/135637900

这是《百图解码支付系统设计与实现》专栏系列文章中的第(16)篇,也是流量控制系列的第(3)篇。点击上方关注,深入了解支付系统的方方面面。

本篇重点讲清楚漏桶原理,在支付系统的应用场景,以及使用reids实现的核心代码。

1. 前言

在流量控制系列文章中的前两篇,分别介绍了固定时间窗口算法和滑动时间窗口算法在支付渠道限流的应用以及使用redis实现的核心代码。

这两个算法有一个共同的问题:那就是超过阀值的数据会直接拒绝掉。如果超过阀值也不想拒绝请求,后面仍然发出去,怎么办?这就是本篇要说的漏桶及下篇要讲的令牌桶解决的问题。

2. 漏桶原理

漏桶算法通过模拟水桶漏水的过程来控制数据的传输速率。它允许短时间的突发数据流,随后以恒定的速率排空积聚的数据。这种机制特别适合于需要平滑处理瞬时高流量冲击,但后端需要恒定速率处理的场景。比如批量接收上游商户的退款,然后根据渠道的要求以极低的TPS慢慢退出去到渠道。

最简单的理解,漏桶 = 队列 + 固定窗口算法。其中队列用于先保存数据。固定窗口算法用于获取可用计数,获取到就从队列获取一个请求进行业务处理。

工作原理:

  1. 桶容量:漏桶有一个固定的容量,代表在任何时刻系统能够容纳的最大请求量。比如上面图中的队列。
  2. 数据流入:数据来了后就保存到桶(队列)中,如果桶已满,则溢出的数据会被丢弃。
  3. 恒定速率流出:数据以固定的速率从桶中“漏出”,即被处理。这个速率是预先设定的,与请求量无关。
  4. 计数器最简单的做法,就是把固定时间窗口的代码用起来。
  5. 保存到数据库,是为了持久化,以及队列出现问题时,可以重新恢复。

3. 在支付系统下的应用场景

中国的IT基础设施领先于全球各个国家,各大银行和第三方钱包也被各电商双十一等大促场景狂虐之后进化到支持极高的TPS,但是在跨境场景下,比如东南亚或南美的国家,他们的银行IT基础设施差,系统老旧,无法支持高并发流量。甚至碰到过一些银行要求退款只能有1TPS。

在分布式场景下,要做到1TPS的高精度限流,只能依赖漏桶来做。

4. Redis实现漏桶的核心代码

漏桶算法通常通过队列 + 固定时间窗口计数法来实现。队列存储待处理的请求,而一个线程以固定速率从队列中取出并处理这些请求。

为什么又是Redis?因为前面已经实现过Redis版本的固定时间窗口算法,再加一个队列就可以搞定。当然大家也可以选择其它的方案实现,这只是一个抛砖引玉。

下面是单机版本的伪代码:

public class LeakyBucket {private final int capacity;private final long leakIntervalInMillis;private final LinkedBlockingQueue<Data> bucket;public LeakyBucket(int capacity, long leakRateInMillis) {this.capacity = capacity;this.leakIntervalInMillis = leakRateInMillis;this.bucket = new LinkedBlockingQueue<>(capacity);}// 尝试添加数据到桶中public boolean addToBucket(Data data) {return bucket.offer(data);}// 启动桶的漏水过程public void startLeaking() {new Thread(() -> {while (true) {try {Data data = bucket.poll(leakIntervalInMillis, TimeUnit.MILLISECONDS);if (data != null) {process(data);}} catch (InterruptedException e) {log.debug("Leaking process interrupted");continue;}}}).start();}// 处理桶中的数据private void process(Data data) {// 业务处理... ...}
}

上面单机的代码实用性不高,因为在分布式环境下,并发请求量是根据部署机器累计起来的,1台机器限流1TPS,20台机器就到了20TPS。

优化为分布式:

class LeakyBucketHolding {private final LinkedBlockingQueue<Data> bucket;private int limit;private String bizType;public LeakyBucketHolding(String bizType, int capacity, int limit) {this.bizType = bizType;this.bucket = new LinkedBlockingQueue<>(capacity);this.limit = limit;}// 其它代码略
}class LeakyBucket {@Autowiredprivate RedisLimitUtil redisLimitUtil;private Map<String, LeakyBucketHolding> leakyBucketHoldingMap = new HashMap();// 添加数据到桶中public boolean addData(Data data) {String key = buildKey(data);LeakyBucketHolding holding = leakyBucketHoldingMap.get(key);if (null == holding) {holding = buildHolding(data);leakyBucketHoldingMap.put(key, holding);}return holding.getLinkedBlockingQueue().offer(data);}public Data getData() {for(LeakyBucketHolding holding : leakyBucketHoldingMap.values()) {if(holding.getBucket().size() == 0) {return null;}/* RedisLimitUtil的实现参考* "精确掌控并发:固定时间窗口算法在分布式环境下并发流量控制的设计与实现"中的示例代码*/boolean limited = RedisLimitUtil.isLimited(holding.getBizType(), holding.getLimit());if (limited) {return null;}try {return holding.getBucket().poll(10, TimeUnit.MILLISECONDS);} catch (InterruptedException e) {log.log("Leaking process interrupted");}return null;}}
}

上面的代码只是写一个示例,也没有做方法的抽取,真实的代码会比这个写得更优雅一点,大家将就看一下,理解思路就行。

代码使用的是内存列队,也就是请求过来后,先保存到DB,然后发到内存队列。在重启服务器时,内存列队的数据会丢失,这种情况下,依赖定时任务从DB中恢复任务到内存列队。

还有一种做法,就不使用内存队列,而是使用redis来实现队列。代码如下:

public class LeakyBucket {// 其它代码略... ...// 添加数据到队列中public void addData(Data data) {return redisTemplate.rpush(data.getBizType(), data);}// 添加数据到队列中public Data getData(String bizType) {return redisTemplate.lpop(bizType);}// 其它代码略... ...
}

退款流量控制实例:RefundServiceImpl

/*** 支付服务示例*/
public class RefundServiceImpl implements RefudnService {@Autowireadprivate LeakyBucket leakyBucket;@Overridepublic RefundOrder refund(RefundRequest request) {// 前置业务处理... ...Data data = buildData(request);leakyBucket.addData(data);// 其它业务处理... ...}@PostConstructpublic void init() {new Thread(() -> {while (true) {Data data = leakyBucket.getData();if (null != data) {process(data);} else {sleep(10);}}}).start();}
}

在代码中可以看到,退款请求来后,只需要往桶里扔就完事。然后等另外的线程按固定速度发出去。

代码中还存在的问题:

  1. 上述代码只是示例,真实的代码还有很多异常处理,比如队列数据丢失,需要重新处理。
  2. 暂时只能用于退款,因为退款的时效要求不高。另外,单机只需要开一个线程就行,因为服务器是分布式部署,多个服务器合并起来仍然是多个线程在并发处理。对退款是足够的。

5. 为什么不使用消息中间件来做队列

为什么不直接使用RabbitMQ或Kafaka等消息中间件来做队列?主要是因为有些公司使用自码的消息中间件,可能只有推模型而没有拉的模式。

如果只有推的模式,就会出现推下来后发现限流,又抛回来,来回做无用功。

如果消息中间件有拉的模式,同时配合redis的固定窗口实现,也是完全没有问题的。

6. 为什么不直接使用消息中间件来做流控

消息中间件是另外的选型方案,会在后面的文章中介绍。

7. 结束语

今天主要介绍了漏桶原理、在支付系统中的使用场景,以及基于redis实现的核心代码。

下一篇将介绍令牌桶在分布式场景下流量控制的应用和核心代码实现。

8. 精选

专栏地址百图解码支付系统设计与实现
《百图解码支付系统设计与实现》专栏介绍
《百图解码支付系统设计与实现》专栏大纲及文章链接汇总(进度更新于2023.1.15)
领域相关(部分)
支付行业黑话:支付系统必知术语一网打尽
跟着图走,学支付:在线支付系统设计的图解教程
图解收单平台:打造商户收款的高效之道
图解结算平台:准确高效给商户结款
图解收银台:支付系统承上启下的关键应用
图解支付引擎:资产流动的枢纽
图解渠道网关:不只是对接渠道的接口(一)

技术专题(部分)
交易流水号的艺术:掌握支付系统的业务ID生成指南
揭密支付安全:为什么你的交易无法被篡改
金融密语:揭秘支付系统的加解密艺术
支付系统日志设计完全指南:构建高效监控和问题排查体系的关键基石
避免重复扣款:分布式支付系统的幂等性原理与实践
支付系统的心脏:简洁而精妙的状态机设计与核心代码实现
精确掌控并发:固定时间窗口算法在分布式环境下并发流量控制的设计与实现
精确掌控并发:滑动时间窗口算法在分布式环境下并发流量控制的设计与实现

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

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

相关文章

解决打开 json 文件中文乱码的问题

如下图&#xff0c;pycharm 打开是下面的样子 右下角的编码尝试了好久&#xff0c;依然打不开 用代码打开就成功了 import jsonwith open(./Mydata/garbage_classification.json,encodingutf8,moder) as f:data json.load(f) print(data)控制台结果&#xff1a;

2024年“华数杯”国际大学生数学建模竞赛B题思路

本题难点在于数据获取和定性定量分析&#xff0c;代码部分没有太大价值、就不更新了 •中国的电力供应和许多因素相互作用。请研究它们之间的关系&#xff0c;并预测2024年至2060年中国电力供应的发展趋势。 首先得获取数据&#xff0c;中国的宏观数据相对容易&#xff08;包括…

两数之和(Hash表)[简单]

优质博文&#xff1a;IT-BLOG-CN 一、题目 给定一个整数数组nums和一个整数目标值target&#xff0c;请你在该数组中找出"和"为目标值target的那两个整数&#xff0c;并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是&#xff0c;数组中同一个元…

C#MQTT编程07--MQTT服务器和客户端(wpf版)

1、前言 上篇完成了winform版的mqtt服务器和客户端&#xff0c;实现了订阅和发布&#xff0c;效果666&#xff0c;长这样 这节要做的wpf版&#xff0c;长这样&#xff0c;效果也是帅BBBB帅&#xff0c;wpf技术是cs程序软件的福音。 wpf的基础知识和案例项目可以看我的另一个专…

单向不带头链表的使用

单向不带头链表的使用 链表的创建&#xff1a; typedef struct LNode {SLDataType data;struct LNode* next; }LNode,*LinkList; 按位查找 LNode* GetElem(LinkList L, int i) {int j 1;LNode* p L->next;if (i < 0)return NULL;if (i 0)return L;while (p &&…

一天一个设计模式---组合模式

基本概念 组合模式是一种结构型设计模式&#xff0c;它允许客户端统一对待单个对象和对象的组合。组合模式通过将对象组织成树形结构&#xff0c;使得客户端可以一致地使用单个对象和组合对象。 主要角色&#xff1a; Component&#xff08;组件&#xff09;&#xff1a; 定…

Git Merge、Rebase 和 Squash 之间的区别

文章目录 Git MergeGit RebaseGit Squash结论 作为一名开发人员&#xff0c;您可能使用过 Git 和 GitHub&#xff0c;掌握了版本控制的要点。通常通过拉取请求将分支的更改集成到主分支中是一项常见任务。许多人的默认选择是“合并”功能。 然而&#xff0c;版本控制领域提供了…

【软件测试】学习笔记-设计一个“好的”测试用例

本篇文章重点探讨如何才能设计出一个“好的”测试用例。 什么才算是“好的”测试用例&#xff1f; 什么才是“好的”测试用例&#xff0c;这个“好”又应该体现在哪些方面。这是一个看似简单实则难以回答的问题&#xff0c;即使深入思考后&#xff0c;也很难有非常标准的答案…

C++力扣题目501--二叉搜索树中的众数

给你一个含重复值的二叉搜索树&#xff08;BST&#xff09;的根节点 root &#xff0c;找出并返回 BST 中的所有 众数&#xff08;即&#xff0c;出现频率最高的元素&#xff09;。 如果树中有不止一个众数&#xff0c;可以按 任意顺序 返回。 假定 BST 满足如下定义&#xf…

【Redis】非关系型数据库之Redis的增删改查

目录 一、Redis的数据类型分类 二、Redis的字符串类型string 三、Redis的列表list 四、Redis的哈希hash 五、Redis的无序集合set 六、Redis的有序集合zset 七、Redis的通用命令 一、Redis的数据类型分类 通常Redis的数据类型有五大基础类型 String&#xff08;字符串&am…

多机TCP通讯之hello world(C++)

文章目录 TCP是什么准备工作CMakeLists.txt服务端代码客户端代码参考 TCP是什么 TCP&#xff08;传输控制协议&#xff09;是一种在计算机网络中广泛使用的协议&#xff0c;它提供了可靠的、面向连接的数据传输服务。TCP 是 OSI 模型中的传输层协议&#xff0c;它确保了数据的…

idea 安装免费Ai工具 codeium

目录 概述 ide安装 使用 chat问答 自动写代码 除此外小功能 概述 这已经是我目前用的最好免费的Ai工具了&#xff0c;当然你要是有钱最好还是用点花钱的&#xff0c;比如copilot&#xff0c;他可以在idea全家桶包括vs&#xff0c;还有c/c的vs上运行&#xff0c;还贼强&am…

安全狗方案入选工信部《2023年工业和信息化领域数据安全典型案例名单》

近日&#xff0c;工业和信息化部网络安全管理局公布了2023年工业和信息化领域数据安全典型案例名单。 安全狗与厦门卫星定位应用股份有限公司、中移 (上海) 信息通信科技有限公司联合申报的智慧交通云数据安全与隐私保障典型案例也成功入选。 厦门服云信息科技有限公司&#…

132基于matlab的采集信号模极大值以及李氏指数计算

基于matlab的采集信号模极大值以及李氏指数计算&#xff0c; 1)计算信号的小波变换。 2)求出模极大曲线。 3)计算其中两个奇异点的Lipschitz指数&#xff0c;程序已调通&#xff0c;可直接运行。 132matlab模极大曲线Lipschitz (xiaohongshu.com)

【计算机网络】第七,八,九章摘要重点

第七章网络管理 1.计算机网络面临的两大威胁&#xff1f; 恶意程序有&#xff1a;计算机病毒&#xff0c;计算机蠕虫&#xff0c;特洛伊木马&#xff0c;逻辑炸弹&#xff0c;后门入侵和流氓软件。 2.安全的计算机网络四个目标&#xff1a; 机密性&#xff0c;端点鉴别&…

PDF.js实现按需分片加载pdf文件

pdf.js实现按需、分片加载pdf文件 1.服务端配置 分片加载的实现是基于 HTTP-RANGE&#xff0c;即服务端的文件接口必须实现了HTTP-RANGE。 服务端文件接口实现HTTP-RANGE&#xff0c;需要服务端添加如下响应头 [{key: "Accept-Ranges",value: "bytes"}…

C++学习笔记——友元、嵌套类、异常

目录 一、友元 一个使用友元的示例代码 输出结果 二、嵌套类 一个使用嵌套类的示例代码 输出结果 三、异常 一个使用异常处理的示例代码 输出结果 四、结论 五、使用它们的注意事项 上一篇文章链接&#xff1a; C中的继承和模板是非常强大和灵活的特性&#xff0c;它…

03.用于LLMs不同的任务-transformer 架构

大多数现代LLMs都依赖于 transformer 架构,这是 2017 年论文 Attention Is All You Need 中介绍的深度神经网络架构。要理解LLMs,我们必须简要回顾一下最初的转换器,它最初是为机器翻译而开发的,将英语文本翻译成德语和法语。变压器架构的简化版本如图 1.4 所示。 图 1.4 …

Redis:原理速成+项目实战——Redis实战9(秒杀优化)

&#x1f468;‍&#x1f393;作者简介&#xff1a;一位大四、研0学生&#xff0c;正在努力准备大四暑假的实习 &#x1f30c;上期文章&#xff1a;Redis&#xff1a;原理速成项目实战——Redis实战8&#xff08;基于Redis的分布式锁及优化&#xff09; &#x1f4da;订阅专栏&…

springboot第49集:【思维导图】多线程,常用类与基础API,集合框架,泛型,数据结构源码...

多线程创建方式一&#xff1a;继承Thread类多线程创建方式二&#xff1a;实现Runnable接口jdk5.0新增两种创建多线程的方式 image.png image.png image.png image.png image.png new Thread(new Runnable() {public void run() {for (int i 1; i < 100; i) {if (i % 2 0) …