Kafka时间轮(TimerWheel)--算法简介

一、简介

一个简单的时间轮是一个定时器任务桶的循环列表。

1. 让u作为时间单位。
2. 尺寸为n的时间轮有n个桶，可以在n*u的时间间隔内保存定时器任务。
3. 每个bucket保存属于相应时间范围的计时器任务。

在开始时，

1. 第一个桶保存[0，u）的任务，第二个桶保存[u，2u），…的任务…，[u*（n-1），u*n）的第n个bucket。
2. 每个时间单位u的间隔，计时器滴答作响移动到下一个bucket，然后使其中的所有计时器任务过期。

因此，计时器从不插入任务到当前时间的存储桶，因为它已经过期。

计时器会立即运行已过期的任务。清空的bucket可用于下一轮，因此如果当前为时间t的bucket，它在一个tick之后变成[t+u*n，t+（n+1）*u）的bucket。

二、时间轮复杂度分析 

• 时间轮的插入/删除（启动定时器/停止定时器）成本为O（1），
• 优先级队列基于定时器，如java.util.concurrent.DelayQueue和java.util.Timer，具有O（logn）插入/删除成本。

三、简单时间轮

简单时间轮的一个主要缺点是，它假设计时器请求在从当前时间开始的n*u的时间间隔。
如果定时器请求超出该间隔，会产生溢出。

四、分级时间轮

1. 分级时间轮会处理上面这种溢出，这是一种等级制度有组织的时间轮。
2. 最低级别的时间分辨率最好。随着向上移动层次结构，时间分辨率变得更粗糙。
3. 如果一个轮子在一个级别上的分辨率是u并且大小为n，下一级的分辨率应为n*u。
4. 在每个级别上，溢出为委托给更高一级的轮子。
5. 当较高级别的轮子发出滴答声时，它会重新插入计时器任务到较低级别。
6. 溢流轮可以按需创建。当一个桶溢出存储桶过期，其中的所有任务都会递归地重新插入计时器。
7. 这些任务会被移动到更细粒度的轮子或被执行。插入（启动计时器）成本为O（m），其中m是轮子的数量，与请求的数量相比，这个数量通常很小，并且删除（停止定时器）成本仍然是O（1）。

五、示例

假设u是1，n是3。如果开始时间是c，则不同级别的桶是：

前序bucket到期时间为后序bucket开始时间。

1. 因此，在时间＝c+1时，存储桶[c，c]、[c，c+2]和[c，c+8]到期。
2. 级别1的时钟移动到c+1，并创建[c+3，c+3]。
3. 级别2和级别3的时钟保持在c，因为它们的时钟分别以3和9为单位移动。因此，在级别2和级别3中不会创建新的bucket。

注意，级别2中的bucket[c，c+2]不会接收任何任务，因为该范围已经在级别1中涵盖。
级别3中的bucket[c，c+8]也是如此，因为它的范围在级别2中涵盖。

这有点浪费，但简化了实现。

在时间＝c+2时，[c+1，c+1]是新到期的, 级别1移动到c+2，并创建[c+4，c+4]，

在时间＝c+3时，[c+2，c+2]是新到期的; 级别2移动到c+3，并创建[c+5，c+5]和[c+9，c+11]。
3级停留在c。

当操作在超时之前完成时，分级正时轮工作得特别好。即使一切都超时了，当计时器中有很多项目时，它仍然具有优势。其插入成本（包括重新插入）和删除成本分别为O（m）和O（1），而优先级为基于队列的计时器为插入和删除取O（log N），其中N是队列中的项目数。

============================= 英文版  ================================== 

Hierarchical Timing Wheels

A simple timing wheel is a circular list of buckets of timer tasks. Let u be the time unit.
A timing wheel with size n has n buckets and can hold timer tasks in n * u time interval.
Each bucket holds timer tasks that fall into the corresponding time range. At the beginning,
the first bucket holds tasks for [0, u), the second bucket holds tasks for [u, 2u), …,
the n-th bucket for [u * (n -1), u * n). Every interval of time unit u, the timer ticks and
moved to the next bucket then expire all timer tasks in it. So, the timer never insert a task
into the bucket for the current time since it is already expired. The timer immediately runs
the expired task. The emptied bucket is then available for the next round, so if the current
bucket is for the time t, it becomes the bucket for [t + u * n, t + (n + 1) * u) after a tick.
A timing wheel has O(1) cost for insert/delete (start-timer/stop-timer) whereas priority queue
based timers, such as java.util.concurrent.DelayQueue and java.util.Timer, have O(log n)
insert/delete cost.

A major drawback of a simple timing wheel is that it assumes that a timer request is within
the time interval of n * u from the current time. If a timer request is out of this interval,
it is an overflow. A hierarchical timing wheel deals with such overflows. It is a hierarchically
organized timing wheels. The lowest level has the finest time resolution. As moving up the
hierarchy, time resolutions become coarser. If the resolution of a wheel at one level is u and
the size is n, the resolution of the next level should be n * u. At each level overflows are
delegated to the wheel in one level higher. When the wheel in the higher level ticks, it reinsert
timer tasks to the lower level. An overflow wheel can be created on-demand. When a bucket in an
overflow bucket expires, all tasks in it are reinserted into the timer recursively. The tasks
are then moved to the finer grain wheels or be executed. The insert (start-timer) cost is O(m)
where m is the number of wheels, which is usually very small compared to the number of requests
in the system, and the delete (stop-timer) cost is still O(1).

Example
Let's say that u is 1 and n is 3. If the start time is c,
then the buckets at different levels are:

level    buckets
1        [c,c]   [c+1,c+1]  [c+2,c+2]
2        [c,c+2] [c+3,c+5]  [c+6,c+8]
3        [c,c+8] [c+9,c+17] [c+18,c+26]

The bucket expiration is at the time of bucket beginning.
So at time = c+1, buckets [c,c], [c,c+2] and [c,c+8] are expired.
Level 1's clock moves to c+1, and [c+3,c+3] is created.
Level 2 and level3's clock stay at c since their clocks move in unit of 3 and 9, respectively.
So, no new buckets are created in level 2 and 3.

Note that bucket [c,c+2] in level 2 won't receive any task since that range is already covered in level 1.
The same is true for the bucket [c,c+8] in level 3 since its range is covered in level 2.
This is a bit wasteful, but simplifies the implementation.

1        [c+1,c+1]  [c+2,c+2]  [c+3,c+3]
2        [c,c+2]    [c+3,c+5]  [c+6,c+8]
3        [c,c+8]    [c+9,c+17] [c+18,c+26]

At time = c+2, [c+1,c+1] is newly expired.
Level 1 moves to c+2, and [c+4,c+4] is created,

1        [c+2,c+2]  [c+3,c+3]  [c+4,c+4]
2        [c,c+2]    [c+3,c+5]  [c+6,c+8]
3        [c,c+8]    [c+9,c+17] [c+18,c+26]

At time = c+3, [c+2,c+2] is newly expired.
Level 2 moves to c+3, and [c+5,c+5] and [c+9,c+11] are created.
Level 3 stay at c.

1        [c+3,c+3]  [c+4,c+4]  [c+5,c+5]
2        [c+3,c+5]  [c+6,c+8]  [c+9,c+11]
3        [c,c+8]    [c+9,c+17] [c+18,c+26]

The hierarchical timing wheels works especially well when operations are completed before they time out.
Even when everything times out, it still has advantageous when there are many items in the timer.
Its insert cost (including reinsert) and delete cost are O(m) and O(1), respectively while priority
queue based timers takes O(log N) for both insert and delete where N is the number of items in the queue.