一、示例代碼

?

HashedWheelTimer時(shí)間輪是一個(gè)高性能，低消耗的數(shù)據(jù)結(jié)構(gòu)，它適合用非準(zhǔn)實(shí)時(shí)，延遲的短平快任務(wù)，例如心跳檢測(cè)。

時(shí)間輪是一種非常驚艷的數(shù)據(jù)結(jié)構(gòu)。其在Linux內(nèi)核中使用廣泛，是Linux內(nèi)核定時(shí)器的實(shí)現(xiàn)方法和基礎(chǔ)之一。Netty內(nèi)部基于時(shí)間輪實(shí)現(xiàn)了一個(gè)HashedWheelTimer來優(yōu)化I/O超時(shí)的檢測(cè)，

由于Netty動(dòng)輒管理100w+的連接，每一個(gè)連接都會(huì)有很多超時(shí)任務(wù)。比如發(fā)送超時(shí)、心跳檢測(cè)間隔等，如果每一個(gè)定時(shí)任務(wù)都啟動(dòng)一個(gè)Timer，不僅低效，而且會(huì)消耗大量的資源。
在Netty中的一個(gè)典型應(yīng)用場(chǎng)景是判斷某個(gè)連接是否idle，如果idle（如客戶端由于網(wǎng)絡(luò)原因?qū)е碌椒?wù)器的心跳無法送達(dá)），則服務(wù)器會(huì)主動(dòng)斷開連接，釋放資源。得益于Netty NIO的優(yōu)異性能，基于Netty開發(fā)的服務(wù)器可以維持大量的長(zhǎng)連接，單臺(tái)8核16G的云主機(jī)可以同時(shí)維持幾十萬長(zhǎng)連接，及時(shí)掐掉不活躍的連接就顯得尤其重要。

HashedWheelTimer本質(zhì)是一種類似延遲任務(wù)隊(duì)列的實(shí)現(xiàn)，那么它的特點(diǎn)就是上述所說的，適用于對(duì)時(shí)效性不高的，可快速執(zhí)行的，大量這樣的“小”任務(wù)，能夠做到高性能，低消耗。
例如：

• 心跳檢測(cè)
• session、請(qǐng)求是否timeout
  業(yè)務(wù)場(chǎng)景則有：
• 用戶下單后發(fā)短信
• 下單之后15分鐘，如果用戶不付款就自動(dòng)取消訂單

@Slf4j public class HashWheelTimerTest {int nIndex = 0;public void testHashWheelTimer(){log.debug(" hash wheel time--> start." );HashedWheelTimer hashedWheelTimer = new HashedWheelTimer();for (int i = 0; i < 10; i++) {hashedWheelTimer.newTimeout(new TimerTask() {@Overridepublic void run(Timeout timeout) throws Exception {log.debug(" wheel timer run nIndex:{},timeout:{}",nIndex++,timeout.isExpired() );}},i + 1 ,TimeUnit.SECONDS);}log.debug(" hash wheel time--> end." );}public static void main(String[] args) {HashWheelTimerTest hashWheelTimerTest = new HashWheelTimerTest();hashWheelTimerTest.testHashWheelTimer();try {System.in.read();} catch (IOException e) {e.printStackTrace();}} }

二、創(chuàng)建時(shí)間輪定時(shí)器對(duì)象

1.類成員變量分析

tick，時(shí)刻即輪上的指針，指向某一個(gè)格子
ticksPerWheel，輪盤一圈包含的格子數(shù)，也就是輪盤總刻度數(shù)
tickDuration，時(shí)刻間距，也就是指針走完一個(gè)格子的時(shí)長(zhǎng)，值越小，精度越高。
roundDuration，計(jì)時(shí)周期，輪盤指針走完一圈耗時(shí)，roundDuration=ticksPerWheel?tickDuration。當(dāng)任務(wù)的延期時(shí)長(zhǎng)delay超出計(jì)時(shí)周期時(shí)，任務(wù)放入對(duì)應(yīng)桶中的同時(shí)保存剩余圈數(shù)：roundsRemaining=delay / roundDuration
bucket，相鄰刻度之間為桶，桶中以鏈表或其他形式存放延時(shí)任務(wù)。當(dāng)指針走過該桶時(shí)，桶中超時(shí)的延時(shí)任務(wù)開始啟動(dòng)
?

public class HashedWheelTimer implements Timer {private final Worker worker = new Worker(); //任務(wù)執(zhí)行工作線程，實(shí)現(xiàn)runnableprivate final Thread workerThread; //工作線程對(duì)象。private final long tickDuration; //每個(gè)時(shí)鐘小格子的時(shí)間長(zhǎng)度。private final HashedWheelBucket[] wheel; //時(shí)間輪子數(shù)組，如果時(shí)鐘有512個(gè)格子，則這個(gè)值的長(zhǎng)度為512private final int mask; //時(shí)間輪數(shù)組長(zhǎng)度-1，用于計(jì)算任務(wù)位于哪個(gè)格子，進(jìn)行掩碼。private final CountDownLatch startTimeInitialized = new CountDownLatch(1);private final Queue<HashedWheelTimeout> timeouts = PlatformDependent.newMpscQueue(); // 待執(zhí)行的延時(shí)任務(wù)。private final long maxPendingTimeouts;private volatile long startTime; //工作線程開始時(shí)間。public HashedWheelTimer(ThreadFactory threadFactory,long tickDuration, TimeUnit unit, int ticksPerWheel, boolean leakDetection,long maxPendingTimeouts) {// Normalize ticksPerWheel to power of two and initialize the wheel.wheel = createWheel(ticksPerWheel);mask = wheel.length - 1;long duration = unit.toNanos(tickDuration);this.tickDuration = duration;workerThread = threadFactory.newThread(worker);this.maxPendingTimeouts = maxPendingTimeouts;}

2.添加任務(wù)分析， 這里就是把task加入到Queue<HashedWheelTimeout> timeouts這個(gè)待執(zhí)行的延遲任務(wù)隊(duì)列中。

public Timeout newTimeout(TimerTask task, long delay, TimeUnit unit) {long pendingTimeoutsCount = pendingTimeouts.incrementAndGet();start();long deadline = System.nanoTime() + unit.toNanos(delay) - startTime;HashedWheelTimeout timeout = new HashedWheelTimeout(this, task, deadline);timeouts.add(timeout);return timeout;}

?三、定時(shí)執(zhí)行任務(wù)。

? ? 1.由workThread中的worker這個(gè)對(duì)象來負(fù)責(zé)執(zhí)行。

時(shí)間輪運(yùn)行的時(shí)候首先會(huì)記錄一下啟動(dòng)時(shí)間（startTime），然后調(diào)用startTimeInitialized釋放外層的等待線程；

進(jìn)入dowhile循環(huán)，調(diào)用waitForNextTick睡眠等待到下一次的tick指針的跳動(dòng)，并返回當(dāng)前時(shí)間減去startTime作為deadline

由于mask= wheel.length -1 ，wheel是2的次方數(shù)，所以可以直接用tick & mask 計(jì)算出此次在wheel中的槽位

調(diào)用processCancelledTasks將cancelledTimeouts隊(duì)列中的任務(wù)取出來，并將當(dāng)前的任務(wù)從時(shí)間輪中移除

調(diào)用transferTimeoutsToBuckets方法將timeouts隊(duì)列中緩存的數(shù)據(jù)取出加入到時(shí)間輪中

運(yùn)行目前指針指向的槽位中的bucket鏈表數(shù)據(jù)

private final class Worker implements Runnable {private final Set<Timeout> unprocessedTimeouts = new HashSet<Timeout>();private long tick;@Overridepublic void run() {// Initialize the startTime.startTime = System.nanoTime();startTimeInitialized.countDown();do {final long deadline = waitForNextTick();if (deadline > 0) {int idx = (int) (tick & mask);processCancelledTasks();HashedWheelBucket bucket =wheel[idx];transferTimeoutsToBuckets();bucket.expireTimeouts(deadline);tick++;}} while (WORKER_STATE_UPDATER.get(HashedWheelTimer.this) == WORKER_STATE_STARTED);}

2.時(shí)間輪指針跳動(dòng)

private long waitForNextTick() {//計(jì)算下一個(gè)tick的時(shí)間，long deadline = tickDuration * (tick + 1);for (;;) {final long currentTime = System.nanoTime() - startTime;//根據(jù)當(dāng)前計(jì)算需要sleep的時(shí)間。這里加了999999是因?yàn)橄蛏先≌?毫秒，假如距離下一個(gè)tick的時(shí)間為2000010納秒，那如果sleep 2毫秒是不夠的，所以需要多sleep 1毫秒。long sleepTimeMs = (deadline - currentTime + 999999) / 1000000;//sleepTimeMs <=0 說明下一個(gè)tick的時(shí)間到了，說明上一個(gè)tick執(zhí)行的時(shí)間“太久”了，所以直接返回就好了，不需要sleepif (sleepTimeMs <= 0) {//currentTime == Long.MIN_VALUE 這個(gè)判斷不是很理解if (currentTime == Long.MIN_VALUE) {return -Long.MAX_VALUE;} else {return currentTime;}}//直接sleep等待try {Thread.sleep(sleepTimeMs);} catch (InterruptedException ignored) {//Worker被中斷，如果是關(guān)閉了則返回負(fù)數(shù)，表示不會(huì)執(zhí)行下一個(gè)tickif (WORKER_STATE_UPDATER.get(HashedWheelTimer.this) == WORKER_STATE_SHUTDOWN) {return Long.MIN_VALUE;}}}}

3.轉(zhuǎn)移任務(wù)到時(shí)間輪中

在調(diào)用時(shí)間輪的方法加入任務(wù)的時(shí)候并沒有直接加入到時(shí)間輪中，而是緩存到了timeouts隊(duì)列中，所以在運(yùn)行的時(shí)候需要將timeouts隊(duì)列中的任務(wù)轉(zhuǎn)移到時(shí)間輪數(shù)據(jù)的鏈表中

private void transferTimeoutsToBuckets() {//最多取隊(duì)列的100000的元素出來for (int i = 0; i < 100000; i++) {HashedWheelTimeout timeout = timeouts.poll();if (timeout == null) {// all processedbreak;}//如果timeout被取消了則不做處理if (timeout.state() == HashedWheelTimeout.ST_CANCELLED) {// Was cancelled in the meantime.continue;}//計(jì)算位于實(shí)踐論的層數(shù)long calculated = timeout.deadline / tickDuration;timeout.remainingRounds = (calculated - tick) / wheel.length;//就是timeout已經(jīng)到期了，也不能放到之前的tick中final long ticks = Math.max(calculated, tick); // Ensure we don't schedule for past.//計(jì)算所在bucket下標(biāo)，并放進(jìn)去int stopIndex = (int) (ticks & mask);HashedWheelBucket bucket = wheel[stopIndex];//又是類似鏈表插入節(jié)點(diǎn)的操作bucket.addTimeout(timeout);}}

在這個(gè)轉(zhuǎn)移方法中，寫死了一個(gè)循環(huán)，每次都只轉(zhuǎn)移10萬個(gè)任務(wù)。

然后根據(jù)HashedWheelTimeout的deadline延遲時(shí)間計(jì)算出時(shí)間輪需要運(yùn)行多少次才能運(yùn)行當(dāng)前的任務(wù)，如果當(dāng)前的任務(wù)延遲時(shí)間大于時(shí)間輪跑一圈所需要的時(shí)間，那么就計(jì)算需要跑幾圈才能到這個(gè)任務(wù)運(yùn)行。

最后計(jì)算出該任務(wù)在時(shí)間輪中的槽位，添加到時(shí)間輪的鏈表中。

4.運(yùn)行時(shí)間輪中的任務(wù)

當(dāng)指針跳到時(shí)間輪的槽位的時(shí)間，會(huì)將槽位的HashedWheelBucket取出來，然后遍歷鏈表，運(yùn)行其中到期的任務(wù)。

public void expireTimeouts(long deadline) {HashedWheelTimeout timeout = head;//把bucket的所有timeout取出來執(zhí)行while (timeout != null) {HashedWheelTimeout next = timeout.next;if (timeout.remainingRounds <= 0) {next = remove(timeout);if (timeout.deadline <= deadline) {//timeout的真正執(zhí)行timeout.expire();} else {// The timeout was placed into a wrong slot. This should never happen.throw new IllegalStateException(String.format("timeout.deadline (%d) > deadline (%d)", timeout.deadline, deadline));}//該timeout被取消了則移除掉 } else if (timeout.isCancelled()) {next = remove(timeout);//否則層數(shù)減一，等待下一輪的到來} else {timeout.remainingRounds --;}timeout = next;}}

HashedWheelBucket是一個(gè)鏈表，所以我們需要從head節(jié)點(diǎn)往下進(jìn)行遍歷。如果鏈表沒有遍歷到鏈表尾部那么就繼續(xù)往下遍歷。

獲取的timeout節(jié)點(diǎn)節(jié)點(diǎn)，如果剩余輪數(shù)remainingRounds大于0，那么就說明要到下一圈才能運(yùn)行，所以將剩余輪數(shù)減一；

如果當(dāng)前剩余輪數(shù)小于等于零了，那么就將當(dāng)前節(jié)點(diǎn)從bucket鏈表中移除，并判斷一下當(dāng)前的時(shí)間是否大于timeout的延遲時(shí)間，如果是則調(diào)用timeout的expire執(zhí)行任務(wù)。

總結(jié)

以上是生活随笔為你收集整理的HashedWheelTimer时间轮定时任务原理分析的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。