面试题：你了解 Kafka 中的时间轮实现吗?

Kafka 中的时间轮（Timing Wheel）是一种高效管理定时任务的机制，主要用于延迟操作，如延迟生产、延迟拉取等。时间轮的核心思想是通过一个环形数组来表示时间槽，每个槽对应一个时间间隔，任务根据其延迟时间被分配到相应的槽中。

时间轮的基本概念

时间槽（Bucket）：时间轮被划分为多个时间槽，每个槽代表一个时间间隔。例如，一个时间轮有 8 个槽，每个槽代表 1 秒，那么整个时间轮可以表示 8 秒的时间范围。
指针（Current Time Pointer）：时间轮有一个指针，指向当前时间所在的槽。随着时间的推进，指针会顺时针移动。
任务（Task）：每个时间槽中可以存放多个任务，这些任务会在该槽对应的时间点被执行。

时间轮的工作原理

任务添加：当一个任务需要被延迟执行时，Kafka 会根据任务的延迟时间计算出它应该被放入哪个时间槽。例如，如果当前时间轮的指针指向槽 0，任务的延迟时间是 3 秒，那么该任务会被放入槽 3。
时间推进：随着时间的推进，时间轮的指针会逐步移动。每当指针移动到一个新的槽时，该槽中的所有任务都会被取出并执行。
槽的循环：时间轮是环形的，当指针移动到最后一个槽后，会重新回到第一个槽。这意味着时间轮可以循环使用，适合处理周期性的定时任务。

Kafka 中的时间轮实现

Kafka 使用时间轮来管理延迟操作，如延迟生产、延迟拉取等。Kafka 的时间轮实现具有以下特点：

多层时间轮：为了支持更长的延迟时间，Kafka 使用了多层时间轮。每一层时间轮的时间粒度不同，高层时间轮的粒度更大。例如，第一层时间轮的每个槽代表 1 秒，第二层时间轮的每个槽代表 1 分钟，依此类推。
任务迁移：当时间轮的指针移动到某个槽时，如果该槽中的任务还未到执行时间（例如，任务延迟时间跨越了多个时间轮），这些任务会被迁移到更高层的时间轮中。
高效性：时间轮的设计使得任务的添加和删除操作都非常高效，时间复杂度为 O(1)。

代码示例

以下是一个简单的时间轮实现的伪代码：

class TimerTask {
    long delayMs;
    Runnable task;
}

class TimingWheel {
    long tickMs; // 每个槽的时间间隔
    int wheelSize; // 槽的数量
    long interval; // 整个时间轮的时间范围 (tickMs * wheelSize)
    List<TimerTask>[] buckets; // 时间槽数组
    long currentTime; // 当前时间

    public TimingWheel(long tickMs, int wheelSize) {
        this.tickMs = tickMs;
        this.wheelSize = wheelSize;
        this.interval = tickMs * wheelSize;
        this.buckets = new ArrayList[wheelSize];
        this.currentTime = System.currentTimeMillis();
    }

    public void add(TimerTask timerTask) {
        long expiration = currentTime + timerTask.delayMs;
        if (expiration < currentTime + tickMs) {
            // 如果任务延迟时间小于一个槽的时间间隔，直接执行
            timerTask.task.run();
        } else {
            // 计算任务应该放入哪个槽
            long virtualId = expiration / tickMs;
            int bucketIndex = (int) (virtualId % wheelSize);
            buckets[bucketIndex].add(timerTask);
        }
    }

    public void advanceClock(long timestamp) {
        if (timestamp >= currentTime + tickMs) {
            currentTime = timestamp - (timestamp % tickMs);
            int bucketIndex = (int) ((currentTime / tickMs) % wheelSize);
            List<TimerTask> bucket = buckets[bucketIndex];
            for (TimerTask task : bucket) {
                task.task.run();
            }
            bucket.clear();
        }
    }
}