Expand description
A hierarchical timing wheel with stable handles.
Entries live in a slab; the wheel’s slots hold indices into it. Cascading therefore moves four-byte indices between slots rather than whole entries, and a handle stays valid for an entry’s whole life however many times it moves, which is what makes cancellation an array index rather than a lookup.
The wheel never reads the clock. TimingWheel::advance_to is told what
time it is, so the whole structure is testable without waiting and a caller
with its own time source can drive it.
What the wheel decides for itself and what the caller decides is spelled out
in Policy: the level layout, which way a deadline between two ticks is
rounded, and how much work answering “what is due next” is worth.
§slab-wheel
A hierarchical timing wheel with stable handles, for schedulers that have to cancel far more often than they fire.
use std::time::{Duration, Instant};
use slab_wheel::{Millis, TimingWheel};
let start = Instant::now();
let mut wheel: TimingWheel<&str, Millis> = TimingWheel::starting_at(start);
let key = wheel.insert(start + Duration::from_millis(50), "read timeout");
// Nothing is due yet, and the wheel says when to come back.
wheel.advance_to(start + Duration::from_millis(10));
let mut due = Vec::new();
wheel.drain_expired_into(&mut due);
assert!(due.is_empty());
assert!(wheel.next_expiry().unwrap() <= start + Duration::from_millis(50));
// The read completed, so withdraw the timeout before it fires.
assert_eq!(wheel.remove(key), Some("read timeout"));
assert!(wheel.is_empty());§What it is for
The workload this is shaped around is a timeout armed per operation and
withdrawn when the operation completes, so most entries are cancelled and few
ever expire. An ordered map handles that at O(log n) with two structures to
keep in step; this handles it at a flat cost with one.
Entries live in a slab and the wheel’s slots hold indices into it. Cascading moves four-byte indices rather than whole entries, and a handle stays valid for an entry’s whole life however many times it moves between slots, which is what makes cancellation an array index rather than a lookup.
§It never reads the clock
advance_to is told what time it is. The whole structure is therefore testable
without waiting, and a caller with its own time source can drive it. The
property tests run two hundred randomized seeds in a tenth of a second for
exactly this reason.
§The contract
A caller sleeps on next_expiry with no clock behind it, so the answer may name
a time earlier than the truth but never a later one. Waking early costs a
wasted poll; waking late is a missed deadline.
Whether an entry can expire early is a separate question, and it is the caller’s to answer:
Rounding | guarantee | for |
|---|---|---|
Up | never early, may be late | runtimes, where waking a future early means it re-arms |
Down | never late, may be early | deadline enforcement, where overshoot is the failure |
Nearest | within half a tick either way | sampling and metrics |
§The one trade worth understanding
CoarseQuery decides how a level too coarse to read directly answers “what is
due next”.
BucketBound answers from the slot’s position alone: nothing in the slot at
offset k from the cursor can be due before that bucket begins. Constant cost,
never reads an entry, may name a time early.
ExactMinimum tracks the earliest deadline per slot and answers with it.
Exact, so no wasted poll.
Measured separately, ExactMinimum wins the query: 11.5ns against 13.4ns. That
is not the case that matters. Cancelling the entry that supplied a slot’s
minimum invalidates it, and the next query rebuilds the slot, so a caller doing
both continuously pays for it:
| entries in one slot | BucketBound | ExactMinimum |
|---|---|---|
| 64 | 17.1 ns | 39.1 ns |
| 512 | 16.1 ns | 221.0 ns |
| 4,096 | 15.9 ns | 1.55 µs |
At a million it does not finish. BucketBound is the default because arming and
cancelling is the workload; choose ExactMinimum if you query far more than you
cancel.
§Configuring the layout
Slot counts and resolutions must be powers of two. That is not a style rule: they are stored as a shift and a mask, so a runtime-configurable layout costs nothing against compiled-in constants. A layout that would be silently slow, or whose levels do not tile exactly, is rejected when the wheel is built.
use slab_wheel::{Policy, Rounding, TimingWheel};
struct Coarse;
impl Policy for Coarse {
const SLOTS: &'static [usize] = &[64, 64, 64];
const RESOLUTION: &'static [u64] = &[1, 64, 4_096];
const ROUNDING: Rounding = Rounding::Down;
}
// Building the wheel is what checks the layout: each level here spans
// exactly what the one below it covers, 64 x 1 and then 64 x 64.
let wheel: TimingWheel<(), Coarse> = TimingWheel::new();
assert!(wheel.is_empty());§Cost
Criterion, one machine, entries sharing a slot:
insert 12.4 -> 9.9 -> 9.9 -> 12.3 ns at 64 .. 1M
cancel_earliest_first 4.1 -> 3.6 -> 3.7 -> 4.0 ns at 64 .. 1M
next_expiry 13.4 ns flat
idle_gap 50 ns at 1ms and at 600sInsertion and cancellation do not care what shape the wheel is, but asking what is due next does, because it consults every level:
levels next_expiry
one level 1 5.2 ns
reactor layout 4 13.2 ns
eight narrow levels 8 20.5 ns
two levels, 1024 slots 2 20.7 nsDepth costs about two nanoseconds a level. Width costs too, at the far end: two levels of a thousand slots search as long as eight levels of two, because the occupancy mask is sixteen words instead of one.
Rounding is very nearly free, 10.8 ns against 11.4 ns, the difference being that rounding up divides with a ceiling. Refusing overflow rather than parking it costs 2.2 ns an insertion, for the check itself.
Flat is the claim. The absolute figures are a sanity check and nothing more until a real caller is driving it.
§What this does not do yet
No integrated measurement against a real runtime, which is the number that would
actually justify it. No no_std. Timing is in whole milliseconds. The wheel is
single-threaded by construction and holds no locks.
§Licence
MIT or Apache-2.0, at your option.
Structs§
- Key
- A handle to a timer, valid until that timer is removed.
- Millis
- Milliseconds, four levels, eighteen hours of reach, and an entry that never expires before it was asked to.
- Timing
Wheel - A hierarchical timing wheel with stable handles.
Enums§
- Coarse
Query - How the wheel answers “what is due next” for a level it cannot read without breaking it down.
- Overflow
- What to do with a deadline beyond the wheel’s furthest slot.
- Rounding
- Where a deadline that falls between two ticks is placed.
Traits§
- Policy
- A wheel’s shape and the decisions it makes.