This is the Byte Visualization series Kafka column.

Through this article you will understand the idea of time wheel algorithm, hierarchical time wheel, time wheel upgrade and downgrade.


The time wheel, a clever algorithm for implementing delay functions (timers), is found in various frameworks such as Netty, Zookeeper, Kafka, and even the Linux kernel.


This article will refer to Kafka’s time wheel as an example.


Design comes from life

Let me show you a Popper Chinese calendar before we begin.

Photo from the official website of Po Po


The watch’s dial combines the extensive and profound timing elements of the Chinese calendar.


The small dial in the upper position shows the numbers and characters of the hour,24 hours a cycle; Year window shows the year of the zodiac, a 12-year cycle;


The left position shows the lunar month, a 12-month cycle; Lunar day, 30 days a cycle;


The position on the right shows five elements and ten heavenly stems, with a 10-year cycle;


The dial below shows the phases of the moon.


As for the price….. I’ll skip that.


And the time wheel, its design is derived from the life of the clock.


1 time round

Here is a simple time wheel:


The center of the circle in the picture shows the current time, and the time at the center of the circle keeps beating as time goes on.


Let’s talk about Kafka’s TimingWheel using this diagram.


At the bottom of the Kafka time wheel is an array of rings, each of which contains a bidirectional linked list called TimerTaskList, which encapsulates many delayed tasks.


In Kafka, a TimingWheel is composed of 20 time cells, wheelSize = 20; The time span of each cell is 1ms, tickMs = 1ms. In Kafka, 20 small circles with gray edges are used to represent the time grid. For the sake of animation, the time span of each circle is 1s.


So the entire time span is now tickMs * wheelSize, or 20s. From 0s to 19s, we each have a small circle with gray edges to carry.


Kafka’s time wheel also has a dial pointer currentTime, which represents the currentTime of the time wheel. This is the circle represented by the thick black line, and it moves forward over time;



Adding a Scheduled Task

With the time wheel, you can now add timed tasks to it. We use a small pink circle to represent a timed task.


Let’s start with the Settings. Each scheduled task has a delay time
delayTime, and expiration time
ExpiredTime.

For example, if the current time is 10s, and we add a task with a delay of 2s, then the expiration time of this task will be 12s, that is, when the current time of 10s moves two more seconds and becomes 12s, it will be time to trigger the scheduled task.


The number displayed on the small circle with gray edge on the time wheel represents the time grid can be understood as the expiration time of the task.



Now that these Settings are clear, let’s start adding scheduled tasks.


At the beginning, the time wheel’s pointer stops at 0. Add a task with a timeout of 2s, and the task will be inserted into the second time cell.



When the pointer of the time wheel reaches the second time cell, the corresponding task on that time cell is processed. In animation is to make the red circle disappear!


If a task with an 8s delay is inserted at this time, and its expiration time is 10s plus 8s of the current 2s, the task will be inserted into the time grid with an expiration time of 10s.





2 “dynamic” time wheel

So far, so easy to understand.


So if you insert a task with a delay of 19s when the current time is 2s, the expiration time of the task is 19s plus the current time of 2s, which is 21s.




Please see the figure below. The current time wheel is a time cell with no expiration time of 21s. This task will be inserted into the time grid with an expiration time of 1s. How does this happen?

Multiplexing time lattice


To answer the above question, let’s do a little magic to make the time wheel move!

In fact, when the pointer is fixed in 2s position, the time squares 0s, 1s and 2s are already expired.


That is to say, Pointers can be used to divide expired time grids [0,2] and future time grids [3,19]. Expired time cells can be reused. For example, the expiration time of 0s becomes 20s, and the task whose expiration time is 20s is saved.



Once you understand the reuse of time cells, go back to the previous example. When the current time is 2s, add a task with a delay of 19s, and the task will be inserted into a time cell with an expiration time of 21s.


3 Time round upgrade

Now, here comes a new question. Please sit and hold on.


If you insert a task with a delay of 22s when the current time is 2s, the task’s expiration time is 24s plus 22s.



Obviously, the current time wheel cannot find a time cell with an expired time cell of 24 seconds, because the current maximum expired time cell only reaches 21s. And we can’t reuse time cells like we did before, because none of the time cells have expired, except for 2s. The current time wheel cannot handle this scheduled task, so what should I do?


Of course we could choose to expand the time lattice on the time wheel, but then the time wheel would be meaningless.


It’s time to upgrade the time wheel!


Let’s first understand the connection between the multiple time wheels.


Level 4 time wheel

Here is a two-tier time wheel:

The second time round is also composed of 20 time cells, with a span of 20s for each cell.


The figure shows the corresponding expiration time range of each time cell. We can clearly see that the expiration time range of the 0 th time cell of the second time round is [0,19]. In other words, one lattice of the second time round can represent all (20) lattice of the first time round;


To further clarify the relationship between the first time wheel and the second time wheel, let’s take time by the hand and watch the GIF below:

It can be seen that the second-layer time wheel also has its own pointer. Whenever the first-layer time wheel completes a cycle, the pointer of the second-layer time wheel will advance by one space.


Adding a Scheduled Task

Back to the original problem, insert a task with a delay of 22s and an expiration time of 24s when the current time is 2s.

When the time wheel of the first layer cannot accommodate any more, it enters the time wheel of the second layer and inserts it into the time lattice with the expiration time [20,39].


Let’s take another example. If you insert a task with a delay of 350s when the current time is 2s, the expiration time of the task is 350s plus 2s.

As can be seen from the figure, the task is inserted into the time grid with the expiration time of [340,359]s of the second layer time round, which is the position of the 17th grid.



5 “dynamic” hierarchical time wheel

Generally speaking, the 0th cell of the layer 2 time round is used to represent the layer 1 time round. This cell cannot store tasks, because tasks with a timeout period of 0-20s can be processed by the layer 1 time round.


But! Things are not always that simple, and the time bars on our time wheel are reusable! How does this manifest itself in the second time wheel?


Here’s the magic time, let’s get the expired time on the time wheel moving!


As can be seen from the figure, when the pointer of the first time round is fixed at 1s, the time lattice of the timeout time of 0s will expire. At this time, the time range of the 0 time cell in the second time round is divided from [0,19] into expired [0] and unexpired [1,19]. The expired [0] is reused by the new expiration time [400].


The evolution of the expiration time range of the 0 th time cell in the second time round is as follows:

[19] 0 –

[400] [1] 3

[400401], [2] 3

.

[400419]


So, if you insert a task with a delay of 399s when the current time is 2s, the expiration time of the task is 399s plus 2s, or 401s. As shown in the figure, this task will still be inserted into the 0 time grid of the second time round.


6 Time round demotion

To return to the familiar example, insert a task with a delay of 22s and an expiration time of 24s when the current time is 2s. Finally, it enters the second time round and is inserted into the time grid whose expiration time is [20,39].




When scheduled tasks on the layer 2 time wheel expire, what does the time wheel do?


As you can see, as the current time goes from 2s to 20s, it’s 18 seconds. In the layer 2 time round, the task in the time pane whose timeout duration is [20-39s] expires.


Tasks with a timeout of 24s are removed and readded to the time wheel. At this point, the delay time of the scheduled task changes from 22s to 4s (22S-18s). The last time to stay in the first time round timeout is 24s time cell, which is the fourth time cell.


The scheduled task will be executed after 4 seconds.




Here you can see the ingenuity of the time wheel. The two-tier time wheel uses only 40 array elements, but can carry the scheduled tasks of [0-399s]. And the three layer time wheel with 60 array elements, can bear [0-7999s] of the scheduled task!



The advance of the time wheel

It can be noticed from the animation that, as time progresses, the pointer of the time wheel circularly freezes on each time grid, and each time it is necessary to judge whether there is a task in the current fixed time grid.


Many of them have no tasks. The pointer is fixed in this empty lattice, which is a “empty advance”.


For example, if you insert a 400s delay, the pointer will have to perform 399 “empty pushes “, which is a waste!


So how does Kafka solve this problem? This starts with the DelayQueue!
What happens when the time wheel is paired with the DelayQueue? Please pay attention to the following updates of the official account bytecarming.



Review past

  • The graph shows heap sort


  • Why does TCP have 3 handshakes and 4 waves? It’s a communication skill
  • One graph to figure out merge sort
  • The story of Java Thread Pools, four vases