An Introduction Of Hierarchical Timing Wheels
Timer is a so important component be needed in many projects to limit a action or to trigger an event, we used to start a thread or coroutine to implement one for rapid development. But some of you may encountered the scenario that requires lot of timers, like developing a restful server or a message server, then a high-performance timer is strongly needed. we got serveral options to choose:
- Ordered Linked Timer List
- Heap Based Timer
- Hashed Timing Wheels
- Hierarchical Timing Wheels
And this documentation illustrates hierarchical timing wheels algorithm and an implemention of it.
I drew some easy-understand diagrams which are time ordered to describe the algorithm, and some corresponding comments had been written next to the graphic content.
Let's name a fixed internal of time going-by as ticking, naming a pre-set-able event as tick which be called timer in common, and timer presents the algorithm. So let's start with the case with simple 2 wheels.
Assuming we got a clean enviroment and doing nothing at ticking 0.
Calculate 2 5-ticking-after ticks's positions in wheels respectively and insert into right place.
Since nothing special happened from ticking 1 to ticking 5, they've all omitted. At ticking 6, the ticks set at ticking 1 fired.
Add another 3 ticks into timer.
This ticking is important because it illustrates what happened when a lower wheel's ticking rotated back at position 0, and this, will raise the ticking of higher wheel.
Two ticks set at ticking 8 fired, one of them ended and another one be set into lower wheel.
The tick in wheel 0 fired.
The last tick set at ticking 7 fired and be set into lower wheel.
The last tick fired and ended.
Everything cleaned up as ticking 0.
see implementation in golang here