文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

高性能调度系统设计总结

2024-11-29 19:01

关注

调度模块在很多系统中都是常用的模块,比如实习生的每天签到邮件,预约银行的业务短信,学习通的上课通知,腾讯视频push中台的任务下发,调度系统在中间起到关键作用。

一、那么什么是调度?

本质就是通过一些自定义策略,定时或者周期性的去触发某些事件,比如去发起一次rpc调用,和下游进行一次通信。

通用流程

调度行为可以抽象成以下几步:

如果能做好这几步,那么一个高性能的调度系统也就诞生了,而每一步的技术选型,都和未来系统想要达成的目标(高精度,高可用),有着密不可分的关系,下面我会针对这几步进行分析。

后面会举出一些实际的系统进行说明。

二、任务生成

三、任务存储

任务存储的思考分为两个方面,第一,是用什么数据结构存。第二是用什么类型的db去存。

对于高性能调度系统而言,主要看重范围查询效率,查询的qps,分布式锁的表现。

至于这里为什么提到了分布式锁,是因为在集群模式下,哪一台实例去执行任务扫描这一过程依赖于分布式锁的抢占。

1.数据结构分析

列表:

大顶堆:

B+树:

跳表:

小总结

总的来说,列表和大顶堆由于自身的性质,并不适合这样的场景。对于扫表+触发的模式,其实本质是需要一个能高速范围查询的数据结构。

B+树和跳表都是高效的能范围查询数据结构,但它们各自适用于不同的场景。B+树更适合于磁盘存储和范围查询,而跳表则更适合于内存中的快速查找和分布式环境。

2.数据库分析

我们举出基于内存的数据库的代表Redis和基于磁盘的数据库进行分析。

Redis VS MySQL:

因此,mysql和redis都有可能是作为存储任务的数据库,需要区分场景。

3.分布式锁的分析

在集群模式下,哪一台实例去执行任务扫描这一过程依赖于分布式锁的抢占。

(1) 基于MySQL实现

select * from lock_table where lock_name = 'schedule_lock' for update

主要是利用了当前读,将这条数据加上了行锁,其他线程在抢锁的时候会阻塞。

(2) 基于Redis实现

加锁:SET key value PX expireTime NX。

解锁:del key。

然而,仅依靠这两行命令作为分布式锁的实现,确实显得过于简单。在网络波动或垃圾回收(GC)的情况下,很有可能出现超时时间已过,但仍尝试释放锁的情况,从而导致错误地释放了其他客户端持有的锁。

这种情况可能会引起任务的重复下发,为了避免这一问题,下游系统不得不引入去重机制。

为确保安全,建议引入Lua脚本来优化锁的操作。在释放锁之前,Lua脚本可以检查锁的持有者是否为当前客户端,只有确认是自身持有的锁时,才执行释放操作。这样一来,GET和DEL两个操作就能合并为一次原子操作,从而避免潜在的安全隐患。

总的而言,mysql的分布式锁实现简单,但性能低。redis实现稍微复杂,性能高,一般用redis的多一点。

四、任务触发

在构建高效、可靠的分布式任务调度系统时,我们需要考虑多个方面,触发包括定时扫描、状态更新、任务重试等关键环节。

1.定时扫描

触发的本质就是将数据从db加载进内存中,那么我们可以通过定时任务,按照一定时间间隔去加载。那么

(1) 谁来扫描?

负责扫描的实例需将扫描到的任务进行下发,即发起RPC调用。

为确保实例能够并发发起多条请求,其机器资源应具备足够的线程数。为实现扫描与下发任务的负载均衡,各实例可通过抢锁机制竞争扫描权限。

获得锁的实例将负责执行扫描及下发任务的职责。

如上图,每个实例都有一个定时任务,x秒执行一次,去尝试抢锁。

(2) 扫描的时间间隔多少合理?

扫描时间间隔的设定对于确保系统性能和精度至关重要。这个间隔应当基于系统所需的实时精度以及单次扫描所生成的任务数量来合理确定。盲目降低扫描时间间隔并不总是能提高精度;相反,它可能会导致效率降低,甚至增加数据延迟。

举个例子,如果系统每1秒执行一次扫描,但每次扫描产生大量任务,而RPC处理时间长达2秒,且在此期间无法解锁以供其他实例扫描,那么第2秒的数据延迟将会显著增加。也就是说,本该1s完成的事情,他拖到了第2s才完成,那么第2s的任务就会被连累到第3s才做完......

因此,在确定扫描时间间隔时,应考虑以下两点:

综上所述,合理的扫描时间间隔应当根据具体应用场景和系统需求进行细致调整,以达到最佳的性能和精度平衡点。

2.状态更新

为了让我们的系统展现出卓越的性能和高精度,我们采用了异步方式来下发任务。异步处理的明显优势在于它能够使任务并发执行,无需等待响应,从而显著提升了系统的信息处理能力。然而,这也带来了一个问题:我们无法确切知道下游系统是否真正收到了任务。即便上游系统竭尽全力发送任务,如果下游系统接收不到,这些努力也将化为泡影。

因此,我们需要下游系统在成功接收到信息后,主动发送一个确认信号(ACK)。一旦系统接收到这个ACK,我们就能记录下触发时间和执行时间等相关信息,以便后续的任务重试模块进行相应的处理。

考虑到任务是并发下发的,返回的信息量可能会非常庞大,每条返回信息都可能触发一次远程过程调用(RPC),这无疑会大量消耗连接资源。为了解决这个问题,我们引入了队列机制。

队列机制的工作原理如下:

通过引入ACK队列,我们实现了以下几个关键效果:

通过这种方式,我们成功地实现了连接复用和即时响应的双重效果,这也是一个写聚合的思想。

但是坏处也很明显,就是我们这个队列是基于内存的,实例宕机有丢消息的可能性。时间的阈值也需要经验去设置,如果设置短了,连接不会复用,设置长了,可能影响后续任务重试时的扫描,造成误判。

这种思想源于Kafka提供的Micro-Batch的概念,他会将相同Topic和Partition的消息聚合成一个批次,然后一次性发送到Kafka集群

3.任务重试

上文我们分析了如何让海量任务下发,但仍然做不到能让调度系统拥有可靠性。在分布式环境下,服务器可能因为网络延迟,服务器故障,资源竞争等原因,任务执行可能会失败。那么如何处理这些失败的任务呢?

其实这个问题可以拆解成几个小任务:

(1) 如何检测到失败的任务?

我们上个步骤的下发回流,就是为了收集任务的执行上下文信息。有了这些信息,我们只需要去设置一个定时任务,快速的扫描这个任务信息即可。

(2) 如何定义一个失败的任务?

在下发一段较长的时间后,仍然没有回流信息写入。

回流信息写入成功,但回流信息中的响应code为失败。

(3) 检测到失败任务以后的重试策略?

重试策略分为重试次数和重试间隔。

每次重试完成,我们需要去更新这个已经重试次数,并检测他是否等于最大重试次数,之所有有这个最大重试次数,是为了防止他无限重试,造成重试风暴,而超过这个最大重试次数的,我们可以把它塞入死信队列中,让负责这个任务的人手动的去处理。

而重试间隔主要也分为几种:

(1) 固定间隔重试

在这种策略中,每次重试之间都有一个固定的时间间隔。例如,如果操作失败,系统会在1秒后重试,然后是2秒后重试,依此类推。

(2) 指数退避重试

指数退避重试策略是一种更复杂的重试策略,其中每次重试之间的时间间隔呈指数增长。例如,第一次重试可能在1秒后,第二次在2秒后,第三次在4秒后,以此类推。这种策略有助于减少对系统的冲击,特别是在高负载或网络拥塞的情况下。

之所以采用以上这两种策略是因为rpc接口调用在遇到服务质量异常的错误的时候,由于服务质量异常是有一定时间的,因此有各种退避策略,一定程度上给足下游恢复的时间。

(3) 下游应该如何处理重试的任务?

在扫描的过程中,如果因为网络波动的原因,导致回流消息的时间被拉长,而我们上游在扫描的时候误认为没有下发成功,而实际上已经下发成功了,我们依旧发起了重试,那么就会导致重复下发。

为了避免这一现象发生,下游有必要去做一次去重。我们可以给每次下发的任务都冠以一个唯一id,然后用位图对当日的下发进行去重处理。

我们可以使用雪花算法去生成唯一id,也可以通过每次生成的业务id去拼接当前下发的秒数去生成唯一id,这个方案很多,不多赘述。

五、路由实例

在经过上述流程之后,我们需要做的是,选择一个合适的实例进行触发,往往通过线程池,协程池进行rpc调度。

总结了市面上的开源中间件主要有以下几种路由算法的实现:

方法

描述

轮询

依次遍历执行器列表

随机数

random函数实现

一致性哈希

通过2^32 ring (md5散列的方式计算hash值),尽可能保证每轮触发都均匀落到每个执行器上。

LRU

最近最久未使用。

LFU

每个使用频率最低的执行器优先被淘汰。

心跳

遍历每个执行器,向每个执行器发起请求,如果哪个执行器最快发回心跳包,说明他最闲,那么就选择他。

这些路由算法都是为了能让不同执行器的负载变得均衡,需要根据场景选择合适的路由算法。

六、优秀系统的设计

1.xxl-job的实现

XXL-JOB是一款知名的分布式任务调度框架,它采用内存中的时间轮算法结合MySQL作为持久化存储来管理调度任务,其调度粒度精准至秒级。

以下是XXL-JOB的核心工作流程:

下面是简易版的伪代码(笔者凭借之前的印象写的,可能并不完整):

// 时间轮 秒数为key,task列表为value
Map> ringData = new HashMap<>();
// rpc线程池
ThreadPoolExecutor threadPool = new ThreadPoolExecutor();

// 调度线程
Thread schedulerThread = new Thread(() -> {
    while(true){
        1. 从数据库预读未来5s的任务
        List tasks = mapper.loadTask(now() + 5000)  
        for(task in tasks){
            long time = task.getTriggerTime();
            // 根据触发时间计算秒数。比如触发时间是 21:00:01 那么秒数就是 1
            Integer second = time.calculateSecond();
            ringData.put(task.getSecond(), task)
            // 更新下一次触发事件,运行状态等信息,
            updateTask(task)
        }
        Thread.sleep(5000)
    }
})
schedulerThread.start();

// 时间轮线程
Thread ringThread = new Thread(() -> {
    while(true){
       //秒数对齐,整秒数激活为可运行状态
       Thread.sleep(1000 - System.currentTimeMillis() % 1000);
       //获取苏醒时候的秒数
       Integer currentSecond = now().getSecond();
       List tasks = ringData.get(currentSecond);
       //放入线程池发起rpc调度
       threadPool.trigger(tasks)
       // help gc
       tasks.clear();
    }
})
ringThread.start();

这里的时间轮就是一个key为秒数,value为即将要执行的任务id列表。

时间轮分为单级时间轮和多级时间轮。xxl-job并没有像kafka那样采用多级时间轮,主要是因为设计理念的不同,他为了简化设计,并且单级时间轮已经满足大部分任务调度的需求。

优点:

缺点:

总体而言,XXL-JOB采用内存结合MySQL的部署方式简单易行,无需额外引入中间件。这种设计在追求调度精度的同时牺牲了一定的水平扩展性。对于任务量适中的场景而言,它仍然是一个值得考虑的优秀调度框架选项。

2.腾讯视频push中台的实现

腾讯视频push中台为了应对海量的并发,牺牲了调度的精度,以redis作为db,ZSet(跳表)作为底层数据结构来支持任务的范围查询。

主要流程:将任务id作为key,时间戳作为value进行任务的新增,利用Zrange 命令获取要触发的任务,并判断是否需要触发。而任务拉取任务依赖不同实例去抢分布式锁,然后执行。

优点:

缺点:精度无法保证。

3.Redis的高精度版本实现

(1) 分片

为了实现更高精度的Redis调度,我们需要确保跳表中的数据量保持在合理范围内。过多的数据可能导致内存占用过高、成本不足以及读写响应时间变长等问题(大Key问题)。因此,为了降低Redis访问的响应时间(即提高精度),我们对数据进行分片处理,使调度器每次只需扫描一个分片的数据。

如下图:

我们可以把一天的数据分为多个分钟级别的数据,虽然搜索的时间复杂度仍为O(logN),但由于N大大减小,搜索效率得到提高,响应速度更快。

然而,这仍然无法解决一个问题:如果某个实例通过抢锁方式获得某一分钟分片的扫描权限,但该分钟内的数据量仍然很大,可能会导致实例的线程数不足,无法实现并发处理。

(2) 分桶

为了解决这个问题,我们可以采用分桶策略,将这一分钟的数据划分为多个bucket。

在集群模式的调度器下,每个实例竞争的是各个bucket的锁,获得锁后,只需扫描相应分桶的数据。这种方法可以实现每分钟级别的tasklist调度,多台机器可以同时扫描和下发,避免了单个实例线程不足的问题。

如下图:

若即使分成三个桶,数据量仍然过大,我们可以引入一个决策服务来监控任务的延时情况。如果任务的延时率持续较高,可以根据实际情况动态调整分桶数量,从而更好地满足实际需求。

总结

本文详细探讨了调度模块在多种系统中的应用及其重要性,并深入分析了调度系统的通用流程,包括任务生成、任务存储、定时扫描和路由实例等关键步骤。

文章针对每个步骤的技术选型进行了探讨,并结合实际系统(如XXL-JOB和腾讯视频push中台)进行了案例分析。此外,还讨论了各种路由算法的实现及其适用场景。

总的来说,一个高性能的调度系统需要综合考虑任务生成策略、存储数据结构的选择、数据库选型、分布式锁的实现以及定时扫描的机制等多个方面。通过合理的技术选型和系统设计,可以实现高精度和高可用的调度目标。同时,根据具体的应用场景和需求,灵活调整调度策略和路由算法,以达到最佳的性能和效率平衡点。

来源:腾讯技术工程内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯