概述
? ? 這篇博文的起源在于阿里的公眾號里面有一篇文章講菜鳥的同學在造一個關(guān)于時間輪定時器的文章，然后在網(wǎng)上搜索資料發(fā)現(xiàn)其實在好多開源的軟件里面已經(jīng)有了，最后選擇了kafka里面的定時器實現(xiàn)來加深自己的理解。這個概念有點繞，我也盡量把核心的點講解清楚，博文末尾的兩旁參考文獻其實是講解的比較清楚的，我應(yīng)該會盜用里面的圖來實現(xiàn)來幫助自己把核心點講清楚。
? ? 在理解kafka的時間輪定時器的概念的時候，我們需要提前了解下java里面的DelayQueue的概念，因為在kafka的時間輪定時器其實是基于DelayQueue來實現(xiàn)的。
? ? 最后我希望一定要好好看博文末尾的參考文獻，將這篇博文+參考文獻就可以把時間輪理解的很清楚。
定時器選型
? ? 傳統(tǒng)方案
????????對于實現(xiàn)一個定時任務(wù)，一般的做法是將定時任務(wù)寫入數(shù)據(jù)庫，通過一個線程定時查詢出將要到期的任務(wù)，再執(zhí)行任務(wù)相關(guān)邏輯。該方案的優(yōu)點是實現(xiàn)簡單，尤其適合單機或者業(yè)務(wù)量比較小的場景來。但是缺點也很明顯：在分布式且業(yè)務(wù)量較大的場景中會引入很多復(fù)雜性。首先，需要設(shè)計一套合理的分庫分表邏輯，以及集群任務(wù)負載邏輯。其次，即使做到這些，也會由于某些場景定時任務(wù)時間集中在某個時間點，導致集群單節(jié)點壓力過大。再次，需要合理的預(yù)估容量，否則后續(xù)線性存儲擴容將會非常復(fù)雜。
? ? 我們的物流處罰其實就是采用類似的機制去實現(xiàn)掃描的，但是后來因為分庫等原因最后還是借用了rocketMq來實現(xiàn)的，與其說借用了rocketMq還不如說借用了rocketMq內(nèi)部的定時器的實現(xiàn)，在開源的4.x的rocketMq版本中其實本質(zhì)上還是用定時任務(wù)加隊列的方式來發(fā)現(xiàn)任務(wù)是否過期。
? ? 傳統(tǒng)的方法一個弊端就在于一般情況下我們按照過期粒度，譬如1分鐘、10分鐘、1小時、24時小時等粒度組裝Timer+隊列，然后同時有n個線程掃描各自的隊列，然后發(fā)現(xiàn)其中過期的進行處理，在大量掃描過程中其實很多任務(wù)可能還是沒有過期的，也就是說白白進行了掃描。那么時間輪在這方面是不是有了優(yōu)化呢。
????時間輪方案
? ??????時間輪方案將現(xiàn)實生活中的時鐘概念引入到軟件設(shè)計中，主要思路是定義一個時鐘周期（比如時鐘的12小時）和步長（比如時鐘的一秒走一次），當指針每走一步的時候，會獲取當前時鐘刻度上掛載的任務(wù)并執(zhí)行，整體結(jié)構(gòu)如圖1。
從上圖可以看到，對于時間的計算是交給一個類似時鐘的組件來做，而任務(wù)是通過一個指針或者引用去關(guān)聯(lián)某個刻度上到期的定時任務(wù)，這樣就能夠?qū)⒍〞r任務(wù)的存儲和時間進行解耦，時鐘組件難度不大，以何種方式存儲這些任務(wù)數(shù)據(jù)，是時間輪方案的關(guān)鍵。
? ? ? ? 我理解時間輪的好處在于如果時間輪的指針指到了對應(yīng)的格子，那么該格子指向的隊列里面的任務(wù)就都是過期的，可以減少很多不必要的無意義的掃描，至于為什么后面可以看分析。
kafka的時間輪
說明
? ? kafka的內(nèi)部Timer其實是自己實現(xiàn)的一個定時器（其實就是一個時間輪），對外提供兩個接口，一個接口是由外部調(diào)用添加任務(wù)add(TimerTask)，一個接口是由外部驅(qū)動時間輪輪轉(zhuǎn)（advanceClock），當發(fā)現(xiàn)任務(wù)過期以后則提交專門的任務(wù)線程去執(zhí)行。時間輪內(nèi)部的真正細節(jié)是下面這個圖。
說明
? ? 其實Timer內(nèi)部是有一個個TimingWheel來實現(xiàn)時間輪的，為什么會有多個時間輪呢，其實參考我們的時鐘就能理解，我們的時鐘有秒針（60s）、分針（60m）、時針（60h）。每走一圈代表的時間含義也不相同，所以就會存在多個時間輪了。
? ? 但是我們看到了上面有一個DelayedQueue這個java集合對象，其實它里面保存了所有的延遲任務(wù)，因為DelayedQueue本身內(nèi)部實現(xiàn)是一個有序的堆，我姑且這么認為，所以每次通過DelayedQueue去獲取隊首數(shù)據(jù)就是快要過期的數(shù)據(jù)。
? ? 在進入kafka時間輪源碼分析之前，我們需要提前知道的幾個概念：子時間輪，父時間輪，添加任務(wù)，消費任務(wù)等。
kafka時間輪流轉(zhuǎn)
? ? kafka時間輪的流轉(zhuǎn)其實按照我們上面分析其實分為兩個核心步驟，步驟一是任務(wù)添加過程，步驟二是執(zhí)行過期任務(wù)。
? ? 任務(wù)添加過程
? ? ? ? 我們用數(shù)組模擬時間輪（數(shù)組的每個元素是一個列表頭，添加任務(wù)就是往列表頭后面掛任務(wù)而已），數(shù)組的大小代表時間的格子數(shù)，添加過程中我們會通過 過期時間/時間輪格子代表時間 % 時間輪格子總數(shù) 算出的格子位置，然后通過掛鏈的方法添加到時間輪格子當中。
? ? ? ? 在這個過程中我們需要注意的是任務(wù)首先需要判斷當前時間輪是否放的下，判斷放得下的標準就是時間輪當前時間 + 一圈時間輪時間是否大于任務(wù)過期時間，如果大于就代表放的下，如果小于就代表無法放置那么就需要往上一層時間輪放置。
? ? ? ? 所有時間輪格子其實是放置在一個DelayQueue當中的。
? ? ? ? 整個邏輯過程的核心在于hash找時間輪格子的過程，具體可以看下面的源碼。
? ? 任務(wù)消費過程
? ? ? ? 每隔200ms去DelayQueue中以200ms的超時去獲取任務(wù)（這個過后在末尾的參考文章講解的很詳細），如果獲取到說明剛好有一堆超時任務(wù)需要處理，那么我們就將所有的任務(wù)直接投遞到過期任務(wù)處理的線程池當中。
? ? ? ?然后將時間輪的格子往前挪一步，挪一步的意思代表時間往前走了一步，然后我們更新當前時間輪的時間，這個時間哪里來的呢，時間就是剛剛我們處理的任務(wù)的過期時間。其實這個操作本質(zhì)上是更新時間輪的當前時間，譬如原理時間是10:00，然后我們處理完一個到期待執(zhí)行的任務(wù)后時間變成了10.40，這個10.40的時間就是代表了過期時間。
kafka時間輪源碼
說明：
????1、kafka時間輪的核心組成部分包括tickMs（時間格代表時間）、wheelSize（時間輪格子的數(shù)量）、startMs（時間輪開始時間）、taskCounter（任務(wù)個數(shù)）、delayQueue（延遲隊列）。
????2、我們每次通過從delayQueue中獲取過期任務(wù)，如果能夠獲取到過期任務(wù)說明時間輪往前進一格。
說明：
????1、前面提到過我們在添加任務(wù)失敗就開始執(zhí)行任務(wù)，那么添加任務(wù)失敗實際代表的是任務(wù)已經(jīng)到期了，對于添加任務(wù)其實是分幾種情況進行解釋的。
????2、如果 任務(wù)的過期時間 < 當前時間+單個時間格時間，那么我們?nèi)蝿?wù)該任務(wù)需要立刻執(zhí)行。
????3、如果 當前時間+單個時間格時間 <= 任務(wù)過期時間 < 當前時間+整個時間輪時間，那么我們首先通過 任務(wù)過期時間/時間格時間 代表應(yīng)該落在具體的哪個格子，但是因為時間輪一直在轉(zhuǎn)動，所以我們需要通過hash來確認應(yīng)該放在時間輪的哪個位置，最后我們需要設(shè)置最新的過期時間并把任務(wù)加入到delayedQueue當中，設(shè)置的過期時間是通過時間格代表的時間進行的歸一。
????4、這里有個疑問就是通過hash的方法計算落在具體的哪個時間格里面，會不會出現(xiàn)覆蓋的情況呢，假設(shè)我們的時間輪有20個格子，那么20%20=0，40%20=0，60%20=0，豈不是還是會存在落在同一個格子里面但是過期時間不一樣的情況嘛，其實不會的，為什么呢，因為我們在前面前置了時間，也就是說基于當前時間我只能放置一個時間輪周期的任務(wù)，超過一個時間輪周期的任務(wù)我們就會放置大父親時間輪當中。
說明：
? ? 1、其實父時間輪本質(zhì)上其時間格代表的時間是子時間輪一周代表的時間而已。
說明：
? ? 1、其實時間輪我們是用數(shù)組也就是buckets來實現(xiàn)的，也就是說一個數(shù)組代表時間輪。
? ? 2、時間輪中每個格子用來保存任務(wù)的數(shù)據(jù)結(jié)構(gòu)是TimeTaskList的數(shù)據(jù)結(jié)構(gòu)，其實就是一個雙向鏈表，然后每次在往某個時間輪格子里面放置任務(wù)也就是timerTaskEntry的時候就會掛置到TimeTaskList的這個對象當中去。
? ? 3、所以說我們放置到DelayedQueue當中其實是TimeTaskList對象，這個對象包含了同一過期時間的所有任務(wù)而已。減少了DelayedQueue的大小。
說明：
? ? 其實TimerTaskList對象就是一個雙向列表而已。
參考文獻
Kafka源碼深度解析－序列13 －Server核心組件之2(續(xù))－ TimingWheel本質(zhì)與DelayedOperationPurgatory核心結(jié)構(gòu)
