京東到家訂單派發的技術實戰
達達-京東到家作為優秀的即時配送物流平臺，實現了多渠道的訂單配送，包括外賣平臺的餐飲訂單、新零售的生鮮訂單、知名商戶的優質訂單等。為了提升平臺的用戶粘性，我們需要兼顧商戶和騎士的各自愿景：商戶希望訂單能夠準時送達，騎士希望可以高效搶單。那么在合適的時候提升訂單定制化的曝光率，是及時送物流平臺的核心競爭力之一。
本文將描述訂單派發系統從無到有的系統演進以及方案設計與關鍵要點，為大家在解決相關業務場景上提供一個案例參考。
訂單派發架構演進
在公司發展的初期，我們的外賣訂單從商戶發單之后直接出現在搶單池中，3公里之內的騎士能夠看到訂單，并且從訂單卡片中獲取配送地址、配送時效等關鍵信息。這種暴力的顯示模式，很容易造成騎士挑選有利于自身的訂單進行配送，從而導致部分訂單超時未被配送。這樣的模式，在一定程度上導致了商戶的流失，同時也浪費了騎士的配送時間。
從上面的場景可以看出來，我們系統中缺少一個訂單核心調度者。有一種方案是選擇區域訂單的訂單調度員，由調度員根據騎士的接單情況、配送時間、訂單擠壓等實時情況來進行訂單調度。這種模式，看似可行，但是人力成本投入太高，且比較依賴個人的經驗總結。
核心問題已經出來了：個人的經驗總結會是什么呢?
- 騎士正在配送的訂單的數量，是否已經飽和
- 騎士的配送習慣是什么
- 某一階段的訂單是否順路，騎士是否可以一起配送
- 騎士到店駐留時間的預估
- ...
理清核心問題的答案，我們的系統派單便成為了可能?；谝陨系脑?，訂單派發模式就可以逐漸從搶單池的訂單顯示演變成系統派單。
我們將會記錄商戶發單行為、騎士配送日志及運行軌跡等信息，并且經過數據挖掘和數據分析，獲取騎士的畫像、騎士配送時間的預估、騎士到店駐留時間的預估等基礎信息;使用遺傳算法規劃出最優的配送路徑...經過上述一系列算法，我們將在騎士池中匹配出最合適的騎士，進而使用長連接(Netty)不間斷的通知到騎士。
隨著達達業務的不斷迭代，訂單配送逐漸孵化出基于大商戶的駐店模式：基于商戶維護一批固定的專屬騎士，訂單只會在運力不足的時候才會外發到搶單池中，正常情況使用派單模式通知騎士。
訂單派發模型
訂單派發可以淺顯的認為是一種信息流的推薦。在訂單進入搶單池之前，我們會根據每個城市的調度情況，先進行輪詢N次的派單。大概的表現形式如下圖：
舉例有筆訂單需要進行推送，在推送過程中，我們暫且假設一直沒有騎士接單，那么這筆訂單會每間隔N秒便會進行一次普通推薦，然后進入搶單池。
從訂單派發的流程周期上可以看出來，派發模型充斥著大量的延遲任務，只要能解決訂單在什么時候可以進行派發，那么整個系統 50% 的功能點就能迎刃而解。
我們先了解一下經典的延遲方案：
1. 數據庫輪詢
通過一個線程定時的掃描數據庫，獲取到需要派單的訂單信息
- 優點：開發簡單，結合quartz即可以滿足分布式掃描
- 缺點：對數據庫服務器壓力大,不利于項目后續發展
2. JDK的延遲隊列 - DelayQueue
DelayQueue是Delayed元素的一個無界阻塞隊列，只有在延遲期滿時才能從中提取元素。隊列中對象的順序按到期時間進行排序。
- 優點：開發簡單，效率高，任務觸發時間延遲低
- 缺點：服務器重啟后，數據會丟失，要滿足高可用場景，需要hook線程二次開發;宕機的擔憂;如果數據量暴增，也會引起OOM的情況產生
3. 時間輪 - TimingWheel
時間輪的結構原理很簡單，它是一個存儲定時任務的環形隊列，底層是由數組實現，而數組中的每個元素都可以存放一個定時任務列表，列表中的每一項都表示一個事件操作單元，當時間指針指向對應的時間格的時候，該列表中的所有任務都會被執行。 時間輪由多個時間格組成，每個時間格代表著當前實踐論的跨度，用tickMs代表;時間輪的個數是固定的，用wheelSize代表;整個時間輪的跨度用interval代表，那么指針轉了一圈的時間為：
- interval = tickMs * wheelSize
如果tickMs=1ms，wheelSize=20，那么便能計算出此時的時間是以20ms為一轉動周期，時間指針(currentTime)指向wheelSize=0的數據槽，此時有5ms延遲的任務插入了wheelSize=5的時間格，隨著時間的不斷推移，指針currentTime不斷向前推進，過了5ms之后，當到達時間格5時，就需要將時間格5所對應的任務做相應的到期操作。
如果此時有個定時為180ms的任務該如何處理?很直觀的思路是直接擴充wheelSize?這樣會導致wheelSize的擴充會隨著業務的發展而不斷擴張，這樣會使時間輪占用很大的內存空間，導致效率低下，因此便衍生出了層級時間輪的數據結構。
180ms的任務會升級到第二層時間輪中，最終被插入到第二層時間輪中時間格#8所對應的TimerTaskList中。如果此時又有一個定時為600ms的任務，那么顯然第二層時間輪也無法滿足條件，所以又升級到第三層時間輪中，最終被插入到第三層時間輪中時間格#1的TimerTaskList中。注意到在到期時間在[400ms,800ms)區間的多個任務(比如446ms、455ms以及473ms的定時任務)都會被放入到第三層時間輪的時間格#1中，時間格#1對應的TimerTaskList的超時時間為400ms。
隨著時間輪的轉動，當TimerTaskList到期時，原本定時為450ms的任務還剩下50ms的時間，還不能執行這個任務的到期操作。便會有個時間輪降級的操作，會將這個剩余時間50ms的定時任務重新提交到下一層級的時間輪中，所以該任務被放到第二層時間輪到期時間為 [40ms,60ms) 的時間格中。再經歷了40ms之后，此時這個任務又被觸發到，不過還剩余10ms，還是不能立即執行到期操作。所以還要再一次的降級，此任務會被添加到第一層時間輪到期時間為[10ms,11ms)的時間格中，之后再經歷10ms后，此任務真正到期，最終執行相應的到期操作。
- 優點：效率高，可靠性高(Netty,Kafka,Akka均有使用)，便于開發
- 缺點：數據存儲在內存中，需要自己實現持久化的方案來實現高可用
訂單派發實現方案
結合了上述的三種方案，最后決定使用redis作為數據存儲，使用timingWhell作為時間的推動者。這樣便可以將定時任務的存儲和時間推動進行解耦，依賴Redis的AOF機制，也不用過于擔心訂單數據的丟失。
kafka中為了處理成千上萬的延時任務選擇了多層時間輪的設計，我們從業務角度和開發難度上做了取舍，只選擇設計單層的時間輪便可以滿足需求。
1. 時間格和緩存的映射維護
假設當前時間currentTime為11:49:50，訂單派發時間dispatchTime為11:49:57，那么時間輪的時間格#7中會設置一個哨兵節點(作為是否有數據存儲在redis的依據 )用來表示該時間段是否會時間事件觸發，同時會將這份數據放入到緩存中(key=dispatchTime+ip), 當7秒過后，觸發了該時間段的數據，便會從redis中獲取數據，異步執行相應的業務邏輯。最后，防止由于重啟等一些操作導致數據的丟失，哨兵節點的維護也會在緩存中維護一份數據，在重啟的時候重新讀取
2. 緩存的key統一加上IP標識
由于我們的時間調度器是依附于自身系統的，通過將緩存的key統一加上IP的標識，這樣就可以保證各臺服務器消費屬于自身的數據，從而防止分布式環境下的并發問題，也可以減輕遍歷整個列表帶來的時間損耗(時間復雜度為O(N))
3. 使用異步線程處理時間格中對應的數據
使用異步線程，是考慮到如果上一個節點發生異?；蛘叱瑫r等情況，會延誤下一秒的操作，如果使用異常可以改善調度的即時性問題。
我們在設計系統的時候，系統的完善度和業務的滿足度是互相關聯影響的，單從上述的設計看，是會有些問題的，比如使用IP作為緩存的key，如果集群發生變更便會導致數據不會被消費;使用線程池異步處理也有概率導致數據不會被消費。這些不會被消費的數據會進入到搶單池中。從派單場景的需求來看，這些場景是可以被接受的，當然了，我們系統會有腳本來進行定期的篩選，將那些進入搶單池的訂單進行再次派單。
為什么不使用ScheduledThreadPoolExecutor來定時輪詢redis? 即便這樣可以完成業務上的需求，獲取定時觸發的任務，但是帶來的空查詢不但會拉高服務的CPU，redis的QPS也會被拉高，可能會導致redis的慢查詢會顯著增多。
結語
我們在完成一個功能的時候，往往需要一些可視化的數據來確定業務發展的正確性。因此我們在開發的時候，也相應的記錄了一些訂單與騎士的交互動作。從每天的報表數據可以看出來，90% 以上的訂單是通過派單發出并且被騎士認可接單。
訂單派發的模式是提升訂單曝光率有效的技術手段，我們一直結合大數據、人工智能等技術手段希望能更好的做好訂單派發，能提供更加多元化的功能，將達達打造成更加一流的配送平臺。
作者：季炳坤，任職Java工程師，負責訂單派發，訂單權限，合并訂單等相關工作。
【本文來自51CTO專欄作者張開濤的微信公眾號(開濤的博客)，公眾號id: kaitao-1234567】
