Rust及 C++ 异步库的计时器实现

最近一直在学习网络编程，尝试使用 C++ 编写一个支持 C++20 co_await 的网络库。在实现 Socket 连接超时自动断开的特性时，发现定时器（Timer）的底层设计与实现别有洞天。

在 Rust 著名的异步运行时 Tokio 中，定时器采用的是**时间轮（Timer Wheel）**的设计。在底层，这是一个高度依赖指针链表的数据结构：它的每一个插槽（Slot）后都挂着一串通过双向链表相连的节点（Node）。

在此之上，Tokio 采用了**分层时间轮（Hierarchical Timing Wheels）**的设计，共包含 6 个轮级（Wheel），每个轮级被等分为 64 个插槽。每个插槽的物理本质是一个双向链表的表头，链表中悬挂着所有落在该时间区间内的定时器任务。这 6 个轮级的转动速度与代表的时间跨度呈几何级数放大（从 1ms $\to$ 64ms $\to$ $64 \times 64$ms $\to$ ...）。这种设计的巧妙之处在于，插入一个定时器的时间复杂度是 $O(1)$。

相比之下，C++ 著名的网络库 Boost.Asio 中的定时器则是基于 std::vector 实现的最小二叉堆（Min-Heap），插入一个定时器的时间复杂度为 $O(\log N)$。出于好奇，我调研了现代 C++ 异步框架，发现 stdexec 中提供的定时器实现 exec::time_context 同样是基于最小二叉堆实现的。

分层时间轮 vs 最小二叉堆：性能对比

根据 Kafka 官方博客 以及 Rust 社区 的评测数据，在纯粹执行 100 万次定时器插入的基准测试中，最小堆以绝对优势完胜时间轮（时间轮耗时约 64ms，而最小堆仅需 2ms）。这主要得益于二叉堆底层的 std::vector 具有极佳的内存连续性，CPU 缓存（L1/L2 Cache）命中率极高。

然而，在真实的高并发网络场景中，情况大不相同。我们往往需要频繁地取消定时器（例如：在超时时间到达前，网络数据已经提前送达，此时需要取消超时闹钟）。对于二叉堆而言，取消一个特定定时器需要 $O(N)$ 的复杂度进行搜寻并重构堆结构；而对于时间轮，由于底层的双向链表设计，只需 $O(1)$ 的复杂度直接将节点断开即可。在频繁插入与取消并存的实测数据中，时间轮的效率比二叉堆快了将近 900 倍。

因此，在面对海量并发连接与高频计时任务的网络服务场景中，分层时间轮依然是无可争议的最佳实践选择。