Image by: goffredo crollalanza

Table of Contents

• Introduction
• Why Do We Need Hashed Time Wheel?
• How Does It Work?
  • Example
• Implementation
• Conclusion

Introduction

Efficient timer management is critical in networking, scheduling, and distributed systems.
Traditional approaches often become slow when there are many timers.
The Hashed Time Wheel (HTW) algorithm solves this by providing a simple yet efficient way to manage thousands of timers.

Why Do We Need Hashed Time Wheel?

• Managing timers with a priority queue (min-heap) can be O(log n) for insertion and deletion.
• In high-performance systems (like Netty or Kafka), we need something closer to O(1).
• Time wheel algorithms give us this improvement by trading precision for efficiency.

How Does It Work?

Imagine a clock:

• Each slot in the wheel represents a small time interval (tick).
• Timers are placed into slots based on their expiration time.
• When the clock ticks, timers in the current slot are checked and executed.

If the timer does not fit into the first round, it waits for multiple rotations.

Example

Suppose:

• Tick = 1 second
• Wheel size = 8 slots

If a timer is set for 10 seconds:

• It goes to slot (current + 10) % 8 = 2.
• But it also remembers it needs 1 full rotation before execution.

The diagram below shows how different timers are positioned in the wheel. Each timer is placed in a specific slot based on its delay, and longer timers have a “rounds” counter indicating how many full wheel rotations they must wait before execution. The current pointer moves clockwise with each tick.

graph TD
    subgraph "Time Wheel (8 slots, tick=1s)"
        A[Slot 0
Current] -.-> B[Slot 1]
        B --> C[Slot 2
Timer 4
rounds: 1]
        C --> D[Slot 3
Timer 1
Timer 2
rounds: 0]
        D --> E[Slot 4]
        E --> F[Slot 5]
        F --> G[Slot 6]
        G --> H[Slot 7]
        H -.-> A
    end
    
    subgraph "Example Timers"
        T1["Timer 1: 3s
slot = (0+3) % 8 = 3
rounds = 0"]
        T2["Timer 2: 3s
slot = (0+3) % 8 = 3
rounds = 0"]
        T3["Timer 3: 8s
slot = (0+8) % 8 = 0
rounds = 1"]
        T4["Timer 4: 10s
slot = (0+10) % 8 = 2
rounds = 1"]
    end
    
    T1 --> D
    T2 --> D
    T3 --> A
    T4 --> C
    
    style A fill:#e1f5fe
    style D fill:#fff3e0
    style C fill:#fff3e0

Implementation

type TimerCallback = () => void;

class Timer {
  rounds: number;
  callback: TimerCallback;

  constructor(rounds: number, callback: TimerCallback) {
    this.rounds = rounds;
    this.callback = callback;
  }
}

class HashedTimeWheel {
  private slots: Timer[][];
  private currentSlot: number = 0;
  private intervalId?: NodeJS.Timeout;

  constructor(
    private tickDuration: number, // in ms
    private wheelSize: number
  ) {
    this.slots = Array.from({ length: wheelSize }, () => []);
  }

  addTimer(delay: number, callback: TimerCallback) {
    const ticks = Math.floor(delay / this.tickDuration);
    const slot = (this.currentSlot + ticks) % this.wheelSize;
    const rounds = Math.floor(ticks / this.wheelSize);

    if (!this.slots[slot]) {
      this.slots[slot] = [];
    }
    this.slots[slot].push(new Timer(rounds, callback));
  }

  start() {
    if (this.intervalId) return;

    this.intervalId = setInterval(() => {
      console.log("tick", this.currentSlot);
      const timers = this.slots[this.currentSlot] ?? [];

      for (let i = 0; i < timers.length; i++) {
        const timer = timers[i];
        if (timer?.rounds === 0) {
          timer?.callback();
          timers.splice(i, 1);
          i--;
        } else {
          timer!.rounds--;
        }
      }

      this.currentSlot = (this.currentSlot + 1) % this.wheelSize;
    }, this.tickDuration);
  }

  stop() {
    if (this.intervalId) clearInterval(this.intervalId);
  }
}

// Example usage
const wheel = new HashedTimeWheel(1000, 8); // tick = 1s, 8 slots
wheel.start();

wheel.addTimer(3000, () => console.log("Timer 1 fired after 3s"));
wheel.addTimer(3000, () => console.log("Timer 2 fired after 3s"));

wheel.addTimer(8000, () => console.log("Timer 3 fired after 8s"));

wheel.addTimer(10000, () => console.log("Timer 4 fired after 10s"));

wheel.addTimer(16000, () => console.log("Timer 5 fired after 16s"));

We implemented a simple Hashed Time Wheel with 8 slots and a tick duration of 1 second. Timers are added with different delays, and the wheel executes them when their time comes.

Output

bun run ./index
tick 0
tick 1
tick 2
tick 3
Timer 1 fired after 3s
Timer 2 fired after 3s
tick 4
tick 5
tick 6
tick 7
tick 0
Timer 3 fired after 8s
tick 1
tick 2
Timer 4 fired after 10s
tick 3
tick 4
tick 5
tick 6
tick 7
tick 0
Timer 5 fired after 16s
tick 1
tick 2
tick 3

Conclusion

Hashed Time Wheel is a simple but powerful algorithm. It makes timer management scalable, which is why it’s widely used in real-world systems. If you’re building anything that needs to handle thousands of timers, this algorithm is worth learning.