精确掌控并发:滑动时间窗口算法在分布式环境下并发流量控制的设计与实现

这篇具有很好参考价值的文章主要介绍了精确掌控并发:滑动时间窗口算法在分布式环境下并发流量控制的设计与实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

上一篇介绍了固定时间窗口算法在支付渠道限流的应用以及使用redis实现的核心代码。

本篇重点讲清楚滑动时间窗口算法原理和应用场景,以及使用reids实现的核心代码。

1. 滑动时间窗口原理

滑动窗口算法是一种更为灵活的流量控制方案,它比固定窗口算法能更平滑地处理突发流量。在滑动窗口中,时间窗口是重叠的,这意味着流量的计算是基于过去的一段连续时间内发生的事件。

精确掌控并发:滑动时间窗口算法在分布式环境下并发流量控制的设计与实现,百图解码支付系统设计与实现,分布式流控,滑动时间窗口

工作流程:

  1. 窗口定义:确定窗口的大小,例如1秒钟,并设置窗口的滑动间隔,比如100毫秒。
  2. 计数与滑动:每个窗口都有自己的计数器。当一个新请求到达时,增加当前时间窗口及其前面相邻的窗口的计数。
  3. 限制检查:如果任何连续时间段内的请求总数超过阈值,则拒绝新的请求。
  4. 窗口更新:随着时间的推移,不断向前滑动窗口,并更新相应的计数器。

2. 滑动时间窗口在支付系统中的应用场景

滑动时间窗口在支付系统中的应用场景主要也是各种精确限流,比如把前一篇讲的固定时间窗口算法中,我们对外部渠道请求会做限流,那么就可以升级到滑动时间窗口,以提高精度。

只要是API限流,都可以使用。

3. 使用redis实现的核心代码

滑动窗口可以通过队列或循环数组来实现。每个窗口对应队列中的一个元素,记录该窗口期间的请求数。当时间滑动时,更新队列头部的元素,并可能将旧的元素出队

在Redis中,可以使用列表或有序集合来模拟这种滑动窗口。下面是一个Rdis实现的示例,使用有序集合(sorted set)来实现了滑动时间窗口算法:

/**
 * redis限流操作类
 */
@Component
public class RedisLimitUtil {
    @Autowired
    private RedisTemplate<String, Object> redisTemplate;
    // 滑动时间窗口大小
    private static final long WINDOW_SIZE_IN_SECONDS = 1000;

    /**
     * 判断是否限流
     * 这里不考虑超过long最大值的情况,系统在达到long最大值前就奔溃了。
     */
    public boolean isLimited(String key, String reuqestId, long countLimit) {
		// 使用Redis的多个命令来实现滑动窗口
        redisTemplate.zremrangeByScore(key, 0, currentTimeMillis - WINDOW_SIZE_IN_SECONDS);
        long count = redisTemplate.zcard(key);

        if (countLimit >= count) {
            redisTemplate.zadd(key, currentTimeMillis, reuqestId);
            return true;
        } else {
            return false;
        }
    }
}

每个请求都以其发生的时间戳作为分数(SCORE)存储在集合中。通过移除旧于当前时间窗口的请求来维护滑动窗口。通过检查集合中的元素数量,以确定是否超过了设定的最大请求数。

  • zremrangeByScore 用于移除窗口之外的旧请求。
  • zcard 获取当前窗口内的请求数量。
  • zadd 将新请求添加到集合中。

使用:PayServiceImpl

/**
 * 支付服务示例
 */
public class PayServiceImpl implements PayService {
    @Autowired
    private RedisLimitUtil redisLimitUtil;

    @Override
    public PayOrder pay(PayRequest request) {
        if (isLimited(request)) {
            throw new RequestLimitedException(buildExceptionMessage(request));
        }

        // 其它业务处理
        ... ...
    }

    /*
     * 限流判断
     */
    private boolean isLimited(PayRequest request) {
        // 限流KEY,这里以[业务类型 + 渠道]举例
        String key = request.getBizType() + request.getChannel();
        // 限流值
        Long countLimit = countLimitMap.get(key);

        // 如果key对应的限流值没有配置,或配置为-1,说明不限流
        if (null == countLimit || -1 == countLimit) {
            return false;
        }

        return redisLimitUtil.isLimited(key, request.getRequestId(), countLimit);
    }
}

需要注意一点的是,这次需要传入requestId进去,用于保存这个requestId在redis有序队列里的分数,用于计数和清理。

其它的注释写得比较清楚,没什么补充的。

4. 注意事项

一些分布式服务框架,为了更高的可靠性,他们使用的是本地计算。比如接口限流1000TPS,一共有20台应用服务器,框架就会把计算出每台机器是50个TPS,下发给所有的应用服务器,在服务器上线、下线过程中,可能会有一段时间是不准确的。

但在渠道限流应该中,因为每个渠道的流量都不太高,所以可以使用这种redis方案。且精度更高,不受应用服务器的上、下线影响。

另外,在分布式系统中,需要确保不同节点之间的时间同步,以保证流量计算的准确性。如果应用服务器之间的时间不同步,那么流量就会计算错误。

5. 结束语

分布式流控有很多实现方案,通过把固定时间窗口算法升级为滑动时间窗口算法,我们对流量控制的精度会大幅提升。

下一篇会介绍漏桶原理及实现。漏桶和令牌桶的特点是请求进来先保存起来,然后按一定的速度发送出,而不是超过阀值就拒绝。

6. 传送门

支付系统设计与实现是一个专业性非常强的领域,里面涉及到的很多设计思路和理论也可以应用到其它行业的软件设计中,比如幂等性,加解密,领域设计思想,状态机设计等。

在《百图解码支付系统设计与实现》的知识宇宙,每一篇深入浅出的文章都是一颗既独立但又彼此强关联的星球,有必要提供一个传送门以便让大家即刻到达想要了解的文章。

专栏地址百图解码支付系统设计与实现
领域相关
支付行业黑话:支付系统必知术语一网打尽
跟着图走,学支付:在线支付系统设计的图解教程
支付交易的三重奏:收单、结算与拒付在支付系统中的协奏曲
在线支付系统的精英搭档:深入剖析收银核心与支付引擎的协同作战(一)
在线支付系统的精英搭档:深入剖析收银核心与支付引擎的协同作战(二)

技术专题
交易流水号的艺术:掌握支付系统的业务ID生成指南
揭密支付安全:为什么你的交易无法被篡改
金融密语:揭秘支付系统的加解密艺术
支付系统日志设计完全指南:构建高效监控和问题排查体系的关键基石
避免重复扣款:分布式支付系统的幂等性原理与实践
支付系统的心脏:简洁而精妙的状态机设计与核心代码实现
精确掌控并发:分布式环境下并发流量控制的设计与实现(一)
精确掌控并发:分布式环境下并发流量控制的设计与实现(二)
金融疆界:在线支付系统渠道网关的创新设计(一)文章来源地址https://www.toymoban.com/news/detail-815117.html

到了这里,关于精确掌控并发:滑动时间窗口算法在分布式环境下并发流量控制的设计与实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 分布式调用与高并发处理 Zookeeper分布式协调服务

    单机架构 一个系统业务量很小的时候所有的代码都放在一个项目中就好了,然后这个项目部署在一台服务器上,整个项目所有的服务都由这台服务器提供。 缺点: 服务性能存在瓶颈,用户增长的时候性能下降等。 不可伸缩性 代码量庞大,系统臃肿,牵一发动全身 单点故障

    2024年02月12日
    浏览(61)
  • 第七章-分布式搜索引擎-ES:全文查询、分词查询、精确查询、地理坐标查询、组合查询(bool、funtion_score)以及RestApi

    DSL查询分类 全文查询、分词查询、非分词查询、地理坐标查询、组合查询 match_all 查询所有,不需要查询条件,固定写法_search 第一个hits就是命中的数据 ,total就是条数,第二个hits是source嘞   全文检索查询 我们不要整多个字段查询,参与的字段越多,查询速度越慢,如果有

    2024年01月16日
    浏览(79)
  • Redis高并发分布式锁

    针对单机环境下的并发访问,可以通过锁机制(Syschronized或独占锁等)来进行控制,使得一个资源在一段时间内只能被一个线程访问;但在多服务器的分布式环境下,并发访问同一个资源,可能会导致被同时修改或更新,原因在于juc包下的并发控制机制,都是基于JVM层面的,而

    2024年02月02日
    浏览(80)
  • LeetCode算法小抄--滑动窗口算法

    ⚠申明: 未经许可,禁止以任何形式转载,若要引用,请标注链接地址。 全文共计6244字,阅读大概需要3分钟 🌈更多学习内容, 欢迎👏关注👀文末我的个人微信公众号:不懂开发的程序猿 个人网站:https://jerry-jy.co/ 滑动窗口算法 思路 1、我们在字符串 S 中使用双指针中的

    2023年04月09日
    浏览(38)
  • 【算法】基础算法002之滑动窗口(二)

    👀 樊梓慕: 个人主页  🎥 个人专栏: 《C语言》 《数据结构》 《蓝桥杯试题》 《LeetCode刷题笔记》 《实训项目》 《C++》 《Linux》 《算法》 🌝 每一个不曾起舞的日子,都是对生命的辜负 目录 前言  5.水果成篮(medium)  6.找到字符串中所有字母异位词 7.串联所有单词的

    2024年02月20日
    浏览(46)
  • 【算法】基础算法002之滑动窗口(一)

    👀 樊梓慕: 个人主页  🎥 个人专栏: 《C语言》 《数据结构》 《蓝桥杯试题》 《LeetCode刷题笔记》 《实训项目》 《C++》 《Linux》《算法》 🌝 每一个不曾起舞的日子,都是对生命的辜负 目录 前言 1.长度最小的子数组 滑动窗口类问题解题思路大纲: 2.无重复字符的最长

    2024年02月19日
    浏览(43)
  • 服务端⾼并发分布式结构演进之路

    应⽤(Application)/系统(System) 为了完成一整套服务的一个程序或相互配合的程序群 模块(Module)/组件(Component) 当应⽤较复杂时,为了分离职责,将其中具有清晰职责的、内聚性强的部分,抽象出概念,便于理解 分布式(Distributed) 分布式(Distributed)是指将计算、任务

    2024年02月13日
    浏览(94)
  • 【算法优选】 滑动窗口专题——壹

    基本概念 滑动窗口是一种 基于双指针 的一种思想,两个指针指向的元素之间形成一个窗口。 分类:窗口有两类,一种是 固定大小类 的窗口,一类是 大小动态变化 的窗口。 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其总和大于等于 target 的长

    2024年02月08日
    浏览(39)
  • 【算法|数组】滑动窗口

    给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度**。**如果不存在符合条件的子数组,返回 0 。 示例 1: 示例 2: 示例 3: 暴力解法 这种做法可以很容易想到,可是谁

    2024年02月12日
    浏览(39)
  • 算法专题整理:滑动窗口

    视频课程:同向双指针 滑动窗口【基础算法精讲 01】_哔哩哔哩_bilibili 滑动窗口也可以理解为双指针法的一种。 滑动窗口的核心在于 连续 !如果需要得到的结果是 满足某种较为明显条件 的 连续 的 子数组 ,可以考虑使用滑动窗口来做。 通常情况下,滑动窗口是 枚举右端

    2024年02月12日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包