Module `Core_kernel__.Timing_wheel_ns_intf`

A specialized priority queue for a set of time-based alarms.

A timing wheel is a data structure that maintains a clock with the current time and a set of alarms scheduled to fire in the future. One can add and remove alarms, and advance the clock to cause alarms to fire. There is nothing asynchronous about a timing wheel. Alarms only fire in response to an advance_clock call.

When one creates a timing wheel, one supplies an initial time, start, and an alarm_precision. The timing wheel breaks all time from the epoch onwards into half-open intervals of size alarm_precision, with the bottom half of each interval closed, and the top half open. Alarms in the same interval fire in the same call to advance_clock, as soon as now t is greater than all the times in the interval. When an alarm a fires on a timing wheel t, the implementation guarantees that:

Alarm.at a < now t

That is, alarms never fire early. Furthermore, the implementation guarantees that alarms don't go off too late. More precisely, for all alarms a in t:

interval_start t (Alarm.at a) >= interval_start t (now t)

This implies that for all alarms a in t:

Alarm.at a > now t - alarm_precision t

Of course, an advance_clock call can advance the clock to an arbitrary time in the future, and thus alarms may fire at a clock time arbitrarily far beyond the time for which they were set. But the implementation has no control over the times supplied to advance_clock; it can only guarantee that alarms will fire when advance_clock is called with a time at least alarm_precision greater than their scheduled time.

There are two implementations of timing wheel, Timing_wheel_float and Timing_wheel_ns, which differ in the representation of time that they use, Time or Time_ns. Timing_wheel_ns is the underlying implementation, whereas Timing_wheel_float is a wrapper around Timing_wheel_ns that converts between the two representations of time.

Implementation

A timing wheel is implemented using a specialized priority queue in which the half-open intervals from the epoch onwards are numbered 0, 1, 2, etc. Each time is stored in the priority queue with the key of its interval number. Thus all alarms with a time in the same interval get the same key, and hence fire at the same time. More specifically, an alarm is fired when the clock reaches or passes the time at the start of the next interval.

Alarms that fire in the same interval will fire in the order in which they were added to the timing wheel, rather than the time they were set to go off. This is consistent with the guarantees of timing wheel mentioned above, but may nontheless be surprising to users.

The priority queue is implemented with an array of levels of decreasing precision, with the lowest level having the most precision and storing the closest upcoming alarms, while the highest level has the least precision and stores the alarms farthest in the future. As time increases, the timing wheel does a lazy radix sort of the alarm keys.

This implementation makes add_alarm and remove_alarm constant time, while advance_clock takes time proportional to the amount of time the clock is advanced. With a sufficient number of alarms, this is more efficient than a log(N) heap implementation of a priority queue.

Representable times

A timing wheel t can only handle a (typically large) bounded range of times as determined by the current time, now t, and the level_bits and alarm_precision arguments supplied to create. Various functions raise if they are supplied a time smaller than now t or >= alarm_upper_bound t. This situation likely indicates a misconfiguration of the level_bits and/or alarm_precision. Here is the duration of alarm_upper_bound t - now t using the default level_bits.

      | # intervals | alarm_precision | duration |
      +-------------+-----------------+----------|
      |        2^61 | nanosecond      | 73 years |

module type Timing_wheel_time = sig ... end: Timing_wheel_time is used to parameterize the timing-wheel interface over both Time and Time_ns.

module type Interval_num = sig ... end: An Interval_num.t is an index of one of the intervals into which a timing-wheel partitions time.

module type Alarm_precision = sig ... end: An Alarm_precision is a time span that is a power of two number of nanoseconds, used to specify the precision of a timing wheel.

module type Timing_wheel = sig ... end

module type Timing_wheel_ns = sig ... end: A timing wheel can be thought of as a set of alarms.