基于多级时间轮的定时器机制
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 Kafka
,Netty
,Zookeeper
等框架中都有应用。
-
从整个定时器上看是由多个轮(如图)组成,每一个轮表示不同的层级(就像时钟是由时分秒三个轮组成)。秒这个轮满了之后会推动分钟这个轮前进一格,分满了之后会推动小时这个轮前进一格。以此来实现定时的功能。
-
从单个轮上看,由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
触发的定时任务,那么如何加入时间轮呢?
时钟是以秒为刻度的 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 测试过程,经常需要修改系统时间来测试,如何支持?
原来轮询式定时器机制的做法
原来轮询式定时器机制的做法
-
中间所有的时间都被跳过了,在新的时间点,所有超时的定时器都会被一次性触发,但是周期性定时器也只会被触发这一次。
-
中间固定时间点的定时器,都不会被触发。
- 因为这类定时器都是在
OnTimer
中判断当前时间是否是 X 点 X 分 0 秒来触发。这也是为什么原来的机制,我们要求 QA 改时间测试时,必须改到具体时间点的前几秒,然后正常经过指定的时间点。
- 因为这类定时器都是在
时间轮改时间带来的问题
时间轮改时间带来的问题
- 因为时间轮是基于 tick 的,所以调时间产生的效果,相当于两次 tick 之间的时间差,为调时间前后的差值。
- 两次 tick 之间的时间会被补偿运行,并不会被跳过。
- 周期性定时器会被触发多次。
- 游服可能直接卡死或者卡顿极长的时间。
解决方案
-
时间轮快进:
- 对于单次触发的定时器,正常触发。
- 对于周期性的定时器,触发后不立即重新加入时间轮,等 tick 跳动到当前时间后,再重新加入时间轮。
为什么不能参考原来的机制,直接修改 tick 值?
-
因为时间轮是基于tick运行的,直接修改tick会导致时间轮的时间错乱,所有固定时间点的定时器发生偏移。
-
例如:
- 直接修改tick往后偏移60000tick(即60s),那么原本在17:00:00触发的定时器,将会偏移到17:01:00触发。