基于多级时间轮的定时器机制

Jan 14, 2025

4.1 原来的定时器调度机制

  • 简单的轮询遍历式定时器:
    • 在线程循环中,每隔一定的时间间隔,调用一次OnTimer
    • 在OnTimer中按照管理器、对象、对象的成员等逐层遍历所有OnTimer

void ThreadProcess()
{
    while (true):
        {
            // do something...
            // 经过一个周期,触发定时器轮询
            if (curTime - lastTime >= 750/*ms*/)
            {
                // 遍历所有管理器,调用OnTimer
                foreach xxxMgr:
                    xxxMgr.OnTimer()
            }            
            // do something else...
        }
}



// 管理器的定时器实现
void xxxMgr::OnTimer()
{
    // 管理器需要在定时器中执行的逻辑
    // ...
    
    // 遍历管理器内的对象,调用OnTimer
    for xxx in xxxMgr:
        xxx.OnTimer()
}

// 对象的定时器实现
void xxx::OnTimer()
{
    // 对象需要在定时器中处理的业务逻辑
    // ...
    // 遍历对象的成员,调用OnTimer
    for member in xxx:
        member.OnTimer()
}

  • 问题:

    • 存在海量的空遍历,很多对象本身不需要触发定时器,也会被遍历
    • 单个onTimer逻辑非常复杂,即使未实际触发定时器,也会有大量分支判断
    • 定时器精度难以提高

如何解决?


基于 tick 的多级时间轮定时器机制


什么是时间轮?

时间轮,是一种实现延迟任务调度(定时器)的巧妙算法,把时间规划成刻度,在需要生成定时任务的时候,根据定时任务的执行间隔插入到相应的刻度上,逻辑形状类似一个轮子。所以叫时间轮。比如我们的时钟,实际上就是一个 60x60x12三级时间轮

多级时间轮算法在Apache KafkaNettyZookeeper等框架中都有应用。


w:1080

  • 从整个定时器上看是由多个轮(如图)组成,每一个轮表示不同的层级(就像时钟是由时分秒三个轮组成)。秒这个轮满了之后会推动分钟这个轮前进一格,分满了之后会推动小时这个轮前进一格。以此来实现定时的功能。

  • 从单个轮上看,由N个时间刻度组成,时间刻度上用来存放特定时间的定时任务队列。


时间轮的特点:

  • 最少的性能消耗来实现定时任务调度的功能
    • 每执行一次调度的 cpu 消耗为 O(1)
    • 增加、删除一个定时器的消耗也是 O(1)
  • 可以快速的执行海量的调度任务
  • 牺牲了一定的精度和灵活性为代价的

时间轮运作的逻辑

offset = curTick - lastTick
for i in range(offset):
    n = 0
    for wheel in Wheels:
        n = (wheel.hand + 1) % slots
           
        for timer in wheel.Timers(n):
            if timer.remain != 0:
                StartTimer(&timer)
            else:
                timer.CallBack()
        wheel.hand = n
        if n != 0:
            break

一个例子

还是以时钟为例,分别假设初始时间为 16:15:46,我们有一个需要在 22:33:51 触发的定时任务,那么如何加入时间轮呢?


image

时钟是以秒为刻度的 3 级时间轮,我们将三级时间轮分别称为秒级轮,分钟轮,小时轮。初始状态时,三个时间轮的指针都为 0。


  • 距离 22:33:51,还有 22685 秒。所以应该放入 Level2 的小时轮第 22685/60/60=6 格,定时器剩余时间 remain 为 1085 秒。
  • 当时间 21:15:45 跳动到 21:15:46 时, 时间轮先将秒针回拨到 0,然后执行秒级轮 0 秒刻度上的所有定时器。秒针回拨到 0,将触发分钟轮的执行,这时分钟轮将分针回拨到 0,然后执行所有分钟轮刻度为 0 的定时器。分针回拨到 0 又会触发小时轮的执行,小时轮将时针前进到 6,然后执行所有小时刻度为 6 的定时器。
  • 定时器 remain 为 1085,则重新执行加入定时器逻辑。这时定时器会被放入 level1 的分钟轮 1085/60=18 格。定时器剩余时间 remain 为 5 秒。

  • 当时间 22:33:45 跳动到 22:33:46 时,时间轮先将秒针回拨到 0,然后执行秒级轮 0 秒刻度上的所有定时器。秒针回拨到 0,将触发分钟轮的执行,这时分钟轮将分针前进到 18,然后执行所有分钟轮刻度为 18 的定时器。
  • 定时器 remain为 5,则重新执行加入定时器逻辑。这时定时器会被放入 5%60=5 格。定时器剩余时间 remain 为 0 秒。
  • 当时间 22:33:50 跳动到 22:33:51 时,执行秒级轮 5 秒刻度上的所有定时器。此时定时器的 remain 为 0,将触发定时器。

时间轮对比轮询方式的优势

  • 支持更高精度的定时器而不会显著加重游服的负担
    • 理论上可以支持任意精度的定时器
  • 避免海量空遍历,按需触发
  • 高性能:O(1)的单次调度,O(1)的增加、删除

优化结果对比

  • 压测环境:开启游服、怪服,刷怪数量:40808

  • 对比业务线程单次 OnTimer 耗时和 5 分钟累计耗时:(目前仅改造了 RoleManager::OnTimer)

轮询(单次) 时间轮(单次) 轮询(5Min 累计) 时间轮(5Min 累计)
在线玩家数:0 48.86 ms 3.54 ms 19545 ms 1417 ms
在线玩家数:900 89.59 ms 26.23 ms 35835 ms 10493 ms

实际应用的问题


业务线程中的时间轮应使用游戏逻辑时钟

  • 游服业务线程通常会有自定义的逻辑时钟(一般略慢于实际时间,随着游戏逻辑帧前进)。
  • 这种情况下,时间轮必须使用逻辑时钟,而不能使用实际时间。
  • 如果时间轮使用实际时间,而业务使用逻辑时钟,那么业务线程的时间将和时间轮的时钟不一致,从而导致业务线程出现逻辑错误。

示例

  • 每日零点的业务处理:
    • 时间轮在实际时间的11月23日0点触发。
    • 业务逻辑获取的基于逻辑时钟的时间为:11月22日23点59分59秒。
    • 业务基于逻辑时钟进行时间计算,导致后续逻辑错误。

QA 测试过程,经常需要修改系统时间来测试,如何支持?


原来轮询式定时器机制的做法

polledFF


原来轮询式定时器机制的做法

  • 中间所有的时间都被跳过了,在新的时间点,所有超时的定时器都会被一次性触发,但是周期性定时器也只会被触发这一次。

  • 中间固定时间点的定时器,都不会被触发。

    • 因为这类定时器都是在 OnTimer 中判断当前时间是否是 X 点 X 分 0 秒来触发。这也是为什么原来的机制,我们要求 QA 改时间测试时,必须改到具体时间点的前几秒,然后正常经过指定的时间点。

时间轮改时间带来的问题

TWNoFF


时间轮改时间带来的问题

  • 因为时间轮是基于 tick 的,所以调时间产生的效果,相当于两次 tick 之间的时间差,为调时间前后的差值。
  • 两次 tick 之间的时间会被补偿运行,并不会被跳过。
  • 周期性定时器会被触发多次。
  • 游服可能直接卡死或者卡顿极长的时间。

解决方案

  • 时间轮快进

    • 对于单次触发的定时器,正常触发。
    • 对于周期性的定时器,触发后不立即重新加入时间轮,等 tick 跳动到当前时间后,再重新加入时间轮。

twFF


为什么不能参考原来的机制,直接修改 tick 值?

  • 因为时间轮是基于tick运行的,直接修改tick会导致时间轮的时间错乱,所有固定时间点的定时器发生偏移。

  • 例如:

    • 直接修改tick往后偏移60000tick(即60s),那么原本在17:00:00触发的定时器,将会偏移到17:01:00触发。

参考文献

  1. Nagle's algorithm
  2. Apache Kafka, Purgatory, and Hierarchical Timing Wheels