返回文章列表

用 Rust 从零实现定时器:时间轮和最小堆各适合什么

349 字·3 分钟阅读
Rust从零造轮子并发

几乎每个长连接服务里都藏着十万个定时任务:连接超时、心跳检测、订单关单、缓存过期。

管理这些任务的结构选错了,CPU 会有相当一部分花在"找下一个到期任务"上。这篇写两个最主流的方案:最小堆和时间轮,并说清楚它们各自适合什么。

先说结论:

结构 插入 取出最早到期 适合
最小堆 O(log n) O(log n) 任务数量中等、到期时间分散
时间轮 O(1) O(1) 任务多、时间粒度固定、大量任务集中在同一时刻

接口先定下来

不管底层怎么实现,对外就是三个动作:

pub trait Timer {
    type Handle: Copy + Eq;
 
    /// 注册一个 timeout 后触发的任务,返回可取消的句柄
    fn schedule(&mut self, timeout: Duration, task: Box<dyn FnOnce() + Send>) -> Self::Handle;
 
    /// 取消一个还没触发的任务
    fn cancel(&mut self, handle: Self::Handle) -> bool;
 
    /// 取出所有已到期的任务并执行
    fn tick(&mut self, now: Instant);
}

cancel 是这个接口里最容易被忽略、也最关键的部分。 一个连接提前关闭了,它注册的超时任务必须能撤掉,否则就是内存泄漏。

版本一:最小堆

最小堆的思路:按到期时间排序,堆顶永远是最近要触发的那个。

Rust 的 BinaryHeap 是最大堆,用它做最小堆要反转比较:

use std::cmp::Ordering;
use std::collections::BinaryHeap;
use std::time::{Duration, Instant};
 
struct Scheduled {
    deadline: Instant,
    seq: u64, // 打破同 deadline 的平局,保证 FIFO
    id: u64,
    task: Option<Box<dyn FnOnce() + Send>>,
    cancelled: bool,
}
 
impl PartialEq for Scheduled {
    fn eq(&self, other: &Self) -> bool { self.deadline == other.deadline && self.seq == other.seq }
}
impl Eq for Scheduled {}
 
impl Ord for Scheduled {
    fn cmp(&self, other: &Self) -> Ordering {
        // 反转:deadline 早的排前面;相同则 seq 小的靠前
        other
            .deadline
            .cmp(&self.deadline)
            .then_with(|| other.seq.cmp(&self.seq))
    }
}
impl PartialOrd for Scheduled {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> { Some(self.cmp(other)) }
}

为什么要有 seq?因为 Instant 可能相同(同一毫秒内注册多个),如果只比 deadline,堆的顺序不稳定,等于破坏了"先注册先触发"的直觉。

定时器主体:

pub struct HeapTimer {
    heap: BinaryHeap<Scheduled>,
    tasks: std::collections::HashMap<u64, ()>, // 记录有效 id,用于取消
    next_id: u64,
    seq: u64,
}
 
impl HeapTimer {
    pub fn new() -> Self {
        Self {
            heap: BinaryHeap::new(),
            tasks: Default::default(),
            next_id: 0,
            seq: 0,
        }
    }
 
    pub fn schedule(&mut self, timeout: Duration, task: Box<dyn FnOnce() + Send>) -> u64 {
        let id = self.next_id;
        self.next_id += 1;
        self.seq += 1;
 
        self.heap.push(Scheduled {
            deadline: Instant::now() + timeout,
            seq: self.seq,
            id,
            task: Some(task),
            cancelled: false,
        });
        self.tasks.insert(id, ());
        id
    }
}

tick 就是不断弹出堆顶,直到堆顶还没到期:

    pub fn tick(&mut self, now: Instant) {
        while let Some(top) = self.heap.peek() {
            if top.deadline > now {
                break; // 堆顶没到期,后面的更没到期
            }
            let mut item = self.heap.pop().unwrap();
            self.tasks.remove(&item.id);
            if !item.cancelled {
                if let Some(task) = item.task.take() {
                    task();
                }
            }
        }
    }

取消:惰性删除

BinaryHeap 没有办法"删除任意元素"(只能删堆顶)。所以要取消一个任务,标准做法是惰性删除:不真删,只打个标记,等它冒到堆顶时再丢掉。

    pub fn cancel(&mut self, handle: u64) -> bool {
        if self.tasks.remove(&handle).is_some() {
            // 只从索引里移除;堆里的节点等 tick 时自然丢弃
            return true;
        }
        false
    }

但上面的代码有个问题:cancelled 字段其实没被设置。真正的实现要么在 tasks 里存 Arc<AtomicBool>,要么让 cancel 扫描堆(O(n),不可接受)。

更干净的做法是用 Arc<AtomicBool>:

struct Scheduled {
    deadline: Instant,
    seq: u64,
    task: Option<Box<dyn FnOnce() + Send>>,
    cancelled: std::sync::Arc<std::sync::atomic::AtomicBool>,
}
    pub fn cancel(&mut self, handle: u64) -> bool {
        if let Some(flag) = self.tasks.remove(&handle) {
            flag.store(true, std::sync::atomic::Ordering::Release);
            return true;
        }
        false
    }

惰性删除是无处不在的模式:主动删除代价高时,就先标记,等结构自然经过时再清理。 时间轮的取消也是同一个思路。

最小堆的问题在于:大量任务同时到期时,每次 tick 都要做 O(log n) 的堆调整。而且堆的内存是分散的,缓存不友好。

版本二:时间轮

时间轮的思路完全不同:不按时间排序,而是把任务放进"时间槽"里。

想象一个时钟的刻度盘,分成 N 个槽。每个槽代表一个时间窗口。指针每走一格就触发对应槽里的所有任务。

const SLOTS: usize = 512;
 
pub struct TimeWheel {
    slots: Vec<Vec<Entry>>,
    current: usize,
    tick_duration: Duration,
    last_tick: Instant,
}
 
struct Entry {
    rounds: usize, // 还要转多少圈才触发
    task: Box<dyn FnOnce() + Send>,
    cancelled: std::sync::Arc<std::sync::atomic::AtomicBool>,
}

注册任务时,算出它应该落在哪个槽、还要转几圈:

impl TimeWheel {
    pub fn schedule(&mut self, timeout: Duration, task: Box<dyn FnOnce() + Send>) -> u64 {
        let ticks = (timeout.as_nanos() / self.tick_duration.as_nanos()) as usize;
        let slot = (self.current + ticks) % SLOTS;
        let rounds = ticks / SLOTS;
 
        let flag = std::sync::Arc::new(std::sync::atomic::AtomicBool::new(false));
        self.slots[slot].push(Entry {
            rounds,
            task,
            cancelled: flag.clone(),
        });
        // 返回句柄...
        0
    }
 
    pub fn advance(&mut self, now: Instant) {
        while now.duration_since(self.last_tick) >= self.tick_duration {
            self.last_tick += self.tick_duration;
            self.current = (self.current + 1) % SLOTS;
 
            // 把当前槽里的任务取出来处理
            let entries = std::mem::take(&mut self.slots[self.current]);
            for mut entry in entries {
                if entry.rounds > 0 {
                    // 还没到,放回同一个槽,圈数减一
                    entry.rounds -= 1;
                    self.slots[self.current].push(entry);
                } else if !entry.cancelled.load(std::sync::atomic::Ordering::Acquire) {
                    (entry.task)();
                }
            }
        }
    }
}

注意 rounds 的处理:这是单层时间轮能覆盖超过一圈时间范围的关键。一个 1 小时后触发的任务,放在 512 槽、每槽 1 秒的轮子里,"轮"是 512 秒,它要转 7 圈。

单层时间轮的问题是:时间精度和覆盖范围互相拉扯。要覆盖 1 天、精度 1 秒,就需要 86400 个槽。内存扛不住。

解法是分层时间轮(Hierarchical Timing Wheel):

秒轮:   60 槽,每槽 1 秒   -> 覆盖 1 分钟
分轮:   60 槽,每槽 1 分   -> 覆盖 1 小时
时轮:   24 槽,每槽 1 小时 -> 覆盖 1 天

任务先放最细的轮。秒轮转完一圈,把"该进分轮"的任务降级进去;分轮转完一圈,再降级到时轮。这也是 Linux 内核定时器和 Kafka 的 TimerWheel 用的方案。

Kafka 的 Purgatory 就是分层时间轮:绝大多数请求的超时时间都是几秒到几十秒,集中在一个槽里,插入和触发都是 O(1),比堆快得多。 这是时间轮最大的胜利场景。

两者怎么选

任务数量少(< 1万)、时间分布散  -> 最小堆
任务数量大、超时时间集中在少数档位 -> 时间轮
需要精确到毫秒、且数量不大      -> 最小堆
需要覆盖从毫秒到天的范围        -> 分层时间轮

还有一个现实角度:最小堆几乎不用自己写——BinaryHeap 就在标准库里,几十行能用。时间轮要自己处理槽、圈数、降级,代码量高一个量级。

所以我的经验是:先上最小堆,profile 发现 tick 成为热点,再换时间轮。

两个必须处理的工程细节

1. 定时器的驱动方式。 tick 谁来调?

  • 专门一个线程 sleep 到下一个到期时间,然后 tick
  • 事件循环(epoll/kqueue)的 timeout 参数
  • tokio 里是 tokio::time 内部集成到 reactor 的

用独立线程最简单,但它引入了额外的线程和调度延迟。高精度场景要把它并进事件循环。

2. 时间回拨。 用 Instant 而不是 SystemTime,就是为了避开这个问题。Instant 是单调时钟,NTP 校时不会让它倒退。定时器里出现 SystemTime::now() 基本就是 bug。

结论

定时器的核心矛盾是"找下一个到期任务"的成本:

最小堆用 O(log n) 的代价维持有序,写起来便宜;时间轮用固定槽位把插入和触发都做成 O(1),代价是精度和范围的取舍;分层时间轮是两者之间的平衡点。

最后一个提醒:定时器代码最难的从来不是数据结构,而是取消路径。任务被取消、连接被关闭、服务要退出——这些路径有没有正确清理注册的任务,决定了服务能不能长期稳定运行。