Expand description
A hierarchical timing wheel (Varghese and Lauck, SOSP 1987).
Four levels of 64 slots; level l slots are 64^l ticks wide, so the wheel spans 64^4
ticks (about 4.6 hours at the default 1 ms tick) and later deadlines wait in the last level
and are re-filed as time approaches. Insert and cancel are O(1) (nodes live in a slab and form
doubly linked lists per slot); finding the next deadline is a few bitmap operations; advancing
touches only slots that hold timers, never every tick in between.
Structsยง
- TimerId
- A handle to a scheduled timer, for
TimerWheel::cancel. Stale handles are ignored. - Timer
Wheel - A hierarchical timing wheel holding payloads of type
T. Time is in ticks; the owner decides what a tick is. See the module docs.