TimerWheel(计时轮)在Rust中的实现及源码解析

计时器轮（TimerWheel），模拟时钟格式组成的高效计时器

TimerWheel算法原理

1. 环形数据结构：TimerWheel，即时间轮，是一个环形的数据结构，类似于时钟的面，被等分为多个格子或槽位（slot）。

2. 槽位时间间隔：每个槽位代表一个固定的时间间隔，例如1毫秒、1秒等。这个时间间隔决定了定时器的精度。

3. 初始化：在算法开始时，需要初始化时间轮，包括设定时间轮的大小（即槽位的数量）和每个槽位代表的时间间隔。即当插入数据后即不允许修改时轮信息。

TimerWheel算法的优缺点

• 优点：
  • 高效性：通过利用循环数组和指针的特性，时间轮算法可以以固定的时间复杂度（通常是O(1)）来处理任务的调度和触发，这提供了一种高效的定时任务管理方式。
  • 可扩展性：如果单个时间轮无法满足需求，可以通过增加时间轮的层数来扩展其表示的时间范围。多层时间轮可以处理更长时间跨度的定时任务。
• 缺点：
  • 精度越高资源耗费多：时间轮的精度取决于每个槽位代表的时间间隔。通过调整这个时间间隔，可以在精度和资源消耗之间找到平衡。
  • 删除效率：通常时轮未索引key值存储位置，删除需要遍历整个列表，复杂度为O(n)

结构设计

在TimerWheel的结构中，我们需要有两层结构，一层TimerWheel管理整个类，用OneTimerWheel来管理每个轮，此外定义了trait为Timer，类型必须实现该接口以管理类的递进时长。

管理类

管理类里定义了时轮的最大最小及其它的信息

pub struct TimerWheel<T:Timer> {/// 时轮的最大轮，以时钟为例就是时针greatest: *mut OneTimerWheel<T>,/// 时轮的最小轮，以时钟为例就是秒针lessest: *mut OneTimerWheel<T>,/// 时轮的最小间隔，以时间为例就是秒min_step: usize,/// 维护定时器idnext_timer_id: usize,/// 离的最近的iddelay_id: usize,/// 总共的递进步长，缓存优化触发all_deltatime: usize,/// 当时时轮里的元素个数len: usize,
}

单轮管理

当前轮管理的当前指针及每个糟里的元素

pub struct OneTimerWheel<T:Timer> {/// 当时指针指向的位置，如秒针指向3点钟方向index: usize,/// 当前结构的容量，如表示秒的为60的容量capation: usize,/// 当前结构步长，如分钟就表示60s的step: usize,/// 当前槽位容纳的元素slots: Vec<Vec<Entry<T>>>,/// 当前轮结构的父轮，如当前是分的，那父轮为时轮parent: *mut OneTimerWheel<T>,/// 当前轮结构的子轮，如当前是分的，那父轮为秒轮child: *mut OneTimerWheel<T>,/// 当前轮的名字，辅助定位name: &'static str,
}

接口Timer

类必须时间Timer结构，以统一知道他对当前时间的间隔。必须覆写when以确定当前的offset。

pub trait Timer {/// 当时与现在的间隔，以确定插入确定的槽fn when(&self) -> usize;/// 可能需要修改对象，此处用可变值fn when_mut(&mut self) -> usize {self.when()}
}

源码分析

初始化

因为时轮是后续设置，最小刻度由最小数额确定。故初始化不需要任何参数：

impl<T:Timer> TimerWheel<T> {pub fn new() -> Self {Self {greatest: ptr::null_mut(),lessest: ptr::null_mut(),next_timer_id: 0,delay_id: 0,min_step: 0,all_deltatime: 0,len: 0,}}
}

设置时轮

时轮从大到小添加，如时钟的模型先添加12小时每个刻度为3600秒。

let mut timer = TimerWheel::new();
timer.append_timer_wheel(12, 60*60, "HourWheel");
timer.append_timer_wheel(60, 60, "MinuteWheel");

接下来添加分钟的轮，槽位60个，每个槽位60秒：

timer.append_timer_wheel(60, 60, "MinuteWheel");

接下来添加秒钟的轮，槽位60个，每个槽位1秒：

timer.append_timer_wheel(60, 1, "SecondWheel");

这里必须保证，每个小的刻度的总和必须为上一个模型的一个小刻度。
完整源码，将在添加的时候自动维护最小刻度及下一个delay_id防止空转。

pub fn append_timer_wheel(&mut self, slots: usize, step: usize, name: &'static str) {debug_assert!(self.len == 0, "必须时轮为空才可改变时轮");let one = Box::into_raw(Box::new(OneTimerWheel::new(slots, step, name)));self.delay_id = self.delay_id.max(slots * step);self.lessest = one;if self.greatest.is_null() {self.greatest = one;} else {unsafe {(*self.greatest).append(one);}}self.min_step = step;
}

添加元素

元素必须实现Timer，以确定放在指定的槽位中，将会返回定时器的id。以方便操作定时器，删除、获取、修改等操作。并且如果当前的时移更小，会重新设置delay_id的大小，以确定指定时间内能触发定时器。

pub fn add_timer(&mut self, mut val: T) -> usize {debug_assert!(!self.greatest.is_null(), "必须设置时轮才能添加元素");let timer_id = self.next_timer_id;self.next_timer_id += 1;self.delay_id = self.delay_id.min(val.when_mut());let entry = Entry { val, id: timer_id };unsafe {(*self.greatest).add_timer(entry);}self.len += 1;timer_id
}

确定时移

时移通过外部系统传入进去，可以方便的设置自己是否根据时间来进行判定。或者自己有另一套时移模式均可通用。

pub fn update_deltatime(&mut self, delta: usize) -> Option<Vec<T>>

如果当前的时移未大于delay_id，那么即表示还未触发任何的定时器。此时处理的仅仅为all_deltatime的自加，效率极高。
当时移大于delay_id后表示将触发定时器，与最小的min_step相除得出时轮中的时移offset

self.all_deltatime += delta;
let mut offset = self.all_deltatime / self.min_step;
if offset < self.delay_id {return None;
}
self.all_deltatime -= offset * self.min_step;

确定后将开始自身的时移，这里用比较高效的方式维护各个时轮：
比如以标准时钟为例，当前offset为156，即表示此时已过了156秒，那么秒轮的将会产生156 % 60 = 36的偏差值，那么秒轮的index=index+36为新的秒轮，且因为156 / 60 > 2，已经完整的转了一圈，表示秒轮上的所有节点全部被触发了。
此时分轮上移动了2分钟，比如此时为3，也就是index=index+2，那么移动的两个位置（3和4）所有元素将会被触发。此时分针指向了5，因为该位置上的最大偏移已经不超过60秒，为了使接下来在60秒内能正确触发该对象的值。那么将5身上的所有元素移除重新加入到了秒轮。

let mut result = vec![];
let mut wheel = self.lessest;
while !wheel.is_null() {unsafe {(offset, remainder) = (*wheel).update_index(offset, remainder, &mut result);if offset == 0 {break;}wheel = (*wheel).parent;}
}

更新索引值update_index，因为每次递进的的梯度可能会非常的大的，也可能会非常的小，这边需要准确的更新索引的值，并且包括降维的数据也能正确的降维。其中余数则是高维往低维降维的关键，例如149，从秒轮上来可以看出分轮有2分钟29秒，将会把第3分钟的进行降维，其中第三分钟如果在29内的标签应该是均命中，大于29的应该-29后的值插入到秒轮。

pub fn update_index(&mut self, offset: usize, remainder: usize, result: &mut Vec<T>) -> (usize, usize) {let next = self.index + offset;let mut all = 0;for idx in self.index..next {if all > self.capation {break;}all += 1;let idx = idx % self.capation;let list = &mut self.slots[idx];for val in list.drain(..) {result.push(val.val);}}self.index = next % self.capation;if !self.child.is_null() {unsafe {let list = &mut self.slots[self.index];for mut val in list.drain(..) {val.when = (val.when % self.step).saturating_sub(remainder);if val.when <= 0 {result.push(val.val);} else {(*self.child).add_step_timer(val);}}}}(next / self.capation, next % self.capation + remainder)
}

此时我们收集到了时移产生156秒触发的所有元素，我们将其打包进行返回，与此同时因为时轮上的指针发生变化，及元素被重新拆解，所以此时需要重新维护delay_id，此时需调用

pub fn calc_delay_id(&mut self)

密度高的基本为O(1)的复杂度，最差情况为O(n)的复杂度
总刻度数以时钟为计秒轮遍历60次，分轮遍历60次，时轮遍历12次，即最高遍历132次。

确定时移的时候也可以调用回调函数版本直接处理时间回调

pub fn update_deltatime_with_callback<F>(&mut self, delta: usize, f: &mut F) 
where F: FnMut(&mut Self, T),

移除定时器

当我们对某个定时器不需要的时候可以提前进行删除

pub fn del_timer(&mut self, timer_id: usize) -> Option<T>

该模型删除不具备优势，时间复杂度为O(n)，n为当前容器内的个数。
需要频繁删除请选用其它时间框架。如红黑树模型（nginx）的删除复杂度仅为O(logn)。

参考示例

以下是按时钟的一个计时轮：

use algorithm::TimerWheel;fn main() {let mut timer = TimerWheel::new();timer.append_timer_wheel(12, 60 * 60, "HourWheel");timer.append_timer_wheel(60, 60, "MinuteWheel");timer.append_timer_wheel(60, 1, "SecondWheel");timer.add_timer(30);assert_eq!(timer.get_delay_id(), 30);timer.add_timer(149);assert_eq!(timer.get_delay_id(), 30);let t = timer.add_timer(600);assert_eq!(timer.get_delay_id(), 30);timer.add_timer(1);assert_eq!(timer.get_delay_id(), 1);timer.del_timer(t);timer.add_timer(150);assert_eq!(timer.get_delay_id(), 1);let val = timer.update_deltatime(30).unwrap();assert_eq!(val, vec![1, 30]);timer.add_timer(2);let val = timer.update_deltatime(119).unwrap();assert_eq!(val, vec![2, 149]);let val = timer.update_deltatime(1).unwrap();assert_eq!(val, vec![150]);assert!(timer.is_empty());
}

完整项目地址

https://github.com/tickbh/algorithm-rs

结语

TimerWheel算法通过其独特的数据结构和运行原理，实现了高效、可扩展且灵活的定时任务管理。该结构用于对高性能的定时器框架，尤其密集程度越高的定时器效率越高。