承接上文
承接上一篇文章【算法数据结构专题】「延时队列算法」史上手把手教你针对层级时间轮（TimingWheel）实现延时队列的开发实战落地（上）】我们基本上对层级时间轮算法的基本原理有了一定的认识，本章节就从落地的角度进行分析和介绍如何通过Java进行实现一个属于我们自己的时间轮服务组件，最后，在告诉大家一下，其实时间轮的技术是来源于生活中的时钟。
时间轮演示结构总览
无序列表时间轮
【无序列表时间轮】主要是由LinkedList链表和启动线程、终止线程实现。
遍历定时器中所有节点，将剩余时间为 0s 的任务进行过期处理，在执行一个周期。
- 无序链表：每一个延时任务都存储在该链表当中（无序存储）。
- 启动线程： 直接在链表后面push ，时间复杂度 O(1)。
- 终止线程： 直接在链表中删除节点，时间复杂度 O(1) 。
遍历周期：需要遍历链表中所有节点，时间复杂度 O(n)，所以伴随着链表中的元素越来越多，速度也会越来越慢！
无序列表时间轮的长度限制了其适用场景，这里对此进行优化。因此引入了有序列表时间轮。
有序列表时间轮
与无序列表时间轮一样，同样使用链表进行实现和设计，但存储的是绝对延时时间点。
- 启动线程：有序插入，比较时间按照时间大小有序插入，时间复杂度O(n)，主要耗时在插入操作。
- 终止线程：链表中查找任务，删除节点，时间复杂度O(n)，主要耗时在插入操作。
找到执行最后一个过期任务即可，无需遍历整个链表，时间复杂度 O(1)，从上面的描述「有序列表定时器」的性能瓶颈在于插入时的任务排序，但是换来的就是缩短了遍历周期。
所以我们如果要提高性，就必须要提升一下插入和删除以及检索的性能，因此引入了「树形有序列表时间轮」在「有序列表定时器」的基础上进行优化，以有序树的形式进行任务存储。
树形有序列表时间轮
- 启动定时器： 有序插入，比较时间按照时间大小有序插入，时间复杂度 O(logn)
- 终止定时器： 在链表中查找任务，删除节点，时间复杂度 O(logn)
- 周期清算: 找到执行最后一个过期任务即可，无需遍历整个链表，时间复杂度 O(1)
层级时间轮
整体流程架构图，如下所示。
对应的原理，在这里就不进行赘述了，之前本人已经有两篇文章对层级式时间轮进行了较为详细的介绍了，有需要的小伙伴，可以直接去前几篇文章去学习，接下来我们进行相关的实现。
时间轮数据模型
时间轮（TimingWheel）是一个存储定时任务的环形队列，数组中的每个元素可以存放一个定时任务列表，其中存放了真正的定时任务，如下图所示。
时间轮的最基本逻辑模型，由多个时间格组成，每个时间格代表当前时间轮的基本时间跨度（tickMs），所以我们先来设计和定义开发对应的时间轮的轮盘模型。命名为Roulette类。
轮盘抽象类-Roulette
之所以定义这个抽象类
java
复制代码
public abstract class Roulette { // 链表数据-主要用于存储每个延时任务节点 List<TimewheelTask> tasks = null; // 游标指针索引 protected int index; // 时间轮轮盘的容量大小，如果是分钟级别，一般就是60个格 protected int capacity; // 时间轮轮盘的层级，如果是一级，它的上级就是二级 protected Integer level; private AtomicInteger num = new AtomicInteger(0); // 构造器 public Roulette(int capacity, Integer level) { this.capacity = capacity; this.level = level; this.tasks = new ArrayList<>(capacity); this.index = 0; } // 获取当前下表的索引对应的时间轮的任务 public TimewheelTask getTask() { return tasks.get(index); } // init初始化操作机制 public List<TimewheelTask> init() { long interval = MathTool.power((capacity + 1), level); long add = 0; TimewheelTask delayTask = null; for (int i = 0; i < capacity; i++) { add += interval; if (level == 0) { delayTask = new DefaultDelayTask(level); } else { delayTask = new SplitDelayTask(level); } //已经转换为最小的时间间隔 delayTask.setDelay(add, TimeUnitProvider.getTimeUnit()); tasks.add(delayTask); } return tasks; } // 索引下标移动 public void indexAdd() { this.index++; if (this.index >= capacity) { this.index = 0; } } // 添加对应的任务到对应的队列里面 public void addTask(TimewheelTask task) { tasks.add(task); } // 给子类提供的方法进行实现对应的任务添加功能 public abstract void addTask(int interval, MyTask task); }
时间轮盘的熟悉信息介绍
链表数据-主要用于存储每个延时任务节点。
java
复制代码
List<TimewheelTask> tasks = null;
tasks也可以改成双向链表 + 数组的结构：即节点存贮的对象中有指针，组成环形，可以通过数组的下标灵活访问每个节点，类似 LinkedHashMap。
游标指针索引
java
复制代码
protected int index;
时间轮轮盘的容量大小，如果是分钟级别，一般就是60个格
java
复制代码
protected int capacity;
时间轮轮盘的层级，如果是一级，它的上级就是二级
java
复制代码
protected Integer level;
init初始化时间轮轮盘对象模型，主要用于分配分配每一个轮盘上面元素的TimewheelTask，用于延时队列的执行任务线程，已经分配对应的每一个节点的延时时间节点数据。
java
复制代码
public List<TimewheelTask> init() { // 那么整个时间轮的总体时间跨度（interval） long interval = MathTool.power((capacity + 1), level); long add = 0; TimewheelTask delayTask = null; for (int i = 0; i < capacity; i++) { add += interval; if (level == 0) { delayTask = new ExecuteTimewheelTask(level); } else { delayTask = new MoveTimewheelTask(level); } //已经转换为最小的时间间隔 delayTask.setDelay(add, TimeUnitProvider.getTimeUnit()); tasks.add(delayTask); } return tasks; }
- 整数a的n次幂：interval，计算跨度，主要是各级别之间属于平方倍数
例如，第一层：20 ，第二层：20^2 ......
java
复制代码
//例如 n=7 二进制 0 1 1 1 //a的n次幂 = a的2次幂×a的2次幂 × a的1次幂×a的1次幂 ×a public static long power(long a, int n) { int rtn = 1; while (n >= 1) { if((n & 1) == 1){ rtn *= a; } a *= a; n = n >> 1; } return rtn; }
TimeUnitProvider工具类
主要用于计算时间单位操作的转换
javas
复制代码
public class TimeUnitProvider { private static TimeUnit unit = TimeUnit.SECONDS; public static TimeUnit getTimeUnit() { return unit; } }
代码简介：
- interval：代表着初始化的延时时间数据值，主要用于不同的层次的出发时间数据
- for (int i = 0; i < capacity; i++) ：代表着进行for循环进行添加对应的延时队列任务到集合中
- add += interval，主要用于添加对应的延时队列的延时数据值！并且分配给当前轮盘得到所有数据节点。
获取当前下标的索引对应的时间轮的任务节点
java
复制代码
public TimewheelTask getTask() { return tasks.get(index); }
层级时间轮的Bucket数据桶
在这里我们建立了一个TimewheelBucket类实现了Roulette轮盘模型，从而进行建立对应的我们的层级时间轮的数据模型，并且覆盖了addTask方法。
java
复制代码
public class TimewheelBucket extends Roulette { public TimewheelBucket(int capacity, Integer level) { super(capacity, level); } public synchronized void addTask(int interval, MyTask task) { interval -= 1; int curIndex = interval + this.index; if (curIndex >= capacity) { curIndex = curIndex - capacity; } tasks.get(curIndex).addTask(task); } }
添加addTask方法，进行获取计算对应的下标，并且此方法add操作才是对外开发调用的，在这里，我们主要实现了根据层级计算出对应的下标进行获取对应的任务执行调度点，将我们外界BizTask，真正的业务操作封装到这个BizTask模型，交由我们的系统框架进行执行。
java
复制代码
public synchronized void addTask(int interval, BizTask task) { interval -= 1; int curIndex = interval + this.index; if (curIndex >= capacity) { curIndex = curIndex - capacity; } tasks.get(curIndex).addTask(task); }
时间轮轮盘上的任务点
我们针对于时间轮轮盘的任务点进行设计和定义对应的调度执行任务模型。一个调度任务点，可以帮到关系到多个BizTask，也就是用户提交上来的业务任务线程对象，为了方便采用延时队列的延时处理模式，再次实现了Delayed这个接口，对应的实现代码如下所示：
Delayed接口
java
复制代码
public interface Delayed extends Comparable<Delayed> { /** * Returns the remaining delay associated with this object, in the * given time unit. * * @param unit the time unit * @return the remaining delay; zero or negative values indicate * that the delay has already elapsed */ long getDelay(TimeUnit unit); }
金石推荐 | 【算法数据结构专题】「延时队列算法」史上手把手教你针对层级时间轮（TimingWheel）实现延时队列的开发实战落地（下）（二）https://developer.aliyun.com/article/1471002
