基于时间轮实现延迟超时

2022-04-25

字数统计: 1.1k字 | 阅读时长≈ 4分

一丶时间轮是什么？

我的理解就是把通过算法生成一个钟表结构，每一个格子存放一个任务，可以设置每走动一步的时间，也可设置一圈有多少个格子。当设置时间大于一圈的时候我们可以进行圈数加一就够时分秒逻辑一样

概念：时间轮算法可以简单的看成一个循环数组+双向链表的数据结构实现的。
循环数组构成一个环形结构，指针每隔 tickDuration 时间走一步，每个数组上挂载一个双向链表结构的定时任务列表。

双向链表上的任务有个属性为 remainingRounds，即当前任务剩下的轮次是多少，每当指针走到该任务的位置时，remainingRounds 减 1，直到remainingRounds 为 0 时，定时任务触发。

通过时间轮算法的原理图我们可以知道，tickDuration 越小，定时任务越精确。

二丶使用环境

时间轮的使用例子：

需求：我向下给员工下发了一条指令，指令又会分成很多个任务。现在我需要新加一个超时功能，一个指令是否超时是取决于所有子任务是否完成来确定的。每增加一个子任务则增加一段超时时间。（实现任务的延迟超时方案）

三丶实现方式

我们可以基于netty提供的时间轮来实现。

1. 先创建一个时间轮工具类

package com.riker.timer.util;

import io.netty.util.HashedWheelTimer;
import io.netty.util.Timer;

import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

public class TimerUtil {

    private static volatile Timer timer;

    // Ban public construction
    private TimerUtil() {}

    /**
     * Returns the singleton hashed-wheel timer.
     *
     * @return hashed-wheel timer
     */
    public static Timer getTimer() {
        if (TimerUtil.timer == null) {
            initTimer();
        }
        return TimerUtil.timer;
    }

    private static synchronized void initTimer() {
        if (TimerUtil.timer == null) {
            final Timer timer = new HashedWheelTimer(Executors.defaultThreadFactory(), 1,
                    TimeUnit.MILLISECONDS, 10);
            TimerUtil.timer = timer;
        }
    }
}

tickDuration（HashedWheelTimer-2号位）：一个间隔时间（步长）
tickDuration（HashedWheelTimer-3号位）：间隔时间的单位
ticksPerWheel（HashedWheelTimer-3号位）：时间轮的大小

2. 处理逻辑编写

大致逻辑编写可参考：

package com.riker.timer;


import com.riker.timer.util.TimerUtil;
import io.netty.util.Timeout;
import io.netty.util.TimerTask;

import java.util.concurrent.TimeUnit;

public class Timer {
    public static void main(String[] args) throws InterruptedException{

        //TODO 创建超时任务时间
        long delay = getDelay(delayTask.getDelay(), delayTask.getTimeUnit());

        long diff = System.currentTimeMillis() - delayTask.getStartTime().getTime();

        delay = delay - diff;

        //TODO 如果任务已经超时则无需继续
        if (delay < 0) {
            log.info("延迟任务已超时,{}", SerializeUtil.toJson(delayTask));

            delayTask.setBizStatus(1);

            delayTaskInfoMapper.updateById(delayTask);

            delayTaskPushService.pushMessage(delayTask);

            return;
        }

        TimerTask timerTask = new TimerTask(){
            public void run(Timeout timeout) throws Exception {
                //TODO 获取超时任务
                DelayTaskInfo dbDelayTask = delayTaskInfoMapper.findByKey(delayTask.getTaskKey());
                //TODO 判断是否有超时任务
                if (dbDelayTask == null) {
                    log.error("超时任务记录不存在,key:{}", delayTask.getTaskKey());
                    return;
                }

                //TODO 如果任务没有被取消或者已经超时，则进行子任务判断
                if (dbDelayTask.getBizStatus() == 0) {// 没有取消或已经超时

                    //TODO 查询该指令的子任务
                    List<DelayChildrenTask> childList = delayChildrenTaskMapper
                            .findByTaskIdAndIsFinished(dbDelayTask.getId(), false);

                    // 在此处增加时间
                    if (childList != null && childList.size() > 0) {
                        long totalDelay = 0;
                        for (DelayChildrenTask child : childList) {
                            //TODO 判断这个子任务是否已经被使用过,没有使用则可延长超时时长
                            if (child.getIsUsed() == 0) { // 未使用
                                totalDelay += getDelay(child.getDelay(), child.getTimeUnit());
                                child.setIsUsed(1);
                            }
                        }
                        TimerUtil.getTimer().newTimeout(this, totalDelay, TimeUnit.MILLISECONDS);
                        //TODO 更新数据库逻辑
                        delayChildrenTaskService.saveOrUpdateBatch(childList);
                    } else {
                        //TODO 如果子任务全部完成则结束该指令，并推送超时任务完成消息
                        dbDelayTask.setBizStatus(1);
                        delayTaskInfoMapper.updateById(dbDelayTask);
                        delayTaskPushService.pushMessage(dbDelayTask);
                        log.info("推送超时任务完成,key:{}", dbDelayTask.getTaskKey());
                    }
                }
            }
        };
        //将定时任务放入时间轮
        TimerUtil.getTimer().newTimeout(timerTask, delay, TimeUnit.MILLISECONDS);
    }
}

netty时间轮源码详解有兴趣的可以看看

四丶时间轮定时器的优缺点

优点：时间轮是一种高效来利用线程资源来进行批量化调度的一种调度模型。把大批量的调度任务全部都绑定到同一个的调度器上面，使用这一个调度器来进行所有任务的管理（manager），触发（trigger）以及运行（runnable）。能够高效的管理各种延时任务，周期任务，通知任务等等。

缺点：时间轮的精度取决于每一格精度，精度越小误差越小，且时间轮无法备份，当服务器宕机时会丢失所有任务。

本文作者： GHOSTLaycoo
本文链接： http://example.com/2022/04/25/基于时间轮定时器实现延迟超时/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！