那些驚豔的算法們（三）—— 時間輪

從定時任務說起

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

大概很少有人想過，這些“定時”是怎樣做到的。當然，計算機領域的同學們可能對此比較熟悉，畢竟工作中的定時任務也是無處不在的：每天淩晨更新一波資料庫，每天9點發一波郵件，每隔10秒鐘搶一次火車票。。。

至于怎麼實作的？很簡單啊，作業系統的crontab，spring架構的quartz,實在不行Java自帶的ScheduledThreadPool都可以很友善的做到定時任務的管理排程。

當你熟練的敲下“* * 9 * * ?”等着神奇的事情發生時，你是否想過背後的“玄機”？

初識時間輪

大概去年的時候，業務需要實作一個時間排程的工具，定時生成報表，同組的哥們兒想了一個取巧的辦法：

1. 啟動時從DB讀取cron表達式解析，算出該任務下次執行的時間。
2. 下次執行的時間 - 目前時間 = 時間差。
3. 向ScheduleThreadPool線程池中送出一個延遲上面算出來的時間差的執行的任務。
4. 任務執行時，算一下這個任務下次執行的時間，算時間差，送出到線程池。

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

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

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

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

絕對時間和相對時間

定時任務一般有兩種：

1. 約定一段時間後執行。

2. 約定某個時間點執行。

   聰明的你會很快發現，這兩者之間可以互相轉換，比如給你個任務，要求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個刻度，示意圖如下：

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

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

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

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

清單中的任務中添加round屬性

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

1. 任務一每周二上午九點。
2. 任務二每周四上午九點。

3. 任務三每個月12号上午九點。

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

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

   示意圖如下：

時間輪每移動到一個刻度時，周遊任務清單，把round值-1，然後取出所有round=0的任務執行。

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

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

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

分層時間輪

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

1. 針對時間複雜度的問題：不做周遊計算round，凡是任務清單中的都應該是應該被執行的，直接全部取出來執行。

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

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

   比如我有三個任務：

3. 任務一每周二上午九點。
4. 任務二每周四上午九點。

5. 任務三每個月12号上午九點。

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

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

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

   月輪的時間刻度是天。

   周輪的時間刻度是天。

   天輪的時間刻度是小時。

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

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

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

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

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

   整體的示意圖如下所示：

時間輪的應用

時間輪的思想應用範圍非常廣泛，各種作業系統的定時任務排程，Crontab,還有基于java的通信架構Netty中也有時間輪的實作，幾乎所有的時間任務排程系統采用的都是時間輪的思想。

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