Location>code7788 >text

Time wheel depth analysis: principle, source code and application scenarios

Popularity：830 ℃/2025-02-25 15:00:30

Kafka time wheel depth analysis: principle, source code and application scenarios

Table of contents

  1. Introduction: Challenges of timing task processing
  2. Analysis of the core principle of time wheel
    • 2.1 Basic concepts and data structures
    • 2.2 Level time round design
  3. Source code analysis: Kafka time round implementation
    • 3.1 Core Class Structure Analysis
    • 3.2 Task addition and execution process
    • 3.3 Time round advancement mechanism
    • 3.4 The key role of DelayQueue
  4. Typical application scenarios
  5. Summary and performance comparison

1. Introduction: Challenges of timing task processing

In distributed systems, timing task management (such as delayed messages and heartbeat detection) needs to meet two core needs:High precisionandHigh throughput. Traditional solutions such as priority queues (O(log n) time complexity) have dramatically declined in the million-level task scenario. Kafka adoptsTiming WheelThe algorithm realizes O(1) time complexity, and a single machine supports millions of timed tasks. The time wheel achieves a qualitative performance breakthrough in timing task processing through ring queues and hash ideas.

2. Analysis of the core principles of the time wheel

2.1 Basic concepts and data structures

  • Data structure disassembly：

    1. Time slot (Bucket)：
      • Each slot corresponds to a time interval (tickMs, such as 1ms)
      • useTwo-way link list（TimerTaskList) Management tasks in the slot
      • Example: IftickMs=1ms，wheelSize=20, then the total span of the time roundinterval=20ms
    2. Pointer advance logic：
      • Initial time pointercurrentTimePoint to the current slot start time
      • Every time you advance,currentTimeaccording totickMsIncrement
      • Alignment mechanism: Pointer time is alwaystickMsinteger multiples ofcurrentTime = (startMs / tickMs) * tickMs）
    3. Task hash positioning：
      • Calculate the difference between the task expiration time and the pointer:expirationMs - currentTime
      • Determine the slot index:(expirationMs / tickMs) % wheelSize
      • Hash conflict handling: Tasks in the same slot are processed in the order of linked list

    Summarize: Time round passesHash bucket + pointer slidingImplement batch processing of tasks, and the time complexity is stable to O(1).

2.2 Level time round design

Kafka usesMulti-level time round(Similar to the hour/minute hand collaboration):

  1. Bottom wheel: high precision small range (such as second level)
  2. Upper wheel: low precision and large range (such as minute level)
  3. Task downgrade: Resubmit to the lower level after the upper level turn expires

Hierarchical collaboration process：

  1. Example of hierarchical parameters：
    • Level 1 (bottom level):tickMs=1ms, wheelSize=20, interval=20ms
    • Level 2:tickMs=20ms, wheelSize=60, interval=1200ms
    • Level 3:tickMs=1200ms, wheelSize=60, interval=72000ms
  2. Overflow Handling：
    • When the task delay exceeds the current time roundintervalWhen submitting to the upper time round
    • The slots of the upper time wheel represent the full cycle of the lower time wheel
    • Example: Each slot in layer 2 (20ms) corresponds to the full 20ms cycle of layer 1
  3. Pointer linkage mechanism：
    • When the upper time wheel pointer advances, the tasks in its slot will recalculate the hash, which may be downgraded to the underlying time wheel.
# Task Add Process Pseudo Code
 void add_task(task):
     if < current_wheel.interval:
         Put into the slot corresponding to the current time wheel
     else:
         Recursively submitting to the upper time round

Summarize: The hierarchical time round passesTime range is enlarged layer by layerandTask recursive downgrade, realizes unified management of delay tasks from milliseconds to hourly levels, and hierarchical design expands the time range while maintaining accuracy, similar to the multi-level time hierarchy idea of ​​CPU cache.

3. Source code analysis: Kafka time round implementation

3.1 Core Class Structure Analysis

// Delay task
 class TimerTask {
     private final long delayMs; //Delay time
     private final Runnable task; //Delay task
     protected TimerTaskList timerTaskList; //Time slot
     protected TimerTask next; //Next node
     protected TimerTask prev; //Previous node
 }
// Task queue, task bidirectional link table
 class TimerTaskList implements Delayed {
 private final AtomicLong expire;// Expiry time
 private final TimerTask root; //root node
 public TimerTaskList(){
 expire = new AtomicLong(-1L);
 root = new TimerTask( null,-1L);
 = root;
 = root;
 }
 //Add a new task, add the task to the head of the two-way linked list
 public void addTask(TimerTask timerTask) {
 synchronized (this) {
 if ( == null) {
 = this;
 TimerTask tail = ;
 = root;
 = tail;
 = timerTask;
 = timerTask;
 }
 }
 }

     //Remove task
 public void removeTask(TimerTask timerTask) {
 synchronized (this) {
 if (()) {
 = ;
 = ;
 = null;
 = null;
 = null;
 }
 }
 }
 }
// Key parameters of Kafka time round class
 class TimingWheel {
     private long tickMs; // Time slot accuracy (such as 1ms)
     private int wheelSize; // Total number of time slots
     private long interval; // Total time range = tickMs * wheelSize
     private List<TimerTaskList> timerTaskList; // ring queue
 private volatile TimingWheel overflowWheel; //Upper level time round
 private final Consumer<TimerTaskList> consumer;//Task Processor
 }

Summarize: manage time slots through two-way linked lists, and combine JDK's delay queue DelayQueue to achieve efficient task downgrade and time-wheel drive.

3.2 Task addition process

// Core entrance
 public boolean addTask(TimerTask timerTask) {
 long expiration = ();
 //Expired tasks are executed directly
 if (expiration < currentTime + tickMs) {
 return false;
 } else if (expiration < currentTime + interval) {
 //The current time wheel can accommodate this task. Add to the time slot.
 long virtualId = expiration / tickMs;
 int index = (int) (virtualId % wheelSize);
 TimerTaskList timerTaskList = timerTaskLists[index];
 (timerTask);
 if ((virtualId * tickMs)) {
 //Add to delayQueue
 (timerTaskList);
 }
 } else {
 //The time round placed on the previous level
 TimingWheel timeWheel = getOverflowWheel();
 (timerTask);
 }
 return true;
 }

 //Get the upper time round
 private TimingWheel getOverflowWheel() {
 if (overflowWheel == null) {
 synchronized (this) {
 if (overflowWheel == null) {
 overflowWheel = new TimingWheel(interval, wheelSize, currentTime, consumer);
 }
 }
 }
 return overflowWheel;
 }
  • Time alignment:passvirtualId * tickMsCalculate the exact expiration time of the slot
  • Delayed queue association: Add the slot only if the first time it is added to the taskDelayQueue
  • Lazy loading of the upper time round:passgetOverflowWheel()Methods to create upper time round as needed
  • Thread safety control：currentTimeuseAtomicLongEnsure visibility

Summarize: When adding tasks, find the appropriate slot through the time round step by step, and send the task directly when it expires.

3.4 The key role of DelayQueue

Implementation details：

  1. Slot Packaging:EachTimerTaskListaccomplishDelayedInterfaces, sorted by slot expiration time
  2. Efficient wake-up：()Wake up the thread immediately when the slot expires to avoid CPU idling
  3. Batch processing: A slot may contain hundreds of tasks, reducing lock competition
	public long getDelay(TimeUnit unit) {
		return (0, (() - (), ));
	}

Summarize：DelayQueueIt is the "heartbeat engine" of the time wheel, driving the pointer to advance as needed.

3.3 Time round advancement mechanism

Driver core: Background thread obtains the expiration time slot through DelayQueue

public void advanceClock(long timestamp) {
 if (timestamp >= currentTime + tickMs) {
 currentTime = timestamp - (timestamp % tickMs);
 if (overflowWheel != null) {
 //Promote the upper time round time
 ().advanceClock(timestamp);
 }
 }
 }

Summarize: Batch processing expired tasks reduce context switching by triggering time round propulsion by delaying queues.

4. Typical application scenarios

  1. Delayed message: Implement accurate delayed message delivery (such as order timeout)
  2. Session timeout: Consumer group heartbeat detection and Rebalance
  3. Request timeout: Timeout control for processing Produce/Fetch requests
  4. Timed indicator collection: Statistics of Broker Performance Indicators

Summarize: The time round is Kafka's core infrastructure for achieving low latency and high throughput.

5. Summary and performance comparison

plan Time complexity Time-consuming for inserting million tasks Applicable scenarios
Priority queue O(log n) ~3ms Low concurrency timing tasks
Time round O(1) ~0.2ms High concurrency delay operation

Performance optimization tips：

  1. Time slot pre-allocation: Avoid memory allocation overhead when adding tasks
  2. Pointer jumping propulsion: Skip empty slot time without task
  3. Batch expiration processing: Merge multiple small tasks into the same slot

Core advantages：

  • Time complexity is stable to O(1)
  • Batch processing reduces thread competition
  • Level design takes into account both precision and range

Philosophical Inspiration for Design：

  • Change time in space: Exchange O(1) time complexity by pre-allocating slot memory
  • Stratified governance: Different levels deal with problems of different sizes (similar to JVM memory generation)

Through layer by layer source code analysis, it can be seen that the Kafka time round isAlgorithm optimizationandEngineering PracticeA model of combination. Its design idea is not only applicable to message queues, but also has important reference value for any system that requires high concurrent timing tasks.

<Previous Next>