15、定时器与时间轮：定时器需求分析、最小堆定时器、时间轮算法、分级时间轮、实战：高性能定时器实现。

定时器这东西，说白了就是「到点了，干活」。在网络编程里，它几乎无处不在——连接超时、心跳检测、延迟任务、定时统计……你想想看，一个高并发服务器要是没有高效的定时器，那基本就是裸奔。

我个人习惯把定时器分为两类：一类是「一次性」的，比如设置一个5秒的超时；另一类是「周期性」的，比如每隔30秒发一次心跳。但不管哪种，底层机制其实差不多。

15.1 定时器需求分析

先聊聊需求。我在项目中遇到过几次定时器设计翻车的情况，总结下来，一个靠谱的定时器至少要满足这几点：

  • 高精度：误差不能太大，尤其是毫秒级的超时场景
  • 低延迟：添加、删除、到期触发的操作要快
  • 可扩展：支持成千上万个定时器同时存在
  • 内存可控：不能无限制地吃内存

嗯，这里要注意，不同的业务场景对定时器的要求差别很大。比如游戏服务器可能要求微秒级精度，而HTTP服务器几十毫秒的误差也能接受。所以选型的时候，得先搞清楚你的场景。

核心指标对比

指标最小堆时间轮分级时间轮
插入复杂度O(log n)O(1)O(1)~O(log m)
删除复杂度O(log n)O(1)O(1)~O(log m)
到期触发O(log n)O(1)O(1)~O(n)
内存占用低中中高
适用场景少量定时器大量短定时器大量混合定时器

15.2 最小堆定时器

最小堆，其实就是个完全二叉树，父节点永远比子节点小。我们把定时器的到期时间作为键值，堆顶就是最近要触发的那个。

为什么用最小堆？因为每次取最近定时器只需要 O(1) 时间，插入和删除是 O(log n)。对于几百个定时器的场景，完全够用。

我曾经在一个网关项目里用过最小堆，当时觉得挺稳的。结果压测到 5000 个并发连接时，定时器数量飙到了 2 万多个，堆操作开始出现明显延迟。嗯，这就是教训——小堆虽好，但别贪杯。

// 最小堆定时器核心结构
struct TimerNode {
    uint64_t expire;  // 到期时间戳（毫秒）
    uint64_t id;      // 定时器ID
    Callback cb;      // 回调函数
};

class MinHeapTimer {
    std::vector<TimerNode> heap_;
    
    void AddTimer(uint64_t expire, Callback cb) {
        heap_.push_back({expire, next_id_++, cb});
        std::push_heap(heap_.begin(), heap_.end(), CompareExpire);
    }
    
    void Tick(uint64_t now) {
        while (!heap_.empty() && heap_.front().expire <= now) {
            auto t = heap_.front();
            std::pop_heap(heap_.begin(), heap_.end(), CompareExpire);
            heap_.pop_back();
            t.cb();  // 触发回调
        }
    }
};

小技巧：最小堆的定时器，建议用「相对时间」而不是「绝对时间」。比如设置 5 秒后触发，存的是当前时间 + 5000。这样在 Tick 时只需要比较当前时间戳，省去了一次转换。

15.3 时间轮算法

时间轮，灵感来自钟表。一个圆盘分成 N 个槽位，每个槽位放一个链表。指针每 tick 一次，就移动到下一个槽位，触发该槽位上的所有定时器。

说白了，这就是个「空间换时间」的典型。插入和删除都是 O(1)，因为只需要计算哈希槽位，然后挂到链表上就行。

我最早接触时间轮是在做 Redis 源码分析时看到的。Redis 的定时器就是用时间轮实现的，支持几十万个定时器毫无压力。当时我就想，这玩意儿真香。

// 简单时间轮（单层）
class SimpleWheelTimer {
    static const int SLOTS = 256;  // 256个槽位
    std::vector<std::list<TimerNode>> wheel_;
    int current_slot_ = 0;
    
    void AddTimer(uint64_t delay_ms, Callback cb) {
        int ticks = delay_ms / TICK_MS;  // 需要跳过的tick数
        int slot = (current_slot_ + ticks) % SLOTS;
        wheel_[slot].push_back({cb});
    }
    
    void Tick() {
        auto& slot = wheel_[current_slot_];
        for (auto& t : slot) t.cb();
        slot.clear();
        current_slot_ = (current_slot_ + 1) % SLOTS;
    }
};

注意：单层时间轮的致命问题是「槽位有限」。如果定时器延迟超过了一圈（比如 256 个槽位，每个 tick 10ms，一圈才 2.56 秒），那超过的定时器就得「绕圈」处理。这时候要么增加槽位，要么用分级时间轮。

15.4 分级时间轮

分级时间轮，其实就是把多个时间轮串起来。就像钟表：秒针走一圈，分针走一格；分针走一圈，时针走一格。

每一级时间轮的精度不同。第一级精度最高（比如 1ms），第二级精度低一些（比如 1s），以此类推。定时器根据延迟时间，选择合适的层级插入。

这样做的好处是：既能支持大范围的超时时间，又能保持 O(1) 的插入性能。我见过一些高性能网络库，比如 Netty 的 HashedWheelTimer，就是用的分级时间轮。

// 分级时间轮示意（两级）
class HierarchicalWheelTimer {
    static const int LEVEL1_SLOTS = 256;  // 1ms精度，256ms一圈
    static const int LEVEL2_SLOTS = 256;  // 256ms精度，65s一圈
    
    std::vector<std::list<TimerNode>> level1_;
    std::vector<std::list<TimerNode>> level2_;
    int pos1_ = 0, pos2_ = 0;
    
    void AddTimer(uint64_t delay_ms, Callback cb) {
        if (delay_ms < 256) {
            int slot = (pos1_ + delay_ms) % LEVEL1_SLOTS;
            level1_[slot].push_back({cb});
        } else {
            int slot = (pos2_ + delay_ms / 256) % LEVEL2_SLOTS;
            level2_[slot].push_back({cb, delay_ms % 256});
        }
    }
    
    void Tick() {
        // 先处理第一级
        auto& slot1 = level1_[pos1_];
        for (auto& t : slot1) t.cb();
        slot1.clear();
        pos1_ = (pos1_ + 1) % LEVEL1_SLOTS;
        
        // 第一级走完一圈，从第二级降级
        if (pos1_ == 0) {
            auto& slot2 = level2_[pos2_];
            for (auto& t : slot2) {
                // 降级到第一级
                int slot = (pos1_ + t.remain) % LEVEL1_SLOTS;
                level1_[slot].push_back({t.cb});
            }
            slot2.clear();
            pos2_ = (pos2_ + 1) % LEVEL2_SLOTS;
        }
    }
};

关键点：分级时间轮的「降级」操作是核心。当高精度轮走完一圈时，需要把下一级的定时器「降级」到当前级。这个过程虽然需要遍历链表，但因为下一级的定时器数量通常不多，所以整体性能依然可控。

15.5 实战：高性能定时器实现

好了，理论说完了，咱们来点实际的。我最近在做一个 RPC 框架，需要支持 10 万个并发连接，每个连接都有心跳超时。选来选去，最后用了分级时间轮。

为什么？因为最小堆在 10 万级别已经扛不住了，而单层时间轮的槽位又不够。分级时间轮正好是那个「甜点」。

具体实现上，我用了三级时间轮：

  • 第一级：256 个槽位，每个 tick 1ms，一圈 256ms
  • 第二级：64 个槽位，每个 tick 256ms，一圈 16.384s
  • 第三级：64 个槽位，每个 tick 16.384s，一圈约 17.5 分钟

这样，从 1ms 到 17 分钟的超时都能覆盖，而且插入和删除都是 O(1)。

// 三级时间轮实战代码片段
class TimerWheel {
    static const int L1_SLOTS = 256;
    static const int L2_SLOTS = 64;
    static const int L3_SLOTS = 64;
    
    struct TimerEntry {
        uint64_t id;
        Callback cb;
        int remaining_ticks;  // 降级时使用
    };
    
    std::vector<std::list<TimerEntry>> l1_, l2_, l3_;
    int pos1_ = 0, pos2_ = 0, pos3_ = 0;
    
public:
    TimerWheel() 
        : l1_(L1_SLOTS), l2_(L2_SLOTS), l3_(L3_SLOTS) {}
    
    void AddTimer(uint64_t delay_ms, Callback cb, uint64_t id) {
        if (delay_ms < L1_SLOTS) {
            int slot = (pos1_ + delay_ms) % L1_SLOTS;
            l1_[slot].push_back({id, cb, 0});
        } else if (delay_ms < L1_SLOTS * L2_SLOTS) {
            int ticks = delay_ms / L1_SLOTS;
            int remain = delay_ms % L1_SLOTS;
            int slot = (pos2_ + ticks) % L2_SLOTS;
            l2_[slot].push_back({id, cb, remain});
        } else {
            int ticks = delay_ms / (L1_SLOTS * L2_SLOTS);
            int remain = delay_ms % (L1_SLOTS * L2_SLOTS);
            int slot = (pos3_ + ticks) % L3_SLOTS;
            l3_[slot].push_back({id, cb, remain});
        }
    }
    
    void Tick() {
        // 处理第一级
        auto& slot1 = l1_[pos1_];
        for (auto& t : slot1) t.cb();
        slot1.clear();
        pos1_ = (pos1_ + 1) % L1_SLOTS;
        
        // 降级逻辑
        if (pos1_ == 0) Cascade(l2_, pos2_, L2_SLOTS, L1_SLOTS);
        if (pos2_ == 0 && pos1_ == 0) Cascade(l3_, pos3_, L3_SLOTS, L1_SLOTS * L2_SLOTS);
    }
    
private:
    void Cascade(std::vector<std::list<TimerEntry>>& wheel, 
                 int& pos, int slots, int scale) {
        auto& slot = wheel[pos];
        for (auto& t : slot) {
            // 降级到下一级
            AddTimer(t.remaining_ticks, t.cb, t.id);
        }
        slot.clear();
        pos = (pos + 1) % slots;
    }
};

避坑指南：我曾经在降级时忘记处理「剩余 ticks」，导致定时器提前触发了。后来加了个 remaining_ticks 字段，每次降级时重新计算精确位置。嗯，这个坑踩得值。

15.6 总结与选型建议

说了这么多，到底该用哪种？我个人的经验是：

  • 定时器数量 < 1000：最小堆就够了，简单可靠
  • 定时器数量 1000~10000：单层时间轮，注意槽位要够
  • 定时器数量 > 10000：分级时间轮，性能和容量都稳

你想想看，选型其实就是在「复杂度」和「容量」之间做权衡。没有银弹，只有最适合你场景的方案。

最后说一句，定时器的实现虽然看起来简单，但真正上线后，各种边界情况会让你头疼。比如系统时间被 NTP 调整了怎么办？定时器回调里又加了定时器怎么办？这些细节，才是区分「能用」和「好用」的关键。

定时器选型决策树 定时器数量 < 1000 1000 ~ 10000 > 10000 最小堆 O(log n) 插入/删除 单层时间轮 O(1) 操作，槽位有限 分级时间轮 O(1) 操作，大范围 优点 • 实现简单 • 内存占用低 • 适合少量定时器 优点 • 插入/删除 O(1) • 实现中等复杂度 • 适合中等规模 优点 • 支持大范围超时 • 高并发下稳定 • 适合大规模场景 缺点 • 大量定时器性能下降 • 删除操作需查找 缺点 • 槽位有限，需绕圈 • 大延迟定时器效率低 缺点 • 实现复杂度高 • 降级逻辑需谨慎 推荐：小项目/原型 推荐：中等规模 推荐：高并发场景

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →