时间轮算法及其扩展

《时间轮算法及其扩展》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、时间轮算法及其扩展1.引言在一个单机系统或分布式系统中，我们需要定时器来实现以下功能：实现故障恢复——如某些错误需要周期性的检查（服务器间的心跳，系统状态自检等）实现某些依赖时间或相对时间的算法——如进程调度程序，流量控制程序等等这些定时器失效的时间也长短不一，有些定时器可能只是期望在一段时间后触发一个函数（比如一个闹钟）；而还有些定时器可能会长期存在，如服务器之间的定期心跳，只要服务存在，该定时器就一直有效。当以下几个条件成立时，一个定时器算法实现是否高效就至关重要：当实现该算法的处理器会在每一个时钟周期都执行该算法时对定时器精度有一定要求时当同时有效的定时器数量很多时2

2、.模型之后的讨论都基于以下模型来进行，该模型认为一个定时器模块有以下4个基本函数：RequestIDStartTimer(Interval,ExpireAction)RequestID——定时器的唯一标识，执行StartTimer的返回值Interval——定时器到期时间ExpireAction——定时器到期动作StopTimer(RequestID)PerTickBookKeeping()ExpireProcessing()用户可以通过调用StartTimer(..)来创建一个定时器，通过StopTimer(..)来取消一个定时器。假设定时器精度的最小单元为T，那每一个T

3、周期定时器模块都会调用PerTickBookKeeping()，来确认是否有定时器过期，如果有的话，则调用ExpireProcessing()函数，该函数则会调用超时定时器对应的ExpireAction函数。以下两个维度用来衡量该文之后介绍的种种算法的优劣：空间（Space）——用于实现定时器模块需要的内存空间延迟（Latency）——从调用一个基本函数到返回成功的时间，假设该调用为阻塞调用3.定时器实现方案介绍3.1.方案一方案一的实现方式如图所示，该定时器模块通过一个数组(或链表)来实现，具体介绍如下：当创建一个新的定时器时（StartTimer），即在数组中插入一个新

4、的元素，记录该定时器距现在的时间差（最小时间度量单位用T表示）每过T个周期，PerTickBookKeeping函数会执行，该函数将所有的定时器中的时间差减T，若某个定时器中的时间差被减为0，则调用该定时器的ExpireAction函数执行该定时器模型实现非常简单，适用于以下场景定时器数量有限；绝大多数定时器在较短时间内到期；PerTickBookKeeping可由特殊硬件支持以提高处理速度；3.2.方案二从减少PerTickBookKeeping执行延迟的角度出发，提出了方案二，如下图所示：当新建一个定时器时，会向有序链表中添加一个新的元素，元素中具体记录定时器的绝对到期

5、时间（而非相对时间）。由于方案二采用了一个有序链表，该链表中的定时器按照到期时间排列。因此每一次进行PerTickBookKeeping操作时，只需要检查第一个定时器和当前时间的关系即可：若第一个定时器的到期时间大于当前时间，则本次检查结束，否则：删除第一个定时器，并执行它的ExpireAction函数，再重新检查队列的头部定时器，并进行相关操作，直到队列头部的定时器时间大于当前时间为止可以容易知道，采用方案二的实现，PerTickBookKeeping操作的时间复杂度为O(1)，然而由于StartTimer相关于进行一次插入排序，其时间复杂度为O(n)。而如果有序链表用双

6、向链表实现，则StopTimer的时间复杂度也为O(1)。为什么StopTimer的时间复杂度为O(1)?因为当用户调用StartTimer(Interval,ExpireAction)来创建定时器时，我们可以在讲定时器插入双向链表后，将该定时器的指针作为RequestID返回给用户，之后用户通过调用StopTimer(RequestID)来取消定时器时，由于为双向链表，因此可以在O(1)时间内完成。3.3.方案三方案二的实现要求每次用系统当前时间和所有定时器的最短过期时间进行比较，从而避免了和去检查每一个定时器是否到期。因此我们可以采用最小堆实现的优先级队列，该数据结构保

7、证了队列最头部是有最短过期时间的定时器。同时该结构可动态调整，当把队列头部定时器删掉后，新的队列头部依然为有最短过期时间的定时器。利用最小堆实现的定时器，其StartTimer的复杂度为O(logN)，StopTimer和PerTickBookKeeping的时间复杂度均为O(1)。3.4.方案四方案四即为一种时间轮的实现方式，它通过一个数组来实现，数组中的每一个元素表示一个时间单元。每一个元素有一个定时器链表，表示在该时间单元上过期的所有定时器。有一个当前时间指针（CurrentTime），该指针每过一个时间单元