【.com原稿】今天想和大家讨论一个听起来很简单的话题：定时任务的机制。图片来自Pexels，无非就是一个定时器，到了指定的时间就会开始运行。太年轻了，如果就这么简单，我要说什么？如果有几万个定时任务，你的定时器应该怎么设计？如果任务A执行完后任务B将执行，你将如何安排它？如果几十台机器要同时处理一些任务，你怎么设计？带着这些看似不简单的问题，我们开始了时间旅行。操作系统的时间系统应用部署在操作系统上，定时任务依赖于操作系统的时钟。由于大多数服务器都部署在Linux上，我们只讨论Linux时间系统，Windows服务器上不要打我。大多数PC中都有两种时钟源，它们分别称为RTC（RealTimeClock，实时时钟）和OS（操作系统）时钟。RTCRTC（RealTimeClock，实时时钟）也叫CMOS时钟。它是PC主板上的一块芯片（或时钟电路）。它由电池供电，即使系统断电也能保持日期和时间。因为它独立于操作系统，所以也被称为硬件时钟。它为整个计算机提供了计时标准，是最原始、最底层的时钟数据。OS时钟OS时钟由PC主板上的定时/计数芯片（8253/8254）产生，芯片的运行由操作系统控制。OS时钟的基本单位是芯片的计数周期。操作系统在开机时获取RTC中的时间数据初始化OS时钟，然后通过计数芯片递减计数形成OS时钟，所以OS时钟不是本质意义上的时钟，应该叫做柜台。OS时钟只有在开机时才有效，完全受操作系统控制，所以又称为软时钟或系统时钟。时钟中断Linux操作系统时钟的物理原因是可编程定时器/计数器产生的输出脉冲。这个脉冲被送到CPU触发一个中断请求信号，我们称之为时钟中断。在Linux中，全局变量jiffies用于表示自系统启动以来的时钟滴答数。每个时钟滴答，时钟中断都会被执行。时钟中断执行的频率很高：每秒100次（Linux设计者定义一个时钟节拍（tick）为10ms），时钟中断的主要工作是处理所有与时间相关的信息，并决定是否执行调度程序。所有与时间相关的信息包括系统时间、进程时间片、延迟、CPU时间、各种定时器。进程更新后的时间片为进程调度提供了依据，进而在时钟中断返回scheduler时决定是否执行。在单处理器系统上，每个滴答只发生一次时钟中断。在相应的中断处理程序中完成更新系统时间、统计、定时器等所有功能。在多处理器系统中，时钟中断实际上分为两部分：全局时钟中断，在系统中每个滴答只发生一次。相应的中断处理程序用于更新系统时间和统计系统负载。本地时钟中断，在系统中的每个CPU上每个时钟周期发生一次。相应的中断处理程序用于统计相应CPU和CPU上运行的进程的时间，并触发相应CPU上的定时器。因此，在多处理器系统中，每个tick和每个CPU都必须处理一个本地时钟中断；此外，其中一个CPU还必须处理一个全局时钟中断。时钟中断更新系统时间的应用：在Linux内核中，全局变量jiffies_64用于记录系统启动以来经历的滴答次数。每次进入时钟中断处理程序（对应多处理器系统中的全局时钟中断）时，jiffies_64的值都会更新。一般情况下jiffies_64总是每次加1。但是，有可能丢失时钟中断。内核中某些临界区是不能被中断的，所以在进入临界区之前需要屏蔽中断。当去掉中断掩码后，硬件只能告诉内核时钟中断是否发生，而不能告诉内核发生了多少次。因此，在极端情况下，中断屏蔽时间可能会超过1个滴答，导致时钟中断丢失。如果计算机上的时钟振荡器精度较高，Linux内核可以读取振荡器中的计数器，将上次读取的值与当前值进行比较，判断中断是否丢失；如果发现中断丢失，则当前中断处理程序将jiffies_64递增相应的count。但是如果振荡器硬件不允许（没有提供计数器，或者不允许读取计数器，或者精度不够），内核就没有办法知道时钟中断是否丢失。内核中的全局变量xtime用于记录当前时间（从1970-01-01开始的秒数，这一秒的纳秒数）。xtime的初始值在内核启动时从RTC中读取。时钟中断处理程序更新jiffies_64的值后，它会更新xtime的值。通过将jiffies_64的当前值与上一次的值进行比较（如前所述，差异可能大于1），确定应该更新多少xtime。系统调用gettimeofday（对应库函数time和gettimeofday）用于读取xtime变量，以便用户程序获取系统时间。实现定时器：既然知道每个tick为10ms，那么用tick做定时任务统计比较好。无论是内核还是应用系统，其实都有大量的定时任务需求。这些定时任务的类型各不相同，但都依赖于滴答。操作系统实现定时任务的已知方法有哪些？①一种简单有效的方法来维护一个有过期时间的任务列表。在一个全局链表中维护一个定时任务链。每次tick中断来了，遍历链表，找到过期的任务。如果任务按expire排序，每次只需要找到链头的元素，时间复杂度为O(1)。这种方法对于早期的Linux系统是没有问题的。随着当前系统复杂度的逐渐变化，已经无法支撑当今网络流量激增时代的需求。②Timing-Wheel算法Timing-Wheel简单易懂。上图中有n个桶，每个桶代表一秒，当前桶代表当前秒到来后要触发的事件。每个桶对应一个链表，链表存储当前时刻需要处理的事件。那么这里就有问题了。如果有定时任务需要在16小时后执行，则秒数为57600s。我们的时间轮需要这么多桶吗？数以万计的记忆也是一种流失。为了减少bucket的数量，timewheel算法提供了一个扩展算法，即Hierarchytimewheel。等级制度很好理解，等级制度。既然一个时间轮可能会导致桶太多，为什么我们不能得到更多的轮子来代替时、分、秒呢？轮子是根据小时、分钟和秒实现的，每个轮子都维护自己的光标。在Hour数组中，每个桶代表一个小时。Minute数组中的每个桶代表1分钟，Second数组中的每个桶代表1秒。使用分层时间轮，我们只需要24+60+60=144个桶来表示所有时间。完全模拟时钟的使用，秒轮每完成60个桶，需要与分轮联动转动一格。同样，当小轮转动60个桶时，也必须与时轮联动转动一步。③维护一个基于小根堆算法的定时任务。小根堆的本质是满足除根节点以外的每个节点都不小于其父节点的堆。基于这个性质，从根节点开始遍历每个节点可以保证得到一个最小优先级队列。然后应用到定时器上，每次只需要获取当前最小堆的根节点，看是否超时。最小堆的插入时间复杂度为O(lgn)，获取头节点的时间复杂度为O(1)。开箱即用的定时器单机版timer①cron/crontabcron是Linux中的一种定时任务机制。cron代表后台运行的守护进程，crontab是设置cron的工具，所有定时任务都写在crontab文件中。cron计划/etc/crontab文件的内容。crontab的命令由时间+动作组成，它的时间有分、时、日、月、周五。这里要注意，最小单位是分钟，默认小于秒。大家也给出了各种精确到秒的解法。有兴趣的可以搜索一下。/etc/crontab文件中的每一行代表一个任务，其格式为：minutehourdaymonthdayofweekuser-namecommand*minute——分钟，0到59之间的任意整数*hour——小时，0到23之间的任意数字Integer*day——日期，任意1到31之间的整数（如果指定月份，则必须是当月的有效日期）*month——月份，1到12之间的任意整数（或使用月份的英文缩写，如jan、feb等。)*dayofweek—week，0到7的任意整数，其中0或7代表Sunday（或使用星期的英文缩写，如sun、mon等）*user-name-user，脚本给什么用户execute*command——要执行的命令（命令可以是ls/proc>>/tmp/proc之类的命令，也可以是执行自己写的脚本的命令。)②JDK提供的Timer：TimerTimer的思路很简单，基于最小堆方案创建一个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(ThreadFactorythreadFactory,//类似于Clock中的updater，负责创建Worker线程。longtickDuration,//时间尺度之间的持续时间（默认100ms），通俗的说就是多久一次tick++once.TimeUnitunit,//tickDuration的单位.intticksPerWheel//类似于Clock中轮子的长度（默认512）；另外，为了不让bucket无休止的增加，这里采用了round的概念。时间：回合时间=ticksPerWheel*tickDuration。如果只有512个桶，当前休眠时间超过一轮，则加上相应轮次代表当前休眠时间。HashedWheelTimer中主要有几个成员：HashedWheelTimer类本身主要负责启动Worker线程，添加任务等。Worker：内部负责添加任务，累积tick，执行任务等HashedWheelTimeout：任务的封装类，链表结构，负责保存截止时间，轮数等HashedWheelBucket：轮子数组的元素，负责存储HashedWheelTimeout链表。Worker线程是HashedWheelTimer的核心，主要负责每经过tickDuration时间就累积一个tick。它还负责执行过期的超时任务，并将超时任务添加到指定的轮子。添加Timeout任务时，会根据设置的时间计算等待时间的长短，根据时间的长短计算要经过多少个tick，再根据tick的个数计算已经过了多少轮，最后完成任务。地点。对于这种时间轮，如何遍历判断任务的到期时间呢？每次票到达时，必须遍历每个桶以确定是否有任何桶到期。所以这种方法要求桶的数量尽量不要太多。如果太多，每次遍历都会耗费很长时间。另外，每次遍历，难免会有很多空转，也是一种资源浪费。④Kafka中的时间轮：TimingWheelNetty中的时间轮采用单轮+轮的方式，Kafka采用多轮的方式。上面说了，多轮模式如果用时分秒来表示的话，每一轮需要的bucket很小，轮次遍历会很快。但是多轮也会带来另外一个问题，就是轮次的维护：比如有一个定时任务是1*60*60+50=36050s。这时，分秒轮需要同时维持这个任务。当这个任务继续进行，只剩下59s的时候，分轮就不需要维护它的信息了，只剩下秒轮维护，落轮的概念就出现在这里了。单机计时机制对比上面简单的描述了各个实现方案，简单对比一下就可以得出结论，Timer的实现方案无疑是最差的。阻塞和异常退出两大“罪名”，无疑让现代程序员背不起犯错被老板责骂的罪魁祸首。ScheduledExecutorService使用线程池异步执行任务。当任务量很大时，如果设置一个优先级的可执行线程数，无疑会阻塞任务。幸运的是，有很多可执行线程。HashedWheelTimer是为桶设计的。如果采用多轮方式，则不受任务量的限制。当任务量很大时，维护数组的成本远低于维护堆的成本。但是，如果任务量不大，时间轮还是需要扫描整个系统，才会出现空转。这种空载无疑是一种资源浪费。因此，如果针对使用场景进行编程：如果当前要运行的定时任务耗时较长，任务量又不是那么大，可以使用ScheduledExecutorService来实现。如果任务量比较大，任务时间比较短，使用HashedWheelTimer进行内存无疑是更友好的。定时任务系统从操作系统的时钟源开始。当涉及到时钟中断产生的时钟节拍时，所有的定时任务都依赖于此。在软件层面，通过各种有效的算法，在节省资源的前提下，通过监控时钟滴答来实现任务。还记得我们文章开头提到的意图，设计一个高效的定时任务系统。既然说了设计，是不是要先出一版产品需求文档呢？这个还真可以，先提需求再说方案吧。你要设计的定时任务系统的核心功能是什么？由于是第一个版本，我们不想要那些花里胡哨和锦上添花的东西。让我们从本质开始。我理解应该是三个核心模块：任务入口：提供进入定时任务的入口，支持最基本的定时任务机制：cron表达式，自定义执行时间等任务调度：通过任务库触发到期任务适合执行的调度算法。当然，调度系统最好不要直接执行参数，自己做就好。任务执行：调度系统触发了任务，可以有专门的执行系统负责任务的执行。执行不会阻塞任务调度。即使执行被阻塞，也会阻塞在执行系统中，以维持调度的可用性。以上三个模块可以满足基本的任务系统需求，接下来说说实现方案。技术实现方案①输入模块实现定时任务一般执行的场景是：多久执行一次操作。这是业务系统中最常见的使用cron表达式代替的方式，所以输入模块必须能够解析cron表达式而已。这种输入方式主要针对后台手动输入任务的场景。对于开发者来说，最好的方案是不用切换鼠标，用代码实现（有同学说，谁会点鼠标，谁就搬砖）。因此，也需要为业务系统集成提供一个可执行的jar包，方便开发者通过编码将任务录入到系统中。总结两种进入任务的方式：提供一个可以和业务系统集成的jar包，让开发者编码进入任务。提供管理后台界面，提供可配置的任务进入方式。对于业务代码中嵌入的任务，业务服务器启动时会通过jar包推送任务，后台进入的任务需要保存在库中。②调度模块在获取到输入模块的定时任务配置信息后，执行接下来要做的事情：将cron表达式逐一转换为可执行的时间点。比如Spring中已经提供了解析cron的功能：CronSequenceGenerator类可以帮我们做这件事。有了可执行的时间点之后要做的就是管理它，让它被调度。我们上面讨论的各种调度算法在这个时候就可以派上用场了。如果任务密度不是很高，而且大部分任务是固定的、定时执行的，小根堆算法可以胜任；如果任务密集，短时间内快速执行的任务很多，可以使用时间轮来提高效率。另外，比如有一个5分钟执行一次的任务，你一次需要分析多少个可执行的时间点？一天、一周、一个月？这绝对是个问题。目前的实现是在任务第一次启动时给定第一次执行的时间，每次执行时计算下一个任务的开始时间。这里有一点：Java相关框架目前实现的解决方案是在当前任务完成后计算下一个任务开始执行的时间。如果任务是每5分钟执行一次，当前时间是：10:00，完成第一个任务需要6分钟，那么第二个任务开始：我们期望它每5分钟执行一次，其实除了第一次除了按预期被执行，后面绝对时间会有延迟。至此我们解决了两个问题：如何将时间表达式解析为时间点，以及如何确定周期任务的下一个可执行时间点。将可执行时间点发送给调度器，让时间流转。③我们完成了任务执行模块的任务入口和任务调度，执行模块是最后的重头戏。让我们在这里细化一下。任务入口不能说只是将任务所属的表情加载到系统中。需要将任务对象化，达到即用状态。这里我们把每个任务封装成一个对象Job，所有的Jobs都加载到内存中，调度器定义为Scheduler，每个可执行的时间都封装成一个Trigger对象。Trigger用于定义调度任务的事件规则，与一个Job唯一关联，标识当前Job的执行状态。上图展示了我们极简定时任务系统的核心功能。这个怎么样？麻雀虽小，五脏俱全。该有的功能相当多，不该有的功能没有一个。至此我们已经导出了定时任务调度系统最小版本的核心设计和实现方案。按照这个方案，就可以实现单机版定时任务调度系统的核心功能。需求增长的问题先不说，先说高可用。上面的解决方案是将任务加载到一台机器的内存中，定时执行。如果我们要实现高可用，如何防止多机情况下的多任务呢？第二次处决呢？显然，上面的方案肯定行不通，那我们就开始扩容吧。高可用要回答高可用的问题，先说说目前的思路：单机纯内存抗所有任务。要高可用，必须大于等于2台机器。那么，如果两台机器都执行任务，必然会重复运行。应该使用什么解决方案来管理、调度和运行多机环境中的任务？方案一：传统方案——触发数据库（排他锁）任务的关键在于Trigger对于触发器，我们只需要握住Trigger的手，让它不至于把任务弄乱。基于数据库操作，保证某个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].根据作业名的哈希值判断基于IP升序/降序算法：如果有3个任务实例，分别为1、2、3，如果作业名对应的哈希值为奇数，则查找按照IP升序执行的机器，作业名对应的hash值如果是偶数，则按照IP降序查找执行的机器。该算法最多需要两个分片，即只有两台机器参与执行。轮询算法：轮询的原理很简单，就是根据可执行的机器依次执行。任务日志：日志功能肯定是少不了的，检测任务是否执行成功，记录任务执行情况，时长，统计任务系统每天的任务量等等。③新的容错机制容错机制：任务执行失败可能是任务本身的逻辑问题，也可能是外部条件，所以可以设置一些容错机制，给它重试的机会。故障转移：如果集群中的一台机器发生故障，如果它还在注册表中注册，则任务将由该机器执行。显然，如果只有失败重试策略，那么这个任务永远不会执行成功。首先需要一个心跳检测机制来检测主用机器是否健康；其次，重试失败后需要进行任务转移操作，防止同一台机器挂多个故障。手动触发：如果需要遇到任务没有执行的情况，是否需要提供手动触发机制？我想一个产品经理肯定不想背锅的，你就该背锅！完成以上功能后，产品经理躺在自己的折叠床上，不时打呼噜，鼻子里冒出几个泡泡，安详地睡着了。程序员小哥苦苦构思如何实现这些功能，给它3天还是3个月，一场人月神话即将上演。目前圈内比较流行的定时任务系统有Quartz、XXLJob、ElasticJob等，实现方式不会脱离上述范围。这些是程序员可以自己摆弄的实用系统。有需求就有输出，有方向就有动力。工作之余，你也可以想想，你现在写的东西，能不能抽象成一个大层次的函数。简单的说，是不是也可以打造一个中间平台。在这个一切都在平台中间的时代，每个人都不遗余力地画出一幅如虎添翼的图画。虽然可能画出四种不同的图像，但至少对于写代码的人来说，他们的抽象能力得到了锻炼。作者：杨越简介：目前就职于广州欢聚时代，专注于音视频服务器技术，对音视频编解码技术有深入研究。我主要研究如何制造轮子和维护已经造好的轮子。深耕直播APP多年。在垂直直播玩法和应用方面有丰富的应用经验。学习技术不局限于技术。欢迎与我们交流。编辑：陶佳龙征稿：如有意向投稿或寻求报道，请联系editor@51cto.com【原创稿件请注明原作者和出处为.com，合作网站转载】
