时间轮

比眉伴天荒 2022-06-07 12:37 270阅读 0赞

问题引入：游戏里面每个Player身上有很多buffs,在每一个tick（最小时间段）都要去检查buff里面的每一个buff是不是过期，产生的效果如何，造成在每个tick里面都去遍历一个长list，明显很不好。

怎么优化？

1.原始模型：

[![model1\_thumb19][model1_thumb19]][model1_thumb19_model1_thumb19]

buff的状态在每一个tick里面都要更新！可以想象指针每移动一下，都会非常沉重地拖着所有的BuffList，好可怕……

2. 优化模型1：

我们要避免的是：原始模型在每一个tick里面都要遍历List,那么我们试下以Times为key,在加入buff里时分配好它的结束和启作用的时间属于哪一个Time,

[![model2\_thumb14][model2_thumb14]][model2_thumb14_model2_thumb14]

这个模型要注意的问题：当要加的Buff起效果已超过了一轮Tick总数时！ 比如时间轮总Tick数为12个，现在指针到了tick=2处，要加一个再经过tick为15（起效果）的buff，怎么办？

可以算得：2 + 15%12 = 5,把此buff放到tick=5的槽里面（每个buff都会记录下它的结束时间的），待tick从2跳一轮回到2再跳3下到tick=5,这个buff就会执行。

这个模型完美解决原始模型（每个Tick都遍历整个BuffList）的问题，似乎很完美哦，但是却引入了新的问题，我们的最小tick明显不可能以小时计算，如果我们把Tick划分到秒级别， 一轮就有12\*3600 = 43200个key,

假如有一个Buff在每3s就起一个效果：（每3秒加一次血）,那么这个buff就会被储存43200/3 = 14400个！！！！如果有大量这种buff,数据冗余就会非常大，储存空间随之也非常大……

要做到保证精度的同时，又保证效率，怎么两全呢？请看模型3.

3. 优化模型3

[![clock4\_thumb14][clock4_thumb14]][clock4_thumb14_clock4_thumb14]

> 网上下了个非常cool的时钟图做示例啦：

这就是要用分层时间轮模型：

![复制代码][copycode.gif]

%%% 1.时钟原理说明：

%%% 1.1. 初始化一个三层时间轮:秒刻盘：0~59个SecList, 分刻盘：0~59个MinList, 时刻盘：0~12个HourList;

%%% 1.2. SecTick由外界推动,每跳一轮(60格),SecTick复位至0,同时MinTick跳1格;

%%% 1.3. 同理MinTick每跳一轮(60格),MinTick复位至0,同时HourTick跳1格;

%%% 1.4. 最高层：HourTick跳一轮(12格）,HourTick复位至0，一个时间轮完整周期完成.

%%% 2.事件原理说明：

%%% 2.1. 设置时间为TimeOut的事件时,根据TimeOut算出发生此事件时刻的指针位置{TriggerHour,TriggerMin,TriggerSec};

%%% 2.2. 用{TriggerHour,TriggerMin,TriggerSec}与当前指针{NowHour,NowMin,NowSec}对比得出事件存放在哪一个指针(Tick);

%%% 2.3. 所有层的指针每跳到下一格(Tick01)都会触发格子的事件列表,处理每一个事件Event01：

%%% 2.3.1 根据事件Event01的剩余TimeOut算出Event01应该存在上一层(跳得更快)层的位置Pos;

%%% 2.3.2 把事件更新到新的Pos(更新TimeOut);

%%% 2.3.3 重复处理完Tick01里面所有的事件;

%%% 2.3.4 清空Tick01的事件;

%%% 2.3.5 最底层(跳最快)层所有的事件遇到指针Tick都会立即执行;

![复制代码][copycode.gif]

我自己用Erlang实现了一个分层时间轮，有兴趣也可以参观下：）知易行难 欢迎大家用自己善长的语言造个漂亮的轮子，自己亲手写还是可以发现里面很多有意思的细节啦.

[https://gist.github.com/zhongwencool/eca6609b59ed635de164][https_gist.github.com_zhongwencool_eca6609b59ed635de164]

--------------------

### 译文：Real-Time Concepts for Embedded Systems Chapter 11 Timer and Timer Services ###

### [http://www.embeddedlinux.org.cn/RTConforEmbSys/5107final/LiB0071.html][http_www.embeddedlinux.org.cn_RTConforEmbSys_5107final_LiB0071.html] ###

上面buff的优化思路也是来源于此，非常简单易懂的时间轮概念.

### 11.6 时间轮（time wheel） ###

如下图Figure11.11所示：时间轮是一个固定大小的数组结构，这个数组的每一个槽（元素）代表着软定时器的精度，(类似于时钟的最小刻度).时间轮的优点:通过排序的时间列表来有效的更新timers.它能非常效率地安装（instaallation),取消(cancellation）timer.(这2个操作的时间复杂度o(1)).

[![Figrue11.6\_thumb5][Figrue11.6_thumb5]][Figrue11.6_thumb5_Figrue11.6_thumb5]

> Figure 11.11 timing wheel.

软时间设备(soft-timer facility)使用硬时间(hadware timer)来确定一个最小的刻度(tick).基于硬时间周期的timer，驱动着所有安装在这上面的软时间. 超时（timeout)的频率决定着软时间的精度，比如：如果定义tick精度为50ms，每个槽（slot)就代表50ms,这也是可以在这个timer里面安装的最小timeout事件了. 同时，一个双向链表会把timeout的事件处理（event handlers)(也叫callback funciton or callbacks)保存在每一个槽中，当timer 过期(expired)时会触发callbacks调用。所以timers列表也代表着过期时间处理事件列表。每个时间槽描述如图Figure11.12：

[![1112\_thumb2][1112_thumb2]][1112_thumb2_1112_thumb2]

> Figure 11.12: Timeout event handlers.

时钟转盘每过一个tick就会指向下一时间(next time)，当指针指到数组的最后一个槽时，下一时间又会回到指针最开始的槽。时间轮的概念就来自于此。因此：当安装一个新的事件(time event)时，转盘当前的位置决定了这个新事件到底应该放在哪一个槽，如下图Figure11.13所描述，每经过一个槽代表过去50ms

[![1113\_thumb3][1113_thumb3]][1113_thumb3_1113_thumb3]

> Figure 11.13: Installing a timeout event.

这个时间槽标记了如果有人想安装一个200ms的timeout事件，就可以把这个事件放在++200的槽中，当然这个转盘的起始位置在槽的开始位置(图中clock dial指的位置)，换句话说：当转盘(clock dial)指向最开始的槽时，这个事件处理就会返回应该是数组的下标(index).

### 11.6.1 问题(Issues) ###

上面这个时间轮方法存在的系列的问题：

问题1： 槽的数量是有限的（也许不同的系统会有不同的限制），比如：你可以在Figure11.13非常明显地看出来：最大的可处理长度(总槽度)是350ms,当要安装一个400ms的事件时怎么办？这个会引起时间轮溢出，为了解决这个问题：一种方法就是禁止超过范围的事件安装，另一个更好的方法：把这些溢出的事件放在一个统一的事件缓冲(event buffer)里面，等转盘转到下一刻度时就从buffer中取出符合范围的事件，这样这些事件也可以被处理了，你可仔细研究Figure11.14得到答案：

[![1114\_thumb1][1114_thumb1]][1114_thumb1_1114_thumb1]

Figure 11.14: Timing wheel overflow event buffer.

比如：当转盘位置在0刻度(图中位置1)处时，同时要安装一个400ms的timeout，这个事件必须暂时存在溢出缓冲buffer里面，随着转盘转到+50ms(图中位置2处），就会从缓冲区取出这个事件安装. 同理：500ms的事件也只能是在转盘到+150ms(图中位置3)处才能安装。转盘每指向下一刻时，都会检查这个事件缓冲区，这就要求缓冲区里面的事件列表是正增长，如果这个列表很长，那么新的事件插入时代价会非常大。

问题2：这个时间轮的精度，试想一下：当tick指到time wheel 到开始指向下一个时间刻度前，如又安装一个150ms的事件，那么这个事件是安装在+150ms，还是在+200呢？按平均来讲，出错的概率均等的情况下，那么这个出错可能会延迟或提前最小刻度的一半，在这里就是50ms/2=25ms.

问题3：非常重要的问题：关于callbacks的安装.理论上，每一个Callback都应该在时间过期时同时发生，但是在现实中，这是不可能的，每一个Callback的工作状态都不可预测，因此，执行的每一个callback的长度也不可预测，导致没有方法可以保证一个在很长列表后面的callback会被马上执行，这个问题是不合需求的，不能引放到系统里面。Figure11.15描述了这个问题：

[![1115\_thumb4][1115_thumb4]][1115_thumb4_1115_thumb4]

Figure 11.15: Unbounded soft-timer handler invocation.

当t1 timeout刚过期时，事件处理函数1马上发生，类似，事件处理函数n会在到过t（n-1）时被触发，由于每一个处理函数的执行长度是不确定的，所有图中x,y是长度也是不定的。

理论上(Ideally),这个时间处理会规定一个处理事件的上限值;比如：当执行到事件处理函数n时距离事件处理函数1开始已超过200ms时，会把没有执行的其它事件忽略掉。这个问题很难，解决方法也是应用程序自己特定的\[译注：可以[点这里][Link 1]参见Linux下的实现\]。

### 11.6.2 分层时间轮(Hierarchical Timing Wheels) ###

Figure11.14里面的问题1：溢出问题可以使用分层时间轮的方法解决。

软时间设备需要适应事件在跨越在不同范围的值，这个跨度可以非常大，比如：适应timers 范畴从100ms到5 分钟需要3000（(5 × 60 × 10）跨度的时间轮，因为这个时间轮的精度最少要100ms，这也是此时间轮的最小精度啦：

10 × 100ms = 1 sec
        10 entries/sec
        60 sec = 1 minute
        60 × 10 entries / min 
        因此: 
        5 × 60 × 10 =需要3000个刻度(entries).

一个分层的时间轮就好像一个数字刻盘指针型时钟，用多个时间轮安装在这个分层结构里面，取代上面单一的时间轮。这里面每个时间轮都有自己的粒度(granularity)精度，时间转盘与所有的时间轮联系在一起，当最低层的时间轮转一轮时，上一层的时间轮就转一个单位。使用分层时间轮刚上面的需要3000entries的现在仅需要75(10 + 60 + 5)entries就可以保证timeout从100ms到5分钟。这里用到的多维数组：

![复制代码][copycode.gif]

10 × 100ms = 1 sec
        10 entries/sec
        60 sec = 1 minute
        60 entries / min
        5 entries for 5 minutes
        因此：
        5 + 60 + 10 =只需要75个刻度(entries)

![复制代码][copycode.gif]

[![1116\_thumb4][1116_thumb4]][1116_thumb4_1116_thumb4]

> Figure 11.16: A hierarchical timing wheel

这个模型不仅节省了大量的空间，并且保持着很高的精度和跨度， Figure11.16说明了这一点。

举个例子：它可能会安装一个2分4秒300ms处timeout事件。首先安装2min，当2分钟发生时，它检查还有4.3s的事件才能timeout,所以它又安装了4s的timeout事件槽，当4s过去后，检查到还有300ms才能timeout,又安装了一个300ms事件，再过300ms,真正的timeout才会被执行.

--------------------

如果你觉得上面意犹未尽：这里面还有一个大餐哦：

1.关于Linux 下定时器的实现方式分析 [http://www.ibm.com/developerworks/cn/linux/l-cn-timers/][http_www.ibm.com_developerworks_cn_linux_l-cn-timers]

2. 浅析 Linux 中的时间编程和实现原理 [http://www.ibm.com/developerworks/cn/linux/1308\_liuming\_linuxtime3/][http_www.ibm.com_developerworks_cn_linux_1308_liuming_linuxtime3]

[model1_thumb19]: http://images.cnitblog.com/blog/629822/201406/271246237269305.png
[model1_thumb19_model1_thumb19]: /images/20220607/f92b7d30eec34c9f8eed583d30c8b7cb.png
[model2_thumb14]: http://images.cnitblog.com/blog/629822/201406/271246248678520.png
[model2_thumb14_model2_thumb14]: /images/20220607/9881cd95d56b4fa097fc3e60c9e6dcca.png
[clock4_thumb14]: http://images.cnitblog.com/blog/629822/201406/271246259765193.png
[clock4_thumb14_clock4_thumb14]: /images/20220607/23fbfba1ec5a475abb0e668f65bd7f23.png
[copycode.gif]: /images/20220607/4587a8f140694cc4bbc0dfdd7af33eca.png
[https_gist.github.com_zhongwencool_eca6609b59ed635de164]: https://gist.github.com/zhongwencool/eca6609b59ed635de164
[http_www.embeddedlinux.org.cn_RTConforEmbSys_5107final_LiB0071.html]: http://www.embeddedlinux.org.cn/RTConforEmbSys/5107final/LiB0071.html
[Figrue11.6_thumb5]: http://images.cnitblog.com/blog/629822/201406/271246279923308.jpg
[Figrue11.6_thumb5_Figrue11.6_thumb5]: /images/20220607/ef4c62f3026647e09e772210af750588.png
[1112_thumb2]: http://images.cnitblog.com/blog/629822/201406/271246287586410.jpg
[1112_thumb2_1112_thumb2]: /images/20220607/b4900c647267463b8f941d1c760f68ca.png
[1113_thumb3]: http://images.cnitblog.com/blog/629822/201406/271246295391581.jpg
[1113_thumb3_1113_thumb3]: /images/20220607/186d5a48e32143bc92bea317fb95f3f4.png
[1114_thumb1]: http://images.cnitblog.com/blog/629822/201406/271246304149481.jpg
[1114_thumb1_1114_thumb1]: /images/20220607/bc65704dd60e4af0837e3b2e8e776c7a.png
[1115_thumb4]: http://images.cnitblog.com/blog/629822/201406/271246312732611.jpg
[1115_thumb4_1115_thumb4]: /images/20220607/cf4a1622dd9d436a84b47307daf811d3.png
[Link 1]: http://blog.csdn.net/lonewolfxw/article/details/8034395
[1116_thumb4]: http://images.cnitblog.com/blog/629822/201406/271246331643455.jpg
[1116_thumb4_1116_thumb4]: /images/20220607/e88e826aef9946099a6bc1c267fc6ccd.png
[http_www.ibm.com_developerworks_cn_linux_l-cn-timers]: http://www.ibm.com/developerworks/cn/linux/l-cn-timers/
[http_www.ibm.com_developerworks_cn_linux_1308_liuming_linuxtime3]: http://www.ibm.com/developerworks/cn/linux/1308_liuming_linuxtime3/