原文地址:Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facility

Yashiro Matsuda最近写了一篇博文Apache Kafka’s use of Hierarchical Timing Wheels 用于监控大量的延时操作。 在Kafka用例中,每个请求都处于“Purgatory”数据结构中,并且与事件驱动处理的超时计时器和观察者列表图相关联。 有效跟踪到期定时器是一个常见问题。 这个原则可以适用于任何跟踪未完成的请求或延时消息系统。

今天的选择是Varghese和Lauck在1987年发表的一篇论文,他们在这篇论文中研究了一些有效管理定时器的方法,并介绍了Kafka所使用的分层定时轮的概念。 他们将定时器建模为两个面向用户的操作,即启动和停止,以及两个内部操作:每个滴答步进和过期处理。

  • 启动计时器由客户端调用,指定一个计时器持续时间和一个回调。在作者的模型中,客户端还传入一个请求ID来区分计时器,但是现在我们更倾向于返回一个计时器ID来响应启动计时器的请求。

  • 停止定时器接收一个请求(定时器)ID,并找到并停止(删除)相关的定时器。

  • 在计时器时钟的每个“滴答声”上都会发生清算。如果设置定时器的粒度单位是T个单位时间(例如1秒),则每T个单位时间将发生一个清算。它检查是否有任何未完成的定时器已经过期,如果是则删除它们并调用过期处理。

  • 到期处理负责调用用户提供的回调(或其他用户请求的操作,具体取决于您的模型)。

不同的数据结构和算法在执行这些操作的成本方面有不同的复杂性(例如,启动一个定时器是一个恒定的时间操作,取决于现有定时器的数量,或者甚至是一些其他变量?)。 我们有七种不同的计时器管理方案,指导方针是“对于一个普通的定时器模块,这个模块预计在各种环境下都能正常工作,我们推荐方案6或7”。方案6是“散列定时轮”和方案7是“分层定时轮”。

让我们来看看这些方案:

1.无序列表的定时器

保留一个无序的列表定时器,并跟踪每个定时器的剩余时间。开始时,只需将新的计时器添加到列表中。每个“嘀嗒”周期必须遍历完整列表,并在每笔记帐中减少每个计时器的剩余时间。如果一个定时器到达零,它将从列表中删除,并调用过期处理。
因此启动一个定时器是O(1),停止一个定时器是O(1),并且每个滴答处理是O(n),其中n是未完成定时器的数量。

2.有序列表计时器

保留方案1中的列表定时器,但记录绝对到期时间(不是剩余时间),并保持定时器列表的排序时间(定时器最接近于列表头部的到期时间)。在每个时钟周期比较列表头部的定时器的到期时间和当前的时钟,并且如果定时器的到期时间是小于当前时间,则删除到期定时器; 继续这样做这样的比较,直到列表的头部包含一个过期时间大于当前时间的计时器。由于在列表中搜索正确的位置来插入它,所以现在启动一个计时器为O(n),但是每个嘀嗒处理是O(1)。

3.定时器树

对于比较大的n,我们可以通过在基于tree的数据结构中保留定时器来改进方案2。 这意味着我们可以在O(log(n))内为有序列表插入(启动)定时器。

4.简单的时间轮

当所有定时器的最大周期不超过MaxInterval时,简单的定时轮的方法是适用的,我们可以用MaxInterval槽(每个代表一个滴答)构造一个循环缓冲区。当前时间由缓冲区中的索引表示。插入一个计时器,过期时间j(小于MaxInterval); 在未来的MaxInterval时间单位中,我们移动环上的j个时隙,并将定时器添加到该时隙中的定时器列表中。 每次“嘀嗒”(模拟时钟,非常形象的描述了时间轮的走动),当前时间索引移动环中的一个槽,并在新槽中的所有定时器上执行到期处理。

开始,停止和每个“嘀嗒”操作都是O(1)。

5.带有序定时器列表的散列轮

如果MaxInterval比较大(例如32位定时器),简单的定时轮就可能会使用大量的内存。 我们可以使用散列的形式而不是每时间单位使用一个插槽。 构建一个具有固定数量的槽的循环缓冲区(2的指数会比较有效率),并且当前时间索引像以前一样在环上前进一个位置。 要插入将来会过期j个时间单位的计时器,计算一个增量时隙 s = j%num-buckets。 将定时器插入环中,并等待其到期。 由于在任何给定的时隙中可能有多个定时器,因此我们为每个时隙维护一个有序的定时器列表。每次处理时移动当前时间索引并处理在方案2中找到的定时器列表。插入定时器的最坏情况延迟是O(n),但是平均值是O(1)。 每次处理“嘀嗒”是O(1)。

6.无序定时器列表的哈希轮

这是方案5中的一个变体,其中不是存储绝对的到期时间,而是存储每个计时器将来在遍历环的次数。 为了插入一个计时器,将来会计算一个时间单位,计算一个计数器值c = j / num-buckets和一个时隙delta s = j%num-bucket。 用计数器值c将定时器的槽插入环中。保持定时器在每个槽中的无序列表中。

现在启动一个计时器是O(1),而每个滴答簿记是最坏的情况O(n),但是O(1)是平均的。

7.分级时间轮

处理由简单的定时轮方法引起的存储器问题的另一种方式是在层次结构中使用多个定时轮。假设我们要存储第二个粒度的定时器,将来可以设置长达100天。我们可以建造四个轮子:

  • 一个“天”轮有100个插槽
  • 一个“小时”轮有24插槽
  • 一个“分钟”轮有60个插槽
  • 一个“秒钟”轮有60个插槽

这总共有244个插槽,总计864万个可能的计时器值。每当我们在一个轮子上完成一次完整的转动,我们就把下一个较大的轮子向前推进一个槽位(本文用分钟,小时和星期计时钟来描述一个微小的变化,但效果是一样的)。例如,当秒轮转回到索引“0”时,我们将分针轮中的索引指针移动一个位置。然后,我们把时间轮上的所有定时器(将在接下来的60秒内到期),并将它们插入到秒针轮中正确的位置。秒轮中的过期时间处理完全按照方案4中所述的方式工作(这只是一个简单的计时轮,恰好在每次旋转时得到补充)。

要插入一个计时器,找到计时器应该到期的一个或多个车轮单元的第一个车轮(从最大单位到最小)。例如,一个计时器将会在未来11小时15分15秒的时间内插入小时轮的current-index + 11时隙,用计时器存储剩余的15分15秒。在小时轮前进11个位置后,该计时器将从该轮上移除,并在分针轮中的当前索引+ 15个插槽中插入,存储剩余的15秒。当分钟轮随后前进15个位置时,该计时器将从轮中移出,并放置在秒针轮中的“当前索引+15”轮槽中。 15秒后,计时器将过期!

插入为O(n),而每个滴答簿记是最坏的情况O(n),但是O(1)是平均的。

注意:本文使用秒,分,小时,天的例子,这当然使得它很容易遵循及更容易理解和记忆,但如果你只是给定时器,例如,在未来的t秒内达到32位计时器值,那么简单地将其分成四个轮子,每个轮子有28个槽或类似的轮子(这使得确定进入哪个轮子是非常有效的)。

在方案6和7之间选择

在任何给定的情况下,方案6或7是否更好取决于许多参数:

  • n,定时器的数量
  • M,可用插槽的总数
  • m,级别的数量(用于分级方法)
  • T,平均时间间隔

根据方案6计算一个条目的散列和索引成本在方案7(将计时器条目移动到下一个轮子的成本)之下。

对于方案6,成本大约是n’s indexcost / M,方案7是nm’s migratecost / T。

由于costindex和costmigrate不会有很大的不同,对于较小的T值和较大的M值,方案6对于START-TIMER和PER-TICK-BOOKKEEPING都可能比方案7更好。然而,对于大的T值和小的M值,方案7对于PER-TICK-BOOKKEEPING将具有更好的平均成本(等待时间),但对于START-TIMER来说成本更高。