NAME Data::HierTimingWheel::Shared - shared-memory hierarchical timing wheel (O(1) timers at any delay) SYNOPSIS use Data::HierTimingWheel::Shared; # 4 levels of 256 slots -> schedules any delay up to 256**4 - 1 ticks my $tw = Data::HierTimingWheel::Shared->new(undef, 256, 4, 100_000); my $id = $tw->add(30, $job_id); # fire in 30 ticks my $id2 = $tw->add(5_000_000, $late); # ...or millions of ticks away, still O(1) $tw->cancel($id); # cancel before it fires # advance the clock; each call returns the payloads that came due for (1 .. $ticks_elapsed) { my @due = $tw->advance(1); handle($_) for @due; } # share the wheel across processes via a backing file my $shared = Data::HierTimingWheel::Shared->new("/tmp/timers.htw", 256, 4, 100_000); DESCRIPTION A hierarchical timing wheel in shared memory (the Varghese-Lauck design behind Linux kernel and Kafka/Netty timers): a timer scheduler where scheduling and cancelling are O(1) at any delay, from one tick to billions, in a fixed amount of memory. It is the multi-level generalisation of Data::TimingWheel::Shared: where the single-level wheel revisits a far-future timer once per rotation, this one parks it in a coarse level and only touches it as its time approaches. Time advances in integer ticks. There are "num_levels" cascading wheels of "num_slots" (= S) buckets each; a level-"k" slot spans "S**k" ticks, so the whole structure schedules any delay in "[1, S**num_levels)". A timer is placed in the lowest level whose range covers its delay. On each tick, level 0 fires the timers in its current slot; when level 0 completes a rotation, the next level's current slot cascades down -- its timers are redistributed into finer levels by their remaining delay -- recursively up the levels. A timer with delay "D" fires at exactly tick "D", just like the single-level wheel, but a far-future timer costs O(1) instead of one visit per rotation. Each timer carries an arbitrary 64-bit payload (e.g. a job id) returned when it fires. Timers live in a fixed pool of "capacity" slots; scheduling beyond it, or with a delay at or beyond "S**num_levels", croaks. Because the wheels live in a shared mapping, several processes schedule into and advance one clock: any process that opens the same backing file, inherits the anonymous mapping across "fork", or reopens a passed memfd shares the same timers. A write-preferring futex rwlock with dead-process recovery guards mutation. Linux-only. Requires 64-bit Perl. METHODS Constructors my $tw = Data::HierTimingWheel::Shared->new($path, $num_slots, $num_levels, $capacity, $mode); my $tw = Data::HierTimingWheel::Shared->new(undef, $num_slots, $num_levels, $capacity); my $tw = Data::HierTimingWheel::Shared->new_memfd($name, $num_slots, $num_levels, $capacity); my $tw = Data::HierTimingWheel::Shared->new_from_fd($fd); $num_slots (S, 2..2^16, default 256) is the number of buckets per level, and $num_levels (L, 1..16, default 4) the number of cascading wheels; together they set the maximum schedulable delay to "S**L - 1" ticks ("num_slots ** num_levels" must fit in 64 bits, else the constructor croaks). $capacity is the maximum number of concurrent timers (1..2^24). Memory is "num_levels * num_slots * 4 + capacity * 32" bytes plus a fixed header. Choose S and L so that "S**L" exceeds your longest delay -- e.g. "256, 4" covers ~4.3 billion ticks, "64, 8" covers ~281 trillion. When reopening an existing file or memfd the stored geometry wins and the caller's arguments are ignored. An optional file mode may be passed as the last argument to "new" (e.g. 0660) for cross-user sharing; it defaults to 0600 (owner-only). Scheduling my $id = $tw->add($delay, $payload); # returns a timer id my $id = $tw->schedule($delay, $payload); # alias for add my $ok = $tw->cancel($id); # 1 if cancelled, 0 if already fired/invalid "add" schedules a timer to fire $delay ticks from now (a delay below 1 is treated as 1) carrying the integer $payload, and returns a timer id; it croaks if the timer pool is full or $delay is at or beyond the wheel's range ("max_delay + 1"). "cancel" removes a still-pending timer by its id, returning 1 if it was cancelled or 0 if it had already fired or the id is not active. Advancing the clock my @due = $tw->advance($ticks); # advance by $ticks (default 1) my @due = $tw->advance; # advance by one tick "advance" moves the wheel forward by $ticks ticks (default 1) and returns the list of payloads of every timer that came due during those ticks, in fire order. Timers that fire are removed automatically. Cost is O(ticks + fired) amortised; cascades happen only when a level rolls over. Introspection and lifecycle $tw->now; # absolute tick count since creation (or last clear) $tw->count; # number of pending timers $tw->num_slots; # slots per level (S) $tw->num_levels; # number of levels (L) $tw->max_delay; # largest schedulable delay (S**L - 1) $tw->capacity; # maximum concurrent timers $tw->clear; # cancel all timers and reset the clock to 0 $tw->stats; # { now, count, num_slots, num_levels, max_delay, capacity, ops, mmap_size } $tw->path; $tw->memfd; $tw->sync; $tw->unlink; "clear" cancels every timer and resets the tick counter. "sync" flushes the mapping to its backing store (a no-op for anonymous and memfd wheels); "unlink" removes the backing file (also callable as "Class->unlink($path)"); "path" returns the backing path ("undef" for anonymous, memfd, or fd-reopened wheels) and "memfd" the backing descriptor. SHARING ACROSS PROCESSES The wheels live in a shared mapping, shared the same three ways as the rest of the family: a backing file, an anonymous mapping inherited across "fork", or a memfd passed to an unrelated process and reopened with new_from_fd($fd). Any process can schedule timers; typically one process owns advancing the clock and dispatches the fired payloads, while others schedule and cancel. The tick counter is shared, so all processes agree on "now". SECURITY Backing files are created with mode 0600 (owner-only) by default; pass an explicit octal mode (e.g. 0660) as the last argument to "new" for cross-user sharing. The file is opened with "O_NOFOLLOW" and "O_EXCL", and the header is validated on attach. Any process granted write access is trusted not to corrupt the mapping. CRASH SAFETY Mutation is guarded by a futex-based write-preferring rwlock with PID-encoded ownership and dead-owner recovery. Scheduling, cancelling, and each tick of an advance are short bounded list operations, so a crash leaves the wheel consistent up to the last completed operation. Limitation: PID reuse is not detected (very unlikely in practice). Reader-slot exhaustion (slotless readers): dead-process recovery attributes a crashed lock holder's contribution through its reader-slot. The slot table holds 1024 entries (one per concurrent reader process). If more than that many reader processes share one mapping at once, a reader that cannot claim a slot proceeds "slotless" -- it still takes the read lock but leaves no per-process record. If such a slotless reader is then killed while holding the read lock, its share of the lock cannot be attributed to a dead process, so writer recovery cannot reclaim it and writers may block until the mapping is recreated. Reaching this needs more than 1024 concurrent reader processes on one mapping plus a crash in the brief read-lock window; the dead-process slot reclaim keeps the table from filling with stale entries, so in practice it is very unlikely. SEE ALSO Data::TimingWheel::Shared (single-level wheel; simpler, for bounded delays), Data::Heap::Shared (priority queue / exact ordering), and the rest of the "Data::*::Shared" family. AUTHOR vividsnow LICENSE This is free software; you can redistribute it and/or modify it under the same terms as Perl itself.