时间轮

1.为什么需要时间轮

海量的定时任务下，小顶堆时间复杂度比较高，性能差

2.时间轮是什么

时间轮这个技术其实出来很久了，在kafka、zookeeper、Netty、Dubbo等高性能组件中都有时间轮使用的方式

时间轮，从图片上来看，就和手表的表圈是一样，所以称为时间轮

时间轮是一种逻辑存储结构再配合线程可以完成高效的进行批量化调度的一种调度模型

3.时间轮的基本概念

概念总览

• wheelSize：总块数
• tickMs：每块对应的时间间隔
• currentTime：当前所处时间，类似于钟表的指针，一般被设计为一个线程根据时间不断指向各个时间间隔
• task：定时任务或延时任务

存储结构

时间轮本身是一种逻辑结构，一般采用数组作为实际存储结构

4.时间轮的时间间隔问题

背景

比如周一上午9点执行一个定时任务，周三下午9点执行一个定时任务，时间间隔多长合适？

解决方案

可以定义以1小时为间隔，一共一周168小时，第9小时就是周一商务九点，第57小时就是周三上午9点

结论

也就是说时间间隔要根据需求来设置不是一成不变的

问题

1. 时间轮有168个格子，但是只有两个定时任务能分别用到9与57号格子这对于空间来说很浪费
2. 线程在轮询所有格子的时候，只有9与57号格子有任务，这很浪费CPU。没有任务的时候去Thread.sleep

5.时间轮刻度不够用问题

背景

比如我有个任务，需要每周一上午九点执行

解决方案总览

• 增大时间轮的刻度
• 列表中的任务中添加round属性
• 分层时间轮

增大时间轮的刻度

介绍

一个刻度一小时， 一天24个小时，一周168个小时，一年8760小时，为了解决时间刻度不够用的问题我可以把时间轮的刻度（槽）增加到8760个

很明显这样的设计是不行的

缺点

• 时间刻度太多会， 导致时间轮走到的多数刻度没有任务执行，比如一个月就2个任务，我得移动720次，其中718次是无用功
• 时间刻度太多会导致存储空间变大，利用率变低，比如一个月就2个任务，我得需要大小是720的数组，如果我的执行时间的粒度精确到秒，那就更恐怖了

解决方案

• round时间轮：典型的是现实是Netty里面的
• 分层时间轮：典型实现是Kafka里面的

6.round时间轮

图示round时间轮

缺点

• 时间轮每次都需要遍历任务列表，耗时增加，当时间轮刻度粒度很小（秒级甚至毫秒级）
• 任务列表又特别长时，这种遍历的办法是不可接受的

7.分层时间轮

思想

• 针对时间复杂度的问题：不做遍历计算round，凡是任务列表中的任务，都应该被执行的，直接全部取出来执行
• 针对空间复杂度的问题：分层，每个时间粒度对应一个时间轮，多个时间轮之间进行级联协作

图示分层时间轮