Anatomy of a Timing Wheel: Design Decisions Behind a Scheduler in C Link to heading

Why C? Link to heading

I wanted to actually learn C, not just read about it. Toy katas don’t force you to confront the things that matter — manual memory management, undefined behavior, and the discipline of running everything under ASan/UBSan/valgrind because the compiler alone won’t save you. So I picked a real, self-contained project instead: cog, a hierarchical timing wheel.

There’s also a more practical reason underneath the “just for fun” one. C is the language that gives you control — direct memory layout, no hidden allocations, no runtime deciding things on your behalf — and that same control is what most of the software I actually use day to day is built out of. The JVM is a C++ program. CPython’s interpreter is a C program. Understanding what a garbage collector actually has to do, why a particular allocation pattern causes GC pressure, or what a “stack” really is underneath a language that never lets you see one, means understanding the layer those runtimes are themselves written in. You can use a JVM-based service for years without ever needing this — plenty of people do — but I wanted to be able to reason about why it behaves the way it does, not just which knobs to turn when it doesn’t.

Why a timing wheel? Link to heading

The choice wasn’t abstract for me. I once worked on the scheduling engine behind a monitoring check execution system — north of 500,000 concurrently active checks at any given moment — and it went through almost exactly the progression this post’s first section walks through. Its original incarnation was in Elixir, where every check was simply its own BEAM process, parked asleep until its next run: the “naive” one-process-per-timer approach, just with the BEAM VM’s scheduler managing it instead of the OS or a userland runtime. And it worked, because the BEAM is more or less built for exactly this — brute-forcing “one lightweight process per timer” is a large part of what the BEAM is for. It worked, that is, up to a point: somewhere around 200,000 concurrently scheduled checks, it started falling over, and that’s what forced the question of what to do about it. Rather than just fix the scaling problem in place, we used the moment to also address something separate that had been sitting on the org’s wishlist for a while: consolidating the technology stack. The rewrite landed on Python — the team’s strongest language, and, practically speaking, about the only option the organization allowed alongside the JVM — which meant that brute-force option simply wasn’t on the table anymore: Python has no equivalent of cheaply parking half a million concurrent, preemptively-scheduled processes. Porting the “one thing per check” model as-is wasn’t viable, which is exactly what forced the two steps this post covers, in order: first a heap-based scheduler, then ultimately, a timing wheel. The heap-to-wheel switch alone is what let us shrink the fleet running it from hundreds of instances down to a few dozen — O(log n) heap operations, at that scale and in Python, were simply the more expensive way to do it. The minimum check interval was 60 seconds, so the wheel ran on a 1-second tick, and we added jitter so checks didn’t all pile into the same handful of buckets every 60 ticks — an orthogonal fix, on top of the heap-to-wheel switch, for keeping load spread evenly across the wheel itself. The service also had an HTTP API, cluster consensus, a rule evaluation engine, and a notification pipeline sitting around it, but the scheduler was still the heart of the system: it was the one stateful component, and it dictated the pace everything else ran at.

Worth sitting with for a second: a runtime built from the ground up for cheap, massive concurrency, brute-forced, topped out around 200,000. A runtime with none of that going for it, paired with the right data structure, comfortably handled 500,000 on a fraction of the fleet. The data structure mattered more than the language’s built-in concurrency model did.

This post isn’t really about the code — it’s about the decisions behind it. A timing wheel is a small enough data structure that you can hold the whole design in your head, but big enough that almost every piece of it involves a real tradeoff. I want to walk through the ones that mattered.

What problem is a timing wheel even solving Link to heading

The laziest way to schedule “run this in N ticks” is to just spawn a thread, a goroutine, a coroutine — whatever your runtime offers — and have it sleep for N ticks before running the callback. It’s the option that requires no data structure at all, and at small scale it’s genuinely fine. It stops being fine as the number of pending, not-yet-fired timers grows:

  • Every pending timer now costs whatever your runtime charges per thread/goroutine/coroutine — a few KB minimum for a lean green thread, far more for an OS thread with its default stack — multiplied by however many timers are in flight at once. A wheel’s per-timer cost is the size of a callback pointer, a data pointer, and a delay: tens of bytes, not kilobytes.
  • Arming a timer this way means a scheduler decision (and for OS threads, a syscall) per timer. Advancing a wheel by one tick is one pass over whichever buckets are due — the scheduling cost is paid once per tick, not once per timer. At real scale this isn’t just a constant-factor annoyance: the scheduler or event loop itself becomes the bottleneck, and the CPU ends up spending most of its time juggling tasks — context-switching between them, deciding which runs next — rather than doing the work those tasks actually exist for.
  • Cancelling early needs its own signaling mechanism (a channel, a context, a flag the sleeping thread polls) bolted on after the fact. In a bucket-based wheel, cancelling should just mean marking a timer in its bucket as cancelled — though it turns out that’s not nearly as simple as it sounds; see “Whether to support cancellation at all” in Open Questions below.

This is exactly why almost none of the runtimes that need to manage large numbers of timers actually do “one thread/goroutine per timer” internally — the Linux kernel’s own timers, Go’s runtime, Netty, Tokio all implement some form of timing wheel or timer heap under the hood, for the same reason outlined below. Reaching for a real data structure here isn’t over- engineering; it’s what the alternative disintegrates into once the timer count actually gets large.

The other standard answer is a priority queue (a binary heap keyed by fire time): O(log n) to schedule, O(log n) to pop the next thing due. That’s a perfectly reasonable general-purpose choice, but it’s not the cheapest one if your delays are bounded and your “clock” advances one discrete tick at a time (a game loop, a simulation step, a network protocol’s retransmit timer — anything where “time” is ticks, not wall clock). A heap also isn’t free of its own operational cost: something has to drive it — a main loop that peeks the minimum, figures out how long until it’s due, and waits. Get that waiting step wrong (or just don’t bother implementing it properly) and that loop degrades into a busy spin, burning CPU checking “is it time yet?” as fast as it possibly can. Done right, it means explicitly sleeping until the next known deadline — but “done right” still isn’t the end of it: if a new timer gets scheduled while the loop is asleep, and that new timer is due earlier than whatever the loop is currently sleeping until, it needs a way to interrupt that sleep and re-evaluate. Skip that, and the new timer simply lags — it won’t fire until the loop wakes up for the deadline it already knew about, however much later that turns out to be. None of this is needed for a tick-driven wheel, because something external is already going to call tick() on its own fixed schedule, whether anything is due or not — there’s no “sleep until the next deadline” to get right, or wrong, in the first place.

A timing wheel trades the log n for a bucket array: if you know the maximum delay in advance, you can allocate one bucket per possible tick offset, drop each timer straight into the bucket matching its target tick, and advance a cursor once per tick. Both schedule and tick become O(1) (amortized, ignoring how many timers land in the same bucket — more on that later). The catch is memory: a flat array needs one bucket per supported tick, so a wheel that needs to support delays of, say, a million ticks needs a million buckets sitting there, mostly empty.

Why hierarchical: trading buckets for cascading Link to heading

The standard fix is to stop trying to cover every possible delay with one flat array, and instead stack multiple rings of a fixed, small size (I used 64 buckets per ring, base-64 throughout), each ring covering a coarser range of ticks than the one below it:

  • Ring 0: resolution 1 tick, covers delays [1, 64)
  • Ring 1: resolution 64 ticks, covers delays [64, 4096)
  • Ring 2: resolution 4096 ticks, covers delays [4096, 262144)
  • …and so on, as many rings as the wheel’s configured range needs.

A timer with a large delay lands directly in the coarse ring that matches its magnitude — not in a specific tick, but in a specific 64-tick window. As the coarse ring’s cursor reaches that window, the timer gets cascaded down into a finer ring, now placed at the exact tick within that window, and so on until it lands at ring 0’s resolution and actually fires.

This buys you a wheel whose memory is O(rings × 64) instead of O(max_delay) — logarithmic in the range you want to support, at the cost of a timer potentially getting rescheduled a few times (once per ring it cascades through) before it fires. In practice that’s a handful of extra O(1) operations over the timer’s lifetime, which is a good trade for turning “memory proportional to your longest delay” into “memory proportional to log of your longest delay.”

Getting “fires on tick N” right is harder than it looks Link to heading

Once you have cascading, an innocuous question turns out to be surprisingly easy to get wrong: if I schedule with delay = N, does it fire on the N-th call to tick(), or the (N+1)-th?

I initially had the off-by-one (N+1) baked in — cheap to live with, but unintuitive: scheduling delay = 1 and expecting it to fire on the very next tick, only to see it fire one tick later, is the kind of surprise that makes an API annoying to use correctly. Fixing “fires on tick N” turned out to interact with something non-obvious: the direction in which a cascaded timer’s target slot is computed relative to the ring’s cursor. Get the adjustment right for a direct placement (no cascade) and you can accidentally break it for a cascaded one — a timer that gets rescheduled into a ring that’s also due to advance on the exact same tick call can end up firing a full tick early, because the newly-computed slot collides with the slot the ring is about to read in that same pass.

Concretely: cog_schedule(cog, cb, data, 65) — a delay that lands in ring 1 and cascades a 1-tick remainder down into ring 0 — fired on tick 64 instead of 65 once I’d made the “fires on tick N” change naively. A larger, multi-level cascade (delay = 65535, passing through two rings on its way down) fired on tick 65470 — 65 ticks early, the error compounding once per level. Both are silent: nothing crashes, the timer just runs early, which is exactly the kind of bug that survives casual testing and only shows up once you check exact fire ticks across enough boundary values.

The fix that held up under an exhaustive boundary probe: apply the “fires on tick N, not N+1” adjustment exactly once, at the public API boundary — not inside the internal function that both the public cog_schedule and the cascade logic in cog_tick share. Concretely, cog.h has a static internal cog_schedule_at that does the real ring-fitting/insert work with no adjustment, and the public cog_schedule is a thin wrapper that subtracts one before calling it. The cascade path inside cog_tick calls cog_schedule_at directly, bypassing the adjustment, because it’s not a new request from a caller — it’s a continuation of one already in flight.

The broader lesson: a “make this off-by-one nicer” change that looks purely cosmetic can quietly depend on an invariant somewhere else in the structure. The safety net here wasn’t careful reasoning alone — it was an exhaustive probe across every ring boundary, run under ASan/UBSan, that caught the cases hand-derivation missed.

Storing timers within a bucket: the part that actually needed fixing Link to heading

Each bucket holds however many timers land in it — could be zero, could be thousands if a lot of things happen to be scheduled at the same relative offset. My first version stored a bucket as a classic doubly linked list, one malloc per timer:

typedef struct cog_node {
  struct cog_node *prev;
  struct cog_node *next;
  void (*cb)(void *);
  void *data;
  uint64_t delay;
} cog_node_t;

Inserting meant walking from the bucket’s head to find the tail, because nothing tracked it:

cog_node_t *bucket = ring->buckets[slot];
while (bucket && bucket->next != NULL) {
  bucket = bucket->next;
}
// ... append here

That’s O(n) per insert, n being however many timers already share the bucket — invisible at small scale, and exactly the kind of thing you only notice once you measure it under load. I benchmarked two things specifically: the cost of one cog_schedule call as a function of how crowded its target bucket already was, and the cost of one cog_tick call per timer processed, with n deliberately pushed up to a million — a much worse single-bucket pileup than the jitter I mentioned earlier would ever let happen in a well-behaved system, but the point of this benchmark is to find the worst case, not to model realistic occupancy. Results, linked-list version:

mode,n,ns_per_op
schedule,100,311.0
schedule,1000,1313.0
schedule,10000,11742.0
schedule,100000,112212.0
schedule,1000000,3534963.0
tick,100,11.22
tick,1000,10.14
tick,10000,12.23
tick,100000,11.38
tick,1000000,11.97

tick is flat — cog_tick walks a bucket exactly once regardless of n, so its per-timer cost really is O(1). schedule is not: it goes from 311ns at n=100 to 3.5 milliseconds at n=1,000,000 — the tail-walk cost, showing up exactly where you’d expect.

The fix wasn’t “stop using a linked list” — a bucket still needs to be an append-friendly, variable-length collection. The actual problem was much more mundane than “linked lists don’t scale”: I was walking from head to tail to find the append point, on every single insert, when the obvious fix was staring at me the whole time — track the tail, and append there. Just doing that, on the exact same node-per-timer list, already turns insertion into O(1): no walk, just a pointer update. It wasn’t a data structure problem; it was that I hadn’t noticed the obvious thing.

I went a step further than that minimal fix, though, and changed the storage itself: each bucket became a linked list of fixed-capacity blocks (64 slots each, a deliberately simple starting point — it matches the ring’s own bucket count, so there’s no new number to justify), each one a flat array. That part wasn’t strictly required to fix the O(n) insert — tracking a tail pointer on the original list would have done that alone. The block layout is an independent bet, made for cog_tick: iterating a packed array during a tick is far more cache-friendly than chasing ->next through individually malloc’d nodes, even though both are already O(1) per node algorithmically.

typedef struct {
  void (*cb)(void *);
  void *data;
  uint64_t delay;
} cog_timer_t;

typedef struct cog_block {
  struct cog_block *prev;
  struct cog_block *next;
  uint64_t size;
  uint64_t capacity;
  cog_timer_t *timers;
} cog_block_t;

The bucket array now stores a pointer straight to the tail block, not the head, so appending is just:

cog_block_t *tail = ring->buckets[slot];
if (tail->size == tail->capacity) {
  // allocate a new block, link it in, tail = new block
}
tail->timers[tail->size++] = timer;

No walk — O(1) amortized, paying for one malloc per 64 inserts instead of one per insert. Same benchmarks, chunked-list version:

mode,n,ns_per_op
schedule,100,90.0
schedule,1000,30.0
schedule,10000,30.0
schedule,100000,40.0
schedule,1000000,80.0
tick,100,2.61
tick,1000,1.64
tick,10000,2.51
tick,100000,2.25
tick,1000000,2.84

schedule goes from unbounded growth to flat, regardless of bucket size — about 44,000x cheaper at a million timers sharing one bucket. The part I didn’t originally set out to measure: tick also got roughly 4x faster, even though its algorithmic complexity didn’t change at all — O(1) per node before, O(1) per node after. Walking a packed array beats chasing ->next through individually malloc’d nodes purely as a function of memory layout, with no change in big-O anywhere in sight.

Time complexity is still the right first tool to reach for — it’s what told me schedule was the real problem in the first place, not tick. But it only describes how a cost scales, not how large it actually is on the hardware you run on. Two structures with the identical O(1) bound can differ by 4x because one of them is friendly to the CPU’s cache hierarchy and the other spends its time on cache misses chasing pointers around the heap. Complexity analysis gets you to the right shape of the problem; it doesn’t get you all the way to the number on the clock.

What happens when a bucket shrinks back down Link to heading

Storing timers in growable blocks raises a question a plain linked list never had: once a bucket has grown to several blocks because it briefly held a lot of timers, what happens to that memory after cog_tick fires everything and the bucket is empty again?

This turned out to have a clean answer specific to how a timing wheel bucket behaves: a bucket is always fully drained the moment cog_tick visits it — every timer in it either fires or gets cascaded elsewhere, never partially. That guarantee rules out the usual headaches of freeing while iterating (no risk of freeing a block that’s still partially in use), so after a drain I keep exactly one block resident and free the rest. It’s a middle ground: a bucket that repeatedly sees similar load doesn’t pay for a fresh allocation every cycle, but a one-off burst doesn’t permanently inflate that bucket’s footprint either.

The alternative I didn’t take — freeing every block down to zero after each drain, and letting the next cog_schedule lazily allocate from scratch — is arguably a fairer comparison against the old linked-list’s “memory exactly tracks live timers” behavior. I haven’t benchmarked the two against each other yet; it’s on the list.

How this compares to the Linux kernel’s timer wheel Link to heading

It’s worth being precise about how cog relates to a “real” timer wheel, so I went and read Reinventing the timer wheel on LWN, which covers a proposed redesign of the Linux kernel’s own timer wheel by Thomas Gleixner. It’s a useful mirror to hold cog up against, because the kernel’s classic design and its proposed replacement sit on opposite sides of a tradeoff cog also had to make.

The classic kernel wheel uses the same cascading mechanism described above (256 slots per level, indexed by the low 8 bits of jiffies, versus cog’s 64 slots per ring — a different radix, same idea). And the article is blunt about the cost of that mechanism: cascading is “expensive,” its cost is “to a first approximation, unpredictable,” it’s “not particularly cache-friendly,” and finding the next timer due at all requires searching through the wheel. cog has this same cascading cost today.

The proposed redesign removes cascading entirely. Instead of ever moving a timer between levels, it’s expired “in place” at whatever level it was first inserted into — accepting reduced precision as the price (a timeout requested for 36 jiffies might fire at 40 instead). The justification is specific to the kernel’s workload: almost all kernel timers are cancelled before they’d ever fire (a socket read completes before its timeout does, a retransmit succeeds before the retry timer goes off), so paying a cascading cost for precision that’s usually thrown away anyway is a bad trade. Loosening the precision on the rare timer that does fire is cheap by comparison.

cog sits on the other side of that same tradeoff, and for a reason worth stating plainly: getting cog to fire on the exact tick it was asked to — not one tick early, not one late — was one of the harder pieces of this whole project (see the “fires on tick N” section above). I optimized for precision and accepted cascading’s cost to get it. The kernel’s newer design makes the opposite bet, and it’s a bet cog currently can’t make even if it wanted to, for two reasons:

  • cog has no cancellation. There’s no cog_cancel — a scheduled timer either fires or sits there until the whole wheel is destroyed. The kernel’s core argument for tolerating imprecision (“it’s almost always cancelled anyway”) simply doesn’t apply to a library that can’t cancel anything.
  • cog doesn’t know how to skip ahead to the next non-empty tick. A kernel needs to answer “how long can I safely sleep before the next timer is due” to avoid pointless wakeups — which is exactly the “search through the wheel” cost the article complains about, and part of what motivates avoiding cascading in the first place. cog_tick() just assumes something external calls it once per unit of time, unconditionally, whether or not anything is due; it never needs to find out how far it could jump ahead, because it isn’t the one deciding when to advance.

One more, unrelated difference worth being upfront about: cog isn’t thread-safe, and doesn’t try to be. The kernel’s timer wheel has to be — it’s touched from interrupt context, from any CPU, at any time. cog assumes a single producer: one thread calls cog_schedule/cog_tick, full stop. Callbacks are free to hand work off to other threads if the caller wants that, but the wheel itself never needs to reason about concurrent access, because nothing about its design asks it to.

None of this makes cog’s choices wrong — they’re just choices matched to a different assumption about the workload (no cancellation, an external, unconditional tick driver, a single thread driving it) than the one the kernel is optimizing for.

Open questions Link to heading

Roughly ordered from “changes the shape of the API” down to “tuning knob I haven’t revisited”:

  • Whether to support cancellation at all. This is the big one, and it’s the gap the Linux kernel comparison keeps circling back to: there’s no cog_cancel. Adding one isn’t just a new function — it means a bucket’s block can no longer be a pure append-only array, because “remove this one entry out of the middle of a block” isn’t free anymore. Tombstoning a slot (mark it dead, skip it on fire, reclaim the space lazily) keeps the append-only property but adds a check on every fire; compacting on cancel keeps the block dense but makes cancellation itself O(block size).

    There’s a problem underneath that one, too: cog_schedule would have to start returning something the caller can hand back to cog_cancel later, and that something needs to still make sense by the time it’s used. A generational handle — (slot, generation), the same pattern behind entity IDs in most ECS libraries, and a natural fit if cog_tick ever ends up returning entity IDs instead of calling back — is the cheap option at fire/cancel time. But it only works if the thing the handle points into has a stable identity, and blocks in this design don’t: they get free()’d once a bucket drains back down to one. A handle holding a raw pointer to a block that’s since been freed and reused for something else isn’t a safe “was this already cancelled?” check anymore — it’s a use-after-free. Making that safe means blocks themselves need a stable identity (an index into a pool, not a raw pointer) and their own generation counter, on top of the per-slot one. The alternative — a plain incrementing ID plus an external hash map from ID to location — sidesteps the block-lifecycle problem entirely, at the cost of exactly the per-timer memory overhead this post spent a whole section trying to shrink. I don’t know yet which is worth it, or whether “no cancellation” is a fine constraint to just keep for the kind of caller this is meant for.

  • Whether cog_tick should call back at all. Right now a fired timer means cog invokes your function pointer directly, synchronously, from inside cog_tick. An alternative is to not call anything — just hand the caller back whatever fired this tick (or, for a caller using an ECS, the entity ID it was scheduled against) and let them decide what to do with it. That fits a data-oriented/ECS-style caller much better: no function pointer indirection, no callback running on the wheel’s terms, and the caller can batch-process everything due this tick alongside its other systems instead of reacting to a stream of individual calls. I went with direct callback invocation because, as far as I know, that’s the canonical form of a timing wheel — but “canonical” isn’t the same as “right for every caller,” and I haven’t actually weighed it against the alternative.

  • Whether to support custom allocators. Every block and every timer entry goes through plain malloc/free today. Letting a caller plug in their own allocator — an arena, in particular — would fit this structure well: blocks are fixed-size and already the unit of allocation, so an arena that hands out same-sized chunks is a natural match, and a caller who knows their workload’s shape could sidestep malloc entirely. I haven’t decided whether that’s worth the API surface it adds.

  • Free-to-zero vs. keep-one-block after a drain — I picked the latter on reasoning, not measurement.

  • Memory overhead per timer, measured rather than estimated. A single old-style node was 40 bytes, all of it live data. A chunked-list timer entry is 24 bytes, plus a 40-byte block header amortized over up to 64 timers — a full block works out to about 24.6 bytes/timer on paper, but I haven’t built the benchmark to confirm it under a realistic allocation pattern.

  • Whether 64 is actually a good block size, or just a comfortable default matching BUCKETS_SIZE that I haven’t had a reason to revisit.

Code is on GitHub if you want to poke at it.