導(dǎo)讀：網(wǎng)上購物的普及化帶動了物流行業(yè)的迅猛發(fā)展沥阳，同時也帶來了極大的壓力和嚴(yán)峻的考驗，特別是在電商大促的時節(jié)自点。如何有效提高整個物流鏈路的時效體驗桐罕，給消費者更好的體驗，這是菜鳥物流一直奮斗的目標(biāo)。
今天功炮，我們來深入了解菜鳥的輕量級定時任務(wù)調(diào)度引擎設(shè)計系統(tǒng)溅潜，學(xué)習(xí)如何在億級別包裹中快速定位運輸超時的包裹。
在中國物流快速發(fā)展的今天死宣，日均包裹量已經(jīng)突破1億伟恶，如何確保1億包裹在合理的時間之內(nèi)送達(dá)收件人，并且能夠在收件人反饋之前毅该，及時處理那些沒有在合理時間內(nèi)運輸?shù)陌╋瑥亩岣呶锪髡麄€鏈路的時效體驗，已經(jīng)成為亟待解決的關(guān)鍵問題眶掌。????
要想解決問題挡育，首先要發(fā)現(xiàn)問題！有效朴爬、及時地發(fā)現(xiàn)問題離不開對這1億包裹運輸過程中每個環(huán)節(jié)實時監(jiān)控即寒，而要實現(xiàn)這個場景，就需要一個能夠支撐起如此量級的實時定時調(diào)度系統(tǒng)召噩。這就是本文的主題：輕量級定時任務(wù)調(diào)度引擎的設(shè)計母赵。
傳統(tǒng)方案
針對上文提到的問題場景，一般的做法是將定時任務(wù)寫入數(shù)據(jù)庫具滴，通過一個線程定時查詢出將要到期的任務(wù)凹嘲，再執(zhí)行任務(wù)相關(guān)邏輯。該方案的優(yōu)點是實現(xiàn)簡單构韵，尤其適合單機(jī)或者業(yè)務(wù)量比較小的場景來周蹭。但是缺點也很明顯：在分布式且業(yè)務(wù)量較大的場景中會引入很多復(fù)雜性。首先疲恢，需要設(shè)計一套合理的分庫分表邏輯凶朗，以及集群任務(wù)負(fù)載邏輯。其次显拳，即使做到這些棚愤，也會由于某些場景定時任務(wù)時間集中在某個時間點，導(dǎo)致集群單節(jié)點壓力過大杂数。再次遇八，需要合理的預(yù)估容量，否則后續(xù)線性存儲擴(kuò)容將會非常復(fù)雜耍休。
我們發(fā)現(xiàn)，上述方案的主要問題其實是定時任務(wù)時間和任務(wù)存儲的耦合货矮。如果能夠?qū)r間和存儲解耦羊精，任務(wù)的存儲就等于是無狀態(tài)的，這樣對存儲的可選擇性范圍會大很多，對存儲的約束也大大降低喧锦！
下文將會介紹如何通過時間輪思想將定時任務(wù)的時間和任務(wù)本身進(jìn)行解耦读规，從而在設(shè)計和性能上得到很大的提升。
時間輪基本介紹
時間輪方案將現(xiàn)實生活中的時鐘概念引入到軟件設(shè)計中燃少，主要思路是定義一個時鐘周期（比如時鐘的12小時）和步長（比如時鐘的一秒走一次）束亏，當(dāng)指針每走一步的時候，會獲取當(dāng)前時鐘刻度上掛載的任務(wù)并執(zhí)行阵具，整體結(jié)構(gòu)如圖1碍遍。
從上圖可以看到，對于時間的計算是交給一個類似時鐘的組件來做阳液，而任務(wù)是通過一個指針或者引用去關(guān)聯(lián)某個刻度上到期的定時任務(wù)怕敬，這樣就能夠?qū)⒍〞r任務(wù)的存儲和時間進(jìn)行解耦，時鐘組件難度不大帘皿，以何種方式存儲這些任務(wù)數(shù)據(jù)东跪，是時間輪方案的關(guān)鍵。
時間輪定時任務(wù)的存儲
我們發(fā)現(xiàn)鹰溜，阿里巴巴MQ（RocketMQ商業(yè)化版本虽填，后文統(tǒng)稱為阿里巴巴MQ）對其定時消息的改造[1]很有借鑒意義，老方案基于定時輪詢的方式check消息是否到期曹动，這種方案對于離散的時間比較受限斋日，所以也就導(dǎo)致老版本只能支持幾種延遲級別的定時消息。為了解決這個問題仁期，阿里巴巴MQ團(tuán)隊將原方案改造為基于時間輪+鏈表的方案桑驱，從而既能支持離散的定時消息，也能夠解決傳統(tǒng)時間輪每個刻度需要管理各自任務(wù)列表的復(fù)雜性跛蛋。
圖2簡明的描述了方案的關(guān)鍵點熬的，其設(shè)計思路就是將任務(wù)列表寫入到磁盤，并且在磁盤中采用鏈表的方式將任務(wù)列表串起來赊级，要達(dá)到這種串起來的效果押框，需要每個任務(wù)中都有一個指向下一個任務(wù)的磁盤offset，只需要拿到鏈表的頭便可以獲取整個任務(wù)鏈表理逊，于是在該方案中橡伞，時間輪的時間刻度不需要存儲所有的任務(wù)列表，只需要存儲鏈表的頭即可晋被，從而將內(nèi)存的壓力釋放出來兑徘。
該方案對于中間件這樣定位的系統(tǒng)來說是可以接受的，但對于一個定位在普通應(yīng)用的系統(tǒng)來說羡洛，對部署的要求就顯得過高了挂脑，因為你需要一塊固定的硬盤。在當(dāng)前容器化以及容量動態(tài)管理的趨勢下，一個普通應(yīng)用需要依賴一塊固定的磁盤崭闲，對系統(tǒng)的運維和部署都會帶來額外的復(fù)雜度肋联。于是在此基礎(chǔ)上形成本文重點介紹的輕量級定時任務(wù)調(diào)度引擎。
輕量級定時任務(wù)調(diào)度引擎
輕量級定時任務(wù)調(diào)度引擎借鑒了時間輪方案的核心思想刁俭，同時去除了系統(tǒng)對磁盤的依賴橄仍。既然不能將數(shù)據(jù)直接存儲在磁盤，那只能依托專門的存儲服務(wù)（比如Hbase牍戚，Redis等）來進(jìn)行存儲侮繁。于是就將下層的存儲替換成了一種存儲服務(wù)能夠滿足的結(jié)構(gòu)：
將任務(wù)設(shè)計成一種結(jié)構(gòu)化的表，并且將上面的offset替換成了一個任務(wù)ID（圖2是文件的offset）翘魄，并且通過ID將整個任務(wù)鏈表串起來鼎天，時間輪上只關(guān)聯(lián)鏈表頭的ID。這里對MQ方案改造的點只是將磁盤的offset替換成一個ID暑竟，從而解耦對磁盤的依賴斋射。
方案到現(xiàn)在感覺可以行得通，但是又引出了另外兩個問題：
問題1：單一鏈表無法并行提取但荤，從而影響提取效率罗岖，對于某個時刻有大量定時任務(wù)的時候，定時任務(wù)處理的延遲會比較嚴(yán)重腹躁；
問題2：既然任務(wù)不是存儲在本機(jī)磁盤了桑包，表明整個集群的定時任務(wù)是集中存儲，而集群中各個節(jié)點都擁有自己的時間輪纺非，那么集群里面每個節(jié)點重啟之后如何恢復(fù)哑了？集群擴(kuò)容&縮容如何自動管理？
任務(wù)鏈表分區(qū)——加速單一鏈表提取
鏈表的好處是在內(nèi)存中不用存儲整個任務(wù)列表烧颖，而只需要存儲一個簡單的ID弱左，這樣減少了內(nèi)存的消耗，但是卻帶來了另一個問題炕淮。眾所周知拆火，鏈表的特性是對寫友好，但讀的效率卻并不高涂圆，如果某個時刻需要掛載很長的任務(wù)鏈表们镜，那鏈表的方式是完全不能利用并發(fā)來提高讀的效率。
如何能夠提高某個時間的任務(wù)隊列提取的效率呢润歉？這里利用分區(qū)的原理模狭，將某個時刻的單一鏈表通過分區(qū)的方式拆分成多個鏈表，當(dāng)將某個時間點的任務(wù)提取的時候踩衩，可以根據(jù)鏈表集合大小來并行處理胞皱，從而可以加速整個任務(wù)提取的速度邪意。所以方案調(diào)整成圖4：
集群管理——集群節(jié)點的自我識別
解決了定時任務(wù)的存儲問題和單一鏈表提取任務(wù)的效率問題，好像整個方案都已經(jīng)ready了反砌，但是還有另一個重要的問題前面沒有考慮進(jìn)去，就是集群部署后節(jié)點重啟后如何進(jìn)行恢復(fù)萌朱？比如需要知道重啟之前的時間輪刻度宴树，需要知道重啟之間時間輪刻度上的定時任務(wù)鏈表數(shù)據(jù)等，后面我統(tǒng)一將這種數(shù)據(jù)稱之為時間輪元數(shù)據(jù)晶疼。如果任務(wù)寫入磁盤酒贬，某個機(jī)器的重啟，可以從本地磁盤加載當(dāng)前節(jié)點的時間輪元數(shù)據(jù)來進(jìn)行恢復(fù)翠霍；而如果不是通過磁盤來實現(xiàn)锭吨，那就帶來問題2-1：一臺機(jī)器在重啟之后怎么獲取它重啟之前的時間輪元數(shù)據(jù)呢？
通過上面的解決定時任務(wù)存儲問題寒匙，對于元數(shù)據(jù)的存儲也可以借助專門的存儲服務(wù)零如，但是由于集群的各個節(jié)點是無狀態(tài)的，所以各個節(jié)點啟動的時候锄弱，并不知道如何從存儲服務(wù)中讀取屬于自己的元數(shù)據(jù)（也就是查詢的條件）考蕾，這便引出了問題2-2：集群節(jié)點怎么獲取屬于它的元數(shù)據(jù)呢？?
可能第一想到的就是將元數(shù)據(jù)和節(jié)點ip或者mac地址關(guān)聯(lián)上会宪，但是在現(xiàn)在動態(tài)容量調(diào)度的情況下肖卧，一個機(jī)器擁有一個固定的ip也是很奢侈的，因為你不能保證你的應(yīng)用會運行在哪臺機(jī)器上掸鹅。既然物理環(huán)境不能依賴塞帐，就只能依賴邏輯環(huán)境來對每個節(jié)點的時間輪進(jìn)行區(qū)分了，于是就通過對集群每個節(jié)點分配一個在集群中唯一的邏輯ID巍沙，每臺機(jī)器通過自己拿到的ID去獲取時間輪數(shù)據(jù)葵姥。于是又引出了問題2-3：這個ID由誰來分配？這就是Master節(jié)點赎瞎。
在整個集群中需要選舉出一個節(jié)點為Master牌里，所有的其他節(jié)點會將自己注冊到Master節(jié)點中，然后再由Master節(jié)點分配一個ID給各個節(jié)點务甥，從而通過這個ID到存儲服務(wù)中獲取之前時間輪的元數(shù)據(jù)信息牡辽，最后初始化時間輪。圖5和圖6是該過程的描述圖：
圖5展示了節(jié)點注冊和獲取ID的過程敞临，注意态辛， Master節(jié)點自身也注冊并且分配了ID，這是因為對一個普通應(yīng)用來說挺尿，并沒有Master和非Master之分奏黑，Master也是會參與整個業(yè)務(wù)的計算的炊邦，只不過它除了參與業(yè)務(wù)計算之外，額外還要進(jìn)行集群的管理熟史。
集群自動化管理——自動感知擴(kuò)容&縮容
上文引出了Master節(jié)點馁害，并且所有節(jié)點都會將自己注冊給Master(包括Master自己)，于是基于Master就可以構(gòu)建出一套集群管理的機(jī)制蹂匹。對于普通應(yīng)用來說碘菜，集群的擴(kuò)容縮容是很正常的操作，在動態(tài)調(diào)度的場景下限寞，擴(kuò)縮容操作甚至連應(yīng)用owner都不感知忍啸，那么集群能夠感知自己被擴(kuò)容了和縮容了么？答案是肯定的履植，因為存在一個Master節(jié)點计雌，而Master可以感知到集群的其他節(jié)點的存活狀態(tài)，Master發(fā)現(xiàn)集群的容量變化玫霎，從而做出集群的負(fù)載調(diào)整凿滤。
定時任務(wù)提取集群化——集群壓力軟負(fù)載
上文通過將時間輪上的某個時間關(guān)聯(lián)單一鏈表拆分成多個鏈表來提高提取任務(wù)的并發(fā)度，同時也已構(gòu)建出了一套集群管理方案鼠渺。如果這個并發(fā)度只是在單節(jié)點鸭巴，只讓該節(jié)點自己提取，將會因為某個時刻的當(dāng)前節(jié)點到期的任務(wù)數(shù)量很大拦盹，從而導(dǎo)致集群中某些節(jié)點的壓力會很大鹃祖。為了能夠更加合理的利用集群計算能力，那么可以基于上面的集群管理能力普舆，對方案再進(jìn)一步優(yōu)化：將提取的到期任務(wù)鏈表集合通過軟負(fù)載的方式分發(fā)給集群其他節(jié)點恬口，同時由于任務(wù)的數(shù)據(jù)是集中存儲的，只要其他節(jié)點能夠拿到任務(wù)鏈表頭的ID沼侣，便可以提取得到該鏈表的所有任務(wù)祖能，從而集群的壓力也將被平攤，圖7是該過程的交互過程：
總結(jié)
上面對整個方案的演進(jìn)蛾洛，以及各個階段遇到的問題進(jìn)行了詳細(xì)的介紹养铸，可能還有一些點沒有太深入，大家可以回復(fù)留言中詳細(xì)討論轧膘。下面結(jié)合上面的內(nèi)容钞螟，做了一個簡單的流程梳理，以方便大家對全文的理解谎碍。
引用：
[1] 消息的處理方法鳞滨、裝置和電子設(shè)備:中國,201710071742.7[P].2017-10-07.
