🔥 本文专栏：C++高阶数据结构
🌸作者主页：努力努力再努力wz

💪 今日博客励志语录：真正能拉开差距的，不是热血，而是你明知道很慢，却还愿意一层一层往下挖。

---

思维导图

引入

在此之前，我们已经学习了基于小根堆实现的定时器，并且将其作为一个定时器组件应用到了高性能 HTTP 服务器当中。

小根堆定时器的核心思想是：堆中的每一个节点都维护一个过期时间，而堆顶节点始终表示当前最早过期的定时任务。因此，我们可以专门创建一个超时检测线程来检查小根堆。

当检测线程检查堆顶节点时，如果发现堆顶节点还没有过期，就说明当前堆中所有节点都不会过期。因为小根堆保证堆顶元素的过期时间最小，所以此时没有必要继续频繁检查，否则就会造成 CPU 空转。更合理的做法是让检测线程主动让出 CPU，并休眠一段时间，而这个休眠时间通常就是当前堆顶节点距离过期所剩余的时间。

等到休眠结束之后，检测线程再次被唤醒，继续检查小根堆。由于睡眠期间可能已经有多个节点到期，因此线程会循环地处理所有已过期的堆顶节点：每次执行堆顶节点对应的超时回调后将其删除，直到堆顶节点尚未过期或堆为空为止。

while (堆非空 && 堆顶已过期) {
    执行堆顶节点对应的超时回调
    弹出堆顶
}
再根据新的堆顶时间计算下一次的睡眠时长

由于小根堆通常是通过数组来模拟完全二叉树的逻辑结构，并通过下标映射父子节点关系，所以删除堆顶元素时，一般会先将堆顶元素与数组末尾元素交换，然后删除数组末尾元素，最后对新的堆顶元素进行向下调整，从而重新维护小根堆的性质。

但是需要注意的是，在实际的服务器应用场景中，我们对定时器的操作并不只是检查堆顶、删除堆顶这么简单。

例如，当某个连接上有新的数据到来时，说明该连接仍然处于活跃状态，此时就需要刷新该连接对应定时器的过期时间；当连接被主动关闭时，也可能需要删除对应的定时器节点。也就是说，实际场景中我们不仅需要操作堆顶元素，还需要支持对堆中任意节点进行更新、删除等操作。

而普通的数据结构堆，或者 C++ STL 中提供的 priority_queue，主要支持的是对堆顶元素的访问和删除，并不适合直接操作堆中的任意节点。因此，如果要将小根堆作为服务器中的定时器组件使用，就通常需要手写一个堆结构。

这里首先要解决的一个问题是：如果要操作堆中的任意节点，就必须先定位该节点在堆数组中的下标。

小根堆虽然是一棵逻辑上的完全二叉树，但它只保证父节点的值小于等于子节点的值，并不具备二叉搜索树那种“左子树小于根节点、右子树大于根节点”的有序关系。因此，我们不能像二叉搜索树那样，从根节点开始根据大小关系逐层查找目标节点。

如果没有额外的辅助结构，那么我们只能从数组开头开始线性遍历，依次比较每一个节点，直到找到目标节点。这样一来，每次定位节点的时间复杂度就是 O(N)，在定时器数量较多或者更新操作较频繁的场景下，这个代价显然是比较高的。

为了解决这个问题，我们可以额外引入一个哈希表，用来维护定时器节点的 key 与其在堆数组中下标之间的映射关系。这样，当我们需要更新或者删除某个定时器节点时，就可以通过哈希表快速找到该节点在数组中的位置，从而将定位复杂度优化为 O(1)。

需要注意的是，引入哈希表之后，每一次堆的向上或向下调整都伴随着数组下标的变动，因此哈希表中对应节点的下标也需要同步更新，否则映射关系就会失效。

当然，定位到节点之后，并不意味着操作已经结束。因为如果修改了某个节点的过期时间，就可能会破坏小根堆的结构性质。

如果某个节点的过期时间被提前了，也就是新的过期时间比原来更小，那么它可能比父节点更早过期，此时就需要执行向上调整；如果某个节点的过期时间被延后了，也就是新的过期时间比原来更大，那么它可能比子节点更晚过期，此时就需要执行向下调整。

由于堆的高度是 logN，所以在维护好哈希表映射关系的前提下，对任意节点进行更新或删除时，定位节点的复杂度是 O(1)，真正的堆调整复杂度是 O(logN)。也就是说，小根堆定时器可以比较高效地支持任意节点的更新和删除操作。

不过，小根堆定时器也并不是完全没有代价。每一次定时器更新、删除或者插入，都可能伴随着一次向上调整或向下调整。如果服务器中连接数量很多，并且定时器刷新非常频繁，那么这些 O(logN) 的堆调整操作仍然会带来一定开销。

因此，除了基于小根堆实现定时器之外，还有另一种常见的定时器组织方式，那就是本文接下来要重点介绍的时间轮。

时间轮原理详解：从结构设计到节点映射与 rounds 计算

从连接超时到时间轮：定时器模型与核心结构

首先需要说明的是，我们第一次接触“定时器”这个概念，其实是在实现高性能 HTTP 服务器的时候。

当时引入定时器组件，主要是为了解决连接超时问题。因为每一个客户端连接都会占用服务端资源，例如对应的套接字、读写缓冲区、连接对象等。如果客户端建立连接之后，迟迟不发送请求报文，或者隔很久才发送一部分数据，导致服务端长时间无法拼接出一个完整的 HTTP 请求报文，那么这个连接就会一直占用服务端资源。

面对这种情况，服务端就不能无限期地等待下去，而是需要为每一个连接设置一个超时时间。如果某个连接在规定时间内没有完成有效交互，那么就可以认为该连接已经超时，此时定时器触发对应的超时回调，关闭连接并释放相关资源。

这就是我们在 HTTP 服务器中引入小根堆定时器的主要原因。

不过，连接超时处理只是定时器的一种具体应用场景。从更广泛的角度来看，定时器的核心作用是：管理一批未来某个时间点需要执行的任务。

也就是说，假设我们现在有一个任务，这个任务并不需要立刻执行，而是希望经过一段时间之后再执行，那么此时就可以设置一个定时器。一个定时器节点可以理解为一条记录，这条记录将过期时间和到期后需要执行的任务绑定在一起。换句话说，定时器节点并不是单独保存过期时间，也不是单独保存任务，而是以类似二元组的形式保存：(过期时间, 回调任务)。当这个节点到期时，定时器组件就根据节点中保存的任务信息触发对应的回调函数。

因此，定时器的基本模型可以理解为：

当某个定时器节点到期之后，就触发该节点对应的回调函数，从而完成对应的任务。

但是需要注意的是，这只是定时器的逻辑模型，用来帮助我们建立一个基础认知。在实际工程实现中，虽然定时器节点过期之后确实需要执行对应的回调函数，但这个回调函数并不一定要由超时检测线程自己执行。

原因也很简单：超时检测线程的主要职责是检查定时器中哪些节点已经过期。如果某个回调函数执行时间比较长，或者回调逻辑中存在阻塞操作，那么超时检测线程就会被这个回调函数拖住，导致后续其他定时器节点无法被及时检查，最终造成定时任务处理延迟。

因此，在工程实践中，通常可以将定时器的处理过程拆成两个阶段：

第一阶段是检测哪些定时器节点已经过期；
第二阶段是执行这些过期节点对应的回调任务。

这两个阶段不一定必须由同一个线程完成。如果回调逻辑非常轻量，那么可以由超时检测线程直接执行；但如果回调任务较重，或者可能阻塞，那么更合理的方式是让超时检测线程只负责发现过期节点，然后将对应的回调任务投递到一个任务队列中，再由其他工作线程从任务队列中取出任务并执行。

这样一来，整个结构就形成了一个典型的生产者-消费者模型：

超时检测线程负责生产已经过期的任务，任务队列负责保存这些任务，而工作线程则负责消费并执行这些任务。

理解了定时器的基本模型之后，接下来就可以引入本文要重点介绍的另一种定时器实现方式：时间轮。

不要被“时间轮”这个名字吓到，它的核心思想其实就体现在这个“轮”字上。

对于小根堆定时器来说，它的核心结构通常是一个数组和一个哈希表。数组用来维护堆结构，哈希表用来建立定时器节点标识与数组下标之间的映射关系，从而支持对任意节点的快速定位。

而对于时间轮来说，它最核心的结构则是一个环形数组和一个当前槽位指针。

这里之所以强调“核心结构”，是因为在实际工程实现中，时间轮可能还会搭配一些辅助结构，例如任务队列、哈希表、锁、条件变量等。比如前面提到，如果我们不希望超时检测线程直接执行回调函数，就可以额外维护一个任务队列，让超时检测线程将过期任务投递到队列中，再由其他工作线程执行。

但是这些结构并不是时间轮思想本身的核心。时间轮最基本的模型，主要就是围绕一个环形数组和一个当前槽位指针展开的。

时间轮的核心结构：环形数组、时间槽与当前指针

接下来，我们就来看时间轮的具体结构。

时间轮中的数组通常不是一个普通数组，而是一个环形数组。数组中的每一个位置都可以看作是一个时间槽，每个时间槽下面可以挂载多个定时器节点。因此，数组中的每个元素通常会指向一个链表，链表中的节点才是真正的定时器节点。

这些定时器节点中会保存对应的回调函数以及与过期时间相关的信息。

可以简单理解为：

环形数组负责划分时间槽，
每个槽位负责管理一批定时器节点，
链表中的节点才是真正等待触发的定时任务。

那么，为什么这里要称为“环形数组”呢？

原因在于，时间轮中会维护一个当前槽位下标，也可以把它理解成一个不断向前移动的指针。这个指针并不是随意移动的，而是按照固定的时间间隔向后推进。

例如，当前指针指向数组下标为 i 的槽位。此时它不会立刻移动到 i + 1，而是要等待一个固定的时间间隔。假设我们将这个时间间隔设置为 2 秒，那么每经过 2 秒，当前指针就会向后移动一格。

也就是说：

经过 2 秒，指针从 i 移动到 i + 1；
再经过 2 秒，指针从 i + 1 移动到 i + 2；
如果指针已经移动到数组末尾，那么下一次移动时，就会通过取模运算重新回到数组开头。

这个过程可以表示为：

current = (current + 1) % slot_num;

这里的 slot_num 表示时间轮中槽位的数量，而 current 表示当前时间轮指向的槽位下标。

因此，时间轮中的每一个槽位并不是表示某一个精确的时间点，而是表示一个固定长度的时间区间。当前指针指向哪个槽位，就说明时间轮当前推进到了哪个时间刻度，需要检查这个槽位中挂载的定时器节点是否已经到期。

例如，假设一个时间轮中有 8 个槽位，每个槽位之间的时间间隔是 2 秒，那么这个时间轮转动一整圈所表示的时间范围就是：

8 * 2 = 16 秒

也就是说，这个时间轮每 2 秒向前推进一格，转完一圈需要 16 秒。

---

定时器节点如何映射到时间轮：相对时间、槽位计算与 rounds 字段

在对时间轮的基本构成有了初步认识之后，接下来就需要思考一个问题：如果现在有一个定时器节点，也就是一个由过期时间和回调函数共同组成的任务记录，那么应该如何将它插入到时间轮的环形数组中呢？

要理解这个问题，首先需要明确当前槽位指针的含义。

我们通常说一个定时器节点“过期”，指的是当前时间已经大于等于该节点设定的过期时间。也就是说，如果按照绝对时间戳的角度来看，定时器过期本质上是当前时间与过期时间之间的一次比较。

但是，时间轮的核心思想并不是每次都显式维护并比较真实的当前时间戳，而是采用一种更加偏向“相对时间”的方式来组织定时任务。

时间轮可以类比成一个圆形钟表。环形数组就像钟表的表盘，数组中的每一个槽位就像表盘上的一个时间刻度，而当前槽位指针就像钟表上的指针。随着时间不断流逝，指针会按照固定的时间间隔向后移动。

需要注意的是，这里的每一个槽位并不是表示一个具体的真实时间点，例如“2026 年 5 月 17 日 12 点 10 分”。它表示的是一个固定长度的时间刻度。这个刻度长度由我们自己设定，例如 1 秒、2 秒或者 10 毫秒。

因此，当指针指向某个槽位时，我们并不一定需要关心当前真实时间戳是多少，而是更关心一个定时器任务距离当前时刻还需要等待多长时间。换句话说，我们需要先计算该任务的过期时间相对于当前时间的时间跨度，然后再将这个时间跨度转换成时间轮中的刻度数量。

例如，假设每个槽位代表 1 秒，那么一个 5 秒后过期的任务，就相当于从当前槽位开始，经过 5 个时间刻度后到期；如果每个槽位代表 2 秒，那么一个 10 秒后过期的任务，同样相当于经过 5 个时间刻度后到期。

因此，在插入定时器节点时，第一步并不是直接将绝对过期时间戳保存下来，然后每次扫描时都拿它和当前时间进行比较，而是先计算该节点距离当前时间还有多久过期。

如果用户设置的是一个绝对过期时间戳，那么可以用该过期时间戳减去当前时刻的时间戳，得到一个相对的超时时间段：

timeout = expire_time - now;

得到这个相对时间段之后，再根据每个槽位代表的时间间隔 tick，将其转换成需要经过的时间刻度数量：

ticks = ceil(timeout / tick);

这样一来，时间轮真正关心的就不再是某个任务在哪一个真实时间点过期，而是这个任务相对于当前槽位，还需要经过多少个时间刻度才会到期。

这里需要特别区分两个概念：

tick 表示每个槽位对应的时间间隔，也就是一个时间刻度的长度；
slot_num 表示时间轮中一共有多少个槽位，也就是环形数组的长度。

因此，tick 决定了时间轮的时间精度，而 slot_num 决定了时间轮一圈包含多少个刻度。二者相乘，才表示时间轮转动一整圈所能覆盖的时间范围：

一圈覆盖的时间范围 = tick * slot_num

当我们计算出一个任务需要等待多少个时间刻度之后，就可以根据当前槽位下标计算它应该被插入到哪个槽位中。

假设当前槽位下标为 current，任务需要等待的刻度数为 ticks，时间轮的槽位数量为 slot_num，那么该任务应该插入的槽位可以通过下面的公式计算：

slot = (current + ticks) % slot_num;

这里之所以要进行取模运算，是因为时间轮底层使用的是环形数组。当下标超过数组末尾之后，需要重新回到数组开头继续计算。

但是，仅仅计算出槽位还不够。

因为时间轮是一个环形数组，任务的过期时间可能超过时间轮一整圈所能表示的范围。也就是说，一个任务可能不是在当前这一圈到期，而是需要等时间轮转动一圈甚至多圈之后，才真正到期。

例如，假设时间轮有 8 个槽位，每个槽位代表 1 秒，当前槽位下标为 3。此时有一个任务 2 秒后到期，那么它需要等待 2 个刻度，最终会落到：

slot = (3 + 2) % 8 = 5

也就是说，它会被插入到 wheel[5] 这个槽位中。

但是，如果此时有另一个任务是 10 秒后到期，那么它需要等待 10 个刻度，最终也会落到：

slot = (3 + 10) % 8 = 5

可以看到，这两个任务都会被插入到 wheel[5] 这个槽位中。但是它们并不是同一时间到期：前者是在当前这一圈走到 5 号槽位时到期，而后者则需要等时间轮多转一圈之后，才会真正到期。

这也说明了一个问题：位于同一个槽位链表中的定时器节点，它们的过期时间并不一定严格相同。

造成这种情况的原因主要有两个。

第一，时间轮本身具有时间粒度。假设每个槽位代表 1 秒，那么一些过期时间非常接近的任务，例如 1.2 秒后到期、1.3 秒后到期、1.4 秒后到期的任务，可能都会被映射到同一个时间槽中。它们的真实过期时间并不完全相同，只是因为时间轮的刻度粒度相同，所以被归入了同一个槽位。

第二，时间轮是环形数组。不同过期时间的任务经过取模运算之后，可能会落到同一个槽位中。例如 2 秒后到期的任务和 10 秒后到期的任务，在 8 个槽位的时间轮中就可能映射到同一个槽位。它们虽然处于同一个链表中，但真正到期的轮次并不相同。

因此，时间轮中同一个槽位下的链表，并不表示这些节点具有完全相同的过期时间，也不表示链表头部节点就一定比后面的节点更早过期。链表只是用来组织那些被映射到同一个槽位中的定时器节点，并不天然维护严格的时间优先级关系。

为了解决“跨越多个周期后落到同一个槽位”的问题，时间轮中的定时器节点通常还需要维护一个额外字段，例如 rounds。

rounds 字段的作用与计算：解决时间轮跨周期触发问题

这里的 rounds 字段表示该节点还需要等待时间轮转动多少个完整周期。由于时间轮是环形数组，多个不同过期时间的节点经过取模运算后可能会落到同一个槽位中，因此仅靠槽位下标无法判断节点是否真正到期。slot 只能表示节点被挂载到哪个槽位，而 rounds 则表示当指针扫描到该槽位时，该节点还需要再等待多少圈才能执行回调。

接下来需要讨论的就是 rounds 字段的计算方式。

根据前面的分析，在插入一个定时器节点时，我们首先需要计算该节点距离当前时间还有多久过期。如果用户设置的是一个绝对过期时间戳，那么就可以用这个过期时间戳减去当前时刻的时间戳，从而得到一个相对的超时时间段：

timeout = expire_time - now;

得到这个时间跨度之后，还需要根据每个槽位代表的时间间隔 tick，将其转换成需要经过的时间刻度数：

ticks = ceil(timeout / tick);

这里需要注意一个细节：计算 ticks 时通常要采取向上取整。

例如，一个定时器节点距离当前时间还有 1.2 秒过期，而时间轮中每个槽位代表 1 秒。如果直接向下取整，那么得到的 ticks 就是 1，该节点会被挂载到 1 个 tick 之后的槽位中。这样当时间轮经过 1 秒扫描到该槽位时，如果该节点的 rounds 等于 0，就会直接执行回调。

但是此时实际上只过去了 1 秒，而该节点真正的过期时间是 1.2 秒之后，所以这就会导致定时器被提前触发。

因此，这里更合理的做法是向上取整：

ticks = ceil(timeout / tick);

这样 1.2 秒会被转换成 2 个 tick。虽然该节点可能会在 2 秒左右才被处理，存在一定延迟，但可以保证当时间轮扫描到该节点并执行回调时，它一定已经过期，而不会出现提前触发的问题。

换句话说，时间轮由于存在时间粒度，本身就可能带来一定误差。向上取整并不是为了完全消除误差，而是为了将误差控制在“延后触发”这一侧，避免定时任务被提前执行。

在得到 ticks 之后，就可以进一步计算该节点应该落入的槽位：

slot = (current + ticks) % slot_num;

这里的 slot 决定的是该定时器节点应该挂载到时间轮中的哪个槽位。但是，仅仅知道槽位还不够，因为时间轮是一个环形数组，不同过期时间的节点经过取模运算之后，可能会落到同一个槽位中。因此，我们还需要计算 rounds 字段，用来判断该节点在第几次被扫描到时才真正过期。

这里需要注意，rounds 并不是简单地表示这个时间跨度中包含了多少个完整周期。更准确地说，rounds 表示的是：在该节点真正到期之前，当时间轮指针扫描到它所在槽位时，还需要跳过多少次。

因此，rounds 的计算通常不是：

rounds = ticks / slot_num;

而是：

rounds = (ticks - 1) / slot_num;

这里最关键的地方就是 ticks - 1。

为什么要减一呢？

核心原因在于，rounds 表示的并不是 ticks 中一共包含多少个完整周期，而是表示在该节点真正到期之前，当时间轮指针扫描到目标槽位时，还需要跳过多少次。

换句话说，当定时器节点已经被挂载到目标槽位之后，每一次时间轮指针扫描到这个槽位时，都会检查该节点的 rounds 值。如果 rounds > 0，说明它还没有真正到期，只需要将 rounds 减一；如果 rounds == 0，说明这一次扫描到该槽位时，节点已经到期，可以执行对应的回调函数。

因此，计算 rounds 时需要排除掉“真正到期的那一次扫描”。因为当时间轮已经经过 ticks 个刻度并到达目标槽位时，这个节点就应该被触发，而不是还要再等待一圈。

所以这里使用 ticks - 1，本质上是为了让 rounds 表示“到期之前需要跳过的次数”，而不是“等待刻度中包含的完整周期数”。

举个例子，假设时间轮中有 8 个槽位，当前指针指向下标 3 的槽位。此时有一个任务刚好需要等待 8 个 tick 后执行，那么它最终会落到：

slot = (3 + 8) % 8 = 3;

也就是说，它会重新落回当前槽位。

但是这个任务显然不是现在立刻执行，而是应该等时间轮转完一整圈、再次回到槽位 3 时执行。

如果我们直接使用：

rounds = ticks / slot_num;

那么得到：

rounds = 8 / 8 = 1;

这样当时间轮转完一整圈后再次扫描到槽位 3 时，发现 rounds > 0，就只会将 rounds 减一，而不会执行回调。结果就是这个任务还要再多等一整圈，明显比预期晚了一个周期。
除了刚好跨越一个完整周期的情况之外，再来看一个跨越多个周期的例子。

假设时间轮中仍然有 8 个槽位，当前指针指向下标为 3 的槽位。此时有一个任务需要等待 18 个 tick 后执行，那么它最终落入的槽位为：

slot = (3 + 18) % 8 = 5;

也就是说，这个任务会被挂载到 wheel[5] 这个槽位对应的链表中。

但是需要注意，从当前槽位 3 第一次移动到槽位 5，只需要经过 2 个 tick，此时该任务显然还没有真正到期。由于它真正需要等待的是 18 个 tick，所以它必须等待时间轮继续转动多个周期之后，才能在某一次扫描到槽位 5 时被触发。

因此，此时需要计算它的 rounds：

rounds = (ticks - 1) / slot_num;
rounds = (18 - 1) / 8 = 2;

这表示在该节点真正触发之前，当时间轮指针扫描到槽位 5 时，还需要跳过 2 次。

具体来看，第一次扫描到槽位 5 时，只经过了 2 个 tick，此时 rounds = 2，不会执行回调，而是将 rounds 减为 1；第二次扫描到槽位 5 时，已经经过了 10 个 tick，此时 rounds = 1，仍然不会执行回调，而是将 rounds 减为 0；第三次扫描到槽位 5 时，已经经过了 18 个 tick，此时 rounds = 0，说明该节点真正到期，可以执行对应的回调函数，或者将回调任务投递到任务队列中。

由此可以看出，slot 只能决定节点被挂载到哪个槽位，而 rounds 才能进一步区分：同一个槽位中的节点到底是在当前这一圈触发，还是需要等待后续某一圈再触发。

所以这里应该使用：

rounds = (ticks - 1) / slot_num;

此时得到：

rounds = (8 - 1) / 8 = 0;

这样当时间轮转完一整圈，再次扫描到槽位 3 时，发现 rounds == 0，就可以直接执行该节点对应的回调函数。

因此，ticks - 1 的作用就是修正这种“刚好跨越完整周期”的边界情况，避免定时器节点被多延迟一圈。

当时间轮指针扫描某个槽位时，对于该槽位链表中的每一个节点，处理逻辑大致如下：

if (node->rounds > 0)
{
    node->rounds--;
}
else
{
    // 节点真正到期
    // 执行回调，或者将回调任务投递到任务队列
    // 然后删除该定时器节点
}

所以，slot 和 rounds 实际上分别解决了两个问题：

slot   决定节点挂载到哪个槽位；
rounds 决定节点第几次被扫描到时真正触发。

也就是说，时间轮插入节点的核心，就是将一个绝对或相对的过期时间，转换成时间轮内部能够识别的两个信息：目标槽位 slot 和 剩余圈数 rounds。

示意图

时间轮的 C++ 实现：代码骨架与核心接口解析

时间轮代码骨架设计：核心成员、节点结构与并发保护

根据上文的分析，我们已经掌握了时间轮的基本原理。接下来，我们就可以使用 C++ 自己动手实现一个基础版本的时间轮。

不过，这里先不急着关注时间轮内部的具体实现细节，比如定时器节点如何插入、时间轮如何推进、节点到期后如何处理等。第一步，我们先把时间轮的整体代码骨架搭建出来。

首先，我们需要定义一个 TimeWheel 类来描述时间轮对象。后续如果要访问、操作或者推进时间轮，就可以通过创建 TimeWheel 类的实例来完成。

对于一个时间轮来说，它内部最核心的成员变量主要包括两个部分：槽数组 和 当前槽位下标。

槽数组用于组织不同时间刻度上的定时器节点。这里我们使用 std::vector<TimerNode*> 来表示槽数组。需要注意的是，这个数组中的每一个元素并不是直接保存一个定时器节点，而是保存一个链表头指针，指向该槽位下挂载的定时器节点链表。也就是说，时间轮通过数组划分时间槽，而真正的定时器节点则挂载在每个槽位对应的链表中。

当前槽位下标则用来表示时间轮当前推进到了哪个时间刻度。每当经过一个固定的时间间隔，当前槽位下标就会向后移动一格，从而模拟时间不断向前推进的过程。

此外，在本文的实现中，超时检测线程并不会直接执行定时器节点中的回调函数。它只负责检测哪些节点已经到期。一旦发现某个定时器节点到期，就会将该节点中保存的回调函数放入任务队列中，后续再由其他线程从任务队列中取出并执行。

因此，TimeWheel 类中还需要维护一个任务队列。这个任务队列中保存的元素就是到期后需要执行的回调函数。这样一来，超时检测线程和回调执行线程之间就形成了一个简单的生产者-消费者模型：超时检测线程负责生产到期任务，其他线程负责消费并执行这些任务。

除了槽数组、当前槽位下标和任务队列之外，时间轮还需要维护槽数组的容量以及时间刻度。

其中，slotSize 表示时间轮中一共有多少个槽位，也就是环形数组的长度；tick_interval 表示时间轮每次向后推进一个槽位所经过的时间间隔。

构造函数会接收两个参数，分别是槽数组的大小 _slotSize 和时间刻度 _tick_interval。在构造函数中，需要先对这两个参数进行合法性检查：槽位数量和时间刻度都必须大于 0，否则直接抛出异常。参数检查通过之后，再对槽数组进行初始化，将数组中的每一个元素都初始化为空指针，表示当前每个槽位下面都还没有挂载任何定时器节点。

为了统一描述定时器到期后需要执行的任务，这里使用 std::function<void()> 作为回调函数类型，并通过 using 为其定义一个类型别名 fun_t，方便后续代码书写。

class TimeWheel
{
public:
    using fun_t = std::function<void()>;

    TimeWheel(int _slotSize, int _tick_interval)
        : slotSize(_slotSize)
        , currentslot(0)
        , tick_interval(_tick_interval)
    {
        if (_slotSize <= 0 || _tick_interval <= 0)
        {
            throw std::invalid_argument("slotSize and tick_interval must be positive");
        }

        slots.resize(slotSize, nullptr);
        lastTickTime = std::chrono::steady_clock::now();
    }

    // ...

private:
    std::vector<TimerNode*> slots;  // 槽数组，每个元素都是一个链表头指针
    int slotSize;                   // 时间轮槽位数量
    int currentslot;                // 当前槽位下标
    int tick_interval;              // 每个槽位对应的时间间隔，单位：毫秒

    std::queue<fun_t> taskQueue;    // 保存已经到期的回调任务

    // ...
};

接下来需要定义的是定时器节点，也就是 TimerNode。

每一个 TimerNode 对象都表示一个具体的定时任务。它内部需要保存该任务到期后执行的回调函数，以及该节点还需要等待时间轮转动的圈数。同时，由于同一个槽位下可能挂载多个定时器节点，所以节点中还需要维护一个指向后继节点的 next 指针，用来将这些节点组织成链表。

因此，TimerNode 中最核心的成员包括：回调函数 cb、剩余圈数 round、以及指向下一个节点的指针 next。

class TimerNode
{
public:
    using fun_t = std::function<void()>;
     //....
    fun_t cb;   // 定时器到期后执行的回调函数

    //...
    int round;        // 剩余圈数，表示还需要等待时间轮转动多少圈
    TimerNode* next;  // 指向同一槽位链表中的下一个节点
};

在完成 TimeWheel 类和 TimerNode 节点的基本定义之后，接下来还需要确定 TimeWheel 对外提供哪些接口。

对于一个基础版本的时间轮来说，至少需要提供三个核心接口。

第一个是 addTimer()，用于向时间轮中添加一个新的定时器节点。该函数的核心任务是根据定时器的过期时间计算出它应该落入的槽位，以及对应的 round 值，然后将节点插入到目标槽位的链表中。

第二个是 tick()，用于推动时间轮向后移动一个槽位。这个函数通常由超时检测线程定期调用。每当经过一个时间刻度，超时检测线程就调用一次 tick()，让当前槽位下标向后移动，并检查新槽位中的定时器节点是否已经到期。

第三个是 popTask()，用于从任务队列中取出已经到期的回调任务。由于本文的设计中，超时检测线程不直接执行回调函数，而是将到期任务放入任务队列，因此其他线程就可以通过 popTask() 从队列中取出任务并执行。

至此，一个基础版本时间轮的代码骨架就基本形成了。

简单来说，addTimer() 负责添加定时任务，tick() 负责推动时间轮并检测到期节点，popTask() 负责取出已经到期的回调任务。后续我们只需要围绕这三个接口继续补充具体实现，就可以逐步完成一个完整的时间轮定时器。

---

在正式讲解 TimeWheel 各个接口的具体实现之前，还需要先补充一下本文在时间轮实现上的几个设计细节。

根据前面对时间轮原理的分析，我们知道，时间轮并不一定需要像小根堆定时器那样，始终维护一个全局最早过期时间，然后不断拿当前时间戳与过期时间戳进行比较。时间轮的核心思想是基于相对时间进行组织：先计算定时任务距离当前时间还有多久过期，再将这个时间跨度转换成时间轮中的时间刻度数，最终映射到对应的槽位和 round 值上。

也就是说，在基础模型中，时间轮主要依赖 slot 和 round 来判断一个节点什么时候应该被触发。

但是，在实际实现时，我还是在 TimerNode 中额外维护了一个绝对过期时间点 expireTime。这里之所以这样设计，主要是考虑到多线程运行环境下可能存在调度延迟问题。

例如，假设时间轮的时间刻度 tick_interval 为 1 秒。按照理想情况，超时检测线程应该每经过 1 秒调用一次 tick()，让时间轮向后推进一个槽位。但是在真实的多线程环境中，线程的执行并不完全由我们控制，它可能因为 CPU 调度、系统负载或者其他阻塞情况而没有被及时执行。

也就是说，超时检测线程在遍历完当前槽位之后，可能并不是准确等待 1 秒就继续推进到下一个槽位，而是过了更长时间才重新获得 CPU 执行权。比如理论上 1 秒后应该推进一格，但实际上 5 秒后才再次调用 tick()。如果此时时间轮仍然只向后移动一个槽位，就会导致时间轮的逻辑推进明显落后于真实时间，从而造成较大的超时误差。

尤其是对于同一个槽位链表中的定时器节点来说，有些节点可能还需要等待若干个周期才真正到期。如果超时检测线程发生明显延迟，那么虽然这些节点的 round 值可能还没有被逐步递减到 0，但从真实时间角度来看，当前时间可能已经大于等于它们的过期时间点。此时如果仍然只依赖 round 判断，就可能导致已经过期的任务不能被及时处理。

因此，在本文的实现中，TimerNode 除了保存回调函数和 round 值之外，还额外保存了一个 expireTime 字段，用来记录该节点真正的过期时间点。这样在遍历槽位链表时，就可以不只是单纯判断 round，还可以结合当前时间与 expireTime 进行判断，从而减少线程调度延迟带来的误差。

需要注意的是，这里的 expireTime 使用的是 std::chrono::steady_clock::time_point。它并不是传统意义上表示年月日时分秒的系统时间戳，而是单调时钟上的时间点。对于定时器来说，使用 steady_clock 更合适，因为它不会受到系统时间被手动修改的影响，更适合用来计算时间间隔和超时。

这里可以顺便简单补充一下 C++ 标准库中的时间库 std::chrono。

在 std::chrono 中，和时间相关的概念主要可以分为三类：时钟、时间点、时间段。

首先是时钟，也就是 clock。时钟用来提供当前时间，例如这里使用的：

std::chrono::steady_clock

它表示一个单调递增的时钟。所谓单调递增，就是它的时间不会因为系统时间被手动修改而发生回退。因此，在实现定时器、超时检测、性能计时等场景时，通常更适合使用 steady_clock。

其次是时间点，也就是 time_point。时间点表示某个时钟上的一个具体时刻。例如：

std::chrono::steady_clock::time_point expireTime;

这里的 expireTime 就表示基于 steady_clock 这个时钟体系下的一个具体过期时间点。需要注意的是，它并不表示现实世界中的“某年某月某日几点几分几秒”，而是表示单调时钟上的某一个时刻。

最后是时间段，也就是 duration。时间段表示两个时间点之间的差值。例如：

auto timeout = expireTime - now;

这里的 timeout 就是一个时间段，表示当前时间点 now 距离过期时间点 expireTime 还剩多久。

同理，我们也可以通过给当前时间点加上一个时间段，得到未来的某个时间点：

auto expireTime = std::chrono::steady_clock::now()
                + std::chrono::milliseconds(timeout_ms);

这段代码表示：从当前时刻开始，经过 timeout_ms 毫秒之后，就是该定时器节点的过期时间点。

因此，在本文的时间轮实现中，可以这样理解：

std::chrono::steady_clock::now()

用于获取当前时间点；

std::chrono::steady_clock::time_point

用于保存某个具体的过期时间点；

std::chrono::milliseconds

用于表示一个以毫秒为单位的时间段。

也就是说，std::chrono 帮助我们把“当前时刻”“过期时刻”“两个时刻之间的时间间隔”这几个概念区分开来，这样在实现定时器时，代码语义会更加清晰。

---

与此对应，TimeWheel 类中还额外维护了一个 lastTickTime 字段，用来记录时间轮上一次推进时的时间点。

除了时间误差问题之外，还需要考虑多线程并发访问的问题。

在本文的设计中，时间轮可能会被多个线程同时访问。例如，其他线程可能会调用 addTimer() 向时间轮中插入新的定时器节点，而超时检测线程又可能同时调用 tick() 遍历槽数组中的链表。如果不加锁保护，就可能出现多个线程同时修改槽位链表的情况，从而引发数据竞争。

因此，这里需要为槽数组以及槽位链表准备一把互斥锁 slots_mtx。凡是涉及访问或修改槽数组、槽位链表的操作，都需要在锁的保护下进行。

同理，任务队列也存在并发访问问题。超时检测线程在发现某个节点到期之后，会将该节点中的回调函数推入任务队列；而其他工作线程则会从任务队列中取出回调函数并执行。因此，任务队列也需要单独使用一把互斥锁 taskQueue_mtx 进行保护。

这样一来，TimeWheel 的整体结构就更加完整了：槽数组和槽位链表由 slots_mtx 保护，任务队列由 taskQueue_mtx 保护，expireTime 用于记录节点真正的过期时间点，lastTickTime 用于记录时间轮上一次推进的时间点，从而在后续 tick() 实现中进行时间补偿。

对应的代码骨架如下：

class TimerNode
{
public:
    using fun_t = std::function<void()>;

    TimerNode(fun_t _cb,
              std::chrono::steady_clock::time_point _expireTime,
              int _round)
        : cb(std::move(_cb))
        , expireTime(_expireTime)
        , round(_round)
        , next(nullptr)
    {
    }

    fun_t cb;   // 定时器到期后需要执行的回调函数

    std::chrono::steady_clock::time_point expireTime; 
    // 节点的绝对过期时间点，用于处理线程调度延迟带来的误差

    int round;        // 剩余圈数，表示还需要等待时间轮转动多少圈
    TimerNode* next;  // 指向同一槽位链表中的下一个节点
};

class TimeWheel
{
public:
    using fun_t = std::function<void()>;

    // ...

private:
    std::vector<TimerNode*> slots;  // 槽数组，每个元素都是一个链表头指针
    int slotSize;                   // 时间轮槽位数量
    int currentslot;                // 当前槽位下标
    int tick_interval;              // 每个槽位对应的时间间隔，单位：毫秒

    std::queue<fun_t> taskQueue;    // 保存已经到期的回调任务

    std::mutex slots_mtx;           // 保护槽数组以及槽位链表
    std::mutex taskQueue_mtx;       // 保护任务队列

    std::chrono::steady_clock::time_point lastTickTime;
    // 记录上一次推进时间轮的时间点，用于计算真实经过了多少个 tick
};

至此，时间轮的整体骨架才算比较完整。它不仅包含时间轮最核心的槽数组和当前槽位下标，还额外考虑了实际多线程环境下的两个关键问题：一个是线程调度延迟带来的时间误差，另一个是多个线程并发访问共享数据时的数据竞争问题。

addTimer() 实现：定时任务的槽位映射与节点插入

首先实现的是 addTimer() 函数。

该函数的作用是向时间轮中添加一个新的定时器节点。它接收两个参数：第一个参数是定时器到期后需要执行的回调函数，第二个参数是该定时任务距离当前时间还需要等待的时间段 delay_ms。

在函数开始时，首先需要对 delay_ms 进行判断。

如果 delay_ms 小于 0，说明传入的时间参数非法，此时直接返回即可；如果 delay_ms 等于 0，说明该任务不需要等待，当前就已经可以执行。由于本文的设计中，超时检测线程不会直接执行回调函数，所以这里会先对任务队列加锁，然后将该回调函数直接放入任务队列中，等待后续由其他线程取出并执行。

if (delay_ms < 0)
{
    return;
}
else if (delay_ms == 0)
{
    std::lock_guard<std::mutex> lock(taskQueue_mtx);
    taskQueue.push(std::move(_cb));
    return;
}

如果 delay_ms 大于 0，说明该任务需要被插入到时间轮中。此时首先需要计算该任务的绝对过期时间点：

auto expireTime = std::chrono::steady_clock::now()
                + std::chrono::milliseconds(delay_ms);

这里的 expireTime 用于记录该定时器节点真正的过期时间点。虽然时间轮的核心判断逻辑主要依赖 slot 和 round，但在多线程环境下，超时检测线程可能因为调度原因无法严格按照固定时间刻度推进，因此保留 expireTime 可以用于辅助判断节点是否已经真正过期，从而减少时间轮推进延迟带来的误差。

接下来，需要根据 delay_ms 和时间轮的时间刻度 tick_interval，计算该任务需要等待多少个时间刻度：

int ticks = (delay_ms + tick_interval - 1) / tick_interval;

这里采用的是向上取整。这样做的目的，是为了避免定时器被提前触发。

例如，当 delay_ms 为 1200 毫秒，而 tick_interval 为 1000 毫秒时，如果直接向下取整，那么得到的 ticks 就是 1。这样时间轮经过 1 秒扫描到对应槽位时，该任务就可能被执行，但此时它实际上还没有真正过期。

因此，这里通过向上取整将其转换成 2 个 tick。这样虽然可能会让任务稍微延后执行，但可以保证当时间轮扫描到该节点时，它一定已经到期，而不会出现提前触发的问题。

在得到 ticks 之后，就可以进一步计算该节点的剩余圈数 round：

int round = (ticks - 1) / slotSize;

这里之所以使用 ticks - 1，是因为 round 表示的不是 ticks 中一共包含多少个完整周期，而是表示在该节点真正到期之前，当时间轮指针扫描到它所在槽位时，还需要跳过多少次。

如果直接使用：

round = ticks / slotSize;

那么对于刚好跨越一整圈的任务来说，会多等待一个周期。

例如，时间轮中有 8 个槽位，当前任务刚好需要等待 8 个 tick，那么它会重新落回当前槽位。这个任务应该在时间轮转完一整圈、再次扫描到当前槽位时执行。如果 round 被计算成 1，那么第一次回到该槽位时只会将 round 减为 0，而不会执行回调，导致任务多等待一整圈。

因此，这里使用：

round = (ticks - 1) / slotSize;

这样可以保证刚好跨越完整周期的任务，在下一次扫描到目标槽位时能够正确触发。

接着，需要计算该定时器节点应该插入到哪个槽位中：

int slotIndex = (currentslot + ticks) % slotSize;

其中，currentslot 表示时间轮当前所在的槽位，ticks 表示该任务还需要等待多少个时间刻度，slotSize 表示时间轮槽数组的大小。通过取模运算，就可以将目标位置映射到环形数组中的某一个槽位上。

也就是说：

slotIndex 决定节点挂载到哪个槽位；
round     决定节点第几次被扫描到时真正触发。

由于 currentslot、槽数组以及槽位链表都属于时间轮的共享数据，在多线程环境下可能会被超时检测线程和其他业务线程并发访问，因此插入节点时需要使用 slots_mtx 进行加锁保护。

在计算出目标槽位之后，就可以创建一个新的 TimerNode 节点，并将其插入到对应槽位的链表中。

由于同一个槽位中的节点并不维护严格的过期时间顺序，它们只是因为时间粒度或者取模运算被映射到了同一个槽位中，所以这里没有必要按照过期时间进行排序，直接采用头插法即可。

TimerNode* node = new TimerNode(std::move(_cb), expireTime, round);

node->next = slots[slotIndex];
slots[slotIndex] = node;

头插法的好处是实现简单，插入效率也比较高。在不考虑锁竞争的情况下，向时间轮中插入一个定时器节点的时间复杂度就是 O(1)。

完整代码如下：

void addTimer(fun_t _cb, int delay_ms)
{
    if (delay_ms < 0)
    {
        return;
    }
    else if (delay_ms == 0)
    {
        std::lock_guard<std::mutex> lock(taskQueue_mtx);
        taskQueue.push(std::move(_cb));
        return;
    }

    std::lock_guard<std::mutex> lock(slots_mtx);

    auto now = std::chrono::steady_clock::now();
    auto expireTime = now + std::chrono::milliseconds(delay_ms);

    int ticks = (delay_ms + tick_interval - 1) / tick_interval;
    int round = (ticks - 1) / slotSize;
    int slotIndex = (currentslot + ticks) % slotSize;

    TimerNode* node = new TimerNode(std::move(_cb), expireTime, round);

    node->next = slots[slotIndex];
    slots[slotIndex] = node;
}

至此，addTimer() 的核心逻辑就比较清晰了：它先将用户传入的相对过期时间 delay_ms 转换成时间轮内部能够识别的 ticks、round 和 slotIndex，然后创建对应的定时器节点，并将其挂载到目标槽位的链表中。

tick() 实现：时间轮推进、过期检测与任务转移

接下来实现的是 tick() 函数。

tick() 函数的作用是推动时间轮向后推进，并检查对应槽位中的定时器节点是否已经到期。按照时间轮的基本模型，每经过一个时间刻度，当前槽位下标就应该向后移动一格，然后遍历该槽位下挂载的链表，判断其中的定时器节点是否需要被触发。

不过在本文的实现中，tick() 并不是简单地每调用一次就只移动一格。因为在真实的多线程环境下，超时检测线程可能会因为线程调度、系统负载等原因，无法严格按照固定的时间刻度运行。比如我们设置的时间刻度是 1 秒，但实际可能过了 5 秒之后，超时检测线程才再次获得 CPU 执行权。

因此，tick() 中首先需要获取当前时间点，然后根据当前时间点和上一次推进时间轮的时间点 lastTickTime，计算真实经过了多少时间：

auto now = std::chrono::steady_clock::now();
auto duration = now - lastTickTime;
auto duration_ms = std::chrono::duration_cast<std::chrono::milliseconds>(duration).count();

接着，再将这个时间段转换成对应的时间刻度数量：

int steps = duration_ms / tick_interval;

如果 steps <= 0，说明距离上一次推进还没有经过一个完整的时间刻度，此时不需要移动时间轮，直接返回即可。

如果 steps > 0，说明真实时间已经经过了一个或多个时间刻度。此时就不能只让时间轮移动一格，而是需要根据 steps 的值进行补偿推进：经过了几个时间刻度，就连续向后推进几个槽位。

为了避免在遍历槽位链表时频繁对任务队列加锁，本文这里并不会在发现一个过期节点时就立刻将它的回调函数 push 到任务队列中，而是先准备一个临时数组 expiredTasks。在遍历槽位链表的过程中，如果发现某个定时器节点已经到期，就先将它的回调函数保存到这个临时数组中。等所有需要处理的槽位都遍历完成之后，再统一对任务队列加锁，将这些回调函数一次性转移到任务队列中。

这样做可以减少 taskQueue_mtx 的加锁次数，也可以避免在持有槽位锁的过程中频繁竞争任务队列锁。

对应的 tick() 实现如下：

void tick()
{
    std::vector<fun_t> expiredTasks;

    auto now = std::chrono::steady_clock::now();

    {
        std::lock_guard<std::mutex> lock(slots_mtx);

        auto duration = now - lastTickTime;
        auto duration_ms =
            std::chrono::duration_cast<std::chrono::milliseconds>(duration).count();

        int steps = duration_ms / tick_interval;

        if (steps <= 0)
        {
            return;
        }

        for (int i = 0; i < steps; i++)
        {
            currentslot = (currentslot + 1) % slotSize;
            processCurrentSlot(now, expiredTasks);
        }

        lastTickTime += std::chrono::milliseconds(steps * tick_interval);
    }

    {
        std::lock_guard<std::mutex> lock(taskQueue_mtx);

        for (auto& task : expiredTasks)
        {
            taskQueue.push(std::move(task));
        }
    }
}

这里需要注意，lastTickTime 的更新方式并不是直接赋值为 now，而是：

lastTickTime += std::chrono::milliseconds(steps * tick_interval);

这样做的原因是，当前真实经过的时间可能并不是 tick_interval 的整数倍。

例如，tick_interval 为 1000 毫秒，而距离上一次推进已经过去了 2500 毫秒，那么此时 steps 的值为 2，说明时间轮只能补偿推进 2 个完整刻度，还剩下 500 毫秒不足一个完整刻度。如果直接将 lastTickTime 更新为 now，这 500 毫秒就会被丢掉；而通过累加 steps * tick_interval 的方式更新，则可以保留这部分不足一个 tick 的时间，让它在下一次 tick() 调用时继续参与计算。

接下来再看 processCurrentSlot() 函数。

这个函数用于处理当前槽位下挂载的定时器节点链表。由于遍历链表的过程中可能会删除节点，所以这里需要使用两个指针：prev 指向当前节点的前驱节点，curr 指向当前正在检查的节点。这样在删除 curr 节点时，就可以正确修改链表指针关系。

void processCurrentSlot(std::chrono::steady_clock::time_point now,
                        std::vector<fun_t>& expiredTasks)
{
    TimerNode* prev = nullptr;
    TimerNode* curr = slots[currentslot];

    while (curr)
    {
        if (now >= curr->expireTime)
        {
            expiredTasks.push_back(std::move(curr->cb));

            TimerNode* temp = curr;
            curr = curr->next;

            if (prev)
            {
                prev->next = curr;
            }
            else
            {
                slots[currentslot] = curr;
            }

            delete temp;
        }
        else if (curr->round > 0)
        {
            curr->round--;

            prev = curr;
            curr = curr->next;
        }
        else
        {
            TimerNode* node = curr;

            if (prev)
            {
                prev->next = curr->next;
                curr = prev->next;
            }
            else
            {
                slots[currentslot] = curr->next;
                curr = slots[currentslot];
            }

            auto remaining = node->expireTime - now;

            int remaining_ms =
                std::chrono::duration_cast<std::chrono::milliseconds>(remaining).count();

            int ticks = (remaining_ms + tick_interval - 1) / tick_interval;

            if (ticks <= 0)
            {
                ticks = 1;
            }

            int slotIndex = (currentslot + ticks) % slotSize;
            node->round = (ticks - 1) / slotSize;

            node->next = slots[slotIndex];
            slots[slotIndex] = node;
        }
    }
}

这个函数中，对定时器节点主要分成三种情况处理。

第一种情况是：

now >= curr->expireTime

这说明从真实时间角度来看，该节点已经到期。此时就需要将该节点中的回调函数保存到临时数组 expiredTasks 中，然后将该节点从当前槽位链表中摘除，并释放对应的节点空间。

这里使用：

expiredTasks.push_back(std::move(curr->cb));

是因为当前节点马上就要被删除，它保存的回调函数后续也只需要被转移到任务队列中，因此可以直接使用移动语义，避免不必要的拷贝。

第二种情况是：

curr->round > 0

这说明该节点虽然挂载在当前槽位中，但还没有到真正触发的轮次。也就是说，当前这一次扫描到它所在的槽位时，它还不能执行回调函数。因此这里只需要将 round 减一，然后继续遍历后续节点即可。

第三种情况是：

now < curr->expireTime && curr->round == 0

也就是进入最后的 else 分支。

这里需要特别注意，这种情况并不是由时间轮的时间粒度造成的。因为在 addTimer() 函数中，我们已经对 ticks 进行了向上取整：

int ticks = (delay_ms + tick_interval - 1) / tick_interval;

向上取整的作用，就是保证定时器节点不会被提前触发。也就是说，在正常情况下，定时器最多会因为时间轮的时间粒度而延后执行，而不会在真正过期之前被执行。

那么，为什么还会出现 round == 0，但是 now < expireTime 的情况呢？

这主要是因为在多线程环境下，超时检测线程并不一定能够严格按照固定时间刻度运行。

假设时间轮的时间刻度 tick_interval 为 1 秒，也就是说，理想情况下，超时检测线程应该每隔 1 秒调用一次 tick()，让时间轮向后推进一个槽位。

但是在真实环境中，线程可能会因为 CPU 调度、系统负载或者其他阻塞原因没有及时运行。比如在 t 时刻，时间轮本来应该每隔 1 秒推进一次，但是超时检测线程被调度走了，直到 5 秒之后才重新获得 CPU 执行权。

在这 5 秒期间，时间轮内部的 currentslot 并没有及时向后推进，它仍然停留在一个相对滞后的槽位上。此时如果有其他线程调用 addTimer()，向时间轮中插入一个新的定时器节点，那么这个新节点就会基于当前这个滞后的 currentslot 来计算自己的目标槽位。

例如，某个线程在这 5 秒期间插入了一个 2 秒后过期的定时任务。由于此时时间轮的 currentslot 还没有及时更新，所以该节点计算出的 slotIndex 实际上是基于一个已经落后于真实时间的槽位位置。

随后，超时检测线程恢复执行并调用 tick()。此时它会根据当前时间和 lastTickTime 计算出真实已经过去了 5 个时间刻度，因此不会只推进一个槽位，而是会连续补偿推进 5 个槽位。

问题就出在这个补偿推进过程中：时间轮可能会扫描到刚才那个新插入节点所在的槽位。

从时间轮的槽位和 round 角度看，这个节点已经被扫描到了，并且它的 round 可能也已经等于 0；但是从真实时间点来看，这个节点是刚刚在那 5 秒期间插入的，它设定的是 2 秒后过期，当前时间可能还没有真正到达它的 expireTime。

于是就会出现这种情况：

now < curr->expireTime && curr->round == 0

也就是说，该节点只是因为时间轮在补偿推进过程中提前扫描到了它所在的槽位，并不代表它真的已经过期。

因此，这个分支不能直接执行回调函数，否则就会造成定时器提前触发。

对于这种节点，正确的处理方式是：先将它从当前槽位链表中摘除，然后根据当前时间 now 和节点真正的过期时间 expireTime，重新计算它还剩余多少时间：

auto remaining = node->expireTime - now;

接着再根据这个剩余时间重新计算 ticks、slotIndex 和 round，最后把它重新插入到新的槽位中。

也就是说，这个分支的本质不是处理“时间粒度误差”，而是处理“时间轮逻辑槽位滞后于真实时间时，新插入节点被补偿推进提前扫描到”的情况。

通过重新计算剩余时间并重新挂载节点，可以避免两个问题：

一方面，避免节点在真正到达 expireTime 之前被提前触发；

另一方面，避免节点继续停留在已经扫描过的当前槽位中，导致后续必须再等一整圈才能被重新检查。

popTask() 实现：到期任务的取出与回调执行

最后实现的是 popTask() 函数。

该函数的作用是从任务队列中取出一个已经到期的回调任务。由于任务队列 taskQueue 会被多个线程访问：超时检测线程会向其中插入到期任务，而工作线程会从其中取出任务执行，所以在访问任务队列之前，需要先使用 taskQueue_mtx 加锁保护。

在函数内部，首先判断任务队列是否为空。如果队列为空，说明当前没有需要执行的到期任务，此时直接返回 false。如果队列不为空，就取出队首元素，并通过移动语义将其赋值给外部传入的 task，然后将队首元素从队列中弹出，最后返回 true，表示成功取出了一个任务。

bool popTask(fun_t& task)
{
    std::lock_guard<std::mutex> lock(taskQueue_mtx);

    if (taskQueue.empty())
    {
        return false;
    }

    task = std::move(taskQueue.front());
    taskQueue.pop();

    return true;
}

这里需要注意，popTask() 只负责从任务队列中取出回调函数，并不会在函数内部直接执行该回调。这样做的好处是，任务队列的锁只在取任务时短暂持有。等任务被取出之后，调用者可以在锁外执行回调函数，避免因为回调逻辑耗时过长而阻塞其他线程继续访问任务队列。

因此，外部线程在使用时，可以按照下面的方式调用：

TimeWheel::fun_t task;

if (tw.popTask(task))
{
    task();
}

这样，时间轮中的任务队列就完成了一个基本的生产者-消费者模型：tick() 负责将到期任务放入队列，而其他线程则通过 popTask() 取出任务并执行。

源码

TimeWheel.hpp:

#pragma once
#include<iostream>
#include<functional>
#include<vector>
#include<mutex>
#include<queue>
#include<chrono>
#include <stdexcept>


/**
 *  定时器节点类
 * 
 * 这个类表示一个定时器节点，用于存储定时器的回调函数、过期时间、轮次以及指向下一个节点的指针。
 */
class TimerNode  // 定时器节点类，用于管理定时任务的执行
{
   public:
       // 使用函数指针类型别名，定义一个接受无参数且返回void的函数类型
       using fun_t = std::function<void()>;  // 定义函数指针类型，用于存储回调函数
     TimerNode(fun_t _cb, std::chrono::steady_clock::time_point _expireTime, int _round)  // 构造函数，初始化定时器节点
    : cb(std::move(_cb))  // 使用移动语义初始化回调函数
    , expireTime(_expireTime)  // 初始化过期时间点
    , round(_round)  // 初始化轮次
    , next(nullptr)  // 初始化下一个节点的指针为空
     {
        
     }
     fun_t cb;  // 回调函数，用于定时器到期时执行
     std::chrono::steady_clock::time_point expireTime;  // 定时器的过期时间点
     int round;  // 定时器的轮次，可能用于重复执行的控制
     TimerNode* next;  // 指向下一个定时器节点的指针，用于链表结构
};

class TimeWheel
{
    public:
     using fun_t = std::function<void()>;
/**
 * 时间轮构造函数
 *  _slotSize 时间轮槽数量
 *  _tick_interval 时间轮每个槽的时间间隔(单位:毫秒)
 */
      TimeWheel(int _slotSize, int _tick_interval)
    : slotSize(_slotSize)        // 初始化时间轮槽数量
    , currentslot(0)             // 初始化当前槽索引为0
    , tick_interval(_tick_interval)  // 初始化时间间隔
      {
        lastTickTime=std::chrono::steady_clock::now();  // 记录构造时的系统时间作为最后更新时间
        if (_slotSize <= 0 || _tick_interval <= 0)   // 检查参数有效性
       {
    throw std::invalid_argument("slotSize and tick_interval must be positive");  // 参数无效时抛出异常
        }
          slots.resize(slotSize,nullptr);  // 初始化时间轮槽数组，大小为slotSize，每个元素初始化为nullptr
      }
/**
 *  TimeWheel类的析构函数
 * 用于释放时间轮中所有定时器节点的内存资源
 */
      ~TimeWheel()
      {
    // 使用互斥锁确保线程安全
          std::lock_guard<std::mutex> lock(slots_mtx);
    // 遍历时间轮的所有槽位
          for(auto& slot : slots)
          {
        // 当槽位不为空时，释放槽位中的所有定时器节点
              while(slot)
              {
            // 临时保存当前节点
                  TimerNode* temp=slot;
            // 将指针移动到下一个节点
                  slot=slot->next;
            // 删除当前节点
                  delete temp;
              }
          }
      }
/**
 *  向时间轮中添加一个定时器任务
 * 
 *  _cb       定时器到期时执行的回调函数
 *  delay_ms  延迟执行的时间，单位为毫秒
 */
void addTimer(fun_t _cb, int delay_ms)
{
    // 1. 如果延迟时间小于0，视为非法参数，直接返回，不添加定时器
    if (delay_ms < 0)
    {
        return;
    }
    // 2. 如果延迟时间等于0，说明需要立即执行
    else if (delay_ms == 0)
    {
        // 加锁保护任务队列，将回调函数直接放入就绪任务队列中
        // 使用 std::move 避免回调函数对象的额外拷贝开销
        std::lock_guard<std::mutex> lock(taskQueue_mtx);
        taskQueue.push(std::move(_cb));
        return;
    }

    // 3. 延迟时间大于0，计算定时器在时间轮中的具体位置和圈数

    // 计算定时器的绝对过期时间点（用于后续可能的精确检查或防抖逻辑）
    std::chrono::steady_clock::time_point expireTime = std::chrono::steady_clock::now() 
                                                     + std::chrono::milliseconds(delay_ms);

    // 计算定时器需要经过多少个“滴答”才会到期
    // (delay_ms + tick_interval - 1) 是向上取整的经典整型计算技巧，确保不足一个tick也算一个tick
    int ticks = (delay_ms + tick_interval - 1) / tick_interval;

    // 计算定时器需要转多少圈才会到期
    // 时间轮转一圈需要 slotSize 个 ticks，(ticks-1) 是因为当前槽位算作第0圈的开始
    int round = (ticks - 1) / slotSize;

    // 加锁保护时间轮的槽位数组，防止多线程并发导致链表结构损坏
    std::lock_guard<std::mutex> lock(slots_mtx);

    // 计算定时器应该插入的槽位索引
    // 当前槽位 currentslot 加上需要经过的 ticks，对总槽位数 slotSize 取余
    int slotIndex = (currentslot + ticks) % slotSize;

    // 创建新的定时器节点，记录回调、过期时间和圈数
    TimerNode* node = new TimerNode(std::move(_cb), expireTime, round);

    // 4. 将新节点采用“头插法”插入到对应槽位的单向链表中
    // 头插法时间复杂度为 O(1)，效率最高
    TimerNode* temp = slots[slotIndex]; // 暂存当前链表的头节点
    slots[slotIndex] = node;            // 新节点成为链表的头节点
    node->next = temp;                  // 将新节点的next指向原来的头节点
}

/**
 * 从任务队列中弹出一个任务
 *  task 引用，用于存储从队列中弹出的任务
 * return 如果队列为空则返回false，否则返回true并成功弹出任务
 */
      bool popTask(fun_t& task)
{
    // 使用互斥锁保护任务队列的访问，防止多线程竞争
    std::lock_guard<std::mutex> lock(taskQueue_mtx);

    // 检查任务队列是否为空
    if (taskQueue.empty())
    {
        return false;
    }

    // 将队列中的第一个任务移动到task参数中
    task = std::move(taskQueue.front());
    // 从队列中移除已处理的任务
    taskQueue.pop();

    return true;
}
      /**
 *  驱动时间轮向前转动，检查并收集所有到期的定时器任务
 * 
 * 该函数通常由一个独立的后台线程以固定频率调用，或者在事件循环中被唤醒时调用。
 * 它采用了"时间补偿"机制，即使系统调度出现延迟，也能准确触发期间错过的定时任务。
 */
void tick()
{
    // 用于临时收集当前这一轮 tick 中所有到期的任务
    std::vector<fun_t> expiredTasks;
    
    // 获取当前时间点，用于判断定时器是否到期
    auto now = std::chrono::steady_clock::now();

    // ============ 第一阶段：操作时间轮内部数据结构（加锁） ============
    {
        // 加锁保护时间轮的槽位、当前指针等内部状态，防止与 addTimer 并发冲突
        std::lock_guard<std::mutex> lock(slots_mtx);

        // 计算距离上一次 tick 经历的时间
        auto duration = now - lastTickTime;
        // 转换为毫秒数
        auto duration_ms = std::chrono::duration_cast<std::chrono::milliseconds>(duration).count();
        
        // 计算时间轮需要向前走几步
        int steps = duration_ms / tick_interval;

        // 如果经历的时间不足一个 tick_interval，则不需要推进，直接返回
        if (steps <= 0)
        {
            return;
        }

        // 逐步推进时间轮指针
        // 【注意】：这里使用 for 循环逐步推进，而不是直接跳跃 steps 步。
        // 这是因为必须逐个槽位检查并处理其中的任务（例如将 round 减 1），
        // 如果直接跳跃，会漏掉中间槽位上 round 已经减到 0 的到期任务。
        for (int i = 0; i < steps; i++)
        {
            // 当前指针向前走一步，通过取余实现循环滚动
            currentslot = (currentslot + 1) % slotSize;
            // 处理当前槽位：遍历链表，将 round 减 1，把 round 为 0 的任务移入 expiredTasks
            processCurrentSlot(now, expiredTasks);
        }

        // 更新最后一次 tick 的时间戳。
        // 【关键优化】：这里没有使用 lastTickTime = now，而是加上了实际推进的时间 (steps * tick_interval)。
        // 这样做可以避免时间漂移，将误差控制在单个 tick_interval 以内，而不会随着系统调度延迟不断累积。
        lastTickTime += std::chrono::milliseconds(steps * tick_interval);
    } // slots_mtx 在此处自动释放

    // ============ 第二阶段：将到期任务放入执行队列（加锁） ============
    {
        // 加锁保护就绪任务队列，防止与工作线程/0延迟任务的并发冲突
        std::lock_guard<std::mutex> lock(taskQueue_mtx);

        // 将所有到期任务推入就绪队列
        for (auto& task : expiredTasks)
        {
            // 使用 std::move 避免函数对象的额外拷贝开销
            taskQueue.push(std::move(task));
        }
    } // taskQueue_mtx 在此处自动释放
}


TimeWheel(const TimeWheel&) = delete;
TimeWheel& operator=(const TimeWheel&) = delete;
    private:
/**
 *  处理时间轮当前槽位的所有定时器节点
 * 
 * 遍历当前槽位对应的链表，根据定时器的状态执行三种操作：
 * 1. 已过期：提取回调任务，删除节点
 * 2. 未过期且需要转圈(round>0)：圈数减1，保留在当前槽位
 * 3. 未过期但不需要转圈(round==0)且未到期：重新计算剩余时间并迁移到正确的槽位
 * 
 *  now           当前的时间点，用于精确判断是否过期和计算剩余时间
 *  expiredTasks  [out] 用于收集已过期任务的回调函数列表
 */
void processCurrentSlot(std::chrono::steady_clock::time_point now, std::vector<fun_t>& expiredTasks)
{
    // 初始化前驱节点指针为空（用于单链表的节点删除操作）
    TimerNode* prev = nullptr;
    // 获取当前槽位链表的头节点
    TimerNode* curr = slots[currentslot];

    // 遍历当前槽位的所有定时器节点
    while (curr)
    {
        // ============ 情况1：定时器绝对时间已过期 ============
        // 即使 round 为 0，只要当前时间超过了 expireTime，就认为已过期
        // 这种设计比单纯依赖 round 更精确，能处理因系统调度延迟导致的提前/滞后触发
        if (now >= curr->expireTime)
        {
            // 将过期任务的回调函数加入到期列表，等待后续执行
            expiredTasks.push_back(curr->cb);
            
            // 从链表中摘除当前节点
            TimerNode* temp = curr; // 保存待删除节点
            curr = curr->next;      // 当前指针后移

            if (prev)
            {
                // 如果有前驱节点，将前驱的 next 指向当前的后继，跳过 temp
                prev->next = curr;
            }
            else
            {
                // 如果没有前驱节点，说明删除的是头节点，更新槽位头指针
                slots[currentslot] = curr;
            }
            
            // 释放被摘除节点的内存
            delete temp;
        }
        // ============ 情况2：定时器未过期，且还需要在时间轮中转圈 ============
        else if (curr->round > 0)
        {
            // 圈数减1，意味着时间轮又转了一圈，离触发更近了一步
            curr->round--;
            // 前驱指针后移，当前指针后移，继续检查下一个节点
            prev = curr;
            curr = curr->next;
        }
        // ============ 情况3：定时器未过期，round为0，但绝对时间还未到期 ============
        // 这种情况发生的原因：由于时间轮精度(tick_interval)限制，节点被放在了当前槽位，
        // 但它的实际过期时间在当前时间之后。如果不处理，会导致任务被提前触发。
        // 解决方案：将其从当前槽位摘除，根据剩余时间重新计算并插入到更远的槽位。
        else
        {
            TimerNode* node = curr;

            // 1. 从当前链表中摘除该节点
            if (prev)
            {
                prev->next = curr->next;
                curr = prev->next;
            }
            else
            {
                slots[currentslot] = curr->next;
                curr = slots[currentslot];
            }

            // 2. 根据剩余时间重新计算应该处于的槽位和圈数
            auto remaining = node->expireTime - now;
            int remaining_ms = std::chrono::duration_cast<std::chrono::milliseconds>(remaining).count();

            // 向上取整计算需要经过的 tick 数
            int ticks = (remaining_ms + tick_interval - 1) / tick_interval;
            // 防御性编程：确保至少移动 1 个 tick，避免原地重插导致死循环
            if (ticks <= 0)
            {
                ticks = 1;
            }
            
            // 计算新的槽位索引和圈数
            int slotIndex = (currentslot + ticks) % slotSize;
            node->round = (ticks - 1) / slotSize;

            // 3. 将该节点头插到新计算出的槽位中
            node->next = slots[slotIndex];
            slots[slotIndex] = node;
            
            // 【注意】此处 prev 指针不需要后移，因为当前节点 curr 已经被摘除，
            // 我们已经把 curr 更新为了被摘除节点的下一个节点。
        }
    }
}

    std::vector<TimerNode*> slots;
    int slotSize;
    int currentslot;
    int tick_interval;
    std::queue<fun_t> taskQueue;
    std::mutex slots_mtx;
    std::mutex taskQueue_mtx;
    std::chrono::steady_clock::time_point lastTickTime;
};

main.cpp:

#include <iostream>
#include <thread>
#include <chrono>
#include <utility>
#include "TimeWheel.hpp"

int main()
{
    using Clock = std::chrono::steady_clock;

    TimeWheel wheel(8, 100); // 8 slots, each slot represents 100 ms

    auto start = Clock::now();

    auto printElapsed = [&](const std::string& message) {
        auto now = Clock::now();
        auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(now - start).count();
        std::cout << "[" << elapsed << " ms] " << message << std::endl;
        };

    std::cout << "Time wheel test started" << std::endl;

    wheel.addTimer([&]() {
        printElapsed("Immediate task fired");
        }, 0);

    wheel.addTimer([&]() {
        printElapsed("150 ms task fired");
        }, 150);

    wheel.addTimer([&]() {
        printElapsed("300 ms task fired");
        }, 300);

    wheel.addTimer([&]() {
        printElapsed("900 ms task fired");
        }, 900);

    auto drainTasks = [&]() {
        TimeWheel::fun_t task;
        while (wheel.popTask(task))
        {
            task();
        }
        };

    // Execute immediate task
    drainTasks();

    std::cout << "Sleep for 350 ms" << std::endl;
    std::this_thread::sleep_for(std::chrono::milliseconds(350));

    std::cout << "Call tick after 350 ms" << std::endl;
    wheel.tick();
    drainTasks();

    std::cout << "Sleep for 700 ms" << std::endl;
    std::this_thread::sleep_for(std::chrono::milliseconds(700));

    std::cout << "Call tick after another 700 ms" << std::endl;
    wheel.tick();
    drainTasks();

    std::cout << "Test finished" << std::endl;

    return 0;
}

运行截图：

结语

那么这就是本篇文章的全部内容，带你掌握以及实现时间轮，我会持续更新，希望你能够多多关注，如果本文有帮助到你的话，还请三连加关注，你的支持就是我创作的最大动力！