How Kafka’s Hierarchical Timing Wheel Optimizes Task Scheduling

Overview

In many development scenarios we need to trigger actions at fixed intervals or after a delay, such as sending emails, generating reports, or decoupling asynchronous work. Traditional tools use ready‑made frameworks, but the time‑wheel algorithm provides a highly efficient model that binds all scheduled tasks to a single scheduler for triggering and management.

Basic Principle

The time wheel consists of a circular belt where each slot represents an equal time slice. A pointer rotates around the belt at a constant speed. When the pointer reaches a slot, the tasks stored in that slot are executed, removed, or new tasks are added.

Simple Timing Wheel

The simple time wheel avoids scanning all pending tasks; it only checks the current time slot and executes all tasks in that slot. This greatly improves traversal efficiency and reduces time complexity. However, higher precision requires more slots, increasing memory usage and traversal cost, especially when tasks reside in later slots.

Timing Wheel with Round

To solve the simple wheel’s overflow problem, each task carries a round counter. The round value equals executionPeriod / precision. When the pointer reaches the task’s slot, the round is decremented; if it reaches zero the task is executed (or re‑queued for periodic tasks). This allows the wheel to maintain second‑level precision while handling longer intervals.

Hierarchical Timing Wheel

A hierarchical wheel adds multiple layers (e.g., seconds, minutes, hours). A task first enters the lowest‑level wheel; if its execution time exceeds the wheel’s range, it overflows to the next level. For example, a task scheduled for 12:30:30 is first placed in the seconds wheel, then propagated to the minutes wheel at 30 minutes, and finally to the hours wheel at 12 o’clock.

Advantages

Improved thread‑polling efficiency: each poll processes only non‑empty slots.

Low memory consumption: higher precision does not require a linear increase in slots.

Time Wheel in Kafka

Kafka uses a custom hierarchical timing wheel for delayed message delivery and consumption. It does not rely on JDK Timer or DelayQueue, which use a priority heap with O(log n) insertion and removal.

Kafka TimingWheel Implementation

@nonthreadsafe
private[timer] class TimingWheel(tickMs: Long, wheelSize: Int, startMs: Long,
    taskCounter: AtomicInteger, queue: DelayQueue[TimerTaskList]) {
  // interval = tickMs * wheelSize, the span of this wheel level
  private[this] val interval = tickMs * wheelSize
  private[this] val buckets = Array.tabulate[TimerTaskList](wheelSize) { _ => new TimerTaskList(taskCounter) }
  private[this] var currentTime = startMs - (startMs % tickMs)
  @volatile private[this] var overflowWheel: TimingWheel = null
}

Key parameters:

tickMs : precision of each slot.

wheelSize : number of slots in the wheel.

interval : total time span of the wheel (tickMs × wheelSize).

startMs : the start time of this wheel level.

currentTime : the wheel’s current time, always a multiple of tickMs.

Adding Tasks

// Add a task
def add(timerTaskEntry: TimerTaskEntry): Boolean = {
  val expiration = timerTaskEntry.expirationMs
  if (timerTaskEntry.cancelled) {
    false
  } else if (expiration < currentTime + tickMs) {
    false // already expired
  } else if (expiration < currentTime + interval) {
    val virtualId = expiration / tickMs
    val bucket = buckets((virtualId % wheelSize.toLong).toInt)
    bucket.add(timerTaskEntry)
    if (bucket.setExpiration(virtualId * tickMs)) {
      queue.offer(bucket)
    }
    true
  } else {
    if (overflowWheel == null) addOverflowWheel()
    overflowWheel.add(timerTaskEntry)
  }
}

private[this] def addOverflowWheel(): Unit = {
  synchronized {
    if (overflowWheel == null) {
      overflowWheel = new TimingWheel(
        tickMs = interval,
        wheelSize = wheelSize,
        startMs = currentTime,
        taskCounter = taskCounter,
        queue = queue
      )
    }
  }
}

SystemTimer – Driving the Wheel

trait Timer {
  def add(timerTask: TimerTask): Unit
  def advanceClock(timeoutMs: Long): Boolean
  def size: Int
  def shutdown(): Unit
}

@threadsafe
class SystemTimer(executorName: String,
                tickMs: Long = 1,
                wheelSize: Int = 20,
                startMs: Long = Time.SYSTEM.hiResClockMs) extends Timer {
  private[this] val taskExecutor = Executors.newFixedThreadPool(1,
    (runnable: Runnable) => KafkaThread.nonDaemon("executor-" + executorName, runnable))
  private[this] val delayQueue = new DelayQueue[TimerTaskList]()
  private[this] val taskCounter = new AtomicInteger(0)
  private[this] val timingWheel = new TimingWheel(tickMs, wheelSize, startMs, taskCounter, delayQueue)

  def advanceClock(timeoutMs: Long): Boolean = {
    var bucket = delayQueue.poll(timeoutMs, TimeUnit.MILLISECONDS)
    if (bucket != null) {
      writeLock.lock()
      try {
        while (bucket != null) {
          timingWheel.advanceClock(bucket.getExpiration())
          bucket.flush(reinsert)
          bucket = delayQueue.poll()
        }
      } finally {
        writeLock.unlock()
      }
      true
    } else {
      false
    }
  }

  private[this] val reinsert = (timerTaskEntry: TimerTaskEntry) => addTimerTaskEntry(timerTaskEntry)
  private def addTimerTaskEntry(timerTaskEntry: TimerTaskEntry): Unit = {
    if (!timingWheel.add(timerTaskEntry)) {
      if (!timerTaskEntry.cancelled) taskExecutor.submit(timerTaskEntry.timerTask)
    }
  }
}

Example Walkthrough

With tickMs = 1 ms and wheelSize = 20, the interval is 20 ms. A task delayed by 4 ms is placed in slot 4; when the pointer reaches slot 4 the task runs. A task delayed by 8 ms goes to slot 12. Longer delays overflow to higher‑level wheels, which handle larger time spans without increasing memory.

When a 300 ms task arrives, it overflows to the second level (slot 15). A 450 ms task overflows to the third level (slot 0, covering 400‑800 ms). As time advances, tasks are gradually re‑inserted into lower‑level wheels until they reach the execution slot.

Thus, Kafka’s hierarchical timing wheel efficiently manages delayed tasks with minimal memory overhead and constant‑time slot traversal.