时间轮在 Netty , Kafka 中的设计与实现

本文基于 Netty 4.1.112.Final , Kafka 3.9.0 版本举行讨论

在业务开辟的场景中，我们经常会碰到许多定时使命的需求。好比，生成业务报表，周期性对账，同步数据，订单支付超时处理惩罚等。针对业务场景中定时使命逻辑复杂，实验时间长的特点，市面上已经有许多成熟的使命调理中心件可供我们选择。好比：ElasticJob , XXL-JOB , PowerJob 等等。
而在中心件的场景中，同样也存在许多定时使命的需求。好比，网络毗连的心跳检测，网络哀求超时或失败的重试机制，网络毗连断开之后的重连机制。和业务场景差别的是，这些中心件场景的定时使命特点是逻辑简单，实验时间非常短，而且对时间精度的要求比力低。好比，心跳检测以及失败重试这些定时使命，着实晚实验个几十毫秒或者 100 毫秒也无所谓。
于是针对中心件场景中的这些定时使命特点：

• 海量使命
  
• 使命逻辑简单
  
• 实验时间短
  
• 对使命调理的及时性没有那么高的要求
  

各大中心件设计了时间轮来调理具有上述 4 种特性的定时使命，而本文主要讨论的就是时间轮的设计与实现。但在这之前我们需要搞清楚时间轮这个设计需求是怎么产生的，我们先从 JDK 中的使命调理组件开始聊起，看看 JDK 中的这些使命调理组件为什么不能满足中心件的场景。

1. JDK 中的使命调理组件

说到定时使命，我们第一时间就能想到的调理组件就是 JDK 中的 Timer，为什么这么说呢，由于笔者刚参加工作时的第一个使命就是用 Timer 实现的，当时对 Java 一无所知，完全零底子。主管交给我一个定时使命的需求，两眼抹黑。于是带着清亮而又稚嫩的眼神到网上一顿搜索，找到了这个 Timer，大喜过望。
1.1 Timer

1. public class Timer {
2.     // 优先队列，按照任务的 ExecutionTime，由近到远组织
3.     private final TaskQueue queue = new TaskQueue();
4.     // 延时任务的调度线程
5.     private final TimerThread thread = new TimerThread(queue);
6. }

复制代码

Timer 中有两个焦点组件，一个是用于调理延时使命的 TimerThread ，另一个是 TaskQueue，用于组织延时使命。它是一个优先级队列，其底层是一个数组实现的小根堆。

1. class TaskQueue {
2.     // 数组实现的小根堆
3.     private TimerTask[] queue = new TimerTask[128];
5.     // 向小根堆的堆底添加TimerTask
6.     void add(TimerTask task) {
7.         if (size + 1 == queue.length)
8.             queue = Arrays.copyOf(queue, 2*queue.length);
10.         queue[++size] = task;
11.         // 向上调整
12.         fixUp(size);
13.     }
15.     // 获取堆顶任务
16.     TimerTask getMin() {
17.         return queue[1];
18.     }
19.    
20.     // 删除堆顶任务
21.     void removeMin() {
22.         queue[1] = queue[size];
23.         queue[size--] = null;
24.         //向下调整堆
25.         fixDown(1);
26.     }
27. }

复制代码

TaskQueue 会将所有延时使命按照它们的 ExecutionTime ，由近到远的组织在小根堆中，堆顶永远存放的是 ExecutionTime 近来的延时使命。

TimerThread 会不断的从 TaskQueue 中获取堆顶使命，如果堆顶使命的 ExecutionTime 已经到达 —— executionTime