A specialized priority queue for a set of time-based alarms.
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.
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 create
s 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.
================== 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.
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.
=======================
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 Int63 = Core_kernel__.Core_int63
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
module type Timing_wheel : sig ... end