Crate ferris [] [src]

A hierarchical timer wheel

The number of wheels in the hierarchy are determined by the number of Resolutions passed into the concrete constructors AllocWheel::new() and 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 Resolution::TenMs and Resolution::HundredMs, then 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 for its key. This allows the key to be stored in a global hashset that can be used for O(1) cancel. A Weak<T> is stored in the wheel slot, so that if the timer is cancelled, the memory is de-allocatd. When the expiry for that slot comes around, an attempt to promote the Weak reference will return None and so it will be ignored when draining the wheel slot. If the timer expires before it is cancelled, the weak reference can be used to remove the Rc from the HashMap, as well as trigger the user timeout behavior.


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