kafka分层时间轮实战和分析

之前分析了定时任务的数据结构演进，其中终极方案就是kafka的分层时间轮。现在实际编写一下kakfa的分层时间轮，并分析数据。

代码说明

代码部分，直接按kafka 0.11.0版本进行编写，给关键语句都加了自己的注释。

java	scala
Poller	kafka.utils.timer.TimerTest
SystemTimer	kafka.utils.timer.SystemTimer(Timer里)
Timer	kafka.utils.timer.Timer(trait Timer)
TimerTask	kafka.utils.timer.TimerTask(trait TimerTask)
TimerTaskEntry	kafka.utils.timer.TimerTaskEntry(TimerTaskList里)
TimerTaskList	kafka.utils.timer.TimerTaskList
TimingWheel	kafka.utils.timer.TimingWheel

代码：timewheel.zip

数据分析

设定

• 时间片1秒，分桶3个
• 7个任务，分别延迟1、2、……、7秒后执行
• 轮询器自旋，直到2秒等待期间，时间轮都没有任务，才退出

开始

新建1层时间轮

参数	参数名	数值
时间片	tickMs	1000
分桶数	wheelSize	3
开始时间	startMs	1675752020558 2023-02-07 14:40:20.558
任务计数器	taskCounter	0
分桶队列	queue	[]
时间跨度	interval	3000 (1000时间片*3个桶)
分桶	buckets	[expiration: -1] [expiration: -1] [expiration: -1]
当前时间	currentTime	1675752020000 2023-02-07 14:40:20.000
溢出时间轮	overflowWheel	null

插入第1个任务

• 延迟1秒执行，所以任务1容器TimerTaskEntry的expirationMs是System.currentTimeMillis() + 1000 = 14:40:21
• 第1层管理 [currentTime, currentTime + interval) = [14:40:20, 14:40:23)，此时任务1的时间14:40:21能被当前层覆盖
• 计算分桶虚拟ID：virtualId = expiration / tickMs = 1675752021
• 哈希到分桶：1675752021%3=0，将其放入1层0桶
• 设置分桶过期时间，-1被替换为时间片对齐的virtualId * tickMs=1675752021000(14:40:21.000)，意味着0桶管理的时间片是[14:40:21.000, 14:40:22.000)
• 1层0桶放入queue，过期出队时间为14:40:21.000

层数	0桶	1桶	2桶
1层 时间片：1000ms 管理：[14:40:20, 14:40:23)	任务1：14:40:21 管理：[14:40:21, 14:40:22)	expiration: -1	expiration: -1

过期出队时间	桶
14:40:21.000	1层0桶

这里可以明显看出：
（1）管理的时间片是[14:40:20, 14:40:23)，但并不是0桶管理20-21、1桶21-22、2桶22-23这样顺序的，因为分桶是通过取余来决定的。
（2）过期出队时间是分桶管理的开始时间，而不是结束时间，后面出队检查会用timeMs >= currentTime + tickMs来执行判断，不会出问题。

插入第2个任务

• 延迟2秒执行，所以任务2容器TimerTaskEntry的expirationMs是System.currentTimeMillis() + 2000 = 14:40:22
• 第1层管理 [currentTime, currentTime + interval) = [14:40:20, 14:40:23)，此时任务2的时间14:40:22能被当前层覆盖
• 计算分桶虚拟ID：virtualId = expiration / tickMs = 1675752022
• 哈希到分桶：1675752022%3=1，将其放入1层1桶
• 设置分桶过期时间，-1被替换为时间片对齐的virtualId * tickMs=1675752022000(14:40:22.000)，意味着1桶管理的时间片是[14:40:22.000, 14:40:23.000)
• 1层1桶放入queue，过期出队时间为14:40:22.000

层数	0桶	1桶	2桶
1层 时间片：1000ms 管理：[14:40:20, 14:40:23)	任务1：14:40:21 管理：[14:40:21, 14:40:22)	任务2：14:40:22 管理：[14:40:22, 14:40:23)	expiration: -1

过期出队时间	桶
14:40:21.000	1层0桶
14:40:22.000	1层1桶

插入第3个任务

• 延迟3秒执行，所以任务3容器TimerTaskEntry的expirationMs是System.currentTimeMillis() + 3000 = 14:40:23
• 第1层管理 [currentTime, currentTime + interval) = [14:40:20, 14:40:23)，此时任务3的时间14:40:23不能被覆盖

因此，需要创建2层时间轮：

• 传入的startMs是1层时间轮的currentTime=1675752020000(14:40:20)
• 时间片传入了1层的时间跨度3000
• 任务计数器全局共用，目前已有2个任务
• 分桶队列全局共用，目前已有2个桶
• 2层分桶是新建的
• 2层的当前时间，为了对齐时间片，反而退回了14:40:18

参数	参数名	数值
时间片	tickMs	3000
分桶数	wheelSize	3
开始时间	startMs	1675752020000 2023-02-07 14:40:20.000
任务计数器	taskCounter	2
分桶队列	queue	[1层0桶, 1层1桶]
时间跨度	interval	9000 (3000时间片*3个桶)
分桶	buckets	[expiration: -1] [expiration: -1] [expiration: -1]
当前时间	currentTime	1675752018000 2023-02-07 14:40:18.000
溢出时间轮	overflowWheel	null

将任务3放入2层时间轮：

• 第2层管理 [currentTime, currentTime + interval) = [14:40:18, 14:40:27)，此时任务3的时间14:40:23能被当前层覆盖
• 计算分桶虚拟ID：virtualId = expiration / tickMs = 558584007
• 558584007%3=0，将其放入2层0桶
• 设置分桶过期时间，-1被替换为时间片对齐的virtualId * tickMs=1675752021000(14:40:21.000)，意味着0桶管理的时间片是[14:40:21.000, 14:40:24.000)
• 2层0桶放入queue，过期出队时间为14:40:21.000

层数	0桶	1桶	2桶
1层 时间片：1000ms 管理：[14:40:20, 14:40:23)	任务1：14:40:21 管理：[14:40:21, 14:40:22)	任务2：14:40:22 管理：[14:40:22, 14:40:23)	expiration: -1
2层 时间片：3000ms 管理：[14:40:18, 14:40:27)	任务3：14:40:23 管理：[14:40:21, 14:40:24)	expiration: -1	expiration: -1

过期出队时间	桶
14:40:21.000	1层0桶
14:40:21.000	2层0桶
14:40:22.000	1层1桶

插入第4个任务

• 延迟4秒执行，所以任务4容器TimerTaskEntry的expirationMs是System.currentTimeMillis() + 4000 = 14:40:24
• 第1层管理 [currentTime, currentTime + interval) = [14:40:20, 14:40:23)，此时任务4的时间14:40:24不能被覆盖
• 第2层管理 [currentTime, currentTime + interval) = [14:40:18, 14:40:27)，此时任务4的时间14:40:24能被当前层覆盖
• 计算分桶虚拟ID：virtualId = expiration / tickMs = 558584008
• 558584008%3=1，将其放入2层1桶
• 设置分桶过期时间，-1被替换为时间片对齐的virtualId * tickMs=1675752024000(14:40:24.000)，意味着2层1桶管理的时间片是[14:40:24.000, 14:40:27.000)
• 2层1桶放入queue，过期出队时间为14:40:24.000

层数	0桶	1桶	2桶
1层 时间片：1000ms 管理：[14:40:20, 14:40:23)	任务1：14:40:21 管理：[14:40:21, 14:40:22)	任务2：14:40:22 管理：[14:40:22, 14:40:23)	expiration: -1
2层 时间片：3000ms 管理：[14:40:18, 14:40:27)	任务3：14:40:23 管理：[14:40:21, 14:40:24)	任务4：14:40:24 管理：[14:40:24, 14:40:27)	expiration: -1

过期出队时间	桶
14:40:21.000	1层0桶
14:40:21.000	2层0桶
14:40:22.000	1层1桶
14:40:24.000	2层1桶

插入第5个任务

• 延迟5秒执行，所以任务5容器TimerTaskEntry的expirationMs是System.currentTimeMillis() + 5000 = 14:40:25
• 第1层管理 [currentTime, currentTime + interval) = [14:40:20, 14:40:23)，此时任务5的时间14:40:25不能被覆盖
• 第2层管理 [currentTime, currentTime + interval) = [14:40:18, 14:40:27)，此时任务5的时间14:40:25能被当前层覆盖
• 计算分桶虚拟ID：virtualId = expiration / tickMs = 558584008
• 558584008%3=1，将其放入2层1桶
• 设置分桶过期时间，由于2层1桶已经有了expiration且相同，不会再执行queue插入

层数	0桶	1桶	2桶
1层 时间片：1000ms 管理：[14:40:20, 14:40:23)	任务1：14:40:21 管理：[14:40:21, 14:40:22)	任务2：14:40:22 管理：[14:40:22, 14:40:23)	expiration: -1
2层 时间片：3000ms 管理：[14:40:18, 14:40:27)	任务3：14:40:23 管理：[14:40:21, 14:40:24)	任务4：14:40:24 任务5：14:40:25 管理：[14:40:24, 14:40:27)	expiration: -1

过期出队时间	桶
14:40:21.000	1层0桶
14:40:21.000	2层0桶
14:40:22.000	1层1桶
14:40:24.000	2层1桶

插入第6个任务

• 延迟6秒执行，所以任务6容器TimerTaskEntry的expirationMs是System.currentTimeMillis() + 6000 = 14:40:26
• 第1层管理 [currentTime, currentTime + interval) = [14:40:20, 14:40:23)，此时任务6的时间14:40:26不能被覆盖
• 第2层管理 [currentTime, currentTime + interval) = [14:40:18, 14:40:27)，此时任务6的时间14:40:26能被当前层覆盖
• 计算分桶虚拟ID：virtualId = expiration / tickMs = 558584008
• 558584008%3=1，将其放入2层1桶
• 设置分桶过期时间，由于2层1桶已经有了expiration且相同，不会再执行queue插入

层数	0桶	1桶	2桶
1层 时间片：1000ms 管理：[14:40:20, 14:40:23)	任务1：14:40:21 管理：[14:40:21, 14:40:22)	任务2：14:40:22 管理：[14:40:22, 14:40:23)	expiration: -1
2层 时间片：3000ms 管理：[14:40:18, 14:40:27)	任务3：14:40:23 管理：[14:40:21, 14:40:24)	任务4：14:40:24 任务5：14:40:25 任务6：14:40:26 管理：[14:40:24, 14:40:27)	expiration: -1

过期出队时间	桶
14:40:21.000	1层0桶
14:40:21.000	2层0桶
14:40:22.000	1层1桶
14:40:24.000	2层1桶

插入第7个任务

• 延迟7秒执行，所以任务7容器TimerTaskEntry的expirationMs是System.currentTimeMillis() + 7000 = 14:40:27
• 第1层管理 [currentTime, currentTime + interval) = [14:40:20, 14:40:23)，此时任务7的时间14:40:27不能被覆盖
• 第2层管理 [currentTime, currentTime + interval) = [14:40:18, 14:40:27)，此时任务7的时间14:40:27不能被覆盖

需要创建3层时间轮：

• 传入的startMs是2层时间轮的currentTime=1675752018000(14:40:18)
• 时间片传入了2层的时间跨度9000
• 任务计数器全局共用，目前已有6个任务
• 分桶队列全局共用，目前已有4个桶
• 3层分桶是新建的
• 3层的当前时间，为了对齐时间片，退回了14:40:12

参数	参数名	数值
时间片	tickMs	9000
分桶数	wheelSize	3
开始时间	startMs	1675752018000 2023-02-07 14:40:18.000
任务计数器	taskCounter	6
分桶队列	queue	[1层0桶, 2层0桶，1层1桶，2层1桶]
时间跨度	interval	27000 (9000时间片*3个桶)
分桶	buckets	[expiration: -1] [expiration: -1] [expiration: -1]
当前时间	currentTime	1675752012000 2023-02-07 14:40:12.000
溢出时间轮	overflowWheel	null

• 计算分桶虚拟ID：virtualId = expiration / tickMs = 186194669
• 186194669%3=2，将其放入3层2桶
• 设置分桶过期时间，-1被替换为时间片对齐的virtualId * tickMs=1675752021000(14:40:21.000)，意味着3层2桶管理的时间片是[14:40:21.000, 14:40:30.000)
• 3层2桶放入queue，过期出队时间为14:40:21.000

层数	0桶	1桶	2桶
1层 时间片：1000ms 管理：[14:40:20, 14:40:23)	任务1：14:40:21 管理：[14:40:21, 14:40:22)	任务2：14:40:22 管理：[14:40:22, 14:40:23)	expiration: -1
2层 时间片：3000ms 管理：[14:40:18, 14:40:27)	任务3：14:40:23 管理：[14:40:21, 14:40:24)	任务4：14:40:24 任务5：14:40:25 任务6：14:40:26 管理：[14:40:24, 14:40:27)	expiration: -1
3层 时间片：9000ms 管理：[14:40:12, 14:40:39)	expiration: -1	expiration: -1	任务7：14:40:27 管理：[14:40:21, 14:40:30)

过期出队时间	桶
14:40:21.000	1层0桶
14:40:21.000	2层0桶
14:40:21.000	3层2桶
14:40:22.000	1层1桶
14:40:24.000	2层1桶

14:40:21.000 第1次前进时间轮

获取第1个过期桶，此时拿到1层0桶，取其过期时间14:40:21.000，递归推进所有时间轮：

第1层时间轮

• 过期时间14:40:21.000 >= 1层当前时间14:40:20 + 1000毫秒，说明[14:40:20, 14:40:21)分桶过期
• 推进1层当前时间：14:40:20 -> 14:40:21
• 存在高层时间轮，递归推进

第2层时间轮

• 过期时间14:40:21.000 >= 2层当前时间14:40:18 + 3000毫秒，说明[14:40:18, 14:40:21)分桶过期
• 推进2层当前时间：14:40:18 -> 14:40:21
• 存在高层时间轮，递归推进

第3层时间轮

• 过期时间14:40:21.000 >= 3层当前时间14:40:12 + 9000毫秒，说明[14:40:12, 14:40:21)分桶过期
• 推进3层当前时间：14:40:12 -> 14:40:21
• 不存在高层时间轮，递归中止

时间轮变化：

层数	0桶	1桶	2桶
1层 时间片：1000ms 管理：[14:40:20, 14:40:23) [14:40:21, 14:40:24)	任务1：14:40:21 管理：[14:40:21, 14:40:22)	任务2：14:40:22 管理：[14:40:22, 14:40:23)	expiration: -1
2层 时间片：3000ms 管理：[14:40:18, 14:40:27) [14:40:21, 14:40:30)	任务3：14:40:23 管理：[14:40:21, 14:40:24)	任务4：14:40:24 任务5：14:40:25 任务6：14:40:26 管理：[14:40:24, 14:40:27)	expiration: -1
3层 时间片：9000ms 管理：[14:40:12, 14:40:39) [14:40:21, 14:40:48)	expiration: -1	expiration: -1	任务7：14:40:27 管理：[14:40:21, 14:40:30)

然后，会将所有过期桶中的任务取出，执行重新插入。

14:40:21.000过期桶有3个：

• 1层0桶：任务1(14:40:21)
• 2层0桶：任务3(14:40:23)
• 3层2桶：任务7(14:40:27)

任务7重新插入

• 将3层2桶移出队列，重置3层2桶的过期时间为-1
• 将任务7移出3层2桶
• 任务7(14:40:27)，1层时间轮推进，[14:40:21, 14:40:24)，仍不能被覆盖，进入2层；2层时间轮推进，已能管理[14:40:21, 14:40:30)，因此任务7被插入2层时间轮
• 计算分桶，插入2层2桶
• 更新2层2桶过期时间，-1被替换为时间片对齐的virtualId * tickMs=1675752027000(14:40:27.000)，意味着2层2桶管理的时间片是[14:40:27.000, 14:40:30.000)
• 由于2层2桶的过期时间更新，被放入队列

任务3重新插入

• 将2层0桶移出队列，重置2层0桶的过期时间为-1
• 将任务3移出2层0桶
• 任务3(14:40:23)，1层时间轮推进，[14:40:21, 14:40:24)，已能覆盖
• 计算分桶，插入1层2桶
• 更新1层2桶过期时间，-1被替换为时间片对齐的virtualId * tickMs=1675752027000(14:40:23.000)，意味着1层2桶管理的时间片是[14:40:23.000, 14:40:24.000)

任务1重新插入

• 将1层0桶移出队列，重置1层0桶的过期时间为-1
• 将任务1移出1层0桶
• 任务1(14:40:21)已过期，被取出执行

插入完成后：

层数	0桶	1桶	2桶
1层 时间片：1000ms 管理：[14:40:21, 14:40:24)	任务1：14:40:21 管理：[14:40:21, 14:40:22) expiration: -1	任务2：14:40:22 管理：[14:40:22, 14:40:23)	任务3：14:40:23 管理：[14:40:23, 14:40:24)
2层 时间片：3000ms 管理：[14:40:21, 14:40:30)	任务3：14:40:23 管理：[14:40:21, 14:40:24) expiration: -1	任务4：14:40:24 任务5：14:40:25 任务6：14:40:26 管理：[14:40:24, 14:40:27)	任务7：14:40:27 管理：[14:40:27, 14:40:30)
3层 时间片：9000ms 管理：[14:40:21, 14:40:48)	expiration: -1	expiration: -1	任务7：14:40:27 管理：[14:40:21, 14:40:30) expiration: -1

过期出队时间	桶
14:40:21.000	1层0桶
14:40:21.000	2层0桶
14:40:21.000	3层2桶
14:40:22.000	1层1桶
14:40:23.000	1层2桶
14:40:24.000	2层1桶
14:40:27.000	2层2桶

产生了轮转的效果。

即使第3层时间轮已经没有数据了，由于没有销毁机制，是不会被销毁的。

14:40:22.000 第2次前进时间轮

获取第1个过期桶，此时拿到1层1桶，取其过期时间14:40:22.000，递归推进所有时间轮：

第1层时间轮

• 过期时间14:40:22.000 >= 1层当前时间14:40:21 + 1000毫秒，说明[14:40:21, 14:40:22)分桶过期
• 推进1层当前时间：14:40:21 -> 14:40:22
• 存在高层时间轮，递归推进

第2层时间轮

• 过期时间14:40:22.000 < 2层当前时间14:40:21 + 3000毫秒，说明2层单位时间片没有转完，递归中止

时间轮变化：

层数	0桶	1桶	2桶
1层 时间片：1000ms 管理：[14:40:21, 14:40:24)[14:40:22, 14:40:25)	expiration: -1	任务2：14:40:22 管理：[14:40:22, 14:40:23)	任务3：14:40:23 管理：[14:40:23, 14:40:24)
2层 时间片：3000ms 管理：[14:40:21, 14:40:30)	expiration: -1	任务4：14:40:24 任务5：14:40:25 任务6：14:40:26 管理：[14:40:24, 14:40:27)	任务7：14:40:27 管理：[14:40:27, 14:40:30)
3层 时间片：9000ms 管理：[14:40:21, 14:40:48)	expiration: -1	expiration: -1	expiration: -1

14:40:22.000过期桶有1个：

• 1层1桶：任务2(14:40:22)

任务2重新插入

• 将1层1桶移出队列，重置1层1桶的过期时间为-1
• 将任务2移出1层1桶
• 任务2(14:40:22)已过期，被取出执行

插入完成后：

层数	0桶	1桶	2桶
1层 时间片：1000ms 管理：[14:40:22, 14:40:25)	expiration: -1	任务2：14:40:22 管理：[14:40:22, 14:40:23) expiration: -1	任务3：14:40:23 管理：[14:40:23, 14:40:24)
2层 时间片：3000ms 管理：[14:40:21, 14:40:30)	expiration: -1	任务4：14:40:24 任务5：14:40:25 任务6：14:40:26 管理：[14:40:24, 14:40:27)	任务7：14:40:27 管理：[14:40:27, 14:40:30)
3层 时间片：9000ms 管理：[14:40:21, 14:40:48)	expiration: -1	expiration: -1	expiration: -1

过期出队时间	桶
14:40:22.000	1层1桶
14:40:23.000	1层2桶
14:40:24.000	2层1桶
14:40:27.000	2层2桶

14:40:23.000 第3次前进时间轮

获取第1个过期桶，此时拿到1层2桶，取其过期时间14:40:23.000，递归推进所有时间轮：

第1层时间轮

• 过期时间14:40:23.000 >= 1层当前时间14:40:22 + 1000毫秒，说明[14:40:22, 14:40:23)分桶过期
• 推进1层当前时间：14:40:22 -> 14:40:23
• 存在高层时间轮，递归推进

第2层时间轮

• 过期时间14:40:23.000 < 2层当前时间14:40:21 + 3000毫秒，说明2层单位时间片没有转完，递归中止

时间轮变化：

层数	0桶	1桶	2桶
1层 时间片：1000ms 管理：[14:40:23, 14:40:26)	expiration: -1	expiration: -1	任务3：14:40:23 管理：[14:40:23, 14:40:24)
2层 时间片：3000ms 管理：[14:40:21, 14:40:30)	expiration: -1	任务4：14:40:24 任务5：14:40:25 任务6：14:40:26 管理：[14:40:24, 14:40:27)	任务7：14:40:27 管理：[14:40:27, 14:40:30)
3层 时间片：9000ms 管理：[14:40:21, 14:40:48)	expiration: -1	expiration: -1	expiration: -1

14:40:23.000过期桶有1个：

• 1层2桶：任务3(14:40:23)

任务3重新插入

• 将1层2桶移出队列，重置1层2桶的过期时间为-1
• 将任务3移出1层2桶
• 任务3(14:40:23)已过期，被取出执行

插入完成后：

层数	0桶	1桶	2桶
1层 时间片：1000ms 管理：[14:40:23, 14:40:26)	expiration: -1	expiration: -1	任务3：14:40:23 管理：[14:40:23, 14:40:24) expiration: -1
2层 时间片：3000ms 管理：[14:40:21, 14:40:30)	expiration: -1	任务4：14:40:24 任务5：14:40:25 任务6：14:40:26 管理：[14:40:24, 14:40:27)	任务7：14:40:27 管理：[14:40:27, 14:40:30)
3层 时间片：9000ms 管理：[14:40:21, 14:40:48)	expiration: -1	expiration: -1	expiration: -1

过期出队时间	桶
14:40:23.000	1层2桶
14:40:24.000	2层1桶
14:40:27.000	2层2桶

14:40:24.000 第4次前进时间轮

获取第1个过期桶，此时拿到2层1桶，取其过期时间14:40:24.000，递归推进所有时间轮：

第1层时间轮

• 过期时间14:40:24.000 >= 1层当前时间14:40:23 + 1000毫秒，说明[14:40:23, 14:40:24)分桶过期
• 推进1层当前时间：14:40:23 -> 14:40:24
• 存在高层时间轮，递归推进

第2层时间轮

• 过期时间14:40:24.000 >= 2层当前时间14:40:21 + 3000毫秒，说明[14:40:21, 14:40:24)分桶过期
• 推进2层当前时间：14:40:21 -> 14:40:24
• 存在高层时间轮，递归推进

第3层时间轮

• 过期时间14:40:24.000 < 3层当前时间14:40:21 + 9000毫秒，说明3层单位时间片没有转完，递归中止

时间轮变化：

层数	0桶	1桶	2桶
1层 时间片：1000ms 管理：[14:40:23, 14:40:26)[14:40:24, 14:40:27)	expiration: -1	expiration: -1	expiration: -1
2层 时间片：3000ms 管理：[14:40:21, 14:40:30)[14:40:24, 14:40:33)	expiration: -1	任务4：14:40:24 任务5：14:40:25 任务6：14:40:26 管理：[14:40:24, 14:40:27)	任务7：14:40:27 管理：[14:40:27, 14:40:30)
3层 时间片：9000ms 管理：[14:40:21, 14:40:48)	expiration: -1	expiration: -1	expiration: -1

14:40:24.000过期桶有1个：

• 2层1桶：任务4(14:40:24), 任务5(14:40:25), 任务6(14:40:26)

任务4重新插入

• 将2层1桶移出队列，重置2层1桶的过期时间为-1
• 将任务4移出2层1桶
• 任务4(14:40:24)已过期，被取出执行

任务5重新插入

• 将任务5移出2层1桶
• 任务5(14:40:25)，1层时间轮推进，[14:40:24, 14:40:27)，已能覆盖
• 计算分桶，插入1层1桶
• 更新1层1桶过期时间，-1被替换为[14:40:25, 14:40:26)
• 由于1层1桶的过期时间更新，被放入队列

任务6重新插入

• 将任务6移出2层1桶
• 任务6(14:40:26)，1层时间轮推进，[14:40:24, 14:40:27)，已能覆盖
• 计算分桶，插入1层2桶
• 更新1层2桶过期时间，-1被替换为[14:40:26, 14:40:27)
• 由于1层2桶的过期时间更新，被放入队列

插入完成后：

层数	0桶	1桶	2桶
1层 时间片：1000ms 管理：[14:40:24, 14:40:27)	expiration: -1	任务5：14:40:25 管理：[14:40:25, 14:40:26)	任务6：14:40:26 管理：[14:40:26, 14:40:27)
2层 时间片：3000ms 管理：[14:40:24, 14:40:33)	expiration: -1	任务4：14:40:24 任务5：14:40:25 任务6：14:40:26 管理：[14:40:24, 14:40:27) expiration: -1	任务7：14:40:27 管理：[14:40:27, 14:40:30)
3层 时间片：9000ms 管理：[14:40:21, 14:40:48)	expiration: -1	expiration: -1	expiration: -1

过期出队时间	桶
14:40:24.000	2层1桶
14:40:25.000	1层1桶
14:40:26.000	1层2桶
14:40:27.000	2层2桶

14:40:25.000 第5次前进时间轮

获取第1个过期桶，此时拿到1层1桶，取其过期时间14:40:25.000，递归推进所有时间轮：

第1层时间轮

• 过期时间14:40:25.000 >= 1层当前时间14:40:24 + 1000毫秒，说明[14:40:24, 14:40:25)分桶过期
• 推进1层当前时间：14:40:24 -> 14:40:25
• 存在高层时间轮，递归推进

第2层时间轮

• 过期时间14:40:25.000 < 2层当前时间14:40:24 + 3000毫秒，说明2层单位时间片没有转完，递归中止

层数	0桶	1桶	2桶
1层 时间片：1000ms 管理：[14:40:24, 14:40:27)[14:40:25, 14:40:28)	expiration: -1	任务5：14:40:25 管理：[14:40:25, 14:40:26)	任务6：14:40:26 管理：[14:40:26, 14:40:27)
2层 时间片：3000ms 管理：[14:40:24, 14:40:33)	expiration: -1	expiration: -1	任务7：14:40:27 管理：[14:40:27, 14:40:30)
3层 时间片：9000ms 管理：[14:40:21, 14:40:48)	expiration: -1	expiration: -1	expiration: -1

14:40:25.000过期桶有1个：

• 1层1桶：任务5(14:40:25)

任务5重新插入

• 将1层1桶移出队列，重置1层1桶的过期时间为-1
• 将任务5移出1层1桶
• 任务5(14:40:25)已过期，被取出执行

插入完成后：

层数	0桶	1桶	2桶
1层 时间片：1000ms 管理：[14:40:25, 14:40:28)	expiration: -1	任务5：14:40:25 管理：[14:40:25, 14:40:26) expiration: -1	任务6：14:40:26 管理：[14:40:26, 14:40:27)
2层 时间片：3000ms 管理：[14:40:24, 14:40:33)	expiration: -1	expiration: -1	任务7：14:40:27 管理：[14:40:27, 14:40:30)
3层 时间片：9000ms 管理：[14:40:21, 14:40:48)	expiration: -1	expiration: -1	expiration: -1

过期出队时间	桶
14:40:25.000	1层1桶
14:40:26.000	1层2桶
14:40:27.000	2层2桶

14:40:26.000 第6次前进时间轮

获取第1个过期桶，此时拿到1层2桶，取其过期时间14:40:26.000，递归推进所有时间轮：

第1层时间轮

• 过期时间14:40:26.000 >= 1层当前时间14:40:25 + 1000毫秒，说明[14:40:25, 14:40:26)分桶过期
• 推进1层当前时间：14:40:25 -> 14:40:26
• 存在高层时间轮，递归推进

第2层时间轮

• 过期时间14:40:26.000 < 2层当前时间14:40:24 + 3000毫秒，说明2层单位时间片没有转完，递归中止

层数	0桶	1桶	2桶
1层 时间片：1000ms 管理：[14:40:26, 14:40:29)	expiration: -1	expiration: -1	任务6：14:40:26 管理：[14:40:26, 14:40:27)
2层 时间片：3000ms 管理：[14:40:24, 14:40:33)	expiration: -1	expiration: -1	任务7：14:40:27 管理：[14:40:27, 14:40:30)
3层 时间片：9000ms 管理：[14:40:21, 14:40:48)	expiration: -1	expiration: -1	expiration: -1

任务6重新插入

• 将1层2桶移出队列，重置1层2桶的过期时间为-1
• 将任务6移出1层2桶
• 任务6(14:40:26)已过期，被取出执行

插入完成后：

层数	0桶	1桶	2桶
1层 时间片：1000ms 管理：[14:40:26, 14:40:29)	expiration: -1	expiration: -1	任务6：14:40:26 管理：[14:40:26, 14:40:27) expiration: -1
2层 时间片：3000ms 管理：[14:40:24, 14:40:33)	expiration: -1	expiration: -1	任务7：14:40:27 管理：[14:40:27, 14:40:30)
3层 时间片：9000ms 管理：[14:40:21, 14:40:48)	expiration: -1	expiration: -1	expiration: -1

过期出队时间	桶
14:40:26.000	1层2桶
14:40:27.000	2层2桶

14:40:27.000 第7次前进时间轮

获取第1个过期桶，此时拿到2层2桶，取其过期时间14:40:27.000，递归推进所有时间轮：

第1层时间轮

• 过期时间14:40:27.000 >= 1层当前时间14:40:26 + 1000毫秒，说明[14:40:26, 14:40:27)分桶过期
• 推进1层当前时间：14:40:26 -> 14:40:27
• 存在高层时间轮，递归推进

第2层时间轮

• 过期时间14:40:27.000 >= 2层当前时间14:40:24 + 3000毫秒，说明[14:40:24, 14:40:27)分桶过期
• 推进2层当前时间：14:40:24 -> 14:40:27
• 存在高层时间轮，递归推进

第3层时间轮

• 过期时间14:40:27.000 < 3层当前时间14:40:21 + 9000毫秒，说明3层单位时间片没有转完，递归中止

层数	0桶	1桶	2桶
1层 时间片：1000ms 管理：[14:40:26, 14:40:29)[14:40:27, 14:40:30)	expiration: -1	expiration: -1	expiration: -1
2层 时间片：3000ms 管理：[14:40:24, 14:40:33)[14:40:27, 14:40:36)	expiration: -1	expiration: -1	任务7：14:40:27 管理：[14:40:27, 14:40:30)
3层 时间片：9000ms 管理：[14:40:21, 14:40:48)	expiration: -1	expiration: -1	expiration: -1

任务7重新插入

• 将2层2桶移出队列，重置2层2桶的过期时间为-1
• 将任务7移出2层2桶
• 任务7(14:40:27)已过期，被取出执行

插入完成后：

层数	0桶	1桶	2桶
1层 时间片：1000ms 管理：[14:40:27, 14:40:30)	expiration: -1	expiration: -1	expiration: -1
2层 时间片：3000ms 管理：[14:40:27, 14:40:36)	expiration: -1	expiration: -1	任务7：14:40:27 管理：[14:40:27, 14:40:30) expiration: -1
3层 时间片：9000ms 管理：[14:40:21, 14:40:48)	expiration: -1	expiration: -1	expiration: -1

过期出队时间	桶
14:40:27.000	2层2桶

拿出执行的标准是：无法插入时间轮。所以即使在第2层的桶，也可能被直接拿出执行。

至此，时间轮的任务均被取出。