一个高效的定时任务系统
今天想跟大家一起探讨一个听起来很简单的话题：定时任务机制。
无非就是一个计时器，到了指定时间就开始跑呗。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 吗。几万个对内存也是一种损耗。
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 的命令构成为时间+动作，其时间有分、时、日、月、周五种。
这里要注意，最小单位为分钟，默认是不到秒的级别，大家也给出了各种精确到秒的方案，有兴趣的可以搜索一下。
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(
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 链表。
单机定时机制对比
如果当前待运行的定时任务属于耗时长一点，任务量也不是那么大的时候，可以采用 ScheduledExecutorService 的方式来实现。
如果任务量比较大，任务耗时短，无疑使用 HashedWheelTimer 对内存更加友好。
定时任务系统
你要的需求设计
定时任务系统的核心功能是什么？既然是第一版，我们不要那些花里胡哨，锦上添花的功能，从本质出发。
任务录入：提供录入定时任务的入口，支持最基本的定时任务机制：cron 表达式，自定义执行时间等等方式。
任务调度：通过合适的调度算法从任务库中触发到期的任务以期执行，当然调度系统最好不要直接参数执行，做好自己的事即可。
任务执行：调度系统已经触发了任务，那么可以由专门的执行系统来负责任务执行，执行不会阻塞任务调度，纵然执行有阻塞也是在执行系统中阻塞，保持调度的可用性。
技术实现方案
提供业务系统可集成 jar 包，由开发人员编码录入任务。
提供管理后台界面，提供可配置方式录入任务。
解析时间表达式为时间点，如何确认周期性任务的下一个可执行时间点。
将可执行时间点送入调度器中，让时间流动起来。
Trigger 用于定义调度任务的事件规则，唯一关联一个 Job 并标识当前 Job 的执行状态。
上图就是我们的极简版定时任务系统核心功能，怎么样，麻雀虽小，五脏俱全。该有的功能一样不少，不该有的功能一个都没有。
高可用
某台机器执行到这个 Trigger 的时候向数据库插入一条 Trigger 记录并持有该锁，那么其余机器即使遇到了这个任务也不能执行。
可以利用 ZK 的临时节点性质，同一个任务注册一个唯一的节点，哪个机器抢到这个节点谁就来执行任务即可。
产品加需求
如果有 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]。
如果有 3 个任务实例分别为 1，2，3，作业名称对应的 hash 值如果为奇数就按照 IP 升序寻找机器执行，作业名称对应的 hash 值如果为偶数就按照 IP 降序寻找机器执行。这种算法最多要求最多只有两个分片，即只有两台机器参与执行。
轮询的原理就很简单，基于可执行机器依次执行。
后话
作者：杨越
简介：目前就职广州欢聚时代，专注音视频服务端技术，对音视频编解码技术有深入研究。日常主要研究怎么造轮子和维护已经造过的轮子，深耕直播类 APP 多年，对垂直直播玩法和应用有广泛的应用经验，学习技术不局限于技术，欢迎大家一起交流。
技术原创及架构实践文章，欢迎通过公众号菜单「联系我们」进行投稿。
长按二维码 关注「高可用架构」公众号