一个高效的定时任务系统
“
今天想跟大家一起探讨一个听起来很简单的话题：定时任务机制。
无非就是一个计时器，到了指定时间就开始跑呗。too young，要是这么简单我还说啥呢，干不就完了。
那如果是几千上万个定时任务，你的计时器该如何设计呢？如果是 A 任务执行完后再执行 B 任务你会怎么调度呢？
如果是几十台机器同时要处理一些任务，你又该如何设计呢？带着这些看似不简单的问题我们开始时间之旅。
操作系统的时间系统
应用程序部署在操作系统上，定时任务依赖操作系统的时钟。鉴于大部分的服务器都部署在 Linux 上，我们就只讨论 Linux 的时间系统，Windows 服务器别打我。
大部分 PC 机中有两个时钟源，他们分别叫做 RTC（Real Time Clock，实时时钟） 和 OS（操作系统）时钟。
RTC
RTC（Real Time Clock，实时时钟）也叫做 CMOS 时钟，它是 PC 主机板上的一块芯片（或者叫做时钟电路），它靠电池供电，即使系统断电也可以维持日期和时间。
由于独立于操作系统所以也被称为硬件时钟，它为整个计算机提供一个计时标准，是最原始最底层的时钟数据。
OS 时钟
OS 时钟产生于 PC 主板上的定时/计数芯片（8253/8254），由操作系统控制这个芯片的工作，OS 时钟的基本单位就是该芯片的计数周期。
在开机时操作系统取得 RTC 中的时间数据来初始化 OS 时钟，然后通过计数芯片的向下计数形成了 OS 时钟，所以 OS 时钟并不是本质意义上的时钟，它更应该被称为一个计数器。
OS 时钟只在开机时才有效，而且完全由操作系统控制，所以也被称为软时钟或系统时钟。
时钟中断
Linux 的 OS 时钟的物理产生原因是可编程定时/计数器产生的输出脉冲，这个脉冲送入 CPU，就可以引发一个中断请求信号，我们就把它叫做时钟中断。
Linux 中用全局变量 jiffies 表示系统自启动以来的时钟滴答数目。每个时钟滴答，时钟中断得到执行。
时钟中断执行的频率很高：100 次/秒（Linux 设计者将一个时钟滴答（tick）定义为 10ms），时钟中断的主要工作是处理和时间有关的所有信息、决定是否执行调度程序。
和时间有关的所有信息包括系统时间、进程的时间片、延时、使用 CPU 的时间、各种定时器，进程更新后的时间片为进程调度提供依据，然后在时钟中断返回时决定是否要执行调度程序。
在单处理器系统中，每个 tick 只发生一次时钟中断。在对应的中断处理程序中完成更新系统时间、统计、定时器、等全部功能。
而在多处理器系统下，时钟中断实际上是分成两个部分：
全局时钟中断，系统中每个 tick 只发生一次。对应的中断处理程序用于更新系统时间和统计系统负载。
本地时钟中断，系统中每个 tick 在每个 CPU 上发生一次。对应的中断处理程序用于统计对应 CPU 和运行于该CPU上的进程的时间，以及触发对应 CPU 上的定时器。
于是，在多处理器系统下，每个 tick，每个 CPU 要处理一次本地时钟中断；另外，其中一个 CPU 还要处理一次全局时钟中断。
时钟中断的应用
更新系统时间：在 Linux 内核中，全局变量 jiffies_64 用于记录系统启动以来所经历的 tick 数。
每次进入时钟中断处理程序（多处理器系统下对应的是全局时钟中断）都会更新 jiffies_64 的值，正常情况下，每次总是给 jiffies_64 加 1。
而时钟中断存在丢失的可能。内核中的某些临界区是不能被中断的，所以进入临界区前需要屏蔽中断。
当中断屏蔽取消的时候，硬件只能告诉内核是否曾经发生了时钟中断、却不知道已经发生过多少次。
于是，在极端情况下，中断屏蔽时间可能超过 1 个 tick，从而导致时钟中断丢失。
如果计算机上的时钟振荡器有很高的精度，Linux 内核可以读振荡器中的计数器，通过比较上一次读的值与当前值，以确定中断是否丢失；如果发现中断丢失，则本次中断处理程序会给 jiffies_64 增加相应的计数。
但是如果振荡器硬件不允许（不提供计数器、或者计数器不允许读、或者精度不够），内核也没法知道时钟中断是否丢失了。
内核中的全局变量 xtime 用于记录当前时间（自 1970-01-01 起经历的秒数、本秒中经历的纳秒数）。xtime 的初始值就是内核启动时从 RTC 读出的。
在时钟中断处理程序更新 jiffies_64 的值后，便更新 xtime 的值。通过比较 jiffies_64 的当前值与上一次的值（上面说到，差值可能大于 1），决定 xtime 应该更新多少。
系统调用 gettimeofday（对应库函数 time 和 gettimeofday）就是用来读 xtime 变量的，从而让用户程序获取系统时间。
实现定时器：既然已知每个 tick 是 10ms，用 tick 来做定时任务统计再好不过。无论是内核还是应用系统其实都有大量的定时任务需求，这些定时任务类型不一，但是都是依赖于 tick。
已知的操作系统实现定时任务的方式有哪些呢？
①维护一个带过期时间的任务链表
简单且行之有效的方式。在一个全局链表中维护一个定时任务链。每次 tick 中断来临，遍历该链表找到 expire 到期的任务。
如果将任务以 expire 排序，每次只用找到链头的元素即可，时间复杂度为 O(1)。
这种方式对于早期的 Linux 系统来说没有问题，随着现在的系统复杂度渐渐变化，它无法支撑如今的网络流量暴增时代的需求。
②时间轮（Timing-Wheel）算法
时间轮很容易理解，上图有 n 个 bucket，每一个 bucket 表示一秒，当前 bucket 表示当前这一秒到来之后要触发的事件。
每个 bucket 会对应着一个链表，链表中存储的就是当前时刻到来要处理的事件。
那这里有个问题来了，如果有个定时任务需要在 16 小时后执行，换算成秒就是 57600s，难道我们的时间轮也要这么多个 bucket 吗。几万个对内存也是一种损耗。
为了减少 bucket 的数量，时间轮算法提供了一个扩展算法，即 Hierarchy 时间轮。
Hierarchy 很好理解，层级制度。既然一个时间轮可能会导致 bucket 过多，那么为什么不能多弄几个*来代替时分秒呢？
基于时、分、秒各自实现一个 wheel，每个 wheel 维护一个自己的 cursor，在 Hour 数组中，每个 bucket 代表一个小时。
Minute 数组中每一个 bucket 代表 1 分钟，Second 数组中每个 bucket 代表 1 秒。
采用分层时间轮，我们只需要 24+60+60=144 个 bucket 就可以表示所有的时间。
完全模拟到时钟的用法，Second wheel 每转完 60 个 bucket ，要联动 Minute wheel 转动一格，同理 Minite wheel 转动 60 个 bucket 也要联动 Hours wheel 转动一格。
③维护一个基于小根堆算法的定时任务
小根堆的性质是满足除了根节点以外的每个节点都不小于其父节点的堆。基于这种性质从根节点开始遍历每个节点能保证获取到一个最小优先级的队列。
那么应用到定时器中，每次只用获取当前最小堆的 root 节点看是否到期即可。最小堆的插入时间复杂度为 O(lgn)，获取头结点时间复杂度为 O(1)。
开箱即用的定时器
单机版定时器
①cron/crontab
cron 是 Linux 中的一个定时任务机制。cron 表示一个在后台运行的守护进程，crontab 是一个设置 cron 的工具，所有的定时任务都写在 crontab 文件中。
cron 调度的是 /etc/crontab 文件中的内容。crontab 的命令构成为时间+动作，其时间有分、时、日、月、周五种。
这里要注意，最小单位为分钟，默认是不到秒的级别，大家也给出了各种精确到秒的方案，有兴趣的可以搜索一下。
/etc/crontab 文件中的每一行都代表一项任务，它的格式是：
minute hour day month dayofweek user-name command
* minute — 分钟，从 0 到 59 之间的任何整数
* hour — 小时，从 0 到 23 之间的任何整数
* day — 日期，从 1 到 31 之间的任何整数（如果指定了月份，必须是该月份的有效日期）
* month — 月份，从 1 到 12 之间的任何整数（或使用月份的英文简写如 jan、feb 等等）
* dayofweek — 星期，从 0 到 7 之间的任何整数，这里的 0 或 7 代表星期日（或使用星期的英文简写如 sun、mon 等等）
* user-name - 用户，脚本以什么用户执行
* command — 要执行的命令（命令可以是 ls /proc >> /tmp/proc 之类的命令，也可以是执行你自行编写的脚本的命令。）
②JDK 提供的定时器：Timer
Timer 的思路很简单，基于最小堆的方案创建一个 TaskQueue 来盛 TimerTask。
Timer 中有一个 TimerThread 线程，该线程是 Timer 中唯一负责任务轮询和任务执行的线程。
这就意味着如果一个任务耗时很久，久到已经超过了下个任务的开始执行时间，那么就意味下一个任务会延迟执行。
另外 Timer 线程是不会捕获异常的，如果某个 TimerTask 执行过程中发生了异常而被终止，那么后面的任务将不会被执行。所以要做好异常处理防止出现异常影响任务继续。
因为有阻塞和异常终止的缺点，JDK 又封装了另一个定时器的实现方式，这次保证不会阻塞。
因为它是线程池实现方式的一种：ScheduledExecutorService。ScheduledExecutorService 内部将任务封装之后交给了 DelayQueue。
DelayQueue 是一个依靠 AQS 队列同步器所实现的*延迟阻塞队列，内部通过 PriorityQueue 来实现，本质还是还是一个堆，所以插入的时间复杂度也是 O(lgn)。
③Netty 封装的时间轮：HashedWheelTimer
上面简要描述了操作系统中的时间轮实现，在著名框架 Netty 中也封装了一个自己的时间轮实现：HashedWheelTimer 类。
因为 Netty 中需要管理大量的 I/O 超时事件，基于时间轮的方案有助于节省资源。
Netty 中采用一个*的方案，一个格子代表的时间是 100ms，默认有 512 个格子。
来看看 HashedWheelTimer 的构造函数参数：
HashedWheelTimer(
ThreadFactory threadFactory, //类似于Clock中的updater, 负责创建Worker线程.
long tickDuration, //时间刻度之间的时长(默认100ms), 通俗的说, 就是多久tick++一次.
TimeUnit unit, //tickDuration的单位.
int ticksPerWheel //类似于Clock中的wheel的长度(默认512).
);
另外为了不无休止的增加 bucket，这里采用了轮（round）的概念，一轮所花费的时间：round time=ticksPerWheel*tickDuration。
如果 bucket 只有 512 个， 而当前休眠时间长于一轮，那么就增加相应的轮次来表示当前休眠时长。
HashedWheelTimer 中有一些主要的成员：
HashedWheelTimer 类本身，主要负责启动 Worker 线程、添加任务等。
Worker：内部负责添加任务，累加 tick，执行任务等。
HashedWheelTimeout：任务的包装类，链表结构，负责保存 deadline，轮数等。
HashedWheelBucket：wheel 数组元素，负责存放 HashedWheelTimeout 链表。
Worker 线程是 HashedWheelTimer 的核心，主要负责每当已过 tickDuration 时间就累加一次 tick。
同时也负责执行到期的 timeout 任务和添加 timeout 任务到指定的 wheel 中。
当添加 Timeout 任务的时候，会根据设置的时间来计算出需要等待的时间长度，根据时间长度进而算出要经过多少次 tick，然后根据 tick 的次数来算出经过多少轮最终得出 task 在 wheel 中的位置。
对于这种时间轮一般是怎么遍历判断任务到期呢？每个 ticket 到来，都要去遍历每一个 bucket ，以此来判断是否有 bucket 到期。
所以这种方式就要求 bucket 尽量不要太多，如果太多每次遍历都需要很长的时间。另外就是每次都会遍历，必然会有很多空转，也是一种资源的浪费。
④Kafka 中的时间轮：TimingWheel
Netty 中的时间轮实现采用了单轮+round 的模式，在 Kafka 中采用了多轮的模式。
上面说过多轮模式下如果按照时分秒来表达，每个轮所需的 bucket 都非常的少，遍历轮的时候就会很快。
但是多轮也会带来另一个问题就是轮的维护：比如有个定时任务是 1*60*60+50=36050s，这时候就需要分钟和秒轮同时维护这个任务。
当这个任务继续走，只剩下 59s 的时候，分钟轮就无需在维护它的信息，只剩下秒轮来维护，这里出现了降轮的概念 。
单机定时机制对比
以上简单描述了各个实现方案，简单对比可以得出：
Timer 的实现方案毋庸置疑是最差的。阻塞，异常退出这两条“罪名”无疑让现代程序员无法承受因为出错被老板骂的锅。
ScheduledExecutorService 使用线程池的方式来异步的执行任务，当任务量巨大的时候，如果设置了优先数量的可执行线程，无疑还是会阻塞任务，好在可执行线程多。
而 HashedWheelTimer 是面向 bucket 设计，如果采用多轮的方式可以不受任务量限制，任务量非常大的时候，维护数组的成本远远要低于维护堆的成本。
但是如果是任务量很少的情况，时间轮依旧需要全盘扫描，出现空转的状态，这种空载无疑也是浪费资源的体现。
所以面向使用场景编程的话：
如果当前待运行的定时任务属于耗时长一点，任务量也不是那么大的时候，可以采用 ScheduledExecutorService 的方式来实现。
如果任务量比较大，任务耗时短，无疑使用 HashedWheelTimer 对内存更加友好。
定时任务系统
前面从操作系统时钟源开始，说到时钟中断产生了时钟滴答，所有的定时任务都依赖于此。
软件层面，通过各种有效的算法在节约资源的前提下通过监听时钟滴答来实现任务。
还记得开篇提到我们本篇文章的意图是什么吗，要设计一个高效的定时任务系统。
既然谈到了设计，是不是要先出一版产品需求文档呢。这个真的可以有，我们先提提需求再聊聊方案。
你要的需求设计
定时任务系统的核心功能是什么？既然是第一版，我们不要那些花里胡哨，锦上添花的功能，从本质出发。
我理解应该有三个核心模块：
任务录入：提供录入定时任务的入口，支持最基本的定时任务机制：cron 表达式，自定义执行时间等等方式。
任务调度：通过合适的调度算法从任务库中触发到期的任务以期执行，当然调度系统最好不要直接参数执行，做好自己的事即可。
任务执行：调度系统已经触发了任务，那么可以由专门的执行系统来负责任务执行，执行不会阻塞任务调度，纵然执行有阻塞也是在执行系统中阻塞，保持调度的可用性。
以上 3 个模块就能满足基本的任务系统需求，接下来聊聊实现方案。
技术实现方案
①录入模块实现
一般执行定时任务的场景是：每隔多久执行一次操作，这种在业务系统中最常见的就是使用 cron 表达式来代替，所以录入模块要做到可以解析 cron 表达式即可。
这种录入模式主要是针对后台手动录入任务的场景，对于开发人员来说最优解就是能用代码实现就不去切换鼠标（有同学说能点点鼠标谁还去砌砖）。
所以还需要提供可执行 jar 包用于业务系统集成，方便开发人员通过编码的方式将任务录入到系统。
总结一下录入任务的两种途径：
提供业务系统可集成 jar 包，由开发人员编码录入任务。
提供管理后台界面，提供可配置方式录入任务。
对于业务代码植入式的任务业务服务器启动的时候会通过 jar 包把任务推送过来，对于后台录入的任务那就需要入库保存。
②调度模块实现
在拿到录入模块的定时任务配置信息之后接下来要做的事情：将 cron 表达式变为一个个可执行的时间点。
比如在 Spring 中就已经提供解析 cron 的功能：CronSequenceGenerator 类可以帮我们执行此操作。
有了可执行时间点之后要做的事情就是管理它，让它调度起来。上面我们讨论过的各种调度算法此时可以派上用场。
如果任务密度不是很大，多为固定的定期执行任务，小根堆算法就可以胜任；如果任务密集，很多短期快速执行的任务，可以采用时间轮的方式提高效率。
另外，比如有个任务是 5 分钟执行一次，那么你一次要解析出来多少个可执行的时间点？一天，一周，一个月？
这样肯定是有问题的，目前的实现方案是任务首次启动的时候给出第一次执行的时间，每次执行的时候去计算下次任务开始的时间。
这里有一个点：Java 相关的框架现在实现的方案都是当前任务执行完成之后再计算下次任务开始执行的时间。
如果任务是 5 分钟一次，当前时间是：10：00，第一个任务完成需要 6 分钟，那么第二个任务开始的时间就是：
我们预期是每隔 5 分钟执行一次，事实上除了第一次是按照预期的准点执行以外，后面都会在绝对时间上有延期。
到这里我们解决了两个问题：
解析时间表达式为时间点，如何确认周期性任务的下一个可执行时间点。
将可执行时间点送入调度器中，让时间流动起来。
③任务执行模块
任务录入，任务调度我们都完成了，执行模块才是最后的重头戏。这里我们再细化一下，任务录入不能说只是把任务所属的表达式载入系统就完事，要把任务对象化，达到招手即用的状态。
这里我们把每个任务都封装为一个对象 Job，所有的 Job 都在内存中加载，调度器定义为 Scheduler，把每个可执行时间封装为 Trigger 对象。
Trigger 用于定义调度任务的事件规则，唯一关联一个 Job 并标识当前 Job 的执行状态。
上图就是我们的极简版定时任务系统核心功能，怎么样，麻雀虽小，五脏俱全。该有的功能一样不少，不该有的功能一个都没有。
到这里为止我们已经输出了极简版定时任务调度系统的核心设计和实现方案，依据这个方案你可以实现定时任务调度系统的单机版核心功能。
我们先不提加需求的问题，先来个高可用的问题，上面的方案是将任务加载到一台机器的内存中定时执行，那么如果要实现高可用，多台机器的情况任务如何防止多次执行呢？
很显然上面的方案肯定是行不通了，下面我们开始扩容。
高可用
回答高可用的问题先说目前的思路：单机纯内存抗所有任务。要做高可用必然会大于等于 2 台机器。
那么两台机器都执行任务必然会重复运行，该用什么方案在多机环境中可以统一管理，统一调度，统一运行任务呢？
方案一：传统方案-数据库（独占锁）
任务触发的关键在于 Trigger 触发器，我们只用管住 Trigger 的手让它别乱动 task 就好，基于数据库操作的话，保证任一时刻某个 Trigger 只会被触发一次即可。这里可以使用行级锁来实现。
某台机器执行到这个 Trigger 的时候向数据库插入一条 Trigger 记录并持有该锁，那么其余机器即使遇到了这个任务也不能执行。
方案二：分布式组件特性支持（分布式锁）
一般来说数据库肯定是值得信任的，但是面对实施要求高，任务执行频繁的场景的时候，数据库又是不敢信任的，数据库有一定的并发瓶颈。
要保证同一时刻的唯一性，除了数据库的锁特性以外，分布式组件肯定也支持，比如 Zookeeper，ETCD 等等。
可以利用 ZK 的临时节点性质，同一个任务注册一个唯一的节点，哪个机器抢到这个节点谁就来执行任务即可。
产品加需求
基础功能我们已经完成，高可用也做到了，上线一段时间，产品觉得的整点幺蛾子啊，不然 KPI 咋整。
①新增功能
基于事件分发的任务机制：可能有一些任务是基于特定的条件触发，这种任务在分布式环境下一般自己实现分布式锁来实现，那么任务系统既然提供分布式特性也可以实现分布式锁的功能。
所以对于这一类任务完全可以交给任务系统来做，把它当成一次性触发的任务。
②新增特性
任务终止：如果某个任务因为业务需求不再执行，那么是否可以不发布的条件下终止该任务呢？这个时候任务终止的功能就很重要，产品经理暗暗自喜，老板加鸡腿。
任务依赖：B 任务依赖 A 任务的结果才能执行，所以要提供任务之间的级联操作。
任务分片：如果我们有 3 台执行任务的机器，有 10 个每 5s 执行一次的定时任务，恰恰每个任务都打到第一台机器。它累如黄牛的时候另外两台还在晒太阳这岂不是资源的浪费嘛。
为了避免任务集中到某一台机和提高资源利用率，我们需要一种将任务均衡分配到当前所有可执行机器的能力，这就是所谓的分片机制。
常用的分片算法有如下：
平均分配算法：
如果有 3 个任务实例，分成 9 片，每个实例对应到的分片就是：1=[1,2,3]，2=[4,5,6]，3=[7,8,9]。
如果有 3 个任务实例，分成 8 片，每个实例对应到的分片就是：1=[0,1,6]，2=[2,3,7]，3=[4,5]。
如果有 3 个任务实例，分成 10 片，每个实例对应到的分片就是：1=[0,1,2,9]，2=[3,4,5]，3=[6,7,8]。
根据作业名 hash 值决定根据 IP 升序/降序算法：
如果有 3 个任务实例分别为 1，2，3，作业名称对应的 hash 值如果为奇数就按照 IP 升序寻找机器执行，作业名称对应的 hash 值如果为偶数就按照 IP 降序寻找机器执行。这种算法最多要求最多只有两个分片，即只有两台机器参与执行。
轮询算法：
轮询的原理就很简单，基于可执行机器依次执行。
任务日志：日志功能肯定不可少，检测任务执行成功与否，任务执行记录、时长，统计任务系统每日任务量等等。
③新增容错机制
容错机制：任务执行失败，可能是任务本身逻辑问题，也可能是外部条件，所以可以设置一些容错机制，给它一次重试的机会。
故障转移：集群中如果某一台机器发生了故障，它如果还在注册中心注册，那么任务会被该机器执行，很显然如果仅有失败重试策略，那么这个任务永远都不会执行成功。
首先需要心跳检测机制，检测活动机器是否健康；其次需要在重试失败之后做任务转移操作，防止多次失败仍在同一台机器吊死。
手动触发：如果万不得已遇到任务没有执行到的情况 ，那么是否要提供手动触发的机制呢？我想产品经理这种人精肯定不想背锅，所以你还是做吧！
后话
做完上面的功能之后，产品经理躺在他的折叠床上打着呼噜鼻子不时的还冒几个泡安心的睡着了。
程序员小哥整苦逼的构思这些功能该如何实现，是给 3 天还是给 3 个月，一场人月神话即将上演。
目前圈子里比较流行的定时任务系统有 Quartz，XXLJob，Elastic Job 等，实现方式不会脱离上文描述的范围。
这些都是程序员自己没事捣鼓的实用型系统，有需求就有产出，有方向就有动力。
工作之余大家也可以自己思考目前在写的东西是否可以抽象为大层次的一个功能，简单说，你是否也能整出个中台来。
在这个万物皆中台的时代，大家不遗余力的照虎画瓢，虽说可能画出个四不像，起码对于写代码的人，抽象能力是得到了锻炼。
作者：杨越
简介：目前就职广州欢聚时代，专注音视频服务端技术，对音视频编解码技术有深入研究。日常主要研究怎么造*和维护已经造过的*，深耕直播类 APP 多年，对垂直直播玩法和应用有广泛的应用经验，学习技术不局限于技术，欢迎大家一起交流。
参考阅读：
技术原创及架构实践文章，欢迎通过公众号菜单「联系我们」进行投稿。
高可用架构
改变互联网的构建方式
长按二维码 关注「高可用架构」公众号
上一篇： JFinal和JBoot创建一个定时任务
下一篇： 贪吃蛇游戏（Java）