How Dubbo Implements Efficient Timers with a Hashed Timing Wheel

Why a specialized timer is needed

JDK's java.util.Timer and DelayQueue use a binary heap, giving O(log n) insertion and removal. When millions of tasks are scheduled, this overhead becomes unacceptable. A hashed timing wheel provides O(1) insertion, cancellation and expiration by mapping future timestamps to slots in a circular buffer.

Time‑wheel model

A wheel is a ring of N slots, where N is a power of two. Each slot holds a doubly‑linked list of HashedWheelTimeout objects. A dedicated worker thread advances a pointer ( tick) every tickDuration nanoseconds. When the pointer lands on a slot, the worker iterates the list: if remainingRounds == 0 the associated TimerTask is executed; otherwise remainingRounds is decremented.

Applicable scenarios

Fault recovery

Traffic control

Scheduling algorithms

Managing packet lifecycles in networks

Dubbo time‑wheel structure

Dubbo implements its timer in the org.apache.dubbo.common.timer package. The core interfaces are:

TimerTask : user‑defined task with a single method void run(Timeout timeout).

Timeout : handle returned by Timer.newTimeout(); provides isCancelled(), isExpired(), cancel(), etc.

Timer : defines

Timeout newTimeout(TimerTask task, long delay, TimeUnit unit)

and void stop().

HashedWheelTimeout

Implements Timeout and acts as a node in the wheel’s doubly‑linked list. prev / next: links for traversal (accessed only by the worker thread, no synchronization required). task: the associated TimerTask. deadline: calculated as currentTime + delay - startTime (nanoseconds). state: managed with AtomicIntegerFieldUpdater; possible states are INIT, CANCELLED, EXPIRED. remainingRounds: number of full wheel rotations left before the timeout becomes eligible.

HashedWheelBucket

Represents a single slot and stores HashedWheelTimeout objects in a doubly‑linked list (head and tail). Key operations:

addTimeout(HashedWheelTimeout timeout)

removeTimeout(HashedWheelTimeout timeout)

expireTimeouts(long deadline)

– iterates the list, executes tasks whose remainingRounds == 0, and decrements the counter for the others.

HashedWheelTimer core fields

workerState

: atomic state of the worker (INIT, STARTED, SHUTDOWN). startTime: timestamp when the wheel started; all deadlines are relative to this value. wheel: array of HashedWheelBucket slots; size is the nearest power‑of‑two greater than the configured number of ticks. timeouts and cancelledTimeouts: queues that buffer newly submitted tasks and tasks cancelled before they reach a bucket. tick: monotonically increasing counter used by the worker thread. mask = wheel.length - 1: enables fast slot index calculation via (tick & mask). tickDuration: duration of one tick in nanoseconds (e.g., 100 ms). pendingTimeouts: total number of tasks still pending execution. workerThread and worker: the dedicated thread and its Runnable that drive the wheel.

Creating and scheduling a task

Calling Timer.newTimeout(task, delay, unit) creates a HashedWheelTimeout and enqueues it into timeouts. If the timer has not been started, the following steps are performed:

Determine startTime = System.nanoTime() (or the first tick time).

Launch workerThread which runs HashedWheelTimer$Worker.run().

When the worker processes a tick, each pending timeout is transferred to its target bucket:

long calculated = timeout.deadline - startTime;
long ticks = calculated / tickDuration;
int stopIndex = (int)(ticks & mask);
timeout.remainingRounds = ticks / wheel.length;
wheel[stopIndex].addTimeout(timeout);

Worker execution flow ( HashedWheelTimer$Worker.run() )

Advance tick and compute the deadline for the current tick.

Remove and discard all entries in cancelledTimeouts.

Transfer pending entries from timeouts to their target buckets.

Fetch the bucket for tick & mask and invoke expireTimeouts(deadline).

If workerState indicates shutdown, drain remaining timeouts via unprocessedTimeouts and clear them.

Repeat until the timer is stopped.

Practical usage in Dubbo

Failure retry (e.g., registration or subscription retries).

Periodic tasks such as heartbeat sending, request timeout handling, and reconnection logic.

Reference

https://zhuanlan.zhihu.com/p/32906730