金石推荐 | 【算法数据结构专题】「延时队列算法」史上手把手教你针对层级时间轮(TimingWheel)实现延时队列的开发实战落地(下)(一)

简介: 金石推荐 | 【算法数据结构专题】「延时队列算法」史上手把手教你针对层级时间轮(TimingWheel)实现延时队列的开发实战落地(下)

承接上文

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

相关文章
|
3天前
|
机器学习/深度学习 算法 存储
[数据结构]——算法的时间复杂度和空间复杂度
[数据结构]——算法的时间复杂度和空间复杂度
|
10天前
|
存储 监控 NoSQL
Redis处理大量数据主要依赖于其内存存储结构、高效的数据结构和算法,以及一系列的优化策略
【5月更文挑战第15天】Redis处理大量数据依赖内存存储、高效数据结构和优化策略。选择合适的数据结构、利用批量操作减少网络开销、控制批量大小、使用Redis Cluster进行分布式存储、优化内存使用及监控调优是关键。通过这些方法,Redis能有效处理大量数据并保持高性能。
33 0
|
1天前
|
算法 搜索推荐 Java
Java数据结构 -- 常见算法分析(查找算法、排序算法)精解详解!!!
Java数据结构 -- 常见算法分析(查找算法、排序算法)精解详解!!!
6 0
|
2天前
|
存储 搜索推荐 算法
C语言数据结构算法,常用10种排序实战
插入排序(Insertion Sort) 希尔排序(Shell Sort) 选择排序(Selection Sort) 冒泡排序(Bubble Sort) 归并排序(Merge Sort) 快速排序(Quick Sort) 堆排序(Heap Sort) 基数排序(Radix Sort)
8 1
C语言数据结构算法,常用10种排序实战
|
2天前
|
算法 安全 数据安全/隐私保护
AES算法逆向实战--某思路
本文是关于AES加密算法的逆向分析实战。通过跟栈方式找出加密位置,发现在`jslencode`函数中完成账号和密码加密。使用CryptoJS库,示例代码展示了如何用AES进行加密,其中`397151C04723421F`作为key,加密手机号和密码,并打印结果。
13 1
|
7天前
|
算法 搜索推荐 Java
滚雪球学Java(33):数组算法大揭秘:应用案例实战分享
【5月更文挑战第8天】🏆本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,希望能够助你一臂之力,帮你早日登顶实现财富自由🚀;同时,欢迎大家关注&&收藏&&订阅!持续更新中,up!up!up!!
34 8
滚雪球学Java(33):数组算法大揭秘:应用案例实战分享
|
8天前
|
算法 前端开发 Android开发
Android文字基线Baseline算法的使用讲解,Android开发面试题
Android文字基线Baseline算法的使用讲解,Android开发面试题
Android文字基线Baseline算法的使用讲解,Android开发面试题
|
9天前
|
缓存 算法 Java
数据结构~缓存淘汰算法--LRU算法(Java的俩种实现方式,万字解析
数据结构~缓存淘汰算法--LRU算法(Java的俩种实现方式,万字解析
|
10天前
|
机器学习/深度学习 算法 数据可视化
Python 数据结构和算法实用指南(四)(4)
Python 数据结构和算法实用指南(四)
19 1
|
10天前
|
机器学习/深度学习 存储 算法
Python 数据结构和算法实用指南(四)(3)
Python 数据结构和算法实用指南(四)
15 1