IT评测·应用市场-qidao123.com技术社区

标题: 【算法数据结构专题】「延时队列算法」史上手把手教你针对层级时间轮（Timi [打印本页]

---

作者: 冬雨财经    时间: 2023-4-8 20:33
标题: 【算法数据结构专题】「延时队列算法」史上手把手教你针对层级时间轮（Timi
承接上文

承接上一篇文章【算法数据结构专题】「延时队列算法」史上手把手教你针对层级时间轮（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

之所以定义这个抽象类

1. public abstract class Roulette {
2.         // 链表数据-主要用于存储每个延时任务节点
3.     List<TimewheelTask> tasks = null;
4.     // 游标指针索引
5.     protected int index;
6.         // 时间轮轮盘的容量大小，如果是分钟级别，一般就是60个格
7.     protected int capacity;
8.         // 时间轮轮盘的层级，如果是一级，它的上级就是二级
9.     protected Integer level;
10.     private AtomicInteger num = new AtomicInteger(0);
12.    // 构造器
13.     public Roulette(int capacity, Integer level) {
14.         this.capacity = capacity;
15.         this.level = level;
16.         this.tasks = new ArrayList<>(capacity);
17.         this.index = 0;
18.     }
19.     // 获取当前下表的索引对应的时间轮的任务
20.     public TimewheelTask getTask() {
21.         return tasks.get(index);
22.     }
23.    // init初始化操作机制
24.     public List<TimewheelTask> init() {
25.         long interval = MathTool.power((capacity + 1), level);
26.         long add = 0;
27.         TimewheelTask delayTask = null;
28.         for (int i = 0; i < capacity; i++) {
29.             add += interval;
30.             if (level == 0) {
31.                 delayTask = new DefaultDelayTask(level);
32.             } else {
33.                 delayTask = new SplitDelayTask(level);
34.             }
35.             //已经转换为最小的时间间隔
36.             delayTask.setDelay(add, TimeUnitProvider.getTimeUnit());
37.             tasks.add(delayTask);
38.         }
39.         return tasks;
40.     }
42.    // 索引下标移动
43.     public void indexAdd() {
44.         this.index++;
45.         if (this.index >= capacity) {
46.             this.index = 0;
47.         }
48.     }
49.    // 添加对应的任务到对应的队列里面
50.     public void addTask(TimewheelTask task) {
51.         tasks.add(task);
52.     }
53.         // 给子类提供的方法进行实现对应的任务添加功能
54.     public abstract void addTask(int interval, MyTask task);
55. }

复制代码

时间轮盘的熟悉信息介绍

链表数据-主要用于存储每个延时任务节点。

1. List<TimewheelTask> tasks = null;

复制代码

tasks也可以改成双向链表 + 数组的结构：即节点存贮的对象中有指针，组成环形，可以通过数组的下标灵活访问每个节点，类似 LinkedHashMap。

游标指针索引

1. protected int index;

复制代码

时间轮轮盘的容量大小，如果是分钟级别，一般就是60个格

1. protected int capacity;

复制代码

时间轮轮盘的层级，如果是一级，它的上级就是二级

1. protected Integer level;

复制代码

init初始化时间轮轮盘对象模型，主要用于分配分配每一个轮盘上面元素的TimewheelTask，用于延时队列的执行任务线程，已经分配对应的每一个节点的延时时间节点数据。

1. public List<TimewheelTask> init() {
2.            //  那么整个时间轮的总体时间跨度（interval）
3.         long interval = MathTool.power((capacity + 1), level);
4.         long add = 0;
5.         TimewheelTask delayTask = null;
6.         for (int i = 0; i < capacity; i++) {
7.             add += interval;
8.             if (level == 0) {
9.                 delayTask = new ExecuteTimewheelTask(level);
10.             } else {
11.                 delayTask = new MoveTimewheelTask(level);
12.             }
13.             //已经转换为最小的时间间隔
14.             delayTask.setDelay(add, TimeUnitProvider.getTimeUnit());
15.             tasks.add(delayTask);
16.         }
17.         return tasks;
18. }

复制代码

• 整数a的n次幂：interval，计算跨度，主要是各级别之间属于平方倍数
  

例如，第一层：20 ，第二层：20^2 ......

1.     //例如 n=7  二进制 0   1                 1          1
2.     //a的n次幂 = a的2次幂×a的2次幂  ×   a的1次幂×a的1次幂  ×a
3.     public static long power(long a, int n) {
4.         int rtn = 1;
5.         while (n >= 1) {
6.             if((n & 1) == 1){
7.                 rtn *= a;
8.             }
9.             a *= a;
10.             n = n >> 1;
11.         }
12.         return rtn;
13.     }

复制代码

TimeUnitProvider工具类

主要用于计算时间单位操作的转换

1. public class TimeUnitProvider {
2.     private static TimeUnit unit = TimeUnit.SECONDS;
3.     public static TimeUnit getTimeUnit() {
4.         return unit;
5.     }
6. }

复制代码

代码简介：

• interval：代表着初始化的延时时间数据值，主要用于不同的层次的出发时间数据
  
• for (int i = 0; i < capacity; i++) ：代表着进行for循环进行添加对应的延时队列任务到集合中
  
• add += interval，主要用于添加对应的延时队列的延时数据值！并且分配给当前轮盘得到所有数据节点。
  

获取当前下标的索引对应的时间轮的任务节点

1. public TimewheelTask getTask() {
2.         return tasks.get(index);
3. }

复制代码

层级时间轮的Bucket数据桶

在这里我们建立了一个TimewheelBucket类实现了Roulette轮盘模型，从而进行建立对应的我们的层级时间轮的数据模型，并且覆盖了addTask方法。

1. public class TimewheelBucket extends Roulette {
3.     public TimewheelBucket(int capacity, Integer level) {
4.         super(capacity, level);
5.     }
7.     public synchronized void addTask(int interval, MyTask task) {
8.         interval -= 1;
9.         int curIndex = interval + this.index;
10.         if (curIndex >= capacity) {
11.             curIndex = curIndex - capacity;
12.         }
13.         tasks.get(curIndex).addTask(task);
14.     }
15. }

复制代码

添加addTask方法，进行获取计算对应的下标，并且此方法add操作才是对外开发调用的，在这里，我们主要实现了根据层级计算出对应的下标进行获取对应的任务执行调度点，将我们外界BizTask，真正的业务操作封装到这个BizTask模型，交由我们的系统框架进行执行。

1.      public synchronized void addTask(int interval, BizTask task) {
2.         interval -= 1;
3.         int curIndex = interval + this.index;
4.         if (curIndex >= capacity) {
5.             curIndex = curIndex - capacity;
6.         }
7.         tasks.get(curIndex).addTask(task);
8.     }

复制代码

时间轮轮盘上的任务点


我们针对于时间轮轮盘的任务点进行设计和定义对应的调度执行任务模型。一个调度任务点，可以帮到关系到多个BizTask，也就是用户提交上来的业务任务线程对象，为了方便采用延时队列的延时处理模式，再次实现了Delayed这个接口，对应的实现代码如下所示：
Delayed接口

1. public interface Delayed extends Comparable<Delayed> {
2.     /**
3.      * Returns the remaining delay associated with this object, in the
4.      * given time unit.
5.      *
6.      * @param unit the time unit
7.      * @return the remaining delay; zero or negative values indicate
8.      * that the delay has already elapsed
9.      */
10.     long getDelay(TimeUnit unit);
11. }

复制代码

TimewheelTask时间轮刻度点

1. @Getter
2. public abstract class TimewheelTask implements Delayed {
3.     private List<BizTask> tasks = new ArrayList<BizTask>();
4.     private int level;
5.     private Long delay;
6.     private long calDelay;
7.     private TimeUnit calUnit;
8.     public TimewheelTask(int level) {
9.         this.level = level;
10.     }
11.     public void setDelay(Long delay, TimeUnit unit) {
12.         this.calDelay=delay;
13.         this.calUnit=unit;
14.     }
15.     public void calDelay() {
16.         this.delay = TimeUnit.NANOSECONDS.convert(this.calDelay, this.calUnit) + System.nanoTime();
17.     }
18.     public long getDelay(TimeUnit unit) {
19.         return this.delay - System.nanoTime();
20.     }
21.     public int compareTo(Delayed o) {
22.         long d = (getDelay(TimeUnit.NANOSECONDS) - o.getDelay(TimeUnit.NANOSECONDS));
23.         return (d == 0) ? 0 : ((d < 0) ? -1 : 1);
24.     }
25.     public void addTask(BizTask task) {
26.         synchronized (this) {
27.             tasks.add(task);
28.         }
29.     }
30.     public void clear() {
31.         tasks.clear();
32.     }
33.     public abstract void run();
34. }

复制代码

• 业务任务集合：private List tasks = new ArrayList();
  
  
  
  • 层级
    
  1. private int level;

  复制代码
  
  
  • 延时时间
    
  1.   private Long delay;

  复制代码
  
  
  • 实际用于延时计算的时间，就是底层是统一化所有的延时时间到对应的延时队列
    1. private long calDelay;

    复制代码
  • 实际用于延时计算的时间，就是底层是统一化所有的延时时间到对应的延时队列（用于统一化的时间单位）
    1. private TimeUnit calUnit;

    复制代码
  
  

添加对应的业务延时任务到轮盘刻度点

1.     public void addTask(BizTask task) {
2.         synchronized (this) {
3.             tasks.add(task);
4.         }
5.     }

复制代码

刻度点的实现类

因为对应的任务可能会需要将下游的业务任务进行升级或者降级，所以我们会针对于执行任务点分为，执行任务刻度点和跃迁任务刻度点两种类型。

• 执行任务延时队列刻度点
  

1. public class ExecuteTimewheelTask extends TimewheelTask {
2.     public ExecuteTimewheelTask(int level) {
3.         super(level);
4.     }
5.     //到时间执行所有的任务
6.     public void run() {
7.         List<BizTask> tasks = getTasks();
8.         if (CollectionUtils.isNotEmpty(tasks)) {
9.             tasks.forEach(task -> ThreadPool.submit(task));
10.         }
11.     }
12. }

复制代码

再次我们就定义执行这些任务的线程池为：

1.     private static ThreadPoolExecutor executor = new ThreadPoolExecutor(20, 100, 3, TimeUnit.MINUTES, new LinkedBlockingQueue<Runnable>(10000),
2.             new MyThreadFactory("executor"), new ThreadPoolExecutor.CallerRunsPolicy());

复制代码

• 跃迁任务延时队列刻度点
  

1. public class MoveTimewheelTask extends TimewheelTask {
2.     public MoveTimewheelTask(int level) {
3.         super(level);
4.     }
5.     //跃迁到其他轮盘，将对应的任务
6.     public void run() {
7.         List<BizTask> tasks = getTasks();
8.         if (CollectionUtils.isNotEmpty(tasks)) {
9.             tasks.forEach(task -> {
10.                 long delay = task.getDelay();
11.                 TimerWheel.adddTask(task,delay, TimeUnitProvider.getTimeUnit());
12.             });
13.         }
14.     }
15. }

复制代码

致辞整个时间轮轮盘的数据模型就定义的差不多了，接下来我们需要定义运行在时间轮盘上面的任务模型，BizTask基础模型。
BizTask基础模型

1. public abstract class BizTask implements Runnable {
2.      protected long interval;
3.      protected int index;
4.      protected long executeTime;
5.      public BizTask(long interval, TimeUnit unit, int index) {
6.           this.interval  = interval;
7.           this.index = index;
8.           this.executeTime= TimeUnitProvider.getTimeUnit().convert(interval,unit)+TimeUnitProvider.getTimeUnit().convert(System.nanoTime(),TimeUnit.NANOSECONDS);
9.      }
10.      public long getDelay() {
11.           return this.executeTime - TimeUnitProvider.getTimeUnit().convert(System.nanoTime(), TimeUnit.NANOSECONDS);
12.      }
13. }

复制代码

主要针对于任务执行，需要交给线程池去执行，故此，实现了Runnable接口。

• protected long interval;：跨度操作
  
• protected int index;：索引下表，在整个队列里面的下表处理
  
• protected long executeTime;：对应的执行时间
  

其中最重要的便是获取延时时间的操作，主要提供给框架的Delayed接口进行判断是否到执行时间了。

1.      public long getDelay() {
2.           return this.executeTime - TimeUnitProvider.getTimeUnit().convert(System.nanoTime(), TimeUnit.NANOSECONDS);
3.      }

复制代码

层级时间轮的门面TimerWheel

最后我们要进行定义和设计开发对应的整体的时间轮层级模型。

1. public class TimerWheel {
3.     private static Map<Integer, TimewheelBucket> cache = new ConcurrentHashMap<>();
4.     //一个轮表示三十秒
5.     private static int interval = 30;
6.     private static wheelThread wheelThread;
8.     public static void adddTask(BizTask task, Long time, TimeUnit unit) {
9.         if(task == null){
10.             return;
11.         }
12.         long intervalTime = TimeUnitProvider.getTimeUnit().convert(time, unit);
13.         if(intervalTime < 1){
14.             ThreadPool.submit(task);
15.             return;
16.         }
17.         Integer[] wheel = getWheel(intervalTime,interval);
18.         TimewheelBucket taskList = cache.get(wheel[0]);
19.         if (taskList != null) {
20.             taskList.addTask(wheel[1], task);
21.         } else {
22.             synchronized (cache) {
23.                 if (cache.get(wheel[0]) == null) {
24.                     taskList = new TimewheelBucket(interval-1, wheel[0]);
25.                     wheelThread.add(taskList.init());
26.                     cache.putIfAbsent(wheel[0],taskList);
27.                 }
28.             }
29.             taskList.addTask(wheel[1], task);
30.         }
31.     }
32.     static{
33.         interval = 30;
34.         wheelThread = new wheelThread();
35.         wheelThread.setDaemon(false);
36.         wheelThread.start();
37.     }
38.     private static Integer[] getWheel(long intervalTime,long baseInterval) {
39.         //转换后的延时时间
40.         if (intervalTime < baseInterval) {
41.             return new Integer[]{0, Integer.valueOf(String.valueOf((intervalTime % 30)))};
42.         } else {
43.             return getWheel(intervalTime,baseInterval,baseInterval, 1);
44.         }
45.     }
47.     private static Integer[] getWheel(long intervalTime,long baseInterval,long interval, int p) {
48.          long nextInterval = baseInterval * interval;
49.         if (intervalTime < nextInterval) {
50.             return new Integer[]{p, Integer.valueOf(String.valueOf(intervalTime / interval))};
51.         } else {
52.             return getWheel(intervalTime,baseInterval,nextInterval, (p+1));
53.         }
54.     }
56.     static class wheelThread extends Thread {
57.         DelayQueue<TimewheelTask> queue = new DelayQueue<TimewheelTask>();
59.         public DelayQueue<TimewheelTask> getQueue() {
60.             return queue;
61.         }
63.         public void add(List<TimewheelTask> tasks) {
64.             if (CollectionUtils.isNotEmpty(tasks)) {
65.                 tasks.forEach(task -> add(task));
66.             }
67.         }
69.         public void add(TimewheelTask task) {
70.             task.calDelay();
71.             queue.add(task);
72.         }
74.         @Override
75.         public void run() {
76.             while (true) {
77.                 try {
78.                     TimewheelTask task = queue.take();
79.                     int p = task.getLevel();
80.                     long nextInterval = MathTool.power(interval, Integer.valueOf(String.valueOf(MathTool.power(2, p))));
81.                     TimewheelBucket timewheelBucket = cache.get(p);
82.                     synchronized (timewheelBucket) {
83.                         timewheelBucket.indexAdd();
84.                         task.run();
85.                         task.clear();
86.                     }
87.                     task.setDelay(nextInterval, TimeUnitProvider.getTimeUnit());
88.                     task.calDelay();
89.                     queue.add(task);
90.                 } catch (InterruptedException e) {
92.                 }
93.             }
94.         }
95.     }
96. }

复制代码

TimerWheel的模型定义

1. private static Map<Integer, TimewheelBucket> cache = new ConcurrentHashMap<>();

复制代码

一个轮表示30秒的整体跨度。

1. private static int interval = 30;

复制代码

创建整体驱动的执行线程

1. private static wheelThread wheelThread;
3. static{
4.         interval = 30;
5.         wheelThread = new wheelThread();
6.         wheelThread.setDaemon(false);
7.         wheelThread.start();
8. }
10.     static class wheelThread extends Thread {
11.         DelayQueue<TimewheelTask> queue = new DelayQueue<TimewheelTask>();
12.         public DelayQueue<TimewheelTask> getQueue() {
13.             return queue;
14.         }
15.         public void add(List<TimewheelTask> tasks) {
16.             if (CollectionUtils.isNotEmpty(tasks)) {
17.                 tasks.forEach(task -> add(task));
18.             }
19.         }
20.         public void add(TimewheelTask task) {
21.             task.calDelay();
22.             queue.add(task);
23.         }
24.         @Override
25.         public void run() {
26.             while (true) {
27.                 try {
28.                     TimewheelTask task = queue.take();
29.                     int p = task.getLevel();
30.                     long nextInterval = MathTool.power(interval, Integer.valueOf(String.valueOf(MathTool.power(2, p))));
31.                     TimewheelBucket timewheelBucket = cache.get(p);
32.                     synchronized (timewheelBucket) {
33.                         timewheelBucket.indexAdd();
34.                         task.run();
35.                         task.clear();
36.                     }
37.                     task.setDelay(nextInterval, TimeUnitProvider.getTimeUnit());
38.                     task.calDelay();
39.                     queue.add(task);
40.                 } catch (InterruptedException e) {
42.                 }
43.             }
44.    }

复制代码

获取对应的时间轮轮盘模型体系

1.     private static Integer[] getWheel(long intervalTime,long baseInterval) {
2.         //转换后的延时时间
3.         if (intervalTime < baseInterval) {
4.             return new Integer[]{0, Integer.valueOf(String.valueOf((intervalTime % 30)))};
5.         } else {
6.             return getWheel(intervalTime,baseInterval,baseInterval, 1);
7.         }
8.     }
10.     private static Integer[] getWheel(long intervalTime,long baseInterval,long interval, int p) {
11.          long nextInterval = baseInterval * interval;
12.         if (intervalTime < nextInterval) {
13.             return new Integer[]{p, Integer.valueOf(String.valueOf(intervalTime / interval))};
14.         } else {
15.             return getWheel(intervalTime,baseInterval,nextInterval, (p+1));
16.         }
17.     }

复制代码

到这里相信大家，基本上应该是了解了如何去实现对应的时间轮盘的技术实现过程，有兴趣希望整个完整源码的，可以联系我哦。谢谢大家!

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

---

欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/)

Powered by Discuz! X3.4