Part 5 · 1 chapters · ~8 min

Schedulers, Priority Queues and Timing Wheels

Priority queues with heaps for job scheduling, delayed jobs with sorted sets, fair scheduling across tenants (weighted round robin, deficit round robin), timing wheels for millions of timeouts, hierarchical wheels, and where each appears (kernels, Netty, Kafka, Tokio, job queues).

Timers and fairness

code

// weighted fair dequeue across tenants (deficit round robin): no tenant starves the others
for (;;) for (const t of tenants) {
  t.deficit += t.quantum;                                       // bigger plans get bigger quanta
  while (t.queue.length && t.queue[0].cost <= t.deficit) { const job = t.queue.shift(); t.deficit -= job.cost; run(job); }
  if (!t.queue.length) t.deficit = 0;
}

A HASHED TIMING WHEEL

O(1) timer insert and expiry for millions of timeouts

swipe the figure sideways, or tap expand for full screen

1/4

the problem

A server with a million connections has a million idle timeouts, most cancelled before they fire. A heap makes insert and cancel O(log n); a sorted list O(n).

millions of timers, mostly cancelledheaps cost O(log n) each