基于时间轮定时器实现延迟超时

一丶时间轮是什么？

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

fig:

概念：时间轮算法可以简单的看成一个循环数组+双向链表的数据结构实现的。
循环数组构成一个环形结构，指针每隔 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时间轮源码详解有兴趣的可以看看