面试Java后端却问我时间轮算法，面试官没想到我看过Dubbo源码！

classDiagram
    class Timer {
        +newTimeout(TimerTask, long, TimeUnit) Timeout
        +stop() Set~Timeout~
        +isStop() boolean
    }

    class Timeout {
        +timer() Timer
        +task() TimerTask
        +isExpired() boolean
        +isCancelled() boolean
        +cancel() boolean
    }

    class TimerTask {
        +run(Timeout) void
    }

    Timer ..> Timeout : creates / returns
    Timeout ..> Timer : references
    Timeout ..> TimerTask : references
    TimerTask ..> Timeout : uses in run()

/**
 * A task which is executed after the delay specified with
 * {@link Timer#newTimeout(TimerTask, long, TimeUnit)} (TimerTask, long, TimeUnit)}.
 */
public interface TimerTask {

    /**
     * Executed after the delay specified with
     * {@link Timer#newTimeout(TimerTask, long, TimeUnit)}.
     *
     * @param timeout a handle which is associated with this task
     */
    void run(Timeout timeout) throws Exception;
}

package org.apache.dubbo.common.timer;

/**
 * A handle associated with a {@link TimerTask} that is returned by a
 * {@link Timer}.
 */
public interface Timeout {

    /**
     * Returns the {@link Timer} that created this handle.
     */
    Timer timer();

    /**
     * Returns the {@link TimerTask} which is associated with this handle.
     */
    TimerTask task();

    /**
     * Returns {@code true} if and only if the {@link TimerTask} associated
     * with this handle has been expired.
     */
    boolean isExpired();

    /**
     * Returns {@code true} if and only if the {@link TimerTask} associated
     * with this handle has been cancelled.
     */
    boolean isCancelled();

    /**
     * Attempts to cancel the {@link TimerTask} associated with this handle.
     * If the task has been executed or cancelled already, it will return with
     * no side effect.
     *
     * @return True if the cancellation completed successfully, otherwise false
     */
    boolean cancel();
}

package org.apache.dubbo.common.timer;

/**
 * Schedules {@link TimerTask}s for one-time future execution in a background
 * thread.
 */
public interface Timer {

    /**
     * Schedules the specified {@link TimerTask} for one-time execution after
     * the specified delay.
     *
     * @return a handle which is associated with the specified task
     * @throws IllegalStateException      if this timer has been {@linkplain #stop() stopped} already
     * @throws RejectedExecutionException if the pending timeouts are too many and creating new timeout
     *                                    can cause instability in the system.
     */
    Timeout newTimeout(TimerTask task, long delay, TimeUnit unit);

    /**
     * Releases all resources acquired by this {@link Timer} and cancels all
     * tasks which were scheduled but not executed yet.
     *
     * @return the handles associated with the tasks which were canceled by
     * this method
     */
    Set<Timeout> stop();

    /**
     * the timer is stop
     *
     * @return true for stop
     */
    boolean isStop();
}

HashedWheelTimeout next;
HashedWheelTimeout prev;

 // 实际被调度的任务
private final TimerTask task;

private final long deadline;

// 抑制以下警告：
//   "unused"            → 未使用
//   "FieldMayBeFinal"   → 字段可以声明为 final
//   "RedundantFieldInitialization" → 字段初始化是冗余的（因为 int 默认值就是 0）
@SuppressWarnings({"unused", "FieldMayBeFinal", "RedundantFieldInitialization" })
private volatile int state = ST_INIT;
// volatile：保证多线程可见性
// state：状态字段，初始值为 ST_INIT（初始状态）

private static final int ST_INIT = 0;
private static final int ST_CANCELLED = 1;
private static final int ST_EXPIRED = 2;

private static final AtomicIntegerFieldUpdater<HashedWheelTimeout> STATE_UPDATER =
                AtomicIntegerFieldUpdater.newUpdater(HashedWheelTimeout.class, "state");

long remainingRounds;

// 当且仅当与此handle关联的TimerTask已被取消时，返回true
// 用于判断与该超时句柄关联的定时任务是否已被取消
@Override
public boolean isCancelled() {
    return state() == ST_CANCELLED;
}

/**
 * 当且仅当与此句柄关联的TimerTask已过期（超时）时，返回true
 */
@Override
public boolean isExpired() {
    return state() == ST_EXPIRED;
}

// 检查当前 HashedWheelTimeout 状态
public int state() {
    return state;
}

@Override
public boolean cancel() {
    // only update the state it will be removed from HashedWheelBucket on next tick.
    // 仅更新状态，下次将其从HashedWheelBucket中删除。
    if (!compareAndSetState(ST_INIT, ST_CANCELLED)) {
        return false;
    }

    // 如果应该取消任务，我们将其放入另一个队列，该队列将在每个刻度上处理
    // 因此，这意味着我们的GC延迟为max。 1个刻度持续时间就足够了
    // 这样，我们就可以再次使用我们的 MpscLinkedQueue，从而尽可能减少锁/开销。
    // If a task should be canceled we put this to another queue which will be processed on each tick.
    // So this means that we will have a GC latency of max. 1 tick duration which is good enough. This way
    // we can make again use of our MpscLinkedQueue and so minimize the locking / overhead as much as possible.
    timer.cancelledTimeouts.add(this);
    return true;
}

public void expire() {
    // 当任务到期时，将当前 HashedWheelTimeout 设为 EXPIRED 态
    if (!compareAndSetState(ST_INIT, ST_EXPIRED)) {
        return;
    }

    try {
        // 然后调用其 run() 方法执行定时任务。
        task.run(this);
    }
    ...
}

/** 将当前 HashedWheelTimeout 从时间轮中删除。 */
void remove() {
    HashedWheelBucket bucket = this.bucket;
    if (bucket != null) {
        bucket.remove(timeout: this);
    } else {
        timer.pendingTimeouts.decrementAndGet();
    }
}

/**
 * Add {@link HashedWheelTimeout} to this bucket.
 */
public void addTimeout(HashedWheelTimeout timeout) {
    assert timeout.bucket == null;
    timeout.bucket = this;
    if (head == null) {
        head = tail = timeout;
    } else {
        tail.next = timeout;
        timeout.prev = tail;
        tail = timeout;
    }
}

private HashedWheelTimeout pollTimeout() {
    HashedWheelTimeout head = this.head;
    if (head == null) {
        return null;
    }
    HashedWheelTimeout next = head.next;
    if (next == null) {
        tail = this.head =  null;
    } else {
        this.head = next;
        next.prev = null;
    }

    // null out prev and next to allow for GC.
    head.next = null;
    head.prev = null;
    head.bucket = null;
    return head;
}

// 时间轮当前所处状态，三个可选值，由 `AtomicIntegerFieldUpdater` 实现其原子地修改
@SuppressWarnings({ "unused", "FieldMayBeFinal" })
private volatile int workerState; // 0 - init, 1 - started, 2 - shut down

// 当前时间轮的启动时间，提交到该时间轮的定时任务的 deadline 字段值均以该时间戳为起点进行计算。
private volatile long startTime;

// 时间轮环形队列，每个元素都是一个槽。当指定时间轮槽数为 n 时，会向上取最靠近 n 的 2 次幂值
private final HashedWheelBucket[] wheel;

// 缓冲外部提交时间轮中的定时任务
private final Queue<HashedWheelTimeout> timeouts = new LinkedBlockingQueue<>();

// 暂存取消的定时任务
private final Queue<HashedWheelTimeout> cancelledTimeouts = new LinkedBlockingQueue<>();

private final class Worker implements Runnable {
    private final Set<Timeout> unprocessedTimeouts = new HashSet<Timeout>();
    // 位于 `HashedWheelTimer$Worker` ，时间轮的指针，步长为 1 的单调递增计数器
    private long tick;


// 掩码， `mask = wheel.length - 1`，执行 `ticks & mask` 便能定位到对应的时钟槽
private final int mask;

// 时间指针每次加 1 所代表的实际时间，单位为纳秒。
private final long tickDuration;

// 当前时间轮剩余的定时任务总数
private final AtomicLong pendingTimeouts = new AtomicLong(0);

// 时间轮内部真正执行定时任务的线程
private final Thread workerThread;

// 真正执行定时任务的逻辑封装这个 Runnable 对象
private final Worker worker = new Worker();

private void processCancelledTasks() {
  for (; ; ) {
    HashedWheelTimeout timeout = cancelledTimeouts.poll();
    if (timeout == null) {
      // all processed
      break;
    }
    try {
      timeout.remove();
    } catch (Throwable t) {
      if (logger.isWarnEnabled()) {
        logger.warn("An exception was thrown while process a cancellation task", t);
      }
    }
  }
}                          

private void transferTimeoutsToBuckets() {
  // transfer only max. 100000 timeouts per tick to prevent a thread to stale the workerThread when it just
  // adds new timeouts in a loop.
  for (int i = 0; i < 100000; i++) {
    HashedWheelTimeout timeout = timeouts.poll();
    if (timeout == null) {
      // 都处理完了
      break;
    }
    if (timeout.state() == HashedWheelTimeout.ST_CANCELLED) {
      // Was cancelled in the meantime.
      continue;
    }

    long calculated = timeout.deadline / tickDuration;
    timeout.remainingRounds = (calculated - tick) / wheel.length;

    // Ensure we don't schedule for past.
    final long ticks = Math.max(calculated, tick);
    int stopIndex = (int) (ticks & mask);

    HashedWheelBucket bucket = wheel[stopIndex];
    bucket.addTimeout(timeout);
  }
}

while (WORKER_STATE_UPDATER.get(HashedWheelTimer.this) == WORKER_STATE_STARTED)

// Fill the unprocessedTimeouts so we can return them from stop() method.

// 遍历时间轮中每个槽位，并调用clearTimeouts() 
for (HashedWheelBucket bucket : wheel) {
  bucket.clearTimeouts(unprocessedTimeouts);
}
// 对 timeouts 队列中未被加入槽中循环调用poll()
for (; ; ) {
  HashedWheelTimeout timeout = timeouts.poll();
  if (timeout == null) {
    break;
  }
  if (!timeout.isCancelled()) {
    unprocessedTimeouts.add(timeout);
  }
}

processCancelledTasks();