Skip to main content

Crate slab_wheel

Crate slab_wheel 

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

Roundingguaranteefor
Upnever early, may be lateruntimes, where waking a future early means it re-arms
Downnever late, may be earlydeadline enforcement, where overshoot is the failure
Nearestwithin half a tick either waysampling 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 slotBucketBoundExactMinimum
6417.1 ns39.1 ns
51216.1 ns221.0 ns
4,09615.9 ns1.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 600s

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

Depth 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.
TimingWheel
A hierarchical timing wheel with stable handles.

Enums§

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