◆绝对时间和相对时间

定时任务一般有两种：

约定一段时间后执行。

约定某个时间点执行。

聪明的你会很快发现，这两者之间可以相互转换，比如给你个任务，要求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. 沿着时间刻度前进 ## 同一时刻存在多个任务 上面说的是同一个时刻只有一个任务需要执行的情况，更通用的情况显然是同一时刻可能需要执行多个任务，比如每天上午九点除了生成报表之外，还需要执行发送邮件的任务，需要执行创建文件的任务，还需执行数据分析的任务等等，于是你刚才可能就比较好奇的时间轮的数据结构到现在可能更加好奇了，那我们先来说说时间轮的数据结构吧。### 时间轮的数据结构 首先，时钟可以用数组或者循环链表表示，这个每个时钟的刻度就是一个槽，槽用来存放该刻度需要执行的任务，如果有多个任务需要执行呢？每个槽里面放一个链表就可以了，就像下面图中这样：

同一时刻存在多个任务时，只要把该刻度对应的链表全部遍历一遍，执行（扔到线程池中异步执行）其中的任务即可。

时间刻度不够用怎么办？

如果任务不只限定在一天之内呢？比如我有个任务，需要每周一上午九点执行，我还有另一个任务，需要每周三的上午九点执行。一种很容易想到的解决办法是：

◆增大时间轮的刻度

一天24个小时，一周168个小时，为了解决上面的问题，我可以把时间轮的刻度（槽）从12个增加到168个，比如现在是星期二上午10点钟，那么下周一上午九点就是时间轮的第9个刻度，这周三上午九点就是时间轮的第57个刻度，示意图如下：

仔细思考一下，会发现这中方式存在几个缺陷：

时间刻度太多会导致时间轮走到的多数刻度没有任务执行，比如一个月就2个任务，我得移动720次，其中718次是无用功。

时间刻度太多会导致存储空间变大，利用率变低，比如一个月就2个任务，我得需要大小是720的数组，如果我的执行时间的粒度精确到秒，那就更恐怖了。

于是乎，聪明的你脑袋一转，想到另一个办法：

列表中的任务中添加round属性

这次我不增加时间轮的刻度了，刻度还是24个，现在有三个任务需要执行，

任务一每周二上午九点。

任务二每周四上午九点。

任务三每个月12号上午九点。

比如现在是9月11号星期二上午10点，时间轮转一圈是24小时，到任务一下次执行（下周二上午九点）,需要时间轮转过6圈后，到第7圈的第9个刻度开始执行。

任务二下次执行第3圈的第9个刻度，任务三是第2圈的第9个刻度。

示意图如下：

时间轮每移动到一个刻度时，遍历任务列表，把round值-1，然后取出所有round=0的任务执行。

这样做能解决时间轮刻度范围过大造成的空间浪费，但是却带来了另一个问题：时间轮每次都需要遍历任务列表，耗时增加，当时间轮刻度粒度很小(秒级甚至毫秒级)，任务列表又特别长时，这种遍历的办法是不可接受的。

当然，对于大多数场景，这种方法还是适用的。

有没有既节省空间，又节省时间的办法呢？答案是有的，正如《Hashed and Hierarchical Timing Wheels》标题中提到的，有一种分层时间轮，可以解决做到既节省空间，又节省时间：

◆分层时间轮

分层时间轮是这样一种思想：

针对时间复杂度的问题：不做遍历计算round，凡是任务列表中的都应该是应该被执行的，直接全部取出来执行。

针对空间复杂度的问题：分层，每个时间粒度对应一个时间轮，多个时间轮之间进行级联协作。

第一点很好理解，第二点有必要举个例子来说明：

比如我有三个任务：

任务一每周二上午九点。

任务二每周四上午九点。

任务三每个月12号上午九点。

三个任务涉及到四个时间单位：小时、天、星期、月份。

拿任务三来说，任务三得到执行的前提是，时间刻度先得来到12号这一天，然后才需要关注其更细一级的时间单位：上午9点。

基于这个思想，我们可以设置三个时间轮：月轮、周轮、天轮。

月轮的时间刻度是天。

周轮的时间刻度是天。

天轮的时间刻度是小时。

初始添加任务时，任务一添加到天轮上，任务二添加到周轮上，任务三添加到月轮上。

三个时间轮以各自的时间刻度不停流转。

当周轮移动到刻度2(星期二)时，取出这个刻度下的任务，丢到天轮上，天轮接管该任务，到9点执行。

同理，当月轮移动到刻度12(12号)时，取出这个刻度下的任务，丢到天轮上，天轮接管该任务，到9点执行。

这样就可以做到既不浪费空间，有不浪费时间。

整体的示意图如下所示：

◆空间利用率以及写性能高的磁盘数据组织

时间轮的思想应用范围非常广泛，各种操作系统的定时任务调度，Crontab,还有基于java的通信框架Netty中也有时间轮的实现，几乎所有的时间任务调度系统采用的都是时间轮的思想。

至于采用round型的时间轮还是采用分层时间轮，看实际需要吧，时间复杂度和实现复杂度的取舍。

BlockHandle

offset:
varint64
size:
varint64
<beginning_of_file>
[data block 1]
3
[data block 2]
..
5
[data block N]
[meta block am filter
[meta block 2: stats 块]
[meta block 3: 压缩字典块]
[meta block 4:范围删除块]
...
(我们以后可能会加入新的元数据块）[meta block K:未来拓展块]
[metaindex block]
[index block]
(定长脚注，从file_size-sizeof(Footer)[Footer]
开始）
<end_of_file>

. 键值对序列在文件中是以排序顺序排列的，并且切分成了一序列的数据块。这些块在文件头一个接一个地排列。每个数据块都根据b1ockbuilder.cc的代码进行编排（参考文件中的注释）,然后选择性压缩（compress);
. 数据块之后，我们存出一系列的元数据块。支持的元数据块类型在下面描述。更多的数据块类型可能会在以后加入。同样的，每个元数据块都根据blockbuilder.cc的代码进行编排(参考文件中的注释）,然后选择性压缩（compress);
. 一个 metaindex 块对每个元数据块都有一个对应的入口项， key 为 meta 块的名字，值是个 BlockHandle,指向具体的元数据块；

·一个索引块，对每个数据块有一个对应的入口项，key是一个string,该string>=该数据块的最后一个key,并且小于下一个数据块的第一个key。值是数据块对应的BlockHandle。如果索引类型 IndexType 是kTwoLevellndexSearch,这个索引块就是索引分片的第二层索引，例如，每个入口指向另一个索引块，该索引块包含每个数据块的索引；
. 在文件的最后，有一个定长的脚注，包含metaindex以及索引块的BlockHandle,同时还有一个魔数：

metaindex_handle: char[p];
// metaindex的Block handle
2
ismlex_handle:
char[q];
// 索引块的Block handle
3
padding:
char[40-p-q];//填充0以达到固定大小
4
(40==2*BlockHandle:: kMaxEncodedLength)
magic:
fixed64;
//0x88e241b785f4cff7(小端）
1
//
5

来源：

https://www.toutiao.com/article/7083100059679588897/?log_from=92c6a389daff5_1650592532467

 IT大咖说  |  关于版权 

感谢您对IT大咖说的热心支持！