Crate hierarchical_hash_wheel_timer

This crate provides a low-level event timer implementation based on hierarchical hash wheels.

The APIs in the crate are offered at three different levels of abstraction, listed below from lowest to highest.

1 – Single Wheel

The fundamental abstraction of this crate a single hash wheel with 256 slots addressed with a single byte. Each slot stores a list of a generic event type. The whole wheel can be “ticked” causing entries in the slots that are being moved over to expire. With every tick, all expired event entries are returned for handling. For more details see the byte_wheel module.

2 – Hierachical Wheel

Combining four byte wheels we get a hierachical timer that can represent timeouts up to u32::MAX time units into the future. In order to support timeouts of up to u64::MAX time units, our implementations also come with an overflow list, which stores all timers that didn’t fit into any slot in the four wheels. Addition into this list happens in (amortised) constant time but movement from the list into the timer array is linear in the number of overflow items. Our design assumed that the vast majority of timers are going be scheduled less than u32::MAX time units into the future. However, as movement from the overflow list still happens at a rate of over 6mio entries per second (on a 2019 16“MBP) for most applications there should be no large issues even if this assumption is not correct.

This crate provides two variant implementations of this four level wheel structure:

• The quad_wheel::QuadWheelWithOverflow corresponds directly to the implementation described above.
• The cancellable::QuadWheelWithOverflow additionally supports the cancellation of outstanding timers before they expire. In order to do so, however, it requires the generic timer entry type to provide a unique identifier field. It also uses Rc internally to avoid double storing the actual entry, which makes it (potentialy) unsuitable for situations where the timer must be able to move threads (since Rc](std::rc::Rc) is not Send).

3 – High Level APIs

This crate also provides two high levels APIs that can either be used directly or can be seen as examples of how to use the lower level APIs in an application.

Bother higher level APIs also offer built-in support for periodically repeating timers, in addition to the normal timers which are schedulled once and discarded once expired.

Simulation Timer

The simulation module provides an implementation for an event timer used to drive a discrete event simulation. Its particular feature is that it can skip quickly through periods where no events are schedulled as it doesn’t track real time, but rather provides the rate at which the simulation proceeds.

Thread Timer

The thread_timer module provides a timer for real-time event schedulling with millisecond accuracy. It runs on its own dedicated thread and uses a shareable handle called a TimerRef for communication with other threads.

Modules

simulation

This module provides an implementation for an event timer used to drive a discrete event simulation.

thread_timer

This module provides a timer for real-time event schedulling with millisecond accuracy.

wheels

This module contains the level 1 and 2 APIs for building event timers.

Structs

IdOnlyTimerEntry

A simple implementation of a timer entry that only stores its own unique id and the original delay

OneShotClosureState

A timeout state for a one-shot timer using a closure as the triggering action

PeriodicClosureState

A timeout state for a periodic timer using a closure as the triggering action

Enums

TimerEntry

A concrete entry for an outstanding timeout

TimerError

Errors encounted by a timer implementation

TimerReturn

Indicate whether or not to reschedule a periodic timer

Traits

ClosureTimer

This trait is a convenience API for timers that use the closure state types, i.e. OneShotClosureState and PeriodicClosureState.

OneshotState

A trait for state that can be triggered once

PeriodicState

A trait for state that can be triggered more than once once

Timer

A basic low-level timer API

Type Aliases

UuidOnlyTimerEntry

A shorthand for id timer entries that use Uuid as their id type