timer_wheel

时间轮定时器

https://kinly.github.io/archives/de38e5db.html

benchmark test

• via: https://github.com/ki7chen/timer-benchmarks

• 简单测试结果

补充

• 前面反复聊到定时器的问题：
• 复看这个实现，其实不算是一个标准意义的时间轮（参见很多资料，关于时间轮都是只表示最大几天的时间）
• 而之前想要覆盖到一个自己不太（调皮）会活到的时间 (2100年)，把这个时间划分了刻度之后一层层向外分层
  • 可以看到后面几个轮子的刻度都是 1 << 6
  • 算不来了，只是一层层往目标时间戳 (2100年) 补轮子
• 当前（2024.07.28）再看这个定时器实现，暂时还不觉得有什么问题....
• 其他：可以把定时器单独放到一个线程，事件的话最好也分配一个触发线程（=业务线程数）

定时器

• 游戏里定时器简直是不可或缺的东西，比如技能冷却、怪物刷新、玩家心跳等等
• 定时器一般分为两类：单次定时器和周期定时器
  • 单次定时器：定时器到时间后，执行一次回调函数，然后销毁
  • 周期定时器：定时器到时间后，执行一次回调函数，然后重新计时
• 游戏里定时器的精度一般要求在毫秒(1-500ms)级别
• 常见游戏类型已经精度控制：
  • FPS、赛车实时游戏：精度要求高，一般要求在1-5ms级别
  • MMO游戏：精度要求一般，一般要求在200ms级别，怪物傻一点在400-500ms
  • ARPG游戏：精度要求比MMO高，一般要求在50ms级别？
• 定时器的通用需求：
  • 排序的
  • 没有空间限制的
  • 最大可能保持精度
  • 对CPU、内存没有太大压力
• 上述要求看好像排序的容器就可以满足需求（set, priority_queue），也有不少介绍定时器的是用最小堆这样的容器实现的，但是这种排序容器在插入的时候有时间复杂度
• 想做到O(1)的插入时间复杂度，首先需要用到数组，假设定义一个3600长度的数组，每个下标代表1s的刻度，那这个数组最多容纳3600秒范围内的定时器，超过这个时间的就塞不进去了

时间轮-定时器

• 在我理解，时间轮核心内容是轮子的复用

标准时间

• 日常表述：(秒级)

• 钟表表示：

• 程序表述：

  • 程序用时间戳(timestamp)表示时间，这里我们依然只用秒级
  • 有了上面钟表表示的方式，这里的程序表示需要被分片到钟表上：把时间戳切成一个个数字（这里为了更直观用的是 % 10 的方式）（如下图）

• 上面相差的时间：2秒，49秒在程序里差异的数字分别是：（红框、橙框）

• 差值用程序的写法：

-- 49秒
....
(04031 + 49) / 10 / 10 / 10 / 10 % 10 = 0 没有变更
(4031 + 49) / 10 / 10 / 10 % 10 = 4 没有变更
(031 + 49) / 10 / 10 % 10 = 0 没有变更
(31 + 49) / 10 % 10 = 8
(1 + 49) % 10 = 0

• 好像时间轮已经快出来了，这就是根据差值，把一个新的定时任务插入到时间轮的写法了：

// cpp: xx 插入到时间轮

clock cc(current_ts);
clock cn(next_ts);

if (cn._0 != cc._0) {
    wheel[cn._0].add(xx);
} else if (cn._1 != cc._1) {
    wheel[cn._1].add(xx);
} else if (cn._2 != cc._2) {
    wheel[cn._2].add(xx);
} else if (cn._3 != cc._3) {
    wheel[cn._3].add(xx);
} else {
  // 这里怎么办？？

  // 我想只支持到 2100 年，也就是这里不会是超过32位的时间
  // 也就只有 current_ts == next_ts 才会出现这种情况
  // 那么也放到 最里面的轮子里就好
}

• 其实写到这里看起来时间轮这个定时器已经写好了