public interface Timer {

    /**
     * 啟動(dòng)時(shí)間輪
     * */
    void startTimeWheel();

    /**
     * 創(chuàng)建新的超時(shí)任務(wù)(必須先startTimeWheel完成后，才能創(chuàng)建新任務(wù))
     * @param task 超時(shí)時(shí)需要調(diào)度的自定義任務(wù)
     * @param delayTime 延遲時(shí)間
     * @param timeUnit 延遲時(shí)間delayTime的單位
     * */
    void newTimeoutTask(Runnable task, long delayTime, TimeUnit timeUnit);
}

/**
 * 參考netty實(shí)現(xiàn)的單層時(shí)間輪
 * */
public class MyHashedTimeWheel implements Timer{

    /**
     * 環(huán)形數(shù)組
     * */
    private final MyHashedTimeWheelBucket[] ringBucketArray;

    /**
     * 世間輪啟動(dòng)時(shí)的具體時(shí)間戳(單位：納秒nanos)
     * */
    private long startTime;

    /**
     * 是否已啟動(dòng)
     * */
    private final AtomicBoolean started = new AtomicBoolean(false);

    /**
     * 時(shí)間輪每次轉(zhuǎn)動(dòng)的時(shí)間(單位：納秒nanos)
     * (perTickTime越短，調(diào)度會更精確，但cpu開銷也會越大)
     * */
    private final long perTickTime;

    /**
     * 總tick數(shù)
     * */
    private long totalTick = 0;

    /**
     * 待處理任務(wù)的隊(duì)列
     * (多外部生產(chǎn)者寫入，時(shí)間輪內(nèi)的單worker消費(fèi)者讀取，所以netty的實(shí)現(xiàn)里使用了效率更高的MpscQueue，Mpsc即MultiProducerSingleConsumer)
     * */
    private final Queue<MyTimeoutTaskNode> unProcessTaskQueue = new LinkedBlockingDeque<>();

    /**
     * 用于實(shí)際執(zhí)行到期任務(wù)的線程池
     * */
    private final Executor taskExecutor;

    private Thread workerThread;

    /**
     * 構(gòu)造函數(shù)
     * */
    public MyHashedTimeWheel(int ringArraySize, long perTickTime, Executor taskExecutor) {
        this.ringBucketArray = new MyHashedTimeWheelBucket[ringArraySize];
        for(int i=0; i<ringArraySize; i++){
            // 初始化，填充滿時(shí)間輪喚醒數(shù)組
            this.ringBucketArray[i] = new MyHashedTimeWheelBucket();
        }

        this.perTickTime = perTickTime;
        this.taskExecutor = taskExecutor;
    }

    /**
     * 啟動(dòng)worker線程等初始化操作，必須執(zhí)行完成后才能正常工作
     * (簡單起見，和netty不一樣不是等任務(wù)被創(chuàng)建時(shí)才懶加載的，必須提前啟動(dòng))
     * */
    @Override
    public void startTimeWheel(){
        // 啟動(dòng)worker線程
        this.workerThread = new Thread(new Worker());
        this.workerThread.start();

        while (!this.started.get()){
            // 自旋循環(huán)，等待一會
        }

        System.out.println("startTimeWheel 啟動(dòng)完成:" + this.getClass().getSimpleName());
    }

    @Override
    public void newTimeoutTask(Runnable task, long delayTime, TimeUnit timeUnit){
        long deadline = System.nanoTime() + timeUnit.toNanos(delayTime);

        // Guard against overflow.
        if (delayTime > 0 && deadline < 0) {
            deadline = Long.MAX_VALUE;
        }

        MyTimeoutTaskNode newTimeoutTaskNode = new MyTimeoutTaskNode();
        newTimeoutTaskNode.setTargetTask(task);
        newTimeoutTaskNode.setDeadline(deadline);

        unProcessTaskQueue.add(newTimeoutTaskNode);
    }

    private final class Worker implements Runnable{

        @Override
        public void run() {
            MyHashedTimeWheel.this.startTime = System.nanoTime();

            // 啟動(dòng)
            MyHashedTimeWheel.this.started.set(true);

            // 簡單起見，不考慮優(yōu)雅啟動(dòng)和暫停的邏輯
            while (true){
                // 等待perTick
                waitForNextTick();

                // 在撈取當(dāng)前tick下需要處理的bucket前，先將加入到隊(duì)列中的任務(wù)轉(zhuǎn)移到環(huán)形數(shù)組中(可能包含在當(dāng)前tick下就要處理的任務(wù))
                transferTaskToBuckets();

                // 基于總tick數(shù)，對環(huán)形數(shù)組的長度取模，計(jì)算出當(dāng)前tick下需要處理的bucket桶的下標(biāo)
                int idx = (int) (MyHashedTimeWheel.this.totalTick % MyHashedTimeWheel.this.ringBucketArray.length);
                MyHashedTimeWheelBucket bucket = MyHashedTimeWheel.this.ringBucketArray[idx];
                // 處理當(dāng)前插槽內(nèi)的任務(wù)(遍歷鏈表中的所有任務(wù)，round全部減一，如果減為負(fù)數(shù)了則說明這個(gè)任務(wù)超時(shí)到期了，將其從鏈表中移除后并交給線程池執(zhí)行指定的任務(wù))
                bucket.expireTimeoutTask(MyHashedTimeWheel.this.taskExecutor);
                // 循環(huán)tick一次，總tick數(shù)自增1
                MyHashedTimeWheel.this.totalTick++;
            }
        }

        /**
         * per tick時(shí)鐘跳動(dòng)，基于Thread.sleep
         * */
        private void waitForNextTick(){
            // 由于Thread.sleep并不是絕對精確的被喚醒，所以只能通過(('總的tick數(shù)+1' * '每次tick的間隔') + '時(shí)間輪啟動(dòng)時(shí)間')來計(jì)算精確的下一次tick時(shí)間
            // 而不能簡單的Thread.sleep(每次tick的間隔)

            long nextTickTime = (MyHashedTimeWheel.this.totalTick + 1) * MyHashedTimeWheel.this.perTickTime
                            + MyHashedTimeWheel.this.startTime;

            // 因?yàn)閚extTickTime是納秒，sleep需要的是毫秒，需要保證納秒數(shù)過小時(shí)，導(dǎo)致直接計(jì)算出來的毫秒數(shù)為0
            // 因此(‘實(shí)際休眠的納秒數(shù)'+999999)/1000000,保證了納秒轉(zhuǎn)毫秒時(shí)，至少會是1毫秒，而不會出現(xiàn)sleep(0毫秒)令cpu空轉(zhuǎn)
            long needSleepTime = (nextTickTime - System.nanoTime() + 999999) / 1000000;
            try {
                // 比起netty，忽略了一些處理特殊場景bug的邏輯
                Thread.sleep(needSleepTime);
            } catch (InterruptedException ignored) {

            }
        }

        private void transferTaskToBuckets() {
            // 為了避免worker線程在一次循環(huán)中處理太多的任務(wù)，所以直接限制了一個(gè)最大值100000
            // 如果真的有這么多，就等到下次tick循環(huán)的時(shí)候再去做。
            // 因?yàn)檫@個(gè)操作是cpu密集型的，處理太多的話，可能導(dǎo)致無法在一個(gè)短的tick周期內(nèi)完成一次循環(huán)
            for (int i = 0; i < 100000; i++) {
                MyTimeoutTaskNode timeoutTaskNode = MyHashedTimeWheel.this.unProcessTaskQueue.poll();
                if (timeoutTaskNode == null) {
                    // 隊(duì)列為空了，直接結(jié)束
                    return;
                }

                // 計(jì)算到任務(wù)超時(shí)時(shí)，應(yīng)該執(zhí)行多少次tick
                // (和netty里的不一樣，這里的deadline是超時(shí)時(shí)間的絕對時(shí)間，所以需要先減去時(shí)間輪的startTime)
                // (netty中是生產(chǎn)者線程在add時(shí)事先減去了startTime，比起由worker線程統(tǒng)一處理效率更高，但個(gè)人覺得這里的寫法會更直觀)
                long totalTickWhenTimeout = (timeoutTaskNode.getDeadline() - MyHashedTimeWheel.this.startTime) / MyHashedTimeWheel.this.perTickTime;
                // 減去當(dāng)前時(shí)間輪已經(jīng)進(jìn)行過的tick數(shù)量
                long remainingTickWhenTimeout = (totalTickWhenTimeout - MyHashedTimeWheel.this.totalTick);
                // 因?yàn)橐淮螘r(shí)間輪旋轉(zhuǎn)會經(jīng)過ringBucketArray.length次tick，所以求個(gè)余數(shù)
                long remainingRounds = remainingTickWhenTimeout / MyHashedTimeWheel.this.ringBucketArray.length;
                // 計(jì)算出當(dāng)前任務(wù)需要轉(zhuǎn)多少圈之后才會超時(shí)
                timeoutTaskNode.setRounds(remainingRounds);

                // 如果傳入的deadline早于當(dāng)前系統(tǒng)時(shí)間，則totalTickWhenTimeout可能會小于當(dāng)前的totalTick
                // 這種情況下，讓這個(gè)任務(wù)在當(dāng)前tick下就立即超時(shí)而被調(diào)度是最合理的，而不能在求余后放到一個(gè)錯(cuò)誤的位置而等一段時(shí)間才調(diào)度（所以必須取兩者的最大值）
                final long ticks = Math.max(totalTickWhenTimeout, MyHashedTimeWheel.this.totalTick); // Ensure we don't schedule for past.
                // 如果能限制環(huán)形數(shù)組的長度為2的冪，則可以改為ticks & mask，位運(yùn)算效率更高
                int stopIndex = (int) (ticks % MyHashedTimeWheel.this.ringBucketArray.length);
                MyHashedTimeWheelBucket bucket = MyHashedTimeWheel.this.ringBucketArray[stopIndex];
                // 計(jì)算并找到應(yīng)該被放置的那個(gè)bucket后，將其插入當(dāng)前bucket指向的鏈表中
                bucket.addTimeout(timeoutTaskNode);
            }
        }
    }
}

/**
 * 時(shí)間輪環(huán)形數(shù)組下標(biāo)對應(yīng)的桶(保存一個(gè)超時(shí)任務(wù)MyTimeoutTaskNode的鏈表)
 * */
public class MyHashedTimeWheelBucket {

    private final LinkedList<MyTimeoutTaskNode> linkedList = new LinkedList<>();

    public void addTimeout(MyTimeoutTaskNode timeout) {
        linkedList.add(timeout);
    }

    /**
     * 遍歷鏈表中的所有任務(wù)，round全部減一，如果減為負(fù)數(shù)了則說明這個(gè)任務(wù)超時(shí)到期了，將其從鏈表中移除后并交給線程池執(zhí)行指定的任務(wù)
     * */
    public void expireTimeoutTask(Executor executor){
        Iterator<MyTimeoutTaskNode> iterator = linkedList.iterator();
        while(iterator.hasNext()){
            MyTimeoutTaskNode currentNode = iterator.next();
            long currentNodeRound = currentNode.getRounds();
            if(currentNodeRound <= 0){
                // 將其從鏈表中移除
                iterator.remove();
                // count小于等于0，說明超時(shí)了，交給線程池去異步執(zhí)行
                executor.execute(currentNode.getTargetTask());
            }else{
                // 當(dāng)前節(jié)點(diǎn)還未超時(shí)，round自減1
                currentNode.setRounds(currentNodeRound-1);
            }

            // 簡單起見，不考慮任務(wù)被外部自己取消的case(netty里的timeout.isCancelled())
        }
    }
}

public class MyTimeoutTaskNode {

    /**
     * 任務(wù)具體的到期時(shí)間(絕對時(shí)間)
     * */
    private long deadline;

    /**
     * 存儲在時(shí)間輪中，需要等待的輪次
     * (rounds在初始化后，每次時(shí)間輪轉(zhuǎn)動(dòng)一周便自減1，當(dāng)減為0時(shí)便代表當(dāng)前任務(wù)需要被調(diào)度)
     * */
    private long rounds;

    /**
     * 創(chuàng)建任務(wù)時(shí)，用戶指定的到期時(shí)進(jìn)行調(diào)度的任務(wù)
     * */
    private Runnable targetTask;

    public long getDeadline() {
        return deadline;
    }

    public void setDeadline(long deadline) {
        this.deadline = deadline;
    }

    public long getRounds() {
        return rounds;
    }

    public void setRounds(long rounds) {
        this.rounds = rounds;
    }

    public Runnable getTargetTask() {
        return targetTask;
    }

    public void setTargetTask(Runnable targetTask) {
        this.targetTask = targetTask;
    }
}

/**
 * 層次時(shí)間輪，會存在空轉(zhuǎn)問題
 * */
public class MyHierarchicalHashedTimerV1 implements Timer {

    /**
     * 是否已啟動(dòng)
     * */
    private AtomicBoolean started = new AtomicBoolean(false);

    /**
     * 世間輪啟動(dòng)時(shí)的具體時(shí)間戳(單位：納秒nanos)
     * */
    private long startTime;

    /**
     * 時(shí)間輪每次轉(zhuǎn)動(dòng)的時(shí)間(單位：納秒nanos)
     * (perTickTime越短，調(diào)度會更精確，但cpu開銷也會越大)
     * */
    private final long perTickTime;

    /**
     * 總tick數(shù)
     * */
    private long totalTick = 0;

    /**
     * 待處理任務(wù)的隊(duì)列
     * (多外部生產(chǎn)者寫入，時(shí)間輪內(nèi)的單worker消費(fèi)者讀取，所以netty的實(shí)現(xiàn)里使用了效率更高的MpscQueue，Mpsc即MultiProducerSingleConsumer)
     * */
    private final Queue<MyTimeoutTaskNode> unProcessTaskQueue = new LinkedBlockingDeque<>();

    /**
     * timer持有的最低層的時(shí)間輪
     * */
    private final MyHierarchicalHashedTimeWheelV1 lowestTimeWheel;

    /**
     * 構(gòu)造函數(shù)
     * */
    public MyHierarchicalHashedTimerV1(int ringArraySize, long perTickTime, Executor taskExecutor) {
        this.perTickTime = perTickTime;

        // 初始化最底層的時(shí)間輪
        this.lowestTimeWheel = new MyHierarchicalHashedTimeWheelV1(ringArraySize,perTickTime,taskExecutor,0);
    }

    /**
     * 啟動(dòng)worker線程等初始化操作，必須執(zhí)行完成后才能正常工作
     * (簡單起見，和netty不一樣不是等任務(wù)被創(chuàng)建時(shí)才懶加載的，必須提前啟動(dòng))
     * */
    @Override
    public void startTimeWheel(){
        // 啟動(dòng)worker線程
        new Thread(new Worker()).start();

        while (!this.started.get()){
            // 自旋循環(huán)，等待一會
        }

        System.out.println("startTimeWheel 啟動(dòng)完成:" + this.getClass().getSimpleName());
    }

    @Override
    public void newTimeoutTask(Runnable task, long delayTime, TimeUnit timeUnit){
        long deadline = System.nanoTime() + timeUnit.toNanos(delayTime);

        // Guard against overflow.
        if (delayTime > 0 && deadline < 0) {
            deadline = Long.MAX_VALUE;
        }

        MyTimeoutTaskNode newTimeoutTaskNode = new MyTimeoutTaskNode();
        newTimeoutTaskNode.setTargetTask(task);
        newTimeoutTaskNode.setDeadline(deadline);

        this.unProcessTaskQueue.add(newTimeoutTaskNode);
    }

    private final class Worker implements Runnable{

        @Override
        public void run() {
            MyHierarchicalHashedTimerV1.this.startTime = System.nanoTime();
            // 啟動(dòng)
            MyHierarchicalHashedTimerV1.this.started.set(true);

            // 簡單起見，不考慮優(yōu)雅啟動(dòng)和暫停的邏輯
            while (true){
                // 等待perTick
                waitForNextTick();

                // 在撈取當(dāng)前tick下需要處理的bucket前，先將加入到隊(duì)列中的任務(wù)轉(zhuǎn)移到時(shí)間輪中(可能包含在當(dāng)前tick下就要處理的任務(wù))
                // 層級時(shí)間輪內(nèi)部會做進(jìn)一步的分配(放不下的話就溢出到更上一層的時(shí)間輪)
                transferTaskToTimeWheel();

                // 推進(jìn)時(shí)間輪(層級時(shí)間輪內(nèi)部滿了一圈就會進(jìn)一步的推進(jìn)更上一層的時(shí)間輪)
                MyHierarchicalHashedTimerV1.this.lowestTimeWheel.advanceClockByTick(
                    (taskNode)->
                        // 參考kafka的寫法，避免Timer里的一些屬性被傳到各個(gè)bucket里面
                        MyHierarchicalHashedTimerV1.this.lowestTimeWheel
                            .addTimeoutTask(MyHierarchicalHashedTimerV1.this.startTime, taskNode)
                );

                // 循環(huán)tick一次，總tick數(shù)自增1
                MyHierarchicalHashedTimerV1.this.totalTick++;
            }
        }

        /**
         * per tick時(shí)鐘跳動(dòng)，基于Thread.sleep
         * */
        private void waitForNextTick(){
            // 由于Thread.sleep并不是絕對精確的被喚醒，所以只能通過(('總的tick數(shù)+1' * '每次tick的間隔') + '時(shí)間輪啟動(dòng)時(shí)間')來計(jì)算精確的下一次tick時(shí)間
            // 而不能簡單的Thread.sleep(每次tick的間隔)

            long nextTickTime = (MyHierarchicalHashedTimerV1.this.totalTick + 1) * MyHierarchicalHashedTimerV1.this.perTickTime
                + MyHierarchicalHashedTimerV1.this.startTime;

            // 因?yàn)閚extTickTime是納秒，sleep需要的是毫秒，需要保證納秒數(shù)過小時(shí)，導(dǎo)致直接計(jì)算出來的毫秒數(shù)為0
            // 因此(‘實(shí)際休眠的納秒數(shù)'+999999)/1000000,保證了納秒轉(zhuǎn)毫秒時(shí)，至少會是1毫秒，而不會出現(xiàn)sleep(0毫秒)令cpu空轉(zhuǎn)
            long needSleepTime = (nextTickTime - System.nanoTime() + 999999) / 1000000;
            
            try {
                // 比起netty，忽略了一些處理特殊場景bug的邏輯
                Thread.sleep(needSleepTime);
            } catch (InterruptedException ignored) {

            }
        }

        /**
         * 加入到隊(duì)列中的任務(wù)轉(zhuǎn)移到時(shí)間輪中
         * */
        private void transferTaskToTimeWheel() {
            // 為了避免worker線程在一次循環(huán)中處理太多的任務(wù)，所以直接限制了一個(gè)最大值100000
            // 如果真的有這么多，就等到下次tick循環(huán)的時(shí)候再去做。
            // 因?yàn)檫@個(gè)操作是cpu密集型的，處理太多的話，可能導(dǎo)致無法在一個(gè)短的tick周期內(nèi)完成一次循環(huán)
            for (int i = 0; i < 100000; i++) {
                MyTimeoutTaskNode timeoutTaskNode = MyHierarchicalHashedTimerV1.this.unProcessTaskQueue.poll();
                if (timeoutTaskNode == null) {
                    // 隊(duì)列為空了，直接結(jié)束
                    return;
                }

                // 層級時(shí)間輪內(nèi)部會做進(jìn)一步的分配(放不下的話就溢出到更上一層的時(shí)間輪)
                MyHierarchicalHashedTimerV1.this.lowestTimeWheel.addTimeoutTask(
                    MyHierarchicalHashedTimerV1.this.startTime, timeoutTaskNode);
            }
        }
    }
}

public class MyHierarchicalHashedTimeWheelV1 {

    private final MyHierarchyHashedTimeWheelBucketV1[] ringBucketArray;

    /**
     * 總tick數(shù)
     * */
    private long totalTick = 0;

    /**
     * 當(dāng)前時(shí)間輪所能承載的時(shí)間間隔
     * */
    private final long interval;

    /**
     * 時(shí)間輪每次轉(zhuǎn)動(dòng)的時(shí)間(單位：納秒nanos)
     * (perTickTime越短，調(diào)度會更精確，但cpu開銷也會越大)
     * */
    private final long perTickTime;

    /**
     * 上一層時(shí)間跨度更大的時(shí)間輪
     * */
    private MyHierarchicalHashedTimeWheelV1 overFlowWheel;

    /**
     * 用于實(shí)際執(zhí)行到期任務(wù)的線程池
     * */
    private final Executor taskExecutor;

    /**
     * 是否是最底層的時(shí)間輪（只有最底層的時(shí)間輪才真正的對任務(wù)進(jìn)行調(diào)度）
     * */
    private final int level;

    public MyHierarchicalHashedTimeWheelV1(int ringArraySize,long perTickTime, Executor taskExecutor,int level) {
        this.ringBucketArray = new MyHierarchyHashedTimeWheelBucketV1[ringArraySize];
        for(int i=0; i<ringArraySize; i++){
            // 初始化，填充滿時(shí)間輪喚醒數(shù)組
            this.ringBucketArray[i] = new MyHierarchyHashedTimeWheelBucketV1();
        }

        this.perTickTime = perTickTime;
        this.taskExecutor = taskExecutor;
        this.interval = perTickTime * ringArraySize;
        this.level = level;

        if(level > 0){
            this.totalTick = 1;
        }
    }

    /**
     * 當(dāng)前時(shí)間輪加入任務(wù)(溢出的話，則需要放到上一層的時(shí)間輪中)
     * */
    public void addTimeoutTask(long startTime, MyTimeoutTaskNode timeoutTaskNode){
        long deadline = timeoutTaskNode.getDeadline();

        // 當(dāng)前時(shí)間輪所能承載的最大絕對時(shí)間為：每個(gè)tick的間隔 * 插槽數(shù) + (基于startTime的當(dāng)前絕對時(shí)間)
        long currentWheelMaxRange = this.interval + (startTime + this.perTickTime * this.totalTick);

        if(deadline < currentWheelMaxRange){
            // 當(dāng)前時(shí)間輪能夠承載這個(gè)任務(wù)，無需放到上一層時(shí)間輪中

            // 計(jì)算到任務(wù)超時(shí)時(shí)，應(yīng)該執(zhí)行多少次tick
            // (和netty里的不一樣，這里的deadline是超時(shí)時(shí)間的絕對時(shí)間，所以需要先減去時(shí)間輪的startTime)
            // (netty中是生產(chǎn)者線程在add時(shí)事先減去了startTime，比起由worker線程統(tǒng)一處理效率更高，但個(gè)人覺得這里的寫法會更直觀)
            long totalTickWhenTimeout = (deadline - startTime) / this.perTickTime;

            // 如果傳入的deadline早于當(dāng)前系統(tǒng)時(shí)間，則totalTickWhenTimeout可能會小于當(dāng)前的totalTick
            // 這種情況下，讓這個(gè)任務(wù)在當(dāng)前tick下就立即超時(shí)而被調(diào)度是最合理的，而不能在求余后放到一個(gè)錯(cuò)誤的位置而等一段時(shí)間才調(diào)度（所以必須取兩者的最大值）
            final long ticks = Math.max(totalTickWhenTimeout, this.totalTick); // Ensure we don't schedule for past.
            // 如果能限制環(huán)形數(shù)組的長度為2的冪，則可以改為ticks & mask，位運(yùn)算效率更高
            int stopIndex = (int) (ticks % this.ringBucketArray.length);

            MyHierarchyHashedTimeWheelBucketV1 bucket = this.ringBucketArray[stopIndex];
            // 計(jì)算并找到應(yīng)該被放置的那個(gè)bucket后，將其插入當(dāng)前bucket指向的鏈表中
            bucket.addTimeout(timeoutTaskNode);
        }else{
            // 當(dāng)前時(shí)間輪無法承載這個(gè)任務(wù)，需要放到上一層時(shí)間輪中

            // 上層時(shí)間輪不存在，創(chuàng)建之
            if(this.overFlowWheel == null){
                // 上層時(shí)間輪的環(huán)形數(shù)組大小保持不變，perTick是當(dāng)前時(shí)間輪的整個(gè)間隔(類似低層的60秒等于上一層的1分鐘)
                this.overFlowWheel = new MyHierarchicalHashedTimeWheelV1(
                    this.ringBucketArray.length, this.interval, taskExecutor,this.level+1);
            }

            // 加入到上一層的時(shí)間輪中(對于較大的deadline，addTimeoutTask操作可能會遞歸數(shù)次，放到第N層的時(shí)間輪中)
            this.overFlowWheel.addTimeoutTask(startTime,timeoutTaskNode);
        }
    }

    public void advanceClockByTick(Consumer<MyTimeoutTaskNode> flushInLowerWheelFn){
        // 基于總tick數(shù)，對環(huán)形數(shù)組的長度取模，計(jì)算出當(dāng)前tick下需要處理的bucket桶的下標(biāo)
        int idx = (int) (this.totalTick % this.ringBucketArray.length);

        MyHierarchyHashedTimeWheelBucketV1 bucket = this.ringBucketArray[idx];

        if(this.level == 0){
            // 如果是最底層的時(shí)間輪，將當(dāng)前tick下命中的bucket中的任務(wù)丟到taskExecutor中執(zhí)行
            bucket.expireTimeoutTask(this.taskExecutor);
        }else{
            // 如果不是最底層的時(shí)間輪，將當(dāng)前tick下命中的bucket中的任務(wù)交給下一層的時(shí)間輪
            // 這里轉(zhuǎn)交到下一層有兩種方式：第一種是從上到下的轉(zhuǎn)交，另一種是當(dāng)做新任務(wù)一樣還是從最下層的時(shí)間輪開始放，放不下再往上溢出
            // 選用后一種邏輯，最大的復(fù)用已有的創(chuàng)建新任務(wù)的邏輯，會好理解一點(diǎn)
            bucket.flush(flushInLowerWheelFn);
        }

        // 當(dāng)前時(shí)間輪的總tick自增1
        this.totalTick++;

        // 當(dāng)前時(shí)間輪的總tick數(shù)滿了一圈之后，推進(jìn)上一層時(shí)間輪進(jìn)行一次tick(如果上一層時(shí)間輪存在的話)
        if(this.totalTick % this.ringBucketArray.length == 0 && this.overFlowWheel != null){
            this.overFlowWheel.advanceClockByTick(flushInLowerWheelFn);
        }
    }
}

/**
 * 時(shí)間輪環(huán)形數(shù)組下標(biāo)對應(yīng)的桶(保存一個(gè)超時(shí)任務(wù)MyTimeoutTaskNode的鏈表)
 * */
public class MyHierarchyHashedTimeWheelBucketV1 {

    private final LinkedList<MyTimeoutTaskNode> linkedList = new LinkedList<>();

    public void addTimeout(MyTimeoutTaskNode timeout) {
        linkedList.add(timeout);
    }

    /**
     * 遍歷鏈表中的所有任務(wù)，round全部減一，如果減為負(fù)數(shù)了則說明這個(gè)任務(wù)超時(shí)到期了，將其從鏈表中移除后并交給線程池執(zhí)行指定的任務(wù)
     * */
    public void expireTimeoutTask(Executor executor){
        Iterator<MyTimeoutTaskNode> iterator = linkedList.iterator();
        while(iterator.hasNext()){
            MyTimeoutTaskNode currentNode = iterator.next();
            long currentNodeRound = currentNode.getRounds();
            if(currentNodeRound <= 0){
                // 將其從鏈表中移除
                iterator.remove();
                // count小于等于0，說明超時(shí)了，交給線程池去異步執(zhí)行
                executor.execute(currentNode.getTargetTask());
            }else{
                // 當(dāng)前節(jié)點(diǎn)還未超時(shí)，round自減1
                currentNode.setRounds(currentNodeRound-1);
            }

            // 簡單起見，不考慮任務(wù)被外部自己取消的case(netty里的timeout.isCancelled())
        }
    }

    /**
     * 將當(dāng)前bucket中的數(shù)據(jù)，通過flushInLowerWheelFn，全部轉(zhuǎn)移到更底層的時(shí)間輪中
     * */
    public void flush(Consumer<MyTimeoutTaskNode> flushInLowerWheelFn){
        Iterator<MyTimeoutTaskNode> iterator = linkedList.iterator();
        while(iterator.hasNext()){
            MyTimeoutTaskNode currentNode = iterator.next();
            // 先從鏈表中移除
            iterator.remove();
            // 通過flushInLowerWheelFn，轉(zhuǎn)移到更底層的時(shí)間輪中
            flushInLowerWheelFn.accept(currentNode);

            // 簡單起見，不考慮任務(wù)被外部自己取消的case(netty里的timeout.isCancelled())
        }
    }
}

public class MyHierarchicalHashedTimerV2 implements Timer {

    /**
     * 是否已啟動(dòng)
     * */
    private AtomicBoolean started = new AtomicBoolean(false);

    /**
     * 關(guān)聯(lián)的最底層時(shí)間輪
     * */
    private volatile MyHierarchicalHashedTimeWheelV2 lowestTimeWheel;

    /**
     * 時(shí)間輪的啟動(dòng)時(shí)間（單位:納秒）
     * */
    private long startTime;

    /**
     * 每次tick的間隔（單位:納秒）
     * */
    private final long perTickTime;

    /**
     * 時(shí)間輪的大小
     * */
    private final int timeWheelSize;

    /**
     * 用于實(shí)際執(zhí)行到期任務(wù)的線程池
     * */
    private final Executor taskExecutor;

    /**
     * 用于存儲bucket元素的延遲隊(duì)列，用于解決時(shí)間輪空轉(zhuǎn)的問題
     * */
    private final DelayQueue<MyHierarchyHashedTimeWheelBucketV2> bucketDelayQueue = new DelayQueue<>();

    public MyHierarchicalHashedTimerV2(int timeWheelSize,long perTickTime, Executor taskExecutor) {
        this.timeWheelSize = timeWheelSize;
        this.perTickTime = perTickTime;
        this.taskExecutor = taskExecutor;
    }

    /**
     * 啟動(dòng)worker線程等初始化操作，必須執(zhí)行完成后才能正常工作
     * (簡單起見，和netty不一樣不是等任務(wù)被創(chuàng)建時(shí)才懶加載的，必須提前啟動(dòng))
     * */
    @Override
    public void startTimeWheel(){
        // 啟動(dòng)worker線程
        new Thread(new Worker()).start();

        while (!this.started.get()){
            // 自旋循環(huán)，等待一會
        }

        System.out.println("startTimeWheel 啟動(dòng)完成:" + this.getClass().getSimpleName());
    }

    @Override
    public void newTimeoutTask(Runnable task, long delayTime, TimeUnit timeUnit){
        long deadline = System.nanoTime() + timeUnit.toNanos(delayTime);

        // Guard against overflow.
        if (delayTime > 0 && deadline < 0) {
            deadline = Long.MAX_VALUE;
        }

        MyTimeoutTaskNode newTimeoutTaskNode = new MyTimeoutTaskNode();
        newTimeoutTaskNode.setTargetTask(task);
        newTimeoutTaskNode.setDeadline(deadline);

        // 加入到最底層的時(shí)間輪中，當(dāng)前時(shí)間輪放不下的會溢出都上一層時(shí)間輪
        this.lowestTimeWheel.addTimeoutTask(newTimeoutTaskNode);
    }

    private void advanceClock(){
        try {
            MyHierarchyHashedTimeWheelBucketV2 bucket = this.bucketDelayQueue.take();
            lowestTimeWheel.advanceClockByTick(bucket.getExpiration());
            bucket.flush((node)->{
                // 當(dāng)前選中的bucket中的任務(wù)，重新插入到時(shí)間輪中
                // 1 原本處于高層的bucket中的任務(wù)會被放到更底層
                // 2 原本就處于最低一層的bucket中的任務(wù)會被直接執(zhí)行
                this.lowestTimeWheel.addTimeoutTask(node);
            });
            // 將當(dāng)前時(shí)間輪的數(shù)據(jù)
        } catch (Exception e) {
            // 忽略掉異常
            e.printStackTrace();
        }
    }


    private final class Worker implements Runnable {
        @Override
        public void run() {
            MyHierarchicalHashedTimerV2.this.startTime = System.nanoTime();

            // 初始化最底層的時(shí)間輪
            MyHierarchicalHashedTimerV2.this.lowestTimeWheel = new MyHierarchicalHashedTimeWheelV2(
                MyHierarchicalHashedTimerV2.this.startTime,
                MyHierarchicalHashedTimerV2.this.perTickTime,
                MyHierarchicalHashedTimerV2.this.timeWheelSize,
                MyHierarchicalHashedTimerV2.this.taskExecutor,
                MyHierarchicalHashedTimerV2.this.bucketDelayQueue
            );

            // 啟動(dòng)
            MyHierarchicalHashedTimerV2.this.started.set(true);

            while (true){
                // 一直無限循環(huán)，不斷推進(jìn)時(shí)間
                advanceClock();
            }
        }
    }
}

public class MyHierarchicalHashedTimeWheelV2 {

    /**
     * 上層時(shí)間輪（生產(chǎn)者/消費(fèi)者都會訪問到，volatile修飾）
     * */
    private volatile MyHierarchicalHashedTimeWheelV2 overflowTimeWheel;

    /**
     * 每次tick的間隔（單位:納秒）
     * */
    private final long perTickTime;

    /**
     * 時(shí)間輪環(huán)形數(shù)組
     * */
    private final MyHierarchyHashedTimeWheelBucketV2[] ringBucketArray;

    /**
     * 用于實(shí)際執(zhí)行到期任務(wù)的線程池
     * */
    private final Executor taskExecutor;

    /**
     * 時(shí)間輪的當(dāng)前時(shí)間
     * */
    private long currentTime;

    /**
     * 當(dāng)前時(shí)間輪的間隔(每次tick的時(shí)間 * 時(shí)間輪的大小)
     * */
    private final long interval;

    private final DelayQueue<MyHierarchyHashedTimeWheelBucketV2> bucketDelayQueue;

    public MyHierarchicalHashedTimeWheelV2(long startTime, long perTickTime, int wheelSize, Executor taskExecutor,
                                           DelayQueue<MyHierarchyHashedTimeWheelBucketV2> bucketDelayQueue) {
        // 初始化環(huán)形數(shù)組
        this.ringBucketArray = new MyHierarchyHashedTimeWheelBucketV2[wheelSize];
        for(int i=0; i<wheelSize; i++){
            this.ringBucketArray[i] = new MyHierarchyHashedTimeWheelBucketV2();
        }

        // 初始化時(shí)，當(dāng)前時(shí)間為startTime
        this.currentTime = startTime - (startTime % perTickTime);
        this.perTickTime = perTickTime;
        this.taskExecutor = taskExecutor;
        this.interval = perTickTime * wheelSize;
        this.bucketDelayQueue = bucketDelayQueue;
    }

    public void addTimeoutTask(MyTimeoutTaskNode timeoutTaskNode) {
        long deadline = timeoutTaskNode.getDeadline();
        if(deadline < this.currentTime + this.perTickTime){
            // 超時(shí)時(shí)間小于1tick，直接執(zhí)行
            this.taskExecutor.execute(timeoutTaskNode.getTargetTask());
        }else if(deadline < this.currentTime + this.interval){
            // 當(dāng)前時(shí)間輪放的下

            // 在超時(shí)時(shí)，理論上總共需要的tick數(shù)
            long totalTick = deadline / this.perTickTime;

            // 如果傳入的deadline早于當(dāng)前系統(tǒng)時(shí)間，則totalTickWhenTimeout可能會小于當(dāng)前的totalTick
            // 這種情況下，讓這個(gè)任務(wù)在當(dāng)前tick下就立即超時(shí)而被調(diào)度是最合理的，而不能在求余后放到一個(gè)錯(cuò)誤的位置而等一段時(shí)間才調(diào)度（所以必須取兩者的最大值）
            // 如果能限制環(huán)形數(shù)組的長度為2的冪，則可以改為ticks & mask，位運(yùn)算效率更高
            int stopIndex = (int) (totalTick % this.ringBucketArray.length);

            MyHierarchyHashedTimeWheelBucketV2 bucket = this.ringBucketArray[stopIndex];
            // 計(jì)算并找到應(yīng)該被放置的那個(gè)bucket后，將其插入當(dāng)前bucket指向的鏈表中
            bucket.addTimeout(timeoutTaskNode);

            // deadline先除以this.perTickTime再乘以this.perTickTime,可以保證放在同一個(gè)插槽下的任務(wù)，expiration都是一樣的
            long expiration = totalTick * this.perTickTime;
            boolean isNewRound = bucket.setExpiration(expiration);
            if(isNewRound){
                this.bucketDelayQueue.offer(bucket);
            }
        }else{
            // 當(dāng)前時(shí)間輪放不下
            if(this.overflowTimeWheel == null){
                createOverflowWheel();
            }

            // 加入到上層的時(shí)間輪中(較大的deadline會遞歸多次)
            this.overflowTimeWheel.addTimeoutTask(timeoutTaskNode);
        }
    }

    /**
     * 推進(jìn)當(dāng)前時(shí)間輪的時(shí)鐘
     * 舉個(gè)例子：假設(shè)當(dāng)前時(shí)間輪的當(dāng)前時(shí)間是第10分鐘，perTickTime是1分鐘，
     * 1.如果expiration是第10分鐘第1秒，則不用推動(dòng)當(dāng)前時(shí)間
     * 2.如果expiration是第11分鐘第0秒，則需要推動(dòng)當(dāng)前時(shí)間
     * */
    public void advanceClockByTick(long expiration){
        // 只會在tick推進(jìn)時(shí)才會被調(diào)用，參數(shù)expiration可以認(rèn)為是當(dāng)前時(shí)間輪的系統(tǒng)時(shí)間
        if(expiration >= this.currentTime + this.perTickTime){
            // 超過了1tick，則需要推進(jìn)當(dāng)前時(shí)間輪 (始終保持當(dāng)前時(shí)間是perTickTime的整數(shù)倍，邏輯上的totalTick)
            this.currentTime = expiration - (expiration % this.perTickTime);
            if(this.overflowTimeWheel != null){
                // 如果上層時(shí)間輪存在，則遞歸的繼續(xù)推進(jìn)
                this.overflowTimeWheel.advanceClockByTick(expiration);
            }
        }
    }

    private synchronized void createOverflowWheel(){
        if(this.overflowTimeWheel == null){
            // 創(chuàng)建上層時(shí)間輪，上層時(shí)間輪的perTickTime = 當(dāng)前時(shí)間輪的interval
            this.overflowTimeWheel = new MyHierarchicalHashedTimeWheelV2(
                this.currentTime, this.interval, this.ringBucketArray.length, this.taskExecutor, this.bucketDelayQueue);
        }
    }
}

public class MyHierarchyHashedTimeWheelBucketV2 implements Delayed {

    private final LinkedList<MyTimeoutTaskNode> taskList = new LinkedList<>();

    private final AtomicLong expiration = new AtomicLong(-1);

    public synchronized void addTimeout(MyTimeoutTaskNode timeout) {
        taskList.add(timeout);
    }

    public synchronized void flush(Consumer<MyTimeoutTaskNode> flush) {
        Iterator<MyTimeoutTaskNode> iterator = taskList.iterator();
        while (iterator.hasNext()){
            MyTimeoutTaskNode node = iterator.next();
            // 從當(dāng)前bucket中移除，轉(zhuǎn)移到更下層的時(shí)間輪中
            iterator.remove();
            flush.accept(node);

            // 簡單起見，不考慮任務(wù)被外部自己取消的case(netty里的timeout.isCancelled())
        }

        this.expiration.set(-1L);
    }

    /**
     * 設(shè)置當(dāng)前bucket的超時(shí)時(shí)間
     * @return 是否是一個(gè)新的bucket  true：是
     * */
    public boolean setExpiration(long expiration){
        long oldValue = this.expiration.getAndSet(expiration);

        // 如果不一樣，說明當(dāng)前的expiration已經(jīng)超過了原來的expiration一圈了，邏輯上不再是同一個(gè)bucket
        return oldValue != expiration;
    }

    public long getExpiration(){
        return this.expiration.get();
    }

    @Override
    public long getDelay(TimeUnit unit) {
        // 還剩余多少時(shí)間過期
        long delayNanos = Math.max(this.expiration.get() - System.nanoTime(), 0);

        // 將納秒單位基于unit轉(zhuǎn)換
        return unit.convert(delayNanos,TimeUnit.NANOSECONDS);
    }

    @Override
    public int compareTo(Delayed o) {
        if(o instanceof MyHierarchyHashedTimeWheelBucketV2){
            return Long.compare(this.expiration.get(),((MyHierarchyHashedTimeWheelBucketV2) o).expiration.get());
        }

        return 0;
    }
}