時間輪算法HashedWheelTimer處理定時任務

前言

 最近部落客在研究螞蟻金服sofastack平台的sofa-jraft架構，其中涉及到選舉部分的定時任務實作HashedWheelTimer，拿出來單獨整理一下，其也是netty處理大量連接配接逾時的心跳檢測實作。

算法描述

關于時間輪算法，有點類似于HashMap。在new 一個HashedWheelTimer執行個體的時候，可以傳入幾個參數。

第一，一個時間長度，這個時間長度跟具體任務何時執行沒有關系，但是跟執行精度有關。這個時間可以看作手表的指針循環一圈的長度。

然後第二，刻度數。這個可以看作手表的刻度。比如第一個參數為24小時，刻度數為12，那麼每一個刻度表示2小時。時間精度隻能到兩小時。時間長度/刻度數值越大，精度越大。=

然後添加一個任務的時候，根據hash算法得到hash值并對刻度數求模得到一個下标，這個下标就是刻度的位置。

然而有一些任務的執行周期超過了第一個參數，比如超過了24小時，就會得到一個圈數round。

簡點說，添加一個任務時會根據任務得到一個hash值，并根據時間輪長度和刻度得到一個商值round和模index，比如時間長度24小時，刻度為12，延遲時間為32小時，那麼round=1,index=8。時間輪從開啟之時起每24/12個時間走一個指針，即index+1,第一圈round=0。當走到第7個指針時，此時index=7，此時剛才的任務并不能執行，因為剛才的任務round=1,必須要等到下一輪index=7的時候才能執行。

測試案例

/**
     * 每5秒執行一次
     * @param args
     */
    public static void main(String[] args) {
        final Timer timer = new HashedWheelTimer(Executors.defaultThreadFactory(),5,TimeUnit.SECONDS,2);
        TimerTask task = new TimerTask() {
            @Override
            public void run(Timeout timeout) throws Exception {
                System.out.println("task=========>>>>>>>>");
                timer.newTimeout(this,5,TimeUnit.SECONDS);
            }
        };

        timer.newTimeout(task,5,TimeUnit.SECONDS);

    }      

 參考

https://blog.csdn.net/nmgrd/article/details/77199666

https://www.cnblogs.com/eryuan/p/7955677.html