江苏龙网

  1. 主页 > 生活百科 > >

那些惊艳的算法—时间轮算法

时间轮算法

从定时任务说起自然界中定时任务无处不在，太阳每天东升西落，候鸟的迁徙，树木的年轮，人们每天按时上班，每个月按时发工资、交房租，四季轮换，潮涨潮落，等等，从某种意义上说，都可以认为是定时任务 。
大概很少有人想过，这些“定时”是怎样做到的 。当然，计算机领域的同学们可能对此比较熟悉，毕竟工作中的定时任务也是无处不在的：每天凌晨备份一波数据库，每天9点发一波邮件，每天定时发送任务通知 。
至于怎么实现的？很简单啊，操作系统的crontab，spring框架的quartz,实在不行JAVA自带的ScheduledThreadPool、c#的System.Timers都可以很方便的做到定时任务的管理调度 。
初识时间轮大概去年的时候，业务需要实现一个时间调度的工具，定时生成报表，同组的哥们没有采用任何框架，而是想了一个很取巧的办法：
启动时从DB读取cron表达式解析，算出该任务下次执行的时间 。
下次执行的时间 - 当前时间 = 时间差 。
向ScheduleThreadPool线程池中提交一个延迟上面算出来的时间差的执行的任务 。
任务执行时，算一下这个任务下次执行的时间，算时间差，提交到线程池 。
当任务需要取消时，直接调用线程池返回的Future对象的cancel()方法就行了 。
当时稍微想了一ScheduleThreadPool是怎么做到定时执行提交过来的任务的，大概有个模糊的概念，后来就把这事忘了 。再后来，一次在博客园上看到一篇文章，讲了一种叫做时间轮的定时任务调度思想，感觉想法很不错，当年那个模糊的概念似乎清晰了很多，再后来，一个偶然的机会，网上搜了一下，竟然有一篇专门讲解时间轮算法的论文，顿时兴奋无比，赶紧打印下来，在上班的地铁上读了半个月，总算读完了 。
戳这里下载：《Hashed and Hierarchical Timing Wheels》
论文中的思路很简单但也十分巧妙，对算法不断地改进对比，各种操作系统，框架中的基于时间的调度算法都是基于时间轮的思想实现的 。下面我们来看看，这个神奇的时间轮到底是怎样实现定时任务的调度的 。
绝对时间和相对时间
定时任务一般有两种：
约定一段时间后执行 。
约定某个时间点执行 。
聪明的你会很快发现，这两者之间可以相互转换，比如给你个任务，要求12点执行，你看了一眼时间，发现现在是9点钟，那么你可以认为这个任务三个小时候执行 。
那么我们换个说话，给你个任务让你3个小时后执行，你看了一眼现在是9点钟，那么你当然可以认为这个任务12点钟执行 。
我们先来考虑一个简单的情况，你接到三个任务A、B、C（都转换成绝对时间），分别需要再3点钟，4点钟和9点钟执行，正当百思不得其解时，不经意间你瞅了一眼墙上的钟表，瞬间来了灵感，如醍醐灌顶，茅塞顿开：

那些惊艳的算法—时间轮算法

文章插图
 
如上图中所示，我只需要把任务放到它需要被执行的时刻，然后等着时针转到这个时刻时，取出该时刻放置的任务，执行就可以了 。这就是时间轮算法最核心的思想了 。什么？时针怎么转？ while-true-sleep 下面让我们一点一点增加复杂度 。## 需要重复执行多次的任务 多数定时任务是需要重复执行，比如每天上午9点执行生成报表的任务 。对于重复执行的任务，其实我们需要关心的只是下次执行时间，并不关心这个任务需要循环多少次，还是那每天上午9点的这个任务来说 。1. 比如现在是下午4点钟，我把这个任务加入到时间轮，并设定当时针转到明天上午九点(该任务下次执行的时间)时执行 。2. 时间来到了第二天上午九点，时间轮也转到了9点钟的位置，发现该位置有一个生成报表的任务，拿出来执行 。3. 同时时间轮发现这是一个循环执行的任务，于是把该任务重新放回到9点钟的位置 。4. 重复步骤2和步骤3 。如果哪一天这个任务不需要再执行了，那么直接通知时间轮，找到这个任务的位置删除掉就可以了 。由上面的过程我们可以看到，时间轮至少需要提供4个功能： 1. 加入任务 2. 执行任务 3. 删除任务 4. 沿着时间刻度前进 ## 同一时刻存在多个任务 上面说的是同一个时刻只有一个任务需要执行的情况，更通用的情况显然是同一时刻可能需要执行多个任务，比如每天上午九点除了生成报表之外，还需要执行发送邮件的任务，需要执行创建文件的任务，还需执行数据分析的任务等等，于是你刚才可能就比较好奇的时间轮的数据结构到现在可能更加好奇了，那我们先来说说时间轮的数据结构吧 。### 时间轮的数据结构 首先，时钟可以用数组或者循环链表表示，这个每个时钟的刻度就是一个槽，槽用来存放该刻度需要执行的任务，如果有多个任务需要执行呢？每个槽里面放一个链表就可以了，就像下面图中这样：


推荐阅读


上一篇：Oracle常用语句

下一篇：新被芯枕芯不洗能直接用吗 为什么枕芯不能洗