在中國物流快速發展的今天，日均包裹量已經突破1億，如何確定1億包裹在合理的時間之内送達收件人，并且能夠在收件人回報之前，及時處理那些沒有在合理時間内運輸的包裹，進而提高物流整個鍊路的時效體驗，已經成為亟待解決的關鍵問題。
要想解決問題，首先要發現問題！有效、及時地發現問題離不開對這1億包裹運輸過程中每個環節實時監控，而要實作這個場景，就需要一個能夠支撐起如此量級的實時定時排程系統。這就是本文的主題：輕量級定時任務排程引擎的設計。
如何讓快遞更"快"？菜鳥自研定時任務排程引擎首次公開
傳統方案
針對上文提到的問題場景，一般的做法是将定時任務寫入資料庫，通過一個線程定時查詢出将要到期的任務，再執行任務相關邏輯。該方案的優點是實作簡單，尤其适合單機或者業務量比較小的場景來。但是缺點也很明顯：在分布式且業務量較大的場景中會引入很多複雜性。首先，需要設計一套合理的分庫分表邏輯，以及叢集任務負載邏輯。其次，即使做到這些，也會由于某些場景定時任務時間集中在某個時間點，導緻叢集單節點壓力過大。再次，需要合理的預估容量，否則後續線性存儲擴容将會非常複雜。
我們發現，上述方案的主要問題其實是定時任務時間和任務存儲的耦合。如果能夠将時間和存儲解耦，任務的存儲就等于是無狀态的，這樣對存儲的可選擇性範圍會大很多，對存儲的限制也大大降低！
下文将會介紹如何通過時間輪思想将定時任務的時間和任務本身進行解耦，進而在設計和性能上得到很大的提升。
時間輪基本介紹
時間輪方案将現實生活中的時鐘概念引入到軟體設計中，主要思路是定義一個時鐘周期（比如時鐘的12小時）和步長（比如時鐘的一秒走一次），當指針每走一步的時候，會擷取目前時鐘刻度上挂載的任務并執行，整體結構如圖1。
圖1 時間輪算法
從上圖可以看到，對于時間的計算是交給一個類似時鐘的元件來做，而任務是通過一個指針或者引用去關聯某個刻度上到期的定時任務，這樣就能夠将定時任務的存儲和時間進行解耦，時鐘元件難度不大，以何種方式存儲這些任務資料，是時間輪方案的關鍵。
時間輪定時任務的存儲
我們發現，阿裡巴巴MQ（RocketMQ商業化版本，後文統稱為阿裡巴巴MQ）對其定時消息的改造[1]很有借鑒意義，老方案基于定時輪詢的方式check消息是否到期，這種方案對于離散的時間比較受限，是以也就導緻老版本隻能支援幾種延遲級别的定時消息。為了解決這個問題，阿裡巴巴MQ團隊将原方案改造為基于時間輪+連結清單的方案，進而既能支援離散的定時消息，也能夠解決傳統時間輪每個刻度需要管理各自任務清單的複雜性。
圖2 阿裡巴巴MQ定時消息方案
圖2簡明的描述了方案的關鍵點，其設計思路就是将任務清單寫入到磁盤，并且在磁盤中采用連結清單的方式将任務清單串起來，要達到這種串起來的效果，需要每個任務中都有一個指向下一個任務的磁盤offset，隻需要拿到連結清單的頭便可以擷取整個任務連結清單，于是在該方案中，時間輪的時間刻度不需要存儲所有的任務清單，隻需要存儲連結清單的頭即可，進而将記憶體的壓力釋放出來。
該方案對于中間件這樣定位的系統來說是可以接受的，但對于一個定位在普通應用的系統來說，對部署的要求就顯得過高了，因為你需要一塊固定的硬碟。在目前容器化以及容量動态管理的趨勢下，一個普通應用需要依賴一塊固定的磁盤，對系統的運維和部署都會帶來額外的複雜度。于是在此基礎上形成本文重點介紹的輕量級定時任務排程引擎。
輕量級定時任務排程引擎
輕量級定時任務排程引擎借鑒了時間輪方案的核心思想，同時去除了系統對磁盤的依賴。既然不能将資料直接存儲在磁盤，那隻能依托專門的存儲服務（比如Hbase，Redis等）來進行存儲。于是就将下層的存儲替換成了一種存儲服務能夠滿足的結構：
圖3 調整後的時間輪+連結清單方案
将任務設計成一種結構化的表，并且将上面的offset替換成了一個任務ID（圖2是檔案的offset），并且通過ID将整個任務連結清單串起來，時間輪上隻關聯連結清單頭的ID。這裡對MQ方案改造的點隻是将磁盤的offset替換成一個ID，進而解耦對磁盤的依賴。
方案到現在感覺可以行得通，但是又引出了另外兩個問題：
問題1：單一連結清單無法并行提取，進而影響提取效率，對于某個時刻有大量定時任務的時候，定時任務處理的延遲會比較嚴重；
問題2：既然任務不是存儲在本機磁盤了，表明整個叢集的定時任務是集中存儲，而叢集中各個節點都擁有自己的時間輪，那麼叢集裡面每個節點重新開機之後如何恢複？叢集擴容&縮容如何自動管理？
任務連結清單分區——加速單一連結清單提取
連結清單的好處是在記憶體中不用存儲整個任務清單，而隻需要存儲一個簡單的ID，這樣減少了記憶體的消耗，但是卻帶來了另一個問題。衆所周知，連結清單的特性是對寫友好，但讀的效率卻并不高，如果某個時刻需要挂載很長的任務連結清單，那連結清單的方式是完全不能利用并發來提高讀的效率。
如何能夠提高某個時間的任務隊列提取的效率呢？這裡利用分區的原理，将某個時刻的單一連結清單通過分區的方式拆分成多個連結清單，當将某個時間點的任務提取的時候，可以根據連結清單集合大小來并行處理，進而可以加速整個任務提取的速度。是以方案調整成圖4：
圖4 分區後的設計方案
叢集管理——叢集節點的自我識别
解決了定時任務的存儲問題和單一連結清單提取任務的效率問題，好像整個方案都已經ready了，但是還有另一個重要的問題前面沒有考慮進去，就是叢集部署後節點重新開機後如何進行恢複？比如需要知道重新開機之前的時間輪刻度，需要知道重新開機之間時間輪刻度上的定時任務連結清單資料等，後面我統一将這種資料稱之為時間輪中繼資料。如果任務寫入磁盤，某個機器的重新開機，可以從本地磁盤加載目前節點的時間輪中繼資料來進行恢複；而如果不是通過磁盤來實作，那就帶來問題2-1：一台機器在重新開機之後怎麼擷取它重新開機之前的時間輪中繼資料呢？
通過上面的解決定時任務存儲問題，對于中繼資料的存儲也可以借助專門的存儲服務，但是由于叢集的各個節點是無狀态的，是以各個節點啟動的時候，并不知道如何從存儲服務中讀取屬于自己的中繼資料（也就是查詢的條件），這便引出了問題2-2：叢集節點怎麼擷取屬于它的中繼資料呢？
可能第一想到的就是将中繼資料和節點ip或者mac位址關聯上，但是在現在動态容量排程的情況下，一個機器擁有一個固定的ip也是很奢侈的，因為你不能保證你的應用會運作在哪台機器上。既然實體環境不能依賴，就隻能依賴邏輯環境來對每個節點的時間輪進行區分了，于是就通過對叢集每個節點配置設定一個在叢集中唯一的邏輯ID，每台機器通過自己拿到的ID去擷取時間輪資料。于是又引出了問題2-3：這個ID由誰來配置設定？ 這就是Master節點。
在整個叢集中需要選舉出一個節點為Master，所有的其他節點會将自己注冊到Master節點中，然後再由Master節點配置設定一個ID給各個節點，進而通過這個ID到存儲服務中擷取之前時間輪的中繼資料資訊，最後初始化時間輪。圖5和圖6是該過程的描述圖：
圖5展示了節點注冊和擷取ID的過程，注意， Master節點自身也注冊并且配置設定了ID，這是因為對一個普通應用來說，并沒有Master和非Master之分，Master也是會參與整個業務的計算的，隻不過它除了參與業務計算之外，額外還要進行叢集的管理。
叢集自動化管理——自動感覺擴容&縮容
上文引出了Master節點，并且所有節點都會将自己注冊給Master(包括Master自己)，于是基于Master就可以建構出一套叢集管理的機制。對于普通應用來說，叢集的擴容縮容是很正常的操作，在動态排程的場景下，擴縮容操作甚至連應用owner都不感覺，那麼叢集能夠感覺自己被擴容了和縮容了麼？答案是肯定的，因為存在一個Master節點，而Master可以感覺到叢集的其他節點的存活狀态，Master發現叢集的容量變化，進而做出叢集的負載調整。
定時任務提取叢集化——叢集壓力軟負載
上文通過将時間輪上的某個時間關聯單一連結清單拆分成多個連結清單來提高提取任務的并發度，同時也已建構出了一套叢集管理方案。如果這個并發度隻是在單節點，隻讓該節點自己提取，将會因為某個時刻的目前節點到期的任務數量很大，進而導緻叢集中某些節點的壓力會很大。為了能夠更加合理的利用叢集計算能力，那麼可以基于上面的叢集管理能力，對方案再進一步優化：将提取的到期任務連結清單集合通過軟負載的方式分發給叢集其他節點，同時由于任務的資料是集中存儲的，隻要其他節點能夠拿到任務連結清單頭的ID，便可以提取得到該連結清單的所有任務，進而叢集的壓力也将被平攤，圖7是該過程的互動過程：
圖7 叢集并行提取任務
總結
上面對整個方案的演進，以及各個階段遇到的問題進行了詳細的介紹，可能還有一些點沒有太深入，大家可以回複留言中詳細讨論。下面結合上面的内容，做了一個簡單的流程梳理，以友善大家對全文的了解。
原文釋出時間為：2018-04-12
本文作者：玄伯
本文來自雲栖社群合作夥伴“
阿裡技術”，了解相關資訊可以關注“
”。