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

这是《百图解码支付系统设计与实现》专栏系列文章中的第(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 {
    
    @Autowired
    private 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 {
    @Autowiread
    private LeakyBucket leakyBucket;

    @Override
    public RefundOrder refund(RefundRequest request) {
        // 前置业务处理
        ... ...
        
    	Data data = buildData(request);
        leakyBucket.addData(data);
        
        // 其它业务处理
        ... ...
    }

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

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

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

相关文章

Python和Java代码实现:切线法求解一维最优化问题

Python和Java代码实现&#xff1a;切线法求解一维最优化问题 代码实现Python代码Java代码 求解实例 根据概念查询&#xff0c;切线法定义如下&#xff1a; 切线法&#xff08;Tangent Method&#xff09;是一种用于求解非线性方程的数值方法。它也被称为牛顿法&#xff08;Newt…

最佳实践分享:SQL性能调优

SQL性能调优是一个需要不断探索和实践的过程&#xff0c;旨在确保数据库查询的高效运行。本文将分享一些SQL性能调优的最佳实践&#xff0c;帮助您提升数据库性能&#xff0c;减少查询响应时间。 一、索引优化 索引是提高查询性能的关键。以下是一些关于索引优化的建议&#…

JavaScript的Class基本语法

&#x1f9d1;‍&#x1f393; 个人主页&#xff1a;《爱蹦跶的大A阿》 &#x1f525;当前正在更新专栏&#xff1a;《VUE》 、《JavaScript保姆级教程》、《krpano》、《krpano中文文档》 ​ ​ ✨ 前言 JavaScript是一种基于原型的语言&#xff0c;但在ES6中引入了class关…

elasticsearch[五]:深入探索ES搜索引擎的自动补全与拼写纠错:如何实现高效智能的搜索体验

elasticsearch[五]&#xff1a;深入探索ES搜索引擎的自动补全与拼写纠错&#xff1a;如何实现高效智能的搜索体验 前一章讲了搜索中的拼写纠错功能&#xff0c;里面一个很重要的概念就是莱文斯坦距离。这章会讲解搜索中提升用户体验的另一项功能 - [自动补全]。本章直接介绍 E…

计算机毕业设计 基于SSM的历史/博物馆藏系统的设计与实现 Java实战项目 附源码+文档+视频讲解

博主介绍&#xff1a;✌从事软件开发10年之余&#xff0c;专注于Java技术领域、Python人工智能及数据挖掘、小程序项目开发和Android项目开发等。CSDN、掘金、华为云、InfoQ、阿里云等平台优质作者✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精…

系统的可观察性是指什么?

系统的可观察性是指什么&#xff1f; 本文转自 公众号 ByteByteGo&#xff0c;如有侵权&#xff0c;请联系&#xff0c;立即删除 系统的可观察性是系统设计的重要一环。不可观察的系统无法度量、无法监控、无法改进。 日志、追踪和度量是系统可观测性的三大支柱。 下图显示了…

黑马程序员——javase基础——day03——循环语句

目录&#xff1a; for循环结构 for循环结构案例1(输出数据)案例2(求和思想)案例3(求偶数和)案例4(水仙花数)案例5(统计思想)案例6(回文数)案例7(逢七过)while循环结构 while循环结构案例1(求奇数和)案例2(珠穆朗玛峰)do-while循环结构 do-while循环结构三种循环的区别continue…

HBase学习二:RegionServer详解

1、内部结构 2、HLog 3、MemStore 4、HFile 5、BlockCache

设计一个抽奖系统

&#x1f44f;作者简介&#xff1a;大家好&#xff0c;我是爱吃芝士的土豆倪&#xff0c;24届校招生Java选手&#xff0c;很高兴认识大家&#x1f4d5;系列专栏&#xff1a;Spring原理、JUC原理、Kafka原理、分布式技术原理、数据库技术&#x1f525;如果感觉博主的文章还不错的…

【Linux操作】国产Linux服务管理操作

【Linux操作】国产Linux服务管理操作 前言SAMBA配置服务器端1. 安装相关包2. 配置/etc/samba/smb.conf&#xff0c;在此文件末尾添加如下内容&#xff0c;并保存退出。3. 创建/home/share并更改权限4. 启动samba服务 客户端• Windows客户端• 麒麟客户端 Telnet1、telnet语法2…

Spring IOC 之加载 BeanDefinition

1、前言 前面的文章我们已经对IOC之Spring统一资源加载策略有了一定的了解&#xff0c;本文我们将探讨Spring IOC 加载 BeanDefinition的整个过程。 我们先先看一段熟悉的代码&#xff1a; ClassPathResource resource new ClassPathResource("bean.xml"); // &l…

区域入侵/区域人数统计AI边缘计算智能分析网关V4如何修改IP地址?

智能分析网关V4是TSINGSEE青犀推出的一款AI边缘计算智能硬件&#xff0c;硬件采用BM1684芯片&#xff0c;集成高性能8核ARM A53&#xff0c;主频高达2.3GHz&#xff0c;INT8峰值算力高达17.6Tops&#xff0c;FB32高精度算力达到2.2T&#xff0c;硬件内置了近40种AI算法模型&…

高精度算法笔记

目录 加法 减法 乘法 除法 高精度加法的步骤&#xff1a; 1.高精度数字利用字符串读入 2.把字符串翻转存入两个整型数组A、B 3.从低位到高位&#xff0c;逐位求和&#xff0c;进位&#xff0c;存余 4.把数组C从高位到低位依次输出 1.2为准备 vector<int> A, B, C…

DataXCloud部署与配置[智数通]

静态IP设置 # 修改网卡配置文件 vim /etc/sysconfig/network-scripts/ifcfg-ens33# 修改文件内容 TYPEEthernet PROXY_METHODnone BROWSER_ONLYno BOOTPROTOstatic IPADDR192.168.18.130 NETMASK255.255.255.0 GATEWAY192.168.18.2 DEFROUTEyes IPV4_FAILURE_FATALno IPV6INIT…

【深度学习入门】深度学习基础概念与原理

*&#xff08;本篇文章旨在帮助新手了解深度学习的基础概念和原理&#xff0c;不深入讨论算法及核心公式&#xff09; 目录 一、深度学习概述 1、什么是深度学习&#xff1f; 2、深度学习与传统机器学习的区别 3、深度学习的应用领域 二、深度学习基本原理 1、神经网络的…

RF自动化环境安装+自动化实例解析

RF定义&#xff1a; 通用型的 自动测试框架&#xff0c; 绝大部分的软件的的自动化系统都可以采用它。 特点&#xff1a; 测试数据文件&#xff08;Test Data&#xff09;对应一个个的测试用例。测试数据文件里面使用的功能小模块叫关键字&#xff0c;由测试库&#xff08;T…

Vue3组件库开发 之Button(1)

需求分析&#xff1a; Button 组件大部分关注样式&#xff0c;没有交互 根本分析可以得到具体的属性列表&#xff1a; type:不同的样式(Default,Primary,Danger,Info,Success,Warning) plain:样式的不同展现模式boolean round:圆角boolean circle:圆形按钮&#xff0c;适合图标…

工具推荐 |Devv.ai — 最懂程序员的新一代 AI 搜索引擎

介绍 伴随 GPT 的出现&#xff0c;我们可以看到越来越多的 AI 产品&#xff0c;其中也不乏针对程序员做的代码生成工具。 今天介绍的这款产品是一款针对中文开发者的 AI 搜索引擎&#xff0c;Devv.ai 使用 Devv.ai 的使用非常简单&#xff0c;就是传统的搜索场景&#xff…

「简明教程」轻松掌握 MongDB 流式聚合操作

「简明教程」轻松掌握 MongDB 流式聚合操作 信息科学中的聚合是指对相关数据进行内容筛选、处理和归类并输出结果的过程。MongoDB 中的聚合是指同时对多个文档中的数据进行处理、筛选和归类并输出结果的过程。数据在聚合操作的过程中&#xff0c;就像是水流过一节一节的管道一…

C++ 程序文档生成器(doxygen)使用说明

程序文档&#xff0c;是每个程序员必看文档&#xff0c;在日常业务开发中&#xff0c;难免会封装一些组件。没有很好的组件文档&#xff0c;再好的组件都是废物&#xff0c;。因此大型业务中&#xff0c;文档和思维导图&#xff0c;两个都是必备&#xff01; 一、注释风格 …