從定時任務說起

自然界中定時任務無處不在，太陽每天東升西落，候鳥的遷徙，樹木的年輪，人們每天按時上班，每個月按時發工資、交房租，四季輪換，潮漲潮落，等等，從某種意義上說，都可以認為是定時任務。

大概很少有人想過，這些“定時”是怎樣做到的。當然，計算機領域的同學們可能對此比較熟悉，畢竟工作中的定時任務也是無處不在的：每天凌晨備份一波數據庫，每天9點發一波郵件，每天定時發送任務通知。

至于怎么實現的？很簡單啊，操作系統的crontab，spring框架的quartz,實在不行JAVA自帶的ScheduledThreadPool、c#的System.Timers都可以很方便的做到定時任務的管理調度。

初識時間輪

大概去年的時候，業務需要實現一個時間調度的工具，定時生成報表，同組的哥們沒有采用任何框架，而是想了一個很取巧的辦法：

啟動時從DB讀取cron表達式解析，算出該任務下次執行的時間。

下次執行的時間 - 當前時間 = 時間差。

向ScheduleThreadPool線程池中提交一個延遲上面算出來的時間差的執行的任務。

任務執行時，算一下這個任務下次執行的時間，算時間差，提交到線程池。

當任務需要取消時，直接調用線程池返回的Future對象的cancel()方法就行了。

當時稍微想了一ScheduleThreadPool是怎么做到定時執行提交過來的任務的，大概有個模糊的概念，后來就把這事忘了。再后來，一次在博客園上看到一篇文章，講了一種叫做時間輪的定時任務調度思想，感覺想法很不錯，當年那個模糊的概念似乎清晰了很多，再后來，一個偶然的機會，網上搜了一下，竟然有一篇專門講解時間輪算法的論文，頓時興奮無比，趕緊打印下來，在上班的地鐵上讀了半個月，總算讀完了。

戳這里下載：《Hashed and Hierarchical Timing Wheels》

論文中的思路很簡單但也十分巧妙，對算法不斷地改進對比，各種操作系統，框架中的基于時間的調度算法都是基于時間輪的思想實現的。下面我們來看看，這個神奇的時間輪到底是怎樣實現定時任務的調度的。

絕對時間和相對時間

定時任務一般有兩種：

約定一段時間后執行。

約定某個時間點執行。

聰明的你會很快發現，這兩者之間可以相互轉換，比如給你個任務，要求12點執行，你看了一眼時間，發現現在是9點鐘，那么你可以認為這個任務三個小時候執行。

那么我們換個說話，給你個任務讓你3個小時后執行，你看了一眼現在是9點鐘，那么你當然可以認為這個任務12點鐘執行。

我們先來考慮一個簡單的情況，你接到三個任務A、B、C（都轉換成絕對時間），分別需要再3點鐘，4點鐘和9點鐘執行，正當百思不得其解時，不經意間你瞅了一眼墻上的鐘表，瞬間來了靈感，如醍醐灌頂，茅塞頓開：

如上圖中所示，我只需要把任務放到它需要被執行的時刻，然后等著時針轉到這個時刻時，取出該時刻放置的任務，執行就可以了。 這就是時間輪算法最核心的思想了。 什么？時針怎么轉？ while-true-sleep 下面讓我們一點一點增加復雜度。 ## 需要重復執行多次的任務 多數定時任務是需要重復執行，比如每天上午9點執行生成報表的任務。對于重復執行的任務，其實我們需要關心的只是下次執行時間，并不關心這個任務需要循環多少次，還是那每天上午9點的這個任務來說。 1. 比如現在是下午4點鐘，我把這個任務加入到時間輪，并設定當時針轉到明天上午九點(該任務下次執行的時間)時執行。 2. 時間來到了第二天上午九點，時間輪也轉到了9點鐘的位置，發現該位置有一個生成報表的任務，拿出來執行。 3. 同時時間輪發現這是一個循環執行的任務，于是把該任務重新放回到9點鐘的位置。 4. 重復步驟2和步驟3。 如果哪一天這個任務不需要再執行了，那么直接通知時間輪，找到這個任務的位置刪除掉就可以了。 由上面的過程我們可以看到，時間輪至少需要提供4個功能： 1. 加入任務 2. 執行任務 3. 刪除任務 4. 沿著時間刻度前進 ## 同一時刻存在多個任務 上面說的是同一個時刻只有一個任務需要執行的情況，更通用的情況顯然是同一時刻可能需要執行多個任務，比如每天上午九點除了生成報表之外，還需要執行發送郵件的任務，需要執行創建文件的任務，還需執行數據分析的任務等等，于是你剛才可能就比較好奇的時間輪的數據結構到現在可能更加好奇了，那我們先來說說時間輪的數據結構吧。 ### 時間輪的數據結構 首先，時鐘可以用數組或者循環鏈表表示，這個每個時鐘的刻度就是一個槽，槽用來存放該刻度需要執行的任務，如果有多個任務需要執行呢？每個槽里面放一個鏈表就可以了，就像下面圖中這樣：

同一時刻存在多個任務時，只要把該刻度對應的鏈表全部遍歷一遍，執行（扔到線程池中異步執行）其中的任務即可。

時間刻度不夠用怎么辦？

如果任務不只限定在一天之內呢？比如我有個任務，需要每周一上午九點執行，我還有另一個任務，需要每周三的上午九點執行。一種很容易想到的解決辦法是：

增大時間輪的刻度

一天24個小時，一周168個小時，為了解決上面的問題，我可以把時間輪的刻度（槽）從12個增加到168個，比如現在是星期二上午10點鐘，那么下周一上午九點就是時間輪的第9個刻度，這周三上午九點就是時間輪的第57個刻度，示意圖如下：

仔細思考一下，會發現這種設計方式存在幾個缺陷：

時間刻度太多會導致時間輪走到的多數刻度沒有任務執行，比如一個月就2個任務，我得移動720次，其中718次是無用功。

時間刻度太多會導致存儲空間變大，利用率變低，比如一個月就2個任務，我得需要大小是720的數組，如果我的執行時間的粒度精確到秒，那就更恐怖了。

于是乎，聰明的你腦袋一轉，想到另一個辦法：

列表中的任務中添加round屬性

這次我不增加時間輪的刻度了，刻度還是24個，現在有三個任務需要執行，

任務一每周二上午九點。

任務二每周四上午九點。

任務三每個月12號上午九點。

比如現在是9月11號星期二上午10點，時間輪轉一圈是24小時，到任務一下次執行（下周二上午九點）,需要時間輪轉過6圈后，到第7圈的第9個刻度開始執行。

任務二下次執行第3圈的第9個刻度，任務三是第2圈的第9個刻度。

示意圖如下：

時間輪每移動到一個刻度時，遍歷任務列表，把round值-1，然后取出所有round=0的任務執行。

這樣做能解決時間輪刻度范圍過大造成的空間浪費，但是卻帶來了另一個問題：時間輪每次都需要遍歷任務列表，耗時增加，當時間輪刻度粒度很小(秒級甚至毫秒級)，任務列表又特別長時，這種遍歷的辦法是不可接受的。

當然，對于大多數場景，這種方法還是適用的。

有沒有既節省空間，又節省時間的辦法呢？答案是有的，正如《Hashed and Hierarchical Timing Wheels》標題中提到的，有一種分層時間輪，可以解決做到既節省空間，又節省時間：

分層時間輪

分層時間輪是這樣一種思想：

針對時間復雜度的問題：不做遍歷計算round，凡是任務列表中的都應該是應該被執行的，直接全部取出來執行。

針對空間復雜度的問題：分層，每個時間粒度對應一個時間輪，多個時間輪之間進行級聯協作。

第一點很好理解，第二點有必要舉個例子來說明：

比如我有三個任務：

任務一每周二上午九點。

任務二每周四上午九點。

任務三每個月12號上午九點。

三個任務涉及到四個時間單位：小時、天、星期、月份。

拿任務三來說，任務三得到執行的前提是，時間刻度先得來到12號這一天，然后才需要關注其更細一級的時間單位：上午9點。

基于這個思想，我們可以設置三個時間輪：月輪、周輪、天輪。

月輪的時間刻度是天。

周輪的時間刻度是天。

天輪的時間刻度是小時。

初始添加任務時，任務一添加到天輪上，任務二添加到周輪上，任務三添加到月輪上。

三個時間輪以各自的時間刻度不停流轉。

當周輪移動到刻度2(星期二)時，取出這個刻度下的任務，丟到天輪上，天輪接管該任務，到9點執行。

同理，當月輪移動到刻度12(12號)時，取出這個刻度下的任務，丟到天輪上，天輪接管該任務，到9點執行。

這樣就可以做到既不浪費空間，又不浪費時間。

整體的示意圖如下所示：

時間輪的應用

時間輪的思想應用范圍非常廣泛，各種操作系統的定時任務調度，Crontab,還有基于java的通信框架Netty中也有時間輪的實現，幾乎所有的時間任務調度系統采用的都是時間輪的思想。

至于采用round型的時間輪還是采用分層時間輪，看實際需要吧，時間復雜度和實現復雜度的取舍。