更多博客请见 我的语雀知识库
作者：akinwang
调度模块在很多系统中都是常用的模块，比如实习生的每天签到邮件，预约银行的业务短信，学习通的上课通知，腾讯视频push中台的任务下发，调度系统在中间起到关键作用。
原文链接：高性能调度系统设计总结

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

通用流程

调度行为可以抽象成以下几步：
1.任务生成。
2.任务存储。
3.任务触发。
4.路由实例。
如果能做好这几步，那么一个高性能的调度系统也就诞生了，而每一步的技术选型，都和未来系统想要达成的目标（高精度，高可用），有着密不可分的关系，下面我会针对这几步进行分析。
后面会举出一些实际的系统进行说明。

任务生成

1.单次任务生成：对于单次任务，通常由管理台直接发起请求，将任务信息写入系统。
2.周期性任务生成：周期性任务生成类似于打点计时器。每当任务触发时，系统会计算出未来需要触发的任务时间列表。例如，对于每小时执行的任务，系统会在第二天生成24个整点任务。
3.推送系统任务生成：对于推送系统任务，系统会根据用户过去的行为画像预测其最有可能点击的时间区间。在第二天到来之前，系统会预先计算并生成第二天各个时间点的推送任务。
image.png

任务存储

任务存储的思考分为两个方面，第一，是用什么数据结构存。第二是用什么类型的db去存。
对于高性能调度系统而言，主要看重范围查询效率，查询的qps，分布式锁的表现。
至于这里为什么提到了分布式锁，是因为在集群模式下，哪一台实例去执行任务扫描这一过程依赖于分布式锁的抢占。

数据结构分析

列表

插入：O(1)
查询：O(logN)
实现：我们可以利用列表去存即将触发的任务信息，通过遍历的方式去取到大于当前时间的任务，并且触发。
优点：实现简单
缺点：但需要对所有任务进行遍历，查出很多无效数据，极其低效。

大顶堆

删除：O(logN)
查询：O(1)
实现：我们也可以利用大顶堆的性质，每次都取堆顶元素，如果堆顶元素大于当前时间，那么就取最大元素。其余元素会利用大顶堆的性质，继续浮出最大的元素，然后继续比较。
优点：查询快，只会查到快到时间的任务，实现简单。
缺点：需要维护自身堆的性质，cpu压力高，无法抗住高并发。

B+树

查询：O(logN)
B+树（B-plus tree）是一种自平衡的树数据结构，它能够保持数据有序，允许插入、删除和查找操作在对数时间内完成。B+树特别适合于磁盘或其他直接存取辅助设备的存储系统，因为它能够最大化地减少I/O操作次数。

跳表

查询：O(logN)
跳表（Skip List）是一种基于有序链表的高效数据结构，它通过在链表的基础上增加多级索引来实现快速的查找操作。跳表允许在对数时间内完成搜索、插入和删除操作，且插入和删除操作不需要频繁调整数据结构。

小总结

总的来说，列表和大顶堆由于自身的性质，并不适合这样的场景。对于扫表+触发的模式，其实本质是需要一个能高速范围查询的数据结构。
B+树和跳表都是高效的能范围查询数据结构，但它们各自适用于不同的场景。B+树更适合于磁盘存储和范围查询，而跳表则更适合于内存中的快速查找和分布式环境。

数据库分析

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

Redis VS MySQL

1.Redis的底层是跳表，而MySQL的底层是B+树。就范围查询而言，两者不分伯仲。
2.但Redis没有事务概念，内部实现是单线程，没有锁竞争，再加上IO多路复用的特性和极其高效的数据结构实现，就注定单机qps要远超过mysql。
3.mysql在这个场景下的优势则是有持久化能力，不容易丢数据，redis可能在RDB和AOF的过程中有丢数据的可能性。
因此，mysql和redis都有可能是作为存储任务的数据库，需要区分场景。

分布式锁的分析

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

基于MySQL实现
select * from lock_table where lock_name = 'schedule_lock' for update

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

基于Redis实现

加锁：SET key value PX expireTime NX。
解锁：del key。
然而，仅依靠这两行命令作为分布式锁的实现，确实显得过于简单。在网络波动或垃圾回收（GC）的情况下，很有可能出现超时时间已过，但仍尝试释放锁的情况，从而导致错误地释放了其他客户端持有的锁。
这种情况可能会引起任务的重复下发，为了避免这一问题，下游系统不得不引入去重机制。
为确保安全，建议引入Lua脚本来优化锁的操作。在释放锁之前，Lua脚本可以检查锁的持有者是否为当前客户端，只有确认是自身持有的锁时，才执行释放操作。这样一来，GET和DEL两个操作就能合并为一次原子操作，从而避免潜在的安全隐患。
总的而言，mysql的分布式锁实现简单，但性能低。redis实现稍微复杂，性能高，一般用redis的多一点。

任务触发

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

定时扫描

触发的本质就是将数据从db加载进内存中，那么我们可以通过定时任务，按照一定时间间隔去加载。那么
1.谁来扫描？
2.扫描的时间间隔多少合理？

谁来扫描？

负责扫描的实例需将扫描到的任务进行下发，即发起RPC调用。
为确保实例能够并发发起多条请求，其机器资源应具备足够的线程数。为实现扫描与下发任务的负载均衡，各实例可通过抢锁机制竞争扫描权限。
获得锁的实例将负责执行扫描及下发任务的职责。
image.png
如上图，每个实例都有一个定时任务，x秒执行一次，去尝试抢锁。

扫描的时间间隔多少合理？

扫描时间间隔的设定对于确保系统性能和精度至关重要。这个间隔应当基于系统所需的实时精度以及单次扫描所生成的任务数量来合理确定。盲目降低扫描时间间隔并不总是能提高精度；相反，它可能会导致效率降低，甚至增加数据延迟。
举个例子，如果系统每1秒执行一次扫描，但每次扫描产生大量任务，而RPC处理时间长达2秒，且在此期间无法解锁以供其他实例扫描，那么第2秒的数据延迟将会显著增加。也就是说，本该1s完成的事情，他拖到了第2s才完成，那么第2s的任务就会被连累到第3s才做完……
因此，在确定扫描时间间隔时，应考虑以下两点：
1.对于精度要求不高且任务量较大的场景：可以适当延长扫描时间间隔，以确保在单次扫描周期内能够完成所有任务的处理下发。这样可以减轻系统负担，提高整体效率。
2.对于精度要求高同时任务量也很大的场景：除了优化RPC处理流程外，还可以考虑改进数据存储结构，将数据分片分桶处理。通过为每个数据分片分配独立的扫描实例，可以实现并行处理，从而在保证高精度的同时提升系统响应速度。
综上所述，合理的扫描时间间隔应当根据具体应用场景和系统需求进行细致调整，以达到最佳的性能和精度平衡点。

状态更新

为了让我们的系统展现出卓越的性能和高精度，我们采用了异步方式来下发任务。异步处理的明显优势在于它能够使任务并发执行，无需等待响应，从而显著提升了系统的信息处理能力。然而，这也带来了一个问题：我们无法确切知道下游系统是否真正收到了任务。即便上游系统竭尽全力发送任务，如果下游系统接收不到，这些努力也将化为泡影。
因此，我们需要下游系统在成功接收到信息后，主动发送一个确认信号（ACK）。一旦系统接收到这个ACK，我们就能记录下触发时间和执行时间等相关信息，以便后续的任务重试模块进行相应的处理。
考虑到任务是并发下发的，返回的信息量可能会非常庞大，每条返回信息都可能触发一次远程过程调用（RPC），这无疑会大量消耗连接资源。为了解决这个问题，我们引入了队列机制。
image.png
队列机制的工作原理如下：
通过引入ACK队列，我们实现了以下几个关键效果：
1.当任务队列满载时，我们可以一次性取出所有元素，触发一次RPC请求。这样，原本需要多次请求的单个数据处理，现在可以合并为一次批量处理。
2.即使任务队列未满，但如果自上次取元素以来经过的时间超过了预设的阈值，我们也会将队列中的所有数据一次性取出，触发一次RPC请求。
通过这种方式，我们成功地实现了连接复用和即时响应的双重效果，这也是一个写聚合的思想。
但是坏处也很明显，就是我们这个队列是基于内存的，实例宕机有丢消息的可能性。时间的阈值也需要经验去设置，如果设置短了，连接不会复用，设置长了，可能影响后续任务重试时的扫描，造成误判。
这种思想源于Kafka提供的Micro-Batch的概念，他会将相同Topic和Partition的消息聚合成一个批次，然后一次性发送到Kafka集群

任务重试

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

1. 如何检测到失败的任务？

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

2. 如何定义一个失败的任务？

1.在下发一段较长的时间后，仍然没有回流信息写入。
2.回流信息写入成功，但回流信息中的响应code为失败。

3. 检测到失败任务以后的重试策略？

重试策略分为重试次数和重试间隔。
每次重试完成，我们需要去更新这个已经重试次数，并检测他是否等于最大重试次数，之所有有这个最大重试次数，是为了防止他无限重试，造成重试风暴，而超过这个最大重试次数的，我们可以把它塞入死信队列中，让负责这个任务的人手动的去处理。
而重试间隔主要也分为几种：
1. 固定间隔重试
在这种策略中，每次重试之间都有一个固定的时间间隔。例如，如果操作失败，系统会在1秒后重试，然后是2秒后重试，依此类推。
2. 指数退避重试
指数退避重试策略是一种更复杂的重试策略，其中每次重试之间的时间间隔呈指数增长。例如，第一次重试可能在1秒后，第二次在2秒后，第三次在4秒后，以此类推。这种策略有助于减少对系统的冲击，特别是在高负载或网络拥塞的情况下。
之所以采用以上这两种策略是因为rpc接口调用在遇到服务质量异常的错误的时候，由于服务质量异常是有一定时间的，因此有各种退避策略，一定程度上给足下游恢复的时间。

4. 下游应该如何处理重试的任务？

在扫描的过程中，如果因为网络波动的原因，导致回流消息的时间被拉长，而我们上游在扫描的时候误认为没有下发成功，而实际上已经下发成功了，我们依旧发起了重试，那么就会导致重复下发。
为了避免这一现象发生，下游有必要去做一次去重。我们可以给每次下发的任务都冠以一个唯一id，然后用位图对当日的下发进行去重处理。
我们可以使用雪花算法去生成唯一id，也可以通过每次生成的业务id去拼接当前下发的秒数去生成唯一id，这个方案很多，不多赘述。

路由实例

在经过上述流程之后，我们需要做的是，选择一个合适的实例进行触发，往往通过线程池，协程池进行rpc调度。
总结了市面上的开源中间件主要有以下几种路由算法的实现：

方法 描述
轮询 依次遍历执行器列表
随机数 random函数实现
一致性哈希 通过2^32 ring (md5散列的方式计算hash值)，尽可能保证每轮触发都均匀落到每个执行器上。
LRU 最近最久未使用。
LFU 每个使用频率最低的执行器优先被淘汰。
心跳 遍历每个执行器，向每个执行器发起请求，如果哪个执行器最快发回心跳包，说明他最闲，那么就选择他。

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

优秀系统的设计

xxl-job的实现

XXL-JOB是一款知名的分布式任务调度框架，它采用内存中的时间轮算法结合MySQL作为持久化存储来管理调度任务，其调度粒度精准至秒级。
以下是XXL-JOB的核心工作流程：
1.调度线程预读与更新：调度线程负责提前读取未来5秒内即将执行的任务，将这些任务载入内存中的时间轮，并同步更新它们的下一次触发时刻。
2.时间轮线程轮询执行：时间轮线程每隔一秒从等待状态激活为可运行状态。它会捕获当前时间的秒级信息，并在时间轮中定位到对应的任务。一旦找到，时间轮线程便会利用预先配置的线程池发起RPC调用，触发任务执行。
下面是简易版的伪代码(笔者凭借之前的印象写的，可能并不完整)：

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

// 调度线程
Thread schedulerThread = new Thread(() -> {
    while(true){
        1. 从数据库预读未来5s的任务
        List<Task> 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<Task> tasks = ringData.get(currentSecond);
       //放入线程池发起rpc调度
       threadPool.trigger(tasks)
       // help gc
       tasks.clear();
    }
})
ringThread.start();

这里的时间轮就是一个key为秒数，value为即将要执行的任务id列表。
时间轮分为单级时间轮和多级时间轮。xxl-job并没有像kafka那样采用多级时间轮，主要是因为设计理念的不同，他为了简化设计，并且单级时间轮已经满足大部分任务调度的需求。
优点：
1.高效检索与持久化：借助MySQL B+树的特性，搜索操作的时间复杂度降至O(logN)，同时提供数据的持久化存储，确保数据安全不易丢失。
2.高精度调度：通过将任务提前预读至内存，提升了任务调度的精度和响应速度。
3.生产者-消费者模型：调度线程与时间轮线程的协同工作构成了经典的生产者-消费者模型。时间轮作为任务缓冲区，有效实现流量削峰，减轻系统瞬时负载压力。
缺点：
1.调度器集群性能瓶颈：现有架构依赖调度器集群间的锁机制来执行任务，这可能导致单个调度器承受过大压力，限制了系统的并发处理能力（QPS）。在任务量激增时，难以通过水平扩展提升调度能力，从而可能导致部分任务延迟过高。
2.磁盘存储的性能局限：虽然MySQL提供了可靠的数据存储，但作为基于磁盘的数据库，在高并发场景下的性能可能不如内存型数据库如Redis。
总体而言，XXL-JOB采用内存结合MySQL的部署方式简单易行，无需额外引入中间件。这种设计在追求调度精度的同时牺牲了一定的水平扩展性。对于任务量适中的场景而言，它仍然是一个值得考虑的优秀调度框架选项。

腾讯视频push中台的实现

腾讯视频push中台为了应对海量的并发，牺牲了调度的精度，以redis作为db，ZSet(跳表)作为底层数据结构来支持任务的范围查询。
主要流程：将任务id作为key，时间戳作为value进行任务的新增，利用Zrange 命令获取要触发的任务，并判断是否需要触发。而任务拉取任务依赖不同实例去抢分布式锁，然后执行。
优点：
1.基于redis，查询快，qps是mysql的好几倍，实现简单，易于维护。
2.redis的分布式锁性能优秀，加锁解锁快。
3.无需依赖其他中间件，成本小。
4.让搜素的时间复杂度降低到O(logN)，查询快，无需遍历额外数据。
缺点：精度无法保证。

Redis的高精度版本实现

分片

为了实现更高精度的Redis调度，我们需要确保跳表中的数据量保持在合理范围内。过多的数据可能导致内存占用过高、成本不足以及读写响应时间变长等问题(大Key问题)。因此，为了降低Redis访问的响应时间（即提高精度），我们对数据进行分片处理，使调度器每次只需扫描一个分片的数据。
如下图：
image.png
我们可以把一天的数据分为多个分钟级别的数据，虽然搜索的时间复杂度仍为O(logN)，但由于N大大减小，搜索效率得到提高，响应速度更快。
然而，这仍然无法解决一个问题：如果某个实例通过抢锁方式获得某一分钟分片的扫描权限，但该分钟内的数据量仍然很大，可能会导致实例的线程数不足，无法实现并发处理。

分桶

为了解决这个问题，我们可以采用分桶策略，将这一分钟的数据划分为多个bucket。
在集群模式的调度器下，每个实例竞争的是各个bucket的锁，获得锁后，只需扫描相应分桶的数据。这种方法可以实现每分钟级别的tasklist调度，多台机器可以同时扫描和下发，避免了单个实例线程不足的问题。
如下图：
image.png
1
若即使分成三个桶，数据量仍然过大，我们可以引入一个决策服务来监控任务的延时情况。如果任务的延时率持续较高，可以根据实际情况动态调整分桶数量，从而更好地满足实际需求。

总结

本文详细探讨了调度模块在多种系统中的应用及其重要性，并深入分析了调度系统的通用流程，包括任务生成、任务存储、定时扫描和路由实例等关键步骤。
文章针对每个步骤的技术选型进行了探讨，并结合实际系统（如XXL-JOB和腾讯视频push中台）进行了案例分析。此外，还讨论了各种路由算法的实现及其适用场景。
总的来说，一个高性能的调度系统需要综合考虑任务生成策略、存储数据结构的选择、数据库选型、分布式锁的实现以及定时扫描的机制等多个方面。通过合理的技术选型和系统设计，可以实现高精度和高可用的调度目标。同时，根据具体的应用场景和需求，灵活调整调度策略和路由算法，以达到最佳的性能和效率平衡点。

个人问题

个人在读完这篇文章后有一个问题：
为什么下发任务走的是RPC而不是MQ？
我的理解是这样的：
MQ适合的是对消息时效性要求不高的场景。是用来削峰填谷的。消息存在Broker里，消费者可以慢慢消费。
但是消息推送系统不一样，它对时效性要求很高。必须保证用户在某个时间点能收到消息推送。扫描任务扫描出的是最近五分钟的推送任务。这些任务必须在短时间内推送到用户手机上。
不可能说存到MQ里让消费者慢慢消费。况且走MQ就涉及到了生产者，中间服务器，消费者三个角色，两次数据传输。RPC呢？只有生产者消费者两个角色，数据传输只有一次，在速度上天然就比MQ更快，消费者能更快消费消息。
但是缺少了中间服务器，就可能会导致消息积压。定时扫描
消费者消费不过来生产者又发来了新的任务怎么办？
这就需要更改生产者的生产逻辑。控制扫描任务的时间间隔。
怎么控制呢？参考原文：

因此，在确定扫描时间间隔时，应考虑以下两点： 1.对于精度要求不高且任务量较大的场景：可以适当延长扫描时间间隔，以确保在单次扫描周期内能够完成所有任务的处理下发。这样可以减轻系统负担，提高整体效率。 2.对于精度要求高同时任务量也很大的场景：除了优化RPC处理流程外，还可以考虑改进数据存储结构，将数据分片分桶处理。通过为每个数据分片分配独立的扫描实例，可以实现并行处理，从而在保证高精度的同时提升系统响应速度。 综上所述，合理的扫描时间间隔应当根据具体应用场景和系统需求进行细致调整，以达到最佳的性能和精度平衡点。