孙玄：毕业于浙江大学，现任转转公司首席架构师，技术委员会主席，大中后台技术负责人（交易平台、基础服务、智能客服、基础架构、智能运维、数据库、安全、IT 等方向）；前58集团技术委员会主席，高级系统架构师；前百度资深研发工程师；

【架构之美】微信公众号作者；擅长系统架构设计，大数据，运维、机器学习等技术领域；代表公司多次在业界顶级技术大会 CIO 峰会、Artificial、Intelligence、Conference、A2M、QCon、ArchSummit、SACC、SDCC、CCTC、DTCC、Top100、Strata+、Hadoop World、WOT、GITC、GIAC、TID等发表演讲，并为《程序员》杂志撰稿 2 篇。

首先声明，本文内容参考了以下博客文章，向这三篇文章的作者表示感谢。
https://www.cnblogs.com/arnoldlu/p/7078262.html
https://blog.****.net/HELPLEE601276804/article/details/36717979
https://www.cnblogs.com/lsgxeva/p/8072468.html

1、时间轮算法基本思想

对于一个复杂的软件系统，定时器的对任务的管理和调度至关重要，通常定时器的管理已成为一个复杂系统的重要基础设施。

定时器有很多种（一文完全理解定时器实现技术），基于升序的定时器时间链表是一种最直接的实现方式：即按照定时器时间到的时间顺序依次存放在一个链表中进行管理。但是这种链表存在效率的不足，就是当插入定时器的时候时间复杂度是O(n). 因此需要一种更高效地管理定时器的数据结构和算法，这里结合Linux内核中基于时间轮的定时器管理器的具体实现，介绍一种基于时间轮的定时器管理算法。图1为时间轮的基本结构：

图 1，所示的是一个时间轮的基本结构。时间轮分为 N 个（例如 8 个）时间槽 slot，每时间槽指向一个定时器链表，这个链表里包含多个定时器，这个链表的定时器 Timeout 时间相同，因此链表里的定时器无须排序。

时间轮每一个滴答时间转动一格，会指向下一个时间槽。这里的滴答时间取决于时间轮的具体实现，可以是系统的一个时钟时间，也可以是一个毫秒，一秒钟等。

如果记时间轮的一个滴答时间为 si（slot interval），即时间轮每转动一个槽的时间为si，如果有N个槽，那么时间轮转动一圈的时间为 N * si。

如果时间轮开始转动的起始时间为 ts，那么当有个定时器 Timeout 时间为t的定时器要加入到时间轮，那么应该将这个定时器放到哪个时间槽对应的链表呢？可以用下面的公式计算：

((t - ts）/ si) % N

以图 1 为例，如果时间轮一个滴答时间为 1 秒，假设时间轮开始转动时间为 0，那么一个定时器 Timeout = 6s 的定时器应该加到 6 号时间槽对应的链表里，一个定时器 Timeout = 7s 的定时器应该加到7号槽对应的链表里。

那么时间轮该如何检查定时器是否时间到呢？同样地，如果时间轮开始转动的起始时间为 ts，当前时间为 tc，则计算

((tc - ts）/ si) % N

计算结果则为定时器时间到的那个时间槽对应编号，这个时间槽对应的链表里的定时器全部时间到。

聪明的读者马上会想到一个问题：那么一个定时器 Timout = 8s 的定时器会加到 0 号槽，岂不是和定时器Timeout = 0s (马上时间到) 的定时器放到一个槽里了？这是因为，图 1 所示的时间轮刻度只要 8 个（即只能管理 8 种不同 Timout 的定时器），因此为了解决这种问题，需要增加 N 的值。

增加 N 的值更聪明的办法是采用多级时间轮，即在图 1 所示的时间轮外面再环绕一个时间轮，假设外面时间轮的刻度为 8，即外轮的时间槽也是 8 个，每个时间槽也对应一个链表。同时定义时间轮的转动规则：当里面的时间轮转动 1 圈（8 格），外面的时间轮转动 1 格。可以看到，采用这种方式，二级时间轮可以管理（8 * 8 = 64）种不同 Timeout 的定时器。

在二级时间轮的结构下，一个定时器 Timeout = t 的定时器怎么加入时间轮呢？还是假设二级时间轮都有 8 个槽，假设时间轮的起始时间为 ts，则采用如下算法将 Timeout = t 的定时器加入时间轮：

1）计算 t - ts / si；
2）如果 t - ts / si < 8，则以 t - ts / si 的低 3 位作为索引加入内轮；
3）如果 t - ts / si >= 8（当然要小于 64，否则又溢出），则以 t - ts / si 的高 3 位作为索引加入外轮；

二级时间轮检查时间到的算法与单机时间轮类似，不同的地方就是当内轮的所有时间槽都时间到后，要把外轮的时间槽链表迁移到内轮。

综上所述：基于排序链表的定时器使用唯一的链表来管理所有定时器，所以插入定时器的数目越多，效率就会越低，而时间轮则是利用哈希表的思想，将定时器散列到不同的链表中，这样每条链表上的数据就会显著少于原来排序链表的数目。插入操作的效率基本不受定时器数目的影响(不需要排序，直接散列到一个链表上)。因此插入定时器的时间复杂度和定时器数量n无关，为 O(1)。

显然，要提高时间轮的精度，就要使 si (slot interval) 足够小，要提高其执行效率则要N要足够大。如果最里面一级时间轮的槽采用 n1 为二进制编码，外面一级时间轮采用 n2 位二进制编码，则总共可以管理的时间范围为 0 ~ 2( n1 + n2) – 1。以上面的例子为例，如果二级时间轮都是 3 位二进制编码（8 个时间槽），那么总共可以管理的时间范围为 0 ~ 63，即 64 种 Timeout 的定时器。

Linux 内核采用多级时间轮。定义了 5 个链表数组（每个数组里面包含多个定时器链表）：tv1 - tv5 都是一个链表数组，其中 tv1 的数组大小为 TVR_SIZE（256，8 位编码）， tv2、tv3、tv4、tv5 的数组大小为TVN_SIZE（64，6 位编码）。可以看到一共是 32 位编码，总共可以管理的时间范围为 0 ~ 232 – 1。

这 5 个数组就好比是 5 个齿轮，它们随着滴答时间的增长而不停地转动，每次只需处理第一个齿轮的某一个齿节，低一级的齿轮转动一圈，高一级的齿轮转动一个齿，同时自动把即将到期的定时器迁移到上一个齿轮中，所以低分辨率定时器通常又被叫做时间轮：time wheel。事实上，它的实现是一个很好的空间换时间软件算法。参考 Linux 的实现，具体代码如下：

首先定义如下宏：

2、定时器的添加

要加入一个新的定时器，按以下步骤进行处理：

1）计算定时器到期时间和当前 cpu 定时器所经历过的毫秒数的差值，记为 idx

2）根据 idx 的值，选择该定时器应该被放到 tv1-tv5 中的哪一个链表数组中，可以认为 tv1-tv5 分别占据一个32 位数的不同比特位，tv1 占据最低的 8 位，tv2 占据紧接着的 6 位，然后 tv3 再占位，以此类推，最高的 6位分配给 tv5。最终的选择规则如下表所示：

确定链表数组后，接着要确定把该定时器放入数组中的哪一个链表中，如果时间差 idx 小于 256，按规则要放入 tv1 中，因为 tv1 包含了 256 个链表，所以可以简单地使定时器的 expires 的低 8 位作为数组的索引下标，把定时器链接到 tv1 中相应的链表中即可。如果时间差 idx 的值在 256-18383 之间，则需要把定时器放入 tv2中，同样的，使用定时器的 expires 的 8-14 位作为数组的索引下标，把定时器链接到 tv2 中相应的链表中,。定时器要加入 tv3 tv4 tv5使用同样的原理。经过这样分组后的定时器，在后续的 tick 事件中，系统可以很方便地定位并取出相应的到期定时器进行处理。代码如下：

3、定时器到期处理

系统中的定时器按到期时间有规律地放置在 tv1-tv5 各个链表数组中，其中 tv1 中放置着在接下来的 256 个滴答时间（如毫秒）即将到期的定时器列表。系统滴答值一直在随着系统的运行而动态地增加，原则上是每个tick 事件会加 1，定时器加入 tv1 中使用的下标索引是定时器到期时间 expires 的低 8 位，所以假设当前的滴答值是 0x34567826，则马上到期的定时器是在 tv1.vec[0x26] 中，如果这时候系统加入一个在滴答值0x34567828 到期的定时器，他将会加入到 tv1.vec[0x28] 中，运行两个 tick 后，系统滴答的值会变为0x34567828，很显然，在每次 tick 事件中，定时器系统只要以当前滴答值的低 8 位作为索引，取出 tv1 中相应的链表，里面正好包含了所有在该滴答值到期的定时器列表 。

那什么时候处理 tv2-tv5 中的定时器？每当当前系统滴答值的低 8 位为 0 值时，这表明当前系统滴答值的第 8 -13 位有进位发生，这 6 位正好代表着 tv2，这时只要按当前系统滴答值的第 8 -13 位的值作为下标，移出 tv2中对应的定时器链表，然后用第 2 节的步骤把它们重新加入到定时器系统中来，因为这些定时器一定会在接下来的 256 个 tick 期间到期，所以它们肯定会被加入到 tv1 数组中，这样就完成了 tv2 往 tv1 迁移的过程。

同样地，当当前系统滴答值的第 8 -13 位为 0 时，这表明当前系统滴答值的第 14 -19 位有进位发生，这 6 位正好代表着 tv3，按当前系统滴答值的第 14 -19 位的值作为下标，移出 tv3 中对应的定时器链表，然后用第 2节的步骤把它们从新加入到定时器系统中来，显然它们会被加入到 tv2 中，从而完成 tv3 到 tv2 的迁移，tv4，tv5 的处理可以以此作类推。具体地，定时器时间到需要实现下面二个函数：check 和 cascade，其中cascade 完成时间轮的从外轮向里轮的进位。

基于 Linux 内核的时间轮实现代码，可以在应用程序层面实现一个基于时间轮的管理器。部分代码如下所示：