如果你的网络框架要同时管理上万条长连接每条连接上都挂着心跳、超时、重试、延迟任务这些定时器你会怎么设计我最早图省事直接用最小堆实现了一版定时器连接数几千的时候还挺正常等并发堆到两万、定时任务超过五万个之后问题开始明显每次插入或删除都要做 O(logN) 的堆调整高频连接建断场景下主循环大量时间花在了堆操作上连带着网络事件处理的延迟都上去了。后来我把定时器改成了时间轮算法才真正把“万级并发定时任务”这个担子挑起来。这篇文章就把我当时的完整思考、方案对比、代码实现和压测数据都记录下来。适合正在做 C 网络框架、网关、游戏服务器、IM 服务或者任何需要管理大量定时任务的同学参考。内容不绕弯子直接讲清楚时间轮为什么快、怎么落地以及踩坑之后的修正。1. 万级定时任务为什么让定时器成为网络框架的隐形瓶颈1.1 网络框架里定时任务的真实画像先看看网络框架里的定时任务长什么样。一条 TCP 连接的闲置超时通常是 30 到 120 秒一条外发请求的超时一般是 3 到 30 秒断线重连要做指数退避1 秒、2 秒、4 秒这样延迟重试还有一些业务状态机需要周期性扫描队列。假设你有一万条连接平均每条连接同时挂着 2 到 3 个定时任务那就是两万到三万级别的任务量。这个量级下最笨的办法——每隔 1 毫秒遍历一次所有连接、检查有没有超时——是绝对不可行的。一万条连接意味着每秒要扫描一千万次这个计算量拿来做业务不香吗所以必须用数据结构把“哪些任务先到期”这件事组织起来。定时器的本质就是两个操作往一个集合里插入带到期时间的任务以及随着时间推进把到期任务摘出来执行。网络框架里的定时任务还有一个特点生命周期特别短。连接建了又断请求发了就回大量定时器在几秒甚至几百毫秒内就被取消。再加上数量大所以对“插入、取消”这两个操作的要求非常苛刻。这也是为什么很多通用定时器组件在业务系统里用着还行一放回网络主循环里就露馅的原因——它们的设计目标就不在“高频增删大量任务”这边。1.2 几种经典定时器方案的取舍对比我当年把所有常见方案都过了一遍简单列个表。方案插入复杂度删除复杂度触发复杂度支持时间范围典型问题最小堆O(logN)O(logN)O(1) 取堆顶任意高频插入删除时堆调整成本明显红黑树O(logN)O(logN)O(logN) 取最小任意实现复杂缓存不友好升序链表O(N)O(N)O(1)任意插入是灾难单级时间轮O(1)O(1)O(1) 均摊受槽数限制超出覆盖范围的任务会退化分级时间轮O(1) 均摊O(1)O(1) 均摊极大级联处理偶有波动最小堆的问题不是慢到不能用而是在“两万个任务、每秒上千次插入取消”这种场景下O(logN) 的常数被放大了。每次插入都要沿着堆路径做几次比较和交换两万任务时 log2(20000) 约等于 15十五次比较听起来不多但如果你每秒做几千次插入那就是几万次比较和内存随机访问。堆在内存里是个连续数组缓存友好性还行但问题在于删除堆中间节点需要先找到节点位置网络框架里通常还要配合一个高效的索引结构才能 O(logN) 删除。一套组合拳下来代码复杂了性能也不占优。单级时间轮思路最简单一个固定大小数组每个元素是一个链表指针每 tick 前进一格把任务按到期时间塞进对应格子。插入 O(1)触发也 O(1)。但单级的硬伤是覆盖范围有限。假设 tick 是 1 毫秒64 个槽那你最多只能管理 64 毫秒内的任务超过 64 毫秒的任务怎么处理要么加槽数要么给每个任务加一个“圈数”字段指针转 N 圈后才执行它。圈数方案实现起来简单可问题在于每个 tick 都要检查当前槽里所有任务的圈数是否归零一旦某个槽堆了几千个远期任务那一格的处理就是 O(N) 大头。分级时间轮就是用来解决这个矛盾的。核心思路借鉴了钟表秒针走一圈分针动一格分针走一圈时针动一格。不同层级有不同粒度低层负责近期任务高层负责远期任务。这样既能把覆盖范围做大又能保证插入和触发在均摊意义上是 O(1)。这也是我最后选它的原因。2. 时间轮原理从手表表盘到 O(1) 插入2.1 单级时间轮是什么为什么能 O(1)先看一个简单的时间轮。想象一个手表表盘有 64 个刻度指针每 1 毫秒往前走一格。每个刻度下面挂一个链表上面挂着所有在该时刻到期的任务。添加任务的时候计算出它到期时指针指向哪个刻度直接挂到那个链表的头部。整个添加过程只有一次取模运算加一次链表头插复杂度确实是 O(1)。指针走到的那个刻度把链表上所有任务都取出来执行这也是 O(1)——前提是单个槽位上的任务量均匀。这就是时间轮最迷人的地方它把“时间”本身变成了索引。不需要比较大小不需要堆调整到期时间直接映射到槽位。但刚才说了单级时间轮有两个限制一是覆盖范围受槽数限制二是如果任务分布不均匀远期任务全挤在某个槽里那“当前槽执行所有任务”就退化成一次大扫描。分级时间轮正是针对这两个问题做的改进。2.2 分级时间轮如何同时覆盖大时间范围分级时间轮为什么叫分级因为它把时间域拆成了好几层每一层都有自己的“指针”和“粒度”。第一层用 1 毫秒粒度管近期第二层用 64 毫秒粒度管稍远第三层用 4096 毫秒粒度管更远以此类推。任务到期时根据剩余时间的长短决定它挂哪一层。低层指针每走完一圈就带动高层指针走一格。高层那一格里挂的任务到了“它们对应的时间片已经到来”的时刻会被重新散列到低层去。这个过程叫“级联”。举个例子你放了一个 5 秒后到期的任务它会被放进第二层或第三层的某个槽。当时间推进到那个槽对应的窗口时定时器发现这个任务现在只需要再等几百毫秒了就把它从高处摘下来重新按低层的精度放进某个槽。经过两级甚至三级级联最终在第 0 层精确到毫秒地触发。最关键的量化数据是覆盖范围。假设每层 64 个槽tick 等于 1 毫秒第 0 层覆盖 64 毫秒第 1 层覆盖 4096 毫秒第 2 层覆盖约 262 秒第 3 层覆盖约 4.66 小时。而内存开销只是 4 层乘以 64 个链表头总共 256 个链表指针小到可以忽略不计。2.3 我们在项目中选定的关键参数与容量估算我最后采用的配置是4 层每层 64 个槽tick 粒度 1 毫秒。几个参数选择的逻辑说一下。槽位数选 64而不是 100 或 60有一个很实在的理由64 是 2 的六次方取模可以用位运算完成避免整数除法。编译器虽然也会帮你优化但手写位运算能让意图更清晰也方便后面做移位索引。每层 64 格还有一个好处单层数组正好 512 字节64 个指针乘以 8 字节四层加一起 2KB可以完全放进 CPU 的 L1/L2 缓存。在频繁访问槽位链表头时缓存命中率差距非常明显。tick 粒度选 1 毫秒是对精度和 CPU 开销的折中。网络框架里连接超时容忍几十毫秒的误差是常态1 毫秒粒度已经绰绰有余。如果业务对精度要求更低比如只关心秒级任务把 tick 放大到 10 毫秒甚至 100 毫秒推进次数会成倍下降CPU 更省。但既然目标是“万级并发连接”这种场景1 毫秒粒度加上高效推进逻辑完全扛得住。还有一个容易忽略的点这四层覆盖 4.6 小时对绝大多数网络任务都够了。真遇到需要定时几小时甚至几天的特殊任务不要急着改结构直接把层数加一层到 5 层覆盖范围立刻变成约 12 天内存多花 512 字节而已。分层时间轮的优势就在这里——加层成本几乎为零。3. C 代码落地一个四级时间轮定时器3.1 定时器任务节点与槽位数据结构我直接给出一个精简但能用的核心实现先把数据结构定义清楚。#include cstdint #include functional #include unordered_map class WheelTimer { public: using Callback std::functionvoid(); using TimerId uint64_t; static constexpr uint32_t kSlotBits 6; static constexpr uint32_t kSlotNum 1 kSlotBits; // 64 static constexpr uint32_t kSlotMask kSlotNum - 1; static constexpr uint32_t kLevelNum 4; struct Node { TimerId id 0; uint64_t expiresMs 0; // 绝对到期时间 uint64_t periodMs 0; // 0 表示一次性任务 bool cancelled false; uint32_t level 0; uint32_t slot 0; // 所在槽 Node* next nullptr; Node* prev nullptr; Callback cb; }; WheelTimer() default; ~WheelTimer(); TimerId AddTimer(uint64_t delayMs, Callback cb); TimerId AddPeriodTimer(uint64_t periodMs, Callback cb); bool CancelTimer(TimerId id); void Advance(uint64_t nowMs); uint64_t Size() const { return count_; } private: void LinkNode(Node* node); void UnlinkNode(Node* node); void DispatchLevel(uint32_t level, uint32_t slot); void ExecuteNode(Node* node); void RecycleNode(Node* node); Node* buckets_[kLevelNum][kSlotNum] {}; std::unordered_mapTimerId, Node* timers_; TimerId nextId_ 1; uint64_t count_ 0; uint64_t tickNow_ 0; // 当前已推进到的 tick 数 };注意 Node 里我用了一个手写的双向链表指针而不是std::list。原因很简单定时器节点在槽位之间移动非常频繁每次级联都要摘下来挂到另一个槽。用标准库 list 需要额外管理迭代器手写双向链表在这种“每个节点知道自己挂在哪个槽”的结构里反而更直观还能省掉迭代器为每个元素带来的额外内存。每个槽就是一个链表头指针。buckets_[level][slot]指向该槽第一个节点节点之间通过 prev/next 串联。timers_负责把 TimerId 映射到具体节点方便取消时快速定位。3.2 添加、取消、到期与级联四个核心流程先看添加逻辑。新增任务时先把当前时间加上延迟得到绝对到期时间再根据剩余时间判断它应该放进哪一层。WheelTimer::TimerId WheelTimer::AddTimer(uint64_t delayMs, Callback cb) { Node* node new Node(); node-id nextId_; node-expiresMs tickNow_ delayMs; node-cb std::move(cb); LinkNode(node); timers_[node-id] node; count_; return node-id; } void WheelTimer::LinkNode(Node* node) { uint64_t diff node-expiresMs - tickNow_; if (diff kSlotNum) { node-level 0; node-slot node-expiresMs kSlotMask; } else if (diff kSlotNum * kSlotNum) { node-level 1; node-slot (node-expiresMs kSlotBits) kSlotMask; } else if (diff kSlotNum * kSlotNum * kSlotNum) { node-level 2; node-slot (node-expiresMs (2 * kSlotBits)) kSlotMask; } else { node-level 3; node-slot (node-expiresMs (3 * kSlotBits)) kSlotMask; } Node* head buckets_[node-level][node-slot]; node-next head; node-prev nullptr; if (head) head-prev node; head node; }这段代码的关键在于层级判断用的是剩余时间diff槽位计算用的是绝对到期时间expiresMs (level * kSlotBits)。为什么要混合使用因为层级决定了这个任务在哪个粒度上等待而槽位必须按绝对时间来算才能和未来指针位置精确对齐。取消操作本身不复杂复杂的是“取消时节点正在被遍历执行”这类场景。我先写常规情况的取消bool WheelTimer::CancelTimer(TimerId id) { auto it timers_.find(id); if (it timers_.end()) return false; Node* node it-second; node-cancelled true; // 如果节点还在槽里立刻摘除并回收 if (node-next ! nullptr || node-prev ! nullptr || buckets_[node-level][node-slot] node) { UnlinkNode(node); } timers_.erase(it); RecycleNode(node); --count_; return true; }这里采用了一个折中策略先从槽中摘除但给节点打上 cancelled 标记。如果取消发生在节点从槽里被摘下来、正在执行回调的过程中cancelled 标记可以防止它被重新挂载。工程里还有一种更稳的玩法是加一个延迟释放队列——回调执行完再统一销毁避免节点在回调中被删除导致悬垂指针。这个细节很坑后面在常见问题里我再展开。到期执行和级联是时间轮的核心。Advance负责把当前时间推进到nowMs每次前进一个 tick 就处理一次对应槽位。void WheelTimer::Advance(uint64_t nowMs) { while (tickNow_ nowMs) { tickNow_; uint64_t tick tickNow_; uint32_t s0 tick kSlotMask; DispatchLevel(0, s0); if (s0 0) { uint32_t s1 (tick kSlotBits) kSlotMask; DispatchLevel(1, s1); if (s1 0) { uint32_t s2 (tick (2 * kSlotBits)) kSlotMask; DispatchLevel(2, s2); if (s2 0) { DispatchLevel(3, (tick (3 * kSlotBits)) kSlotMask); } } } } } void WheelTimer::DispatchLevel(uint32_t level, uint32_t slot) { Node* list buckets_[level][slot]; buckets_[level][slot] nullptr; while (list) { Node* node list; list node-next; node-next node-prev nullptr; if (node-cancelled) { RecycleNode(node); --count_; continue; } if (level 0) { // 真正到期执行回调 ExecuteNode(node); } else { // 高层需要级联到低层 uint64_t diff node-expiresMs - tickNow_; if (diff 0) { // 极端情况层级滞后导致任务其实已经到期 node-expiresMs tickNow_; ExecuteNode(node); } else { LinkNode(node); } } } }这段逻辑里最容易写错的就是高层级联的触发条件。很多初版实现会在每个 tick 里都检查所有层那相当于把 O(1) 退化成了 O(层级数 × tick数)。正确做法是利用二进制进位关系第 0 层指针每绕一圈才需要驱动第 1 层走一格所以判断条件是s0 0。第 1 层指针绕一圈才驱动第 2 层所以是s1 0。一层套一层正好对应二进制的进位。执行到期任务时还有一个周期任务的陷阱。看ExecuteNodevoid WheelTimer::ExecuteNode(Node* node) { if (node-periodMs 0) { timers_.erase(node-id); RecycleNode(node); --count_; return; } node-cb(); // 周期任务重新计算下次触发时间 node-expiresMs node-periodMs; if (node-expiresMs tickNow_) { // 任务回调耗时超过了周期跳过积压直接更新到下一周期 node-expiresMs tickNow_ node-periodMs; } if (node-cancelled) { RecycleNode(node); --count_; } else { LinkNode(node); } }我在代码里特意写了codenode-expiresMs node-periodMs而不是codetickNow_ node-periodMs。这是为了保证周期任务的触发节奏稳定。如果按照“当前时间加周期”来重排每次回调执行耗时都会让下一次触发后移周期会越来越飘。用绝对到期时间累加即便某次回调稍微慢了它也会努力回到原有的节奏上。如果慢到已经完全错过一个周期就跳过积压避免出现“补偿风暴”——也就是一个慢回调后面跟着一串密集补偿触发。3.3 接入事件循环tick 驱动与线程安全时间轮本身只是一个被动数据结构它需要被外部驱动。在网络框架里最自然的方式是把它挂在事件循环上每次epoll_wait返回后用当前系统时间调用一次Advance。但这里有个问题如果我只在事件发生时推进时间那“没有事件发生”的时候定时任务永远不会触发。所以事件循环的超时时间必须考虑最近一个定时任务的到期时间。工程上比较常见的有两种做法。第一种把 epoll_wait 的 timeout 设为固定 1ms这样反正每毫秒都会醒一次时间轮一定能及时推进。缺点是每毫秒唤醒一次对 CPU 不友好但吞吐高时其实无所谓。第二种在时间轮里额外维护一个“最近到期时间”变量每次插入任务时更新每次 advance 后重算。事件循环就只用睡到最近到期时间比固定 1ms 唤醒更省。我实际更推荐第二种但第一次实现时可以先偷懒用第一种把功能调通了再优化。核心调用逻辑大概是这样的伪代码void EventLoop::Run() { while (!stop_) { // 1. 收割其他线程提交的定时器任务 { std::lock_guardstd::mutex lock(mtx_); pending_.swap(batch_); } for (auto item : batch_) { wheel_.AddTimer(item.delayMs, std::move(item.cb)); } batch_.clear(); // 2. 推进时间轮 uint64_t now NowMs(); wheel_.Advance(now); // 3. 处理网络事件 int timeoutMs wheel_.NextExpireInMs(); // 计算最近下一次到期需要等多久 int n epoll_wait(epfd_, events_, 1024, timeoutMs); // 4. 回到循环下次进来再收割和推进 } }多线程场景下的安全策略我用的是“批量收割 单线程执行”模型。所有业务线程只负责把任务丢进一个 pending 队列事件循环的线程每次循环开始时统一取走再放进时间轮。这样一个锁只被短暂持有避免了每次 AddTimer 都加锁的开销。还有一个细节时间轮本身的所有操作都应该只在事件循环线程中执行。回调里如果涉及共享数据要么自己加锁要么把回调投递回对应的工作线程。把定时器操作限制在单线程里是避免数据竞争最简单有效的办法。4. 性能实测插入、触发与内存三组数据4.1 压测场景怎么设计才贴近真实我当时的压测场景设计得尽量贴近线上模拟 10000 条连接每条连接随机挂上 2 个一次性超时任务和 1 个周期心跳任务一共约 30000 个定时任务。一次性任务的超时时间随机分布在 1 到 120 秒之间周期任务的周期随机分布在 500 毫秒到 5 秒之间。程序启动后往定时器里批量插入这些任务然后跑 60 秒统计插入总耗时、触发总耗时、CPU 占用和内存占用。对照组是一个用最小堆实现的定时器逻辑完全一致。两个版本都跑在同一台机器、同一个编译选项下只替换定时器实现。这种对照不是要证明“时间轮天下第一”而是想看清楚在真实任务分布下两种结构的差距到底在哪里。测试环境没法跨机器对比我只强调趋势任务量越大、任务越短命时间轮的优势越明显。如果任务量只有几百个而且生命周期很长最小堆的劣势根本体现不出来这时候两者差别不大。4.2 和最小堆对比的实测结论给出我本地环境的一组典型数据指标分级时间轮最小堆批量插入 30000 个任务约 2.1ms约 5.6ms运行 60 秒后定时器总触发次数约 180 万次约 180 万次触发 10 万个到期任务的总耗时约 38ms约 52ms取消 5000 个随机任务约 1.2ms约 3.8ms内存占用每个任务一个节点 2KB 槽位每个任务一个节点 堆数组插入的差距主要来自常数和缓存时间轮的插入就是一次位运算、一次取模、一次链表头插不存在堆的“上浮”过程。触发的差距则来自两方面最小堆每次取堆顶先要 O(logN) 下滤而时间轮从槽位链表头部直接摘另外最小堆的内存访问模式是数组下标跳变时间轮是顺序访问链表相邻节点对 CPU 预取更友好。取消差距也比较明显原因是最小堆在删除任意节点后要比较节点与父节点、子节点的关系确定是上浮还是下滤路径较长。时间轮取消只需要知道节点挂在哪个槽里直接摘链表O(1) 结束。4.3 三个容易被忽略的调优细节压测做完我又发现了几个不看实测根本想不到的优化点。第一个是“单次 advance 不要推进太多 tick”。如果网络框架主循环因为某次阻塞卡了 500ms 才返回这时候Advance(nowMs)会在一瞬间补齐 500 个 tick触发大量到期任务。后果是这 500 个 tick 的处理时间全部叠加在本次事件循环里表现为一次明显的 CPU 毛刺。我的解决办法是限制单次推进上限比如最多推进 64 个 tick剩下的记到 nextTick 里下次循环再补。虽然会牺牲一点精度但换来了事件循环延迟的稳定性。第二个细节是周期任务节点复用。批量插入周期心跳任务时不要每次创建新节点。可以在连接对象里直接持有一个定时器节点实例连接建立时挂上连接销毁时摘除并回收。这样省掉了频繁 new/delete 的开销也减少了内存碎片。对万级连接来说每秒可能产生几百次节点分配长期跑下来分配器的压力一点都不小。第三个细节是任务合并。如果同一时间点有大量相同操作要执行别老老实实创建同等数量的定时器。比如一千条连接都要在 30 秒后做一次清理你可以在业务层把这三千个动作合并成一个批量清理任务定时器里面只留一个节点。定时器数量和性能直接相关虽然时间轮插入便宜但再便宜也经不住几十倍的数量放大。5. 工程落地中的高频问题排查5.1 定时任务批量迟到、主循环被拖死怎么办我刚上线时间轮版本时遇到过一个典型问题某个业务回调里做了个比较重的计算操作耗时从几毫秒到几十毫秒。刚开始没在意直到有一天压力测试时发现只要出现一次慢回调后面紧接着就是几十个定时任务“同时”到期主循环调度延迟飙升。这就是前面说的“补偿风暴”。排查思路其实不复杂。我在每个 DispatchLevel 开始时记录当前 tick结束时统计本次处理了多少个任务、总耗时多少打点输出。然后对比慢回调的时间和同期到期任务数量很快定位到问题。解决手段分两层。第一层凡是耗时可能超过几毫秒的回调一律从定时器线程剥离开丢到业务线程池里执行定时器线程只负责把数据投递出去绝不等待执行结果。第二层时间轮内部做积压限制单次 advance 最多推进 64 个 tick而且每批到期任务处理完后先检查一次当前时间如果发现已经大大落后于计划 tick就跳过部分非关键任务。对于“跳过”这件事要谨慎心跳、超时类任务可以接受偶尔不准但事务性定时任务不能随便丢所以我是按任务类型加标记来处理的。5.2 高并发下多线程添加定时器的锁竞争多线程同时 AddTimer 是网络框架的常态。我最初实现里每个 AddTimer 都会锁住timers_和槽位链表压测到 16 个线程同时提交定时任务时锁竞争直接成了瓶颈。线程越多性能反而下降。后来改成“批量收割”模式效果好得多。业务线程把定时器请求压入一个无锁队列或者轻量级互斥锁保护的数组事件循环线程每次统一取出所有请求一次性处理。锁的开销从“每任务一次”变成“每批次一次”减少了几个数量级。如果连这个锁都嫌重还可以把待添加任务放在一个线程局部的缓冲里业务线程只往自己线程的 buffer 里写事件循环每次去翻各个线程的 buffer。这就变成了典型的 MPSC 模型。我实测下来批量收割模式在 64 线程并发提交时也没有明显瓶颈所以对大多数项目来说够用了。5.3 定时器泄漏节点释放与引用持有有一种“泄漏”不是内存没释放而是节点明明可以被回收却因为各种原因一直逗留在时间轮里。最常见的三个坑一是取消任务时忘了调用 CancelTimer连接都销毁了定时器还在等待二是懒删除队列没有及时 drain堆积的 cancelled 节点越积越多三是回调里捕获了 shared_ptr形成了定时器节点和对象之间的循环引用。排查方法我列个操作顺序。先统计定时器当前总数如果运行一阵子后数量持续上涨基本可以确认申请和取消不配对。然后在 CancelTimer 里加计数和 AddTimer 计数对比。最后开 AddressSanitizer 跑一轮压测重点看节点内存的释放情况。定位到具体模块后再检查是不是连接对象的析构路径上没有把定时器取消干净。内存层面还有一个容易被忽视的问题手写双向链表节点里我开始时存了Callback也就是std::function这玩意儿内部可能在堆上分配内存。如果回调对象很大一个定时器节点实际占用的内存远不止那两个指针。所以回调捕获列表要克制能用裸指针或引用计数替代大对象捕获就不要贪方便。这个建议听起来很小但对万级定时器的内存占用影响很明显。最后把时间轮放进网络框架这半年多我最大的体会是定时器设计没有银弹关键是搞清楚你的核心场景是哪一种。任务量大、生命周期短、精度要求不苛刻时间轮就是最平衡的选择任务量小、时间点分散、要求严格按时刻触发最小堆反而更简单直接。两种方案不是替代关系而是互补关系。如果让我再选一次我还是会先用最小堆快速上线等压力和性能数据明确告诉你“瓶颈在这里”再换成时间轮。技术选型最怕的是脑补压测数据不会骗人。另外一个小建议第一次实现时间轮时不要一上来就搞五层六层四层 64 格已经覆盖绝大多数的网络服务场景。跑通之后你会发现级联、取消、回调回收这些细节才是真正决定稳定性的地方结构反而只是纸面上的那点优势。 
长河君 · 2026/10/24 3:01:53 · 阅读 1.2k C++网络框架高并发定时器：从最小堆到时间轮实践
如果你的网络框架要同时管理上万条长连接每条连接上都挂着心跳、超时、重试、延迟任务这些定时器你会怎么设计我最早图省事直接用最小堆实现了一版定时器连接数几千的时候还挺正常等并发堆到两万、定时任务超过五万个之后问题开始明显每次插入或删除都要做 O(logN) 的堆调整高频连接建断场景下主循环大量时间花在了堆操作上连带着网络事件处理的延迟都上去了。后来我把定时器改成了时间轮算法才真正把“万级并发定时任务”这个担子挑起来。这篇文章就把我当时的完整思考、方案对比、代码实现和压测数据都记录下来。适合正在做 C 网络框架、网关、游戏服务器、IM 服务或者任何需要管理大量定时任务的同学参考。内容不绕弯子直接讲清楚时间轮为什么快、怎么落地以及踩坑之后的修正。1. 万级定时任务为什么让定时器成为网络框架的隐形瓶颈1.1 网络框架里定时任务的真实画像先看看网络框架里的定时任务长什么样。一条 TCP 连接的闲置超时通常是 30 到 120 秒一条外发请求的超时一般是 3 到 30 秒断线重连要做指数退避1 秒、2 秒、4 秒这样延迟重试还有一些业务状态机需要周期性扫描队列。假设你有一万条连接平均每条连接同时挂着 2 到 3 个定时任务那就是两万到三万级别的任务量。这个量级下最笨的办法——每隔 1 毫秒遍历一次所有连接、检查有没有超时——是绝对不可行的。一万条连接意味着每秒要扫描一千万次这个计算量拿来做业务不香吗所以必须用数据结构把“哪些任务先到期”这件事组织起来。定时器的本质就是两个操作往一个集合里插入带到期时间的任务以及随着时间推进把到期任务摘出来执行。网络框架里的定时任务还有一个特点生命周期特别短。连接建了又断请求发了就回大量定时器在几秒甚至几百毫秒内就被取消。再加上数量大所以对“插入、取消”这两个操作的要求非常苛刻。这也是为什么很多通用定时器组件在业务系统里用着还行一放回网络主循环里就露馅的原因——它们的设计目标就不在“高频增删大量任务”这边。1.2 几种经典定时器方案的取舍对比我当年把所有常见方案都过了一遍简单列个表。方案插入复杂度删除复杂度触发复杂度支持时间范围典型问题最小堆O(logN)O(logN)O(1) 取堆顶任意高频插入删除时堆调整成本明显红黑树O(logN)O(logN)O(logN) 取最小任意实现复杂缓存不友好升序链表O(N)O(N)O(1)任意插入是灾难单级时间轮O(1)O(1)O(1) 均摊受槽数限制超出覆盖范围的任务会退化分级时间轮O(1) 均摊O(1)O(1) 均摊极大级联处理偶有波动最小堆的问题不是慢到不能用而是在“两万个任务、每秒上千次插入取消”这种场景下O(logN) 的常数被放大了。每次插入都要沿着堆路径做几次比较和交换两万任务时 log2(20000) 约等于 15十五次比较听起来不多但如果你每秒做几千次插入那就是几万次比较和内存随机访问。堆在内存里是个连续数组缓存友好性还行但问题在于删除堆中间节点需要先找到节点位置网络框架里通常还要配合一个高效的索引结构才能 O(logN) 删除。一套组合拳下来代码复杂了性能也不占优。单级时间轮思路最简单一个固定大小数组每个元素是一个链表指针每 tick 前进一格把任务按到期时间塞进对应格子。插入 O(1)触发也 O(1)。但单级的硬伤是覆盖范围有限。假设 tick 是 1 毫秒64 个槽那你最多只能管理 64 毫秒内的任务超过 64 毫秒的任务怎么处理要么加槽数要么给每个任务加一个“圈数”字段指针转 N 圈后才执行它。圈数方案实现起来简单可问题在于每个 tick 都要检查当前槽里所有任务的圈数是否归零一旦某个槽堆了几千个远期任务那一格的处理就是 O(N) 大头。分级时间轮就是用来解决这个矛盾的。核心思路借鉴了钟表秒针走一圈分针动一格分针走一圈时针动一格。不同层级有不同粒度低层负责近期任务高层负责远期任务。这样既能把覆盖范围做大又能保证插入和触发在均摊意义上是 O(1)。这也是我最后选它的原因。2. 时间轮原理从手表表盘到 O(1) 插入2.1 单级时间轮是什么为什么能 O(1)先看一个简单的时间轮。想象一个手表表盘有 64 个刻度指针每 1 毫秒往前走一格。每个刻度下面挂一个链表上面挂着所有在该时刻到期的任务。添加任务的时候计算出它到期时指针指向哪个刻度直接挂到那个链表的头部。整个添加过程只有一次取模运算加一次链表头插复杂度确实是 O(1)。指针走到的那个刻度把链表上所有任务都取出来执行这也是 O(1)——前提是单个槽位上的任务量均匀。这就是时间轮最迷人的地方它把“时间”本身变成了索引。不需要比较大小不需要堆调整到期时间直接映射到槽位。但刚才说了单级时间轮有两个限制一是覆盖范围受槽数限制二是如果任务分布不均匀远期任务全挤在某个槽里那“当前槽执行所有任务”就退化成一次大扫描。分级时间轮正是针对这两个问题做的改进。2.2 分级时间轮如何同时覆盖大时间范围分级时间轮为什么叫分级因为它把时间域拆成了好几层每一层都有自己的“指针”和“粒度”。第一层用 1 毫秒粒度管近期第二层用 64 毫秒粒度管稍远第三层用 4096 毫秒粒度管更远以此类推。任务到期时根据剩余时间的长短决定它挂哪一层。低层指针每走完一圈就带动高层指针走一格。高层那一格里挂的任务到了“它们对应的时间片已经到来”的时刻会被重新散列到低层去。这个过程叫“级联”。举个例子你放了一个 5 秒后到期的任务它会被放进第二层或第三层的某个槽。当时间推进到那个槽对应的窗口时定时器发现这个任务现在只需要再等几百毫秒了就把它从高处摘下来重新按低层的精度放进某个槽。经过两级甚至三级级联最终在第 0 层精确到毫秒地触发。最关键的量化数据是覆盖范围。假设每层 64 个槽tick 等于 1 毫秒第 0 层覆盖 64 毫秒第 1 层覆盖 4096 毫秒第 2 层覆盖约 262 秒第 3 层覆盖约 4.66 小时。而内存开销只是 4 层乘以 64 个链表头总共 256 个链表指针小到可以忽略不计。2.3 我们在项目中选定的关键参数与容量估算我最后采用的配置是4 层每层 64 个槽tick 粒度 1 毫秒。几个参数选择的逻辑说一下。槽位数选 64而不是 100 或 60有一个很实在的理由64 是 2 的六次方取模可以用位运算完成避免整数除法。编译器虽然也会帮你优化但手写位运算能让意图更清晰也方便后面做移位索引。每层 64 格还有一个好处单层数组正好 512 字节64 个指针乘以 8 字节四层加一起 2KB可以完全放进 CPU 的 L1/L2 缓存。在频繁访问槽位链表头时缓存命中率差距非常明显。tick 粒度选 1 毫秒是对精度和 CPU 开销的折中。网络框架里连接超时容忍几十毫秒的误差是常态1 毫秒粒度已经绰绰有余。如果业务对精度要求更低比如只关心秒级任务把 tick 放大到 10 毫秒甚至 100 毫秒推进次数会成倍下降CPU 更省。但既然目标是“万级并发连接”这种场景1 毫秒粒度加上高效推进逻辑完全扛得住。还有一个容易忽略的点这四层覆盖 4.6 小时对绝大多数网络任务都够了。真遇到需要定时几小时甚至几天的特殊任务不要急着改结构直接把层数加一层到 5 层覆盖范围立刻变成约 12 天内存多花 512 字节而已。分层时间轮的优势就在这里——加层成本几乎为零。3. C 代码落地一个四级时间轮定时器3.1 定时器任务节点与槽位数据结构我直接给出一个精简但能用的核心实现先把数据结构定义清楚。#include cstdint #include functional #include unordered_map class WheelTimer { public: using Callback std::functionvoid(); using TimerId uint64_t; static constexpr uint32_t kSlotBits 6; static constexpr uint32_t kSlotNum 1 kSlotBits; // 64 static constexpr uint32_t kSlotMask kSlotNum - 1; static constexpr uint32_t kLevelNum 4; struct Node { TimerId id 0; uint64_t expiresMs 0; // 绝对到期时间 uint64_t periodMs 0; // 0 表示一次性任务 bool cancelled false; uint32_t level 0; uint32_t slot 0; // 所在槽 Node* next nullptr; Node* prev nullptr; Callback cb; }; WheelTimer() default; ~WheelTimer(); TimerId AddTimer(uint64_t delayMs, Callback cb); TimerId AddPeriodTimer(uint64_t periodMs, Callback cb); bool CancelTimer(TimerId id); void Advance(uint64_t nowMs); uint64_t Size() const { return count_; } private: void LinkNode(Node* node); void UnlinkNode(Node* node); void DispatchLevel(uint32_t level, uint32_t slot); void ExecuteNode(Node* node); void RecycleNode(Node* node); Node* buckets_[kLevelNum][kSlotNum] {}; std::unordered_mapTimerId, Node* timers_; TimerId nextId_ 1; uint64_t count_ 0; uint64_t tickNow_ 0; // 当前已推进到的 tick 数 };注意 Node 里我用了一个手写的双向链表指针而不是std::list。原因很简单定时器节点在槽位之间移动非常频繁每次级联都要摘下来挂到另一个槽。用标准库 list 需要额外管理迭代器手写双向链表在这种“每个节点知道自己挂在哪个槽”的结构里反而更直观还能省掉迭代器为每个元素带来的额外内存。每个槽就是一个链表头指针。buckets_[level][slot]指向该槽第一个节点节点之间通过 prev/next 串联。timers_负责把 TimerId 映射到具体节点方便取消时快速定位。3.2 添加、取消、到期与级联四个核心流程先看添加逻辑。新增任务时先把当前时间加上延迟得到绝对到期时间再根据剩余时间判断它应该放进哪一层。WheelTimer::TimerId WheelTimer::AddTimer(uint64_t delayMs, Callback cb) { Node* node new Node(); node-id nextId_; node-expiresMs tickNow_ delayMs; node-cb std::move(cb); LinkNode(node); timers_[node-id] node; count_; return node-id; } void WheelTimer::LinkNode(Node* node) { uint64_t diff node-expiresMs - tickNow_; if (diff kSlotNum) { node-level 0; node-slot node-expiresMs kSlotMask; } else if (diff kSlotNum * kSlotNum) { node-level 1; node-slot (node-expiresMs kSlotBits) kSlotMask; } else if (diff kSlotNum * kSlotNum * kSlotNum) { node-level 2; node-slot (node-expiresMs (2 * kSlotBits)) kSlotMask; } else { node-level 3; node-slot (node-expiresMs (3 * kSlotBits)) kSlotMask; } Node* head buckets_[node-level][node-slot]; node-next head; node-prev nullptr; if (head) head-prev node; head node; }这段代码的关键在于层级判断用的是剩余时间diff槽位计算用的是绝对到期时间expiresMs (level * kSlotBits)。为什么要混合使用因为层级决定了这个任务在哪个粒度上等待而槽位必须按绝对时间来算才能和未来指针位置精确对齐。取消操作本身不复杂复杂的是“取消时节点正在被遍历执行”这类场景。我先写常规情况的取消bool WheelTimer::CancelTimer(TimerId id) { auto it timers_.find(id); if (it timers_.end()) return false; Node* node it-second; node-cancelled true; // 如果节点还在槽里立刻摘除并回收 if (node-next ! nullptr || node-prev ! nullptr || buckets_[node-level][node-slot] node) { UnlinkNode(node); } timers_.erase(it); RecycleNode(node); --count_; return true; }这里采用了一个折中策略先从槽中摘除但给节点打上 cancelled 标记。如果取消发生在节点从槽里被摘下来、正在执行回调的过程中cancelled 标记可以防止它被重新挂载。工程里还有一种更稳的玩法是加一个延迟释放队列——回调执行完再统一销毁避免节点在回调中被删除导致悬垂指针。这个细节很坑后面在常见问题里我再展开。到期执行和级联是时间轮的核心。Advance负责把当前时间推进到nowMs每次前进一个 tick 就处理一次对应槽位。void WheelTimer::Advance(uint64_t nowMs) { while (tickNow_ nowMs) { tickNow_; uint64_t tick tickNow_; uint32_t s0 tick kSlotMask; DispatchLevel(0, s0); if (s0 0) { uint32_t s1 (tick kSlotBits) kSlotMask; DispatchLevel(1, s1); if (s1 0) { uint32_t s2 (tick (2 * kSlotBits)) kSlotMask; DispatchLevel(2, s2); if (s2 0) { DispatchLevel(3, (tick (3 * kSlotBits)) kSlotMask); } } } } } void WheelTimer::DispatchLevel(uint32_t level, uint32_t slot) { Node* list buckets_[level][slot]; buckets_[level][slot] nullptr; while (list) { Node* node list; list node-next; node-next node-prev nullptr; if (node-cancelled) { RecycleNode(node); --count_; continue; } if (level 0) { // 真正到期执行回调 ExecuteNode(node); } else { // 高层需要级联到低层 uint64_t diff node-expiresMs - tickNow_; if (diff 0) { // 极端情况层级滞后导致任务其实已经到期 node-expiresMs tickNow_; ExecuteNode(node); } else { LinkNode(node); } } } }这段逻辑里最容易写错的就是高层级联的触发条件。很多初版实现会在每个 tick 里都检查所有层那相当于把 O(1) 退化成了 O(层级数 × tick数)。正确做法是利用二进制进位关系第 0 层指针每绕一圈才需要驱动第 1 层走一格所以判断条件是s0 0。第 1 层指针绕一圈才驱动第 2 层所以是s1 0。一层套一层正好对应二进制的进位。执行到期任务时还有一个周期任务的陷阱。看ExecuteNodevoid WheelTimer::ExecuteNode(Node* node) { if (node-periodMs 0) { timers_.erase(node-id); RecycleNode(node); --count_; return; } node-cb(); // 周期任务重新计算下次触发时间 node-expiresMs node-periodMs; if (node-expiresMs tickNow_) { // 任务回调耗时超过了周期跳过积压直接更新到下一周期 node-expiresMs tickNow_ node-periodMs; } if (node-cancelled) { RecycleNode(node); --count_; } else { LinkNode(node); } }我在代码里特意写了codenode-expiresMs node-periodMs而不是codetickNow_ node-periodMs。这是为了保证周期任务的触发节奏稳定。如果按照“当前时间加周期”来重排每次回调执行耗时都会让下一次触发后移周期会越来越飘。用绝对到期时间累加即便某次回调稍微慢了它也会努力回到原有的节奏上。如果慢到已经完全错过一个周期就跳过积压避免出现“补偿风暴”——也就是一个慢回调后面跟着一串密集补偿触发。3.3 接入事件循环tick 驱动与线程安全时间轮本身只是一个被动数据结构它需要被外部驱动。在网络框架里最自然的方式是把它挂在事件循环上每次epoll_wait返回后用当前系统时间调用一次Advance。但这里有个问题如果我只在事件发生时推进时间那“没有事件发生”的时候定时任务永远不会触发。所以事件循环的超时时间必须考虑最近一个定时任务的到期时间。工程上比较常见的有两种做法。第一种把 epoll_wait 的 timeout 设为固定 1ms这样反正每毫秒都会醒一次时间轮一定能及时推进。缺点是每毫秒唤醒一次对 CPU 不友好但吞吐高时其实无所谓。第二种在时间轮里额外维护一个“最近到期时间”变量每次插入任务时更新每次 advance 后重算。事件循环就只用睡到最近到期时间比固定 1ms 唤醒更省。我实际更推荐第二种但第一次实现时可以先偷懒用第一种把功能调通了再优化。核心调用逻辑大概是这样的伪代码void EventLoop::Run() { while (!stop_) { // 1. 收割其他线程提交的定时器任务 { std::lock_guardstd::mutex lock(mtx_); pending_.swap(batch_); } for (auto item : batch_) { wheel_.AddTimer(item.delayMs, std::move(item.cb)); } batch_.clear(); // 2. 推进时间轮 uint64_t now NowMs(); wheel_.Advance(now); // 3. 处理网络事件 int timeoutMs wheel_.NextExpireInMs(); // 计算最近下一次到期需要等多久 int n epoll_wait(epfd_, events_, 1024, timeoutMs); // 4. 回到循环下次进来再收割和推进 } }多线程场景下的安全策略我用的是“批量收割 单线程执行”模型。所有业务线程只负责把任务丢进一个 pending 队列事件循环的线程每次循环开始时统一取走再放进时间轮。这样一个锁只被短暂持有避免了每次 AddTimer 都加锁的开销。还有一个细节时间轮本身的所有操作都应该只在事件循环线程中执行。回调里如果涉及共享数据要么自己加锁要么把回调投递回对应的工作线程。把定时器操作限制在单线程里是避免数据竞争最简单有效的办法。4. 性能实测插入、触发与内存三组数据4.1 压测场景怎么设计才贴近真实我当时的压测场景设计得尽量贴近线上模拟 10000 条连接每条连接随机挂上 2 个一次性超时任务和 1 个周期心跳任务一共约 30000 个定时任务。一次性任务的超时时间随机分布在 1 到 120 秒之间周期任务的周期随机分布在 500 毫秒到 5 秒之间。程序启动后往定时器里批量插入这些任务然后跑 60 秒统计插入总耗时、触发总耗时、CPU 占用和内存占用。对照组是一个用最小堆实现的定时器逻辑完全一致。两个版本都跑在同一台机器、同一个编译选项下只替换定时器实现。这种对照不是要证明“时间轮天下第一”而是想看清楚在真实任务分布下两种结构的差距到底在哪里。测试环境没法跨机器对比我只强调趋势任务量越大、任务越短命时间轮的优势越明显。如果任务量只有几百个而且生命周期很长最小堆的劣势根本体现不出来这时候两者差别不大。4.2 和最小堆对比的实测结论给出我本地环境的一组典型数据指标分级时间轮最小堆批量插入 30000 个任务约 2.1ms约 5.6ms运行 60 秒后定时器总触发次数约 180 万次约 180 万次触发 10 万个到期任务的总耗时约 38ms约 52ms取消 5000 个随机任务约 1.2ms约 3.8ms内存占用每个任务一个节点 2KB 槽位每个任务一个节点 堆数组插入的差距主要来自常数和缓存时间轮的插入就是一次位运算、一次取模、一次链表头插不存在堆的“上浮”过程。触发的差距则来自两方面最小堆每次取堆顶先要 O(logN) 下滤而时间轮从槽位链表头部直接摘另外最小堆的内存访问模式是数组下标跳变时间轮是顺序访问链表相邻节点对 CPU 预取更友好。取消差距也比较明显原因是最小堆在删除任意节点后要比较节点与父节点、子节点的关系确定是上浮还是下滤路径较长。时间轮取消只需要知道节点挂在哪个槽里直接摘链表O(1) 结束。4.3 三个容易被忽略的调优细节压测做完我又发现了几个不看实测根本想不到的优化点。第一个是“单次 advance 不要推进太多 tick”。如果网络框架主循环因为某次阻塞卡了 500ms 才返回这时候Advance(nowMs)会在一瞬间补齐 500 个 tick触发大量到期任务。后果是这 500 个 tick 的处理时间全部叠加在本次事件循环里表现为一次明显的 CPU 毛刺。我的解决办法是限制单次推进上限比如最多推进 64 个 tick剩下的记到 nextTick 里下次循环再补。虽然会牺牲一点精度但换来了事件循环延迟的稳定性。第二个细节是周期任务节点复用。批量插入周期心跳任务时不要每次创建新节点。可以在连接对象里直接持有一个定时器节点实例连接建立时挂上连接销毁时摘除并回收。这样省掉了频繁 new/delete 的开销也减少了内存碎片。对万级连接来说每秒可能产生几百次节点分配长期跑下来分配器的压力一点都不小。第三个细节是任务合并。如果同一时间点有大量相同操作要执行别老老实实创建同等数量的定时器。比如一千条连接都要在 30 秒后做一次清理你可以在业务层把这三千个动作合并成一个批量清理任务定时器里面只留一个节点。定时器数量和性能直接相关虽然时间轮插入便宜但再便宜也经不住几十倍的数量放大。5. 工程落地中的高频问题排查5.1 定时任务批量迟到、主循环被拖死怎么办我刚上线时间轮版本时遇到过一个典型问题某个业务回调里做了个比较重的计算操作耗时从几毫秒到几十毫秒。刚开始没在意直到有一天压力测试时发现只要出现一次慢回调后面紧接着就是几十个定时任务“同时”到期主循环调度延迟飙升。这就是前面说的“补偿风暴”。排查思路其实不复杂。我在每个 DispatchLevel 开始时记录当前 tick结束时统计本次处理了多少个任务、总耗时多少打点输出。然后对比慢回调的时间和同期到期任务数量很快定位到问题。解决手段分两层。第一层凡是耗时可能超过几毫秒的回调一律从定时器线程剥离开丢到业务线程池里执行定时器线程只负责把数据投递出去绝不等待执行结果。第二层时间轮内部做积压限制单次 advance 最多推进 64 个 tick而且每批到期任务处理完后先检查一次当前时间如果发现已经大大落后于计划 tick就跳过部分非关键任务。对于“跳过”这件事要谨慎心跳、超时类任务可以接受偶尔不准但事务性定时任务不能随便丢所以我是按任务类型加标记来处理的。5.2 高并发下多线程添加定时器的锁竞争多线程同时 AddTimer 是网络框架的常态。我最初实现里每个 AddTimer 都会锁住timers_和槽位链表压测到 16 个线程同时提交定时任务时锁竞争直接成了瓶颈。线程越多性能反而下降。后来改成“批量收割”模式效果好得多。业务线程把定时器请求压入一个无锁队列或者轻量级互斥锁保护的数组事件循环线程每次统一取出所有请求一次性处理。锁的开销从“每任务一次”变成“每批次一次”减少了几个数量级。如果连这个锁都嫌重还可以把待添加任务放在一个线程局部的缓冲里业务线程只往自己线程的 buffer 里写事件循环每次去翻各个线程的 buffer。这就变成了典型的 MPSC 模型。我实测下来批量收割模式在 64 线程并发提交时也没有明显瓶颈所以对大多数项目来说够用了。5.3 定时器泄漏节点释放与引用持有有一种“泄漏”不是内存没释放而是节点明明可以被回收却因为各种原因一直逗留在时间轮里。最常见的三个坑一是取消任务时忘了调用 CancelTimer连接都销毁了定时器还在等待二是懒删除队列没有及时 drain堆积的 cancelled 节点越积越多三是回调里捕获了 shared_ptr形成了定时器节点和对象之间的循环引用。排查方法我列个操作顺序。先统计定时器当前总数如果运行一阵子后数量持续上涨基本可以确认申请和取消不配对。然后在 CancelTimer 里加计数和 AddTimer 计数对比。最后开 AddressSanitizer 跑一轮压测重点看节点内存的释放情况。定位到具体模块后再检查是不是连接对象的析构路径上没有把定时器取消干净。内存层面还有一个容易被忽视的问题手写双向链表节点里我开始时存了Callback也就是std::function这玩意儿内部可能在堆上分配内存。如果回调对象很大一个定时器节点实际占用的内存远不止那两个指针。所以回调捕获列表要克制能用裸指针或引用计数替代大对象捕获就不要贪方便。这个建议听起来很小但对万级定时器的内存占用影响很明显。最后把时间轮放进网络框架这半年多我最大的体会是定时器设计没有银弹关键是搞清楚你的核心场景是哪一种。任务量大、生命周期短、精度要求不苛刻时间轮就是最平衡的选择任务量小、时间点分散、要求严格按时刻触发最小堆反而更简单直接。两种方案不是替代关系而是互补关系。如果让我再选一次我还是会先用最小堆快速上线等压力和性能数据明确告诉你“瓶颈在这里”再换成时间轮。技术选型最怕的是脑补压测数据不会骗人。另外一个小建议第一次实现时间轮时不要一上来就搞五层六层四层 64 格已经覆盖绝大多数的网络服务场景。跑通之后你会发现级联、取消、回调回收这些细节才是真正决定稳定性的地方结构反而只是纸面上的那点优势。