A hierarchical timer wheel
The number of wheels in the hierarchy are determined by the number of Resolutions passed into
the concrete constructors
CopyWheel::new(). The size of each wheel is
automatically determined based on whether certain other resolutions are available. For instance
if a wheel is constructed consisting of
the number of slots in the 10 ms wheel will be 10 (10 slots to get to 100ms). However, if
Resolution::HundredMs was not used, then
Resolution::TenMs would have 100 slots (100ms to
get to 1 sec).
In order for the timer to operate correctly, it must tick at the maximum resolution. For
instance if 10ms and 1s resolutions are used,
expire() must be called every 10ms.
The minimum length of a timer is limited by the highest resolution. For instance if 10ms and 1s resolutions were used, the minimum length of a timer would be 10ms.
The maximum length of a timer is limited by the lowest resolution. For instance if 10ms, and 1s resolutions were used, the maximum length of a timer would be 59s.
There is no migration between wheels. A timer is assigned to a single wheel and is scheduled at it's minimum resolution. E.g. If a timer is scheduled for 1.3s it will be scheduled to fire 2 second ticks later. This is most useful for coarse grain timers, is more efficient computationally and uses less memory than being more precise. The wheels don't have to keep track of offsets for the next inner wheel for wheel to wheel migration, and thus save memory. And since the migration ddoesn't actually occur, we save cpu, and potentially extra allocations.
This wheel requires an allocation for each timer as it creates an Rc
This wheel maintains a copy of the timer key in both the appropriate inner timer wheel slot and the global hashset. This does not require an allocation for each timer but may use more memory than an CopyWheel depending upon the size of the keys. When the expiry for a slot occurs, the global hashmap is checked for the expiring keys. If they are still there it means they are valid to expire, otherwise they have already been cancelled.
A resolution for a wheel in the hierarchy