Production Case Study: Hierarchical Hashed Timer Wheels vs Four-Heap Timers (Go runtime, Kafka, Linux)

Architectural Tradeoff: 4-Ary Min-Heap vs Hierarchical Timing Wheel

Why do the Linux kernel (kernel/time/timer.c), Netty (HashedWheelTimer), and Apache Kafka (TimingWheel) use Timing Wheels for network timeouts, whereas Go's runtime (runtime/time.go) and the Linux high-resolution timer subsystem (hrtimer) use 4-ary Heaps or Red-Black Trees?

• 4-Ary Min-Heap (Go Runtime / libev): Stores [when, period, fn, seq] entries in a flat 4-ary array. Gives exact nanosecond resolution and $O(1)$ lookup of the next deadline (timers[0].when), allowing an idle OS thread to sleep until the exact nanosecond via epoll_wait / kqueue with zero periodic tick wakeups. However, inserting or rescheduling costs $O(\log_4 N)$.
• Single-Level Hashed Wheel (Netty): A circular array of $W$ buckets (e.g., $W = 512$, tick $\Delta t = 10\text{ ms}$). A timer expiring in $\tau$ ticks is appended in $O(1)$ to bucket $(\text{cursor} + \tau) \bmod W$ with remainingRounds = τ / W. Cancellation is an $O(1)$ doubly-linked list unlink! However, if $\tau \gg W$, ticking through empty or high-round entries wastes CPU.
• Hierarchical Timing Wheel (Kafka Purgatory / Varghese Scheme 6): Stacks multiple wheels like an odometer (e.g., Wheel 0: $20 \times 1\text{ ms}$; Wheel 1: $20 \times 20\text{ ms}$; Wheel 2: $20 \times 400\text{ ms}$). Long-horizon timers sit silently in upper wheels and cascade downward only when their coarse bucket expires. And how does Kafka avoid waking up an idle CPU every $1\text{ ms}$? By inserting only the non-empty buckets themselves (at most $20 \times 4 = 80$ buckets total!) into a tiny Java DelayQueue (Min-Heap), so the heap size is $O(M \cdot W) = O(1)$ instead of $O(N)$!

Implementation: O(1) Intrusive Hierarchical Timing Wheel Level

// C++20: O(1) Insert / O(1) Cancel Intrusive Timing Wheel Level (Linux / Kafka Style)
#include <cstdint>
#include <array>

struct TimerNode {
    uint64_t expireMs = 0;
    TimerNode *prev = nullptr, *next = nullptr;
    bool active = false;

    // O(1) Cancellation via intrusive doubly-linked list unlink
    void cancel() noexcept {
        if (!active) return;
        if (prev) prev->next = next;
        if (next) next->prev = prev;
        prev = next = nullptr;
        active = false;
    }
};

template <size_t W = 64> // Power-of-2 wheel size for bitmask modulo
class TimingWheelLevel {
    static_assert((W & (W - 1)) == 0, "Wheel size W must be a power of 2");
    std::array<TimerNode, W> sentinels{}; // Dummy head nodes per slot
    uint64_t currentTick = 0;
    uint64_t tickShift = 0;               // tickMs = 1ULL << tickShift

public:
    explicit TimingWheelLevel(uint64_t shift = 0) : tickShift(shift) {
        for (auto& s : sentinels) s.prev = s.next = &s;
    }

    // O(1) Timer insertion into circular bucket
    void schedule(TimerNode* node, uint64_t expireMs) noexcept {
        node->cancel();
        node->expireMs = expireMs;
        size_t slot = (expireMs >> tickShift) & (W - 1);
        TimerNode* head = &sentinels[slot];
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
        node->active = true;
    }
};