多级时间轮的工作原理是什么？数据链表是挂在秒上的吗？

## **多级时间轮的工作原理** 多级时间轮（Hierarchical Timing Wheels）是一种高效的定时任务调度结构，适用于长时间跨度的任务管理，如 Kafka 的延迟任务。它的核心思想是使用多个层级时间轮，每层管理不同粒度的任务，任务会从高层向低层逐步移动，直到最终执行。 ### **1. 数据存储结构** 多级时间轮的底层数据结构包括： 1. **环形数组（slots）**：每层时间轮是一个固定大小的环形数组。 2. **链表存储任务（Task List）**：每个槽位存储一个链表，任务挂载在链表上。 3. **指针（Pointer）**：表示当前时间，每次 tick 时向前移动一个槽位。 ### **2. 层级示例** | 层级 | 粒度 | 槽位数 | 表示范围 | |-------------|----------|---------|---------| | **第 1 层** | 100ms | 10 | 1 秒 | | **第 2 层** | 1 秒 | 60 | 1 分钟 | | **第 3 层** | 1 分钟 | 60 | 1 小时 | | **第 4 层** | 1 小时 | 24 | 1 天 | 任务不会直接存到秒级时间轮，而是放到合适的层级，等时间推进后逐层下沉，最终进入秒级时间轮执行。 ### **3. 多级时间轮的工作流程** 任务进入时间轮后，存放到合适的层级，并随着时间推进逐层向下移动，最终到达秒级时间轮并执行。 #### **示例：任务存放过程** 假设当前时间是 **12:00:00.000**，有一个任务要在 **12:03:15.400** 运行（延迟 195.4 秒）： 1. **计算任务的存放层级** - 195.4 秒 > 60 秒，任务不会放在秒级时间轮。 - 195.4 秒 ≈ 3 分钟，任务存入 **第 3 层（分钟级）** 的 `slotIndex = 3` 号槽。 2. **层级推进** - 3 分钟后，第 3 层时间轮的指针推进到 `slotIndex = 3`，发现有任务，任务移动到 **第 2 层（秒级时间轮）的 `slotIndex = 15`**（代表 15 秒后执行）。 - 15 秒后，第 2 层时间轮的指针推进到 `slotIndex = 15`，任务进入 **第 1 层（100ms 级时间轮）的 `slotIndex = 4`**（代表 400ms 后执行）。 - 400ms 后，任务执行。 ### **4. 数据链表是如何存储任务的？** 任务存放在时间轮的链表上，而不是直接存放在数组中。 #### **数据结构** ```java class TimerTaskList { private final LinkedList<TimerTaskEntry> tasks = new LinkedList<>(); } class TimerTaskEntry { private Runnable task; // 要执行的任务 private long expireTimestamp; // 任务的目标执行时间 } ``` 1. 每个时间轮的槽（slot）是一个链表，存放多个任务。 2. 任务的 `expireTimestamp` 确保它能被正确触发。 3. 当时间轮推进时，任务会从高层级时间轮移动到低层级，直到到达秒级时间轮并最终执行。 ### **5. 时间轮推进机制** 时间轮的推进机制依赖系统时钟定期 tick（推进）： ```java public void advanceClock(long timestamp) { while (currentTime < timestamp) { int index = (int) (currentTime / tickDuration) % slotCount; TimerTaskList bucket = buckets[index]; // 将任务下沉到下一层时间轮 bucket.flush(this::addTimerTask); currentTime += tickDuration; } } ``` #### **推进逻辑** 1. 计算当前时间轮指针的位置 `index`。 2. 取出当前 `index` 位置的槽 `bucket`，其中存放了一批任务。 3. 如果任务未到期，就把它们下沉到下一层时间轮。 4. 如果任务已经到期，就执行。 5. 继续推进时间，直到当前时间达到 `timestamp`。 ### **6. 任务下沉机制** 如果任务的执行时间远超当前时间轮的粒度，则任务会逐层存放： - 小时级任务存放在小时层级时间轮。 - 分钟级任务存放在分钟层级时间轮。 - 秒级任务存放在秒级时间轮。 当低层时间轮转动一圈，高层任务会被移入低层继续倒计时，最终精准执行。 #### **任务下沉示例** | 任务目标执行时间 | 存放层级 | 槽位索引 | 任务执行方式 | |------------|------|------|--------------------| | 3 天 10 小时 | 天级时间轮 | `slotIndex = 3` | 3 天后下沉到小时级时间轮 | | 10 小时 30 分钟 | 小时级时间轮 | `slotIndex = 10` | 10 小时后下沉到分钟级时间轮 | | 30 分钟 15 秒 | 分钟级时间轮 | `slotIndex = 30` | 30 分钟后下沉到秒级时间轮 | | 15 秒 400ms | 秒级时间轮 | `slotIndex = 15` | 15 秒后下沉到 100ms 级时间轮 | | 400ms | 100ms 级时间轮 | `slotIndex = 4` | 400ms 后任务执行 | ### **7. 总结** 1. 多级时间轮不会直接存任务到秒级时间轮，而是存放到合适的层级。 2. 时间轮的推进机制会不断将任务从高层时间轮下沉到低层时间轮，最终到达秒级时间轮并执行。 3. 数据链表挂载在时间轮的槽位上，每个槽位是一个任务链表，其中存储多个任务。 4. 任务执行时，先被存入大粒度时间轮，等时间接近时，再下沉到秒级时间轮，最终执行。 5. Kafka 采用层级时间轮，使得它能高效处理秒级到天级的定时任务，同时避免使用巨大数组带来的存储和查询问题。