Up
# Module Timing_wheel_intf

#
Implementation

#
Representable times

### Signature

An

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 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

`Interval_num.t`

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