本文由達(dá)達(dá)京東到家Java工程師季炳坤原創(chuàng)分享。
1、前言
達(dá)達(dá)-京東到家作為優(yōu)秀的即時配送物流平臺，實(shí)現(xiàn)了多渠道的訂單配送，包括外賣平臺的餐飲訂單、新零售的生鮮訂單、知名商戶的優(yōu)質(zhì)訂單等。為了提升平臺的用戶粘性，我們需要兼顧商戶和騎士的各自愿景：商戶希望訂單能夠準(zhǔn)時送達(dá)，騎士希望可以高效搶單。那么在合適的時候提升訂單定制化的曝光率，是及時送物流平臺的核心競爭力之一。
本文將描述“達(dá)達(dá)-京東到家”的訂單即時派發(fā)系統(tǒng)從無到有的系統(tǒng)演進(jìn)過程，以及方案設(shè)計(jì)的關(guān)鍵要點(diǎn)，希望能為大家在解決相關(guān)業(yè)務(wù)場景上提供一個案例參考。
關(guān)于“達(dá)達(dá)-京東到家”：
達(dá)達(dá)-京東到家，是同城速遞信息服務(wù)平臺和無界零售即時消費(fèi)平臺。達(dá)達(dá)-京東到家創(chuàng)始人兼首席執(zhí)行官蒯佳祺；
公司旗下，目前已覆蓋全國400 多個主要城市，服務(wù)超過120萬商家用戶和超 5000萬個人用戶；
2018年8月，達(dá)達(dá)-京東到家正式宣布完成最新一輪5億美元融資，投資方分別為沃爾瑪和京東。
（本文同步發(fā)布于：http://www.52im.net/thread-1928-1-1.html）
2、關(guān)于作者
季炳坤：“達(dá)達(dá)-京東到家”Java工程師，負(fù)責(zé)“達(dá)達(dá)-京東到家”的訂單派發(fā)、訂單權(quán)限、合并訂單等相關(guān)技術(shù)工作的實(shí)現(xiàn)。
3、訂單即時派發(fā)架構(gòu)的演進(jìn)
在公司發(fā)展的初期，我們的外賣訂單從商戶發(fā)單之后直接出現(xiàn)在搶單池中，3公里之內(nèi)的騎士能夠看到訂單，并且從訂單卡片中獲取配送地址、配送時效等關(guān)鍵信息。這種暴力的顯示模式，很容易造成騎士挑選有利于自身的訂單進(jìn)行配送，從而導(dǎo)致部分訂單超時未被配送。這樣的模式，在一定程度上導(dǎo)致了商戶的流失，同時也浪費(fèi)了騎士的配送時間。
從上面的場景可以看出來，我們系統(tǒng)中缺少一個訂單核心調(diào)度者。有一種方案是選擇區(qū)域訂單的訂單調(diào)度員，由調(diào)度員根據(jù)騎士的接單情況、配送時間、訂單擠壓等實(shí)時情況來進(jìn)行訂單調(diào)度。這種模式，看似可行，但是人力成本投入太高，且比較依賴個人的經(jīng)驗(yàn)總結(jié)。
核心問題已經(jīng)出來了：個人的經(jīng)驗(yàn)總結(jié)會是什么呢?
1） 騎士正在配送的訂單的數(shù)量，是否已經(jīng)飽和；
2） 騎士的配送習(xí)慣是什么；
3） 某一階段的訂單是否順路，騎士是否可以一起配送；
4） 騎士到店駐留時間的預(yù)估；
5） ...
理清核心問題的答案，我們的系統(tǒng)派單便成為了可能。
基于以上的原理，訂單派發(fā)模式就可以逐漸從搶單池的訂單顯示演變成系統(tǒng)派單：
我們將會：
1）記錄商戶發(fā)單行為；
2）騎士配送日志及運(yùn)行軌跡等信息。
并且經(jīng)過數(shù)據(jù)挖掘和數(shù)據(jù)分析：
1）獲取騎士的畫像；
2）騎士配送時間的預(yù)估；
3）騎士到店駐留時間的預(yù)估等基礎(chǔ)信息；
4）使用遺傳算法規(guī)劃出最優(yōu)的配送路徑；
5）...
經(jīng)過上述一系列算法，我們將在騎士池中匹配出最合適的騎士，進(jìn)而使用長連接（Netty）不間斷的通知到騎士。
隨著達(dá)達(dá)業(yè)務(wù)的不斷迭代，訂單配送逐漸孵化出基于大商戶的駐店模式：基于商戶維護(hù)一批固定的專屬騎士，訂單只會在運(yùn)力不足的時候才會外發(fā)到搶單池中，正常情況使用派單模式通知騎士。
4、訂單派發(fā)模型的方案選型
訂單派發(fā)可以淺顯的認(rèn)為是一種信息流的推薦。在訂單進(jìn)入搶單池之前，我們會根據(jù)每個城市的調(diào)度情況，先進(jìn)行輪詢N次的派單。
大概的表現(xiàn)形式如下圖：
舉例：有筆訂單需要進(jìn)行推送，在推送過程中，我們暫且假設(shè)一直沒有騎士接單，那么這筆訂單會每間隔N秒便會進(jìn)行一次普通推薦，然后進(jìn)入搶單池。
從訂單派發(fā)的流程周期上可以看出來，派發(fā)模型充斥著大量的延遲任務(wù)，只要能解決訂單在什么時候可以進(jìn)行派發(fā)，那么整個系統(tǒng) 50% 的功能點(diǎn)就能迎刃而解。
我們先了解一下經(jīng)典的延遲方案，請繼續(xù)往下讀。。。
4.1 方案1：數(shù)據(jù)庫輪詢
通過一個線程定時的掃描數(shù)據(jù)庫，獲取到需要派單的訂單信息。
優(yōu)點(diǎn)：開發(fā)簡單，結(jié)合quartz即可以滿足分布式掃描；
缺點(diǎn)：對數(shù)據(jù)庫服務(wù)器壓力大,不利于項(xiàng)目后續(xù)發(fā)展。
4.2 方案2：JDK的延遲隊(duì)列 - DelayQueue
DelayQueue是Delayed元素的一個無界阻塞隊(duì)列，只有在延遲期滿時才能從中提取元素。隊(duì)列中對象的順序按到期時間進(jìn)行排序。
優(yōu)點(diǎn)：開發(fā)簡單，效率高，任務(wù)觸發(fā)時間延遲低；
缺點(diǎn)：服務(wù)器重啟后，數(shù)據(jù)會丟失，要滿足高可用場景，需要hook線程二次開發(fā)；宕機(jī)的擔(dān)憂；如果數(shù)據(jù)量暴增，也會引起OOM的情況產(chǎn)生。
4.3 方案3：時間輪 - TimingWheel
時間輪的結(jié)構(gòu)原理很簡單，它是一個存儲定時任務(wù)的環(huán)形隊(duì)列，底層是由數(shù)組實(shí)現(xiàn)，而數(shù)組中的每個元素都可以存放一個定時任務(wù)列表。列表中的每一項(xiàng)都表示一個事件操作單元，當(dāng)時間指針指向?qū)?yīng)的時間格的時候，該列表中的所有任務(wù)都會被執(zhí)行。 時間輪由多個時間格組成，每個時間格代表著當(dāng)前實(shí)踐論的跨度，用tickMs代表；時間輪的個數(shù)是固定的，用wheelSize代表。
整個時間輪的跨度用interval代表，那么指針轉(zhuǎn)了一圈的時間為：
interval = tickMs * wheelSize
如果tickMs=1ms，wheelSize=20，那么便能計(jì)算出此時的時間是以20ms為一轉(zhuǎn)動周期，時間指針（currentTime）指向wheelSize=0的數(shù)據(jù)槽，此時有5ms延遲的任務(wù)插入了wheelSize=5的時間格。隨著時間的不斷推移，指針currentTime不斷向前推進(jìn)，過了5ms之后，當(dāng)?shù)竭_(dá)時間格5時，就需要將時間格5所對應(yīng)的任務(wù)做相應(yīng)的到期操作。
如果此時有個定時為180ms的任務(wù)該如何處理？很直觀的思路是直接擴(kuò)充wheelSize？這樣會導(dǎo)致wheelSize的擴(kuò)充會隨著業(yè)務(wù)的發(fā)展而不斷擴(kuò)張，這樣會使時間輪占用很大的內(nèi)存空間，導(dǎo)致效率低下，因此便衍生出了層級時間輪的數(shù)據(jù)結(jié)構(gòu)。
180ms的任務(wù)會升級到第二層時間輪中，最終被插入到第二層時間輪中時間格#8所對應(yīng)的TimerTaskList中。如果此時又有一個定時為600ms的任務(wù)，那么顯然第二層時間輪也無法滿足條件，所以又升級到第三層時間輪中，最終被插入到第三層時間輪中時間格#1的TimerTaskList中。注意到在到期時間在[400ms,800ms)區(qū)間的多個任務(wù)（比如446ms、455ms以及473ms的定時任務(wù)）都會被放入到第三層時間輪的時間格#1中，時間格#1對應(yīng)的TimerTaskList的超時時間為400ms。
隨著時間輪的轉(zhuǎn)動，當(dāng)TimerTaskList到期時，原本定時為450ms的任務(wù)還剩下50ms的時間，還不能執(zhí)行這個任務(wù)的到期操作。便會有個時間輪降級的操作，會將這個剩余時間50ms的定時任務(wù)重新提交到下一層級的時間輪中，所以該任務(wù)被放到第二層時間輪到期時間為 [40ms,60ms) 的時間格中。再經(jīng)歷了40ms之后，此時這個任務(wù)又被觸發(fā)到，不過還剩余10ms，還是不能立即執(zhí)行到期操作。所以還要再一次的降級，此任務(wù)會被添加到第一層時間輪到期時間為[10ms,11ms)的時間格中，之后再經(jīng)歷10ms后，此任務(wù)真正到期，最終執(zhí)行相應(yīng)的到期操作。
優(yōu)點(diǎn)：效率高，可靠性高(Netty,Kafka,Akka均有使用)，便于開發(fā)；
缺點(diǎn)：數(shù)據(jù)存儲在內(nèi)存中，需要自己實(shí)現(xiàn)持久化的方案來實(shí)現(xiàn)高可用。
5、訂單派發(fā)方案的具體實(shí)現(xiàn)
結(jié)合了上述的三種方案，最后決定使用redis作為數(shù)據(jù)存儲，使用timingWhell作為時間的推動者。這樣便可以將定時任務(wù)的存儲和時間推動進(jìn)行解耦，依賴Redis的AOF機(jī)制，也不用過于擔(dān)心訂單數(shù)據(jù)的丟失。
kafka中為了處理成千上萬的延時任務(wù)選擇了多層時間輪的設(shè)計(jì)，我們從業(yè)務(wù)角度和開發(fā)難度上做了取舍，只選擇設(shè)計(jì)單層的時間輪便可以滿足需求。
1）時間格和緩存的映射維護(hù)：
假設(shè)當(dāng)前時間currentTime為11:49:50，訂單派發(fā)時間dispatchTime為11:49:57，那么時間輪的時間格#7中會設(shè)置一個哨兵節(jié)點(diǎn)（作為是否有數(shù)據(jù)存儲在redis的依據(jù) ）用來表示該時間段是否會時間事件觸發(fā)，同時會將這份數(shù)據(jù)放入到緩存中（key=dispatchTime+ip）, 當(dāng)7秒過后，觸發(fā)了該時間段的數(shù)據(jù)，便會從redis中獲取數(shù)據(jù)，異步執(zhí)行相應(yīng)的業(yè)務(wù)邏輯。最后，防止由于重啟等一些操作導(dǎo)致數(shù)據(jù)的丟失，哨兵節(jié)點(diǎn)的維護(hù)也會在緩存中維護(hù)一份數(shù)據(jù)，在重啟的時候重新讀取。
2）緩存的key統(tǒng)一加上IP標(biāo)識：
由于我們的時間調(diào)度器是依附于自身系統(tǒng)的，通過將緩存的key統(tǒng)一加上IP的標(biāo)識，這樣就可以保證各臺服務(wù)器消費(fèi)屬于自身的數(shù)據(jù)，從而防止分布式環(huán)境下的并發(fā)問題，也可以減輕遍歷整個列表帶來的時間損耗（時間復(fù)雜度為O(N)）。
3）使用異步線程處理時間格中對應(yīng)的數(shù)據(jù)：
使用異步線程，是考慮到如果上一個節(jié)點(diǎn)發(fā)生異常或者超時等情況，會延誤下一秒的操作，如果使用異常可以改善調(diào)度的即時性問題。
我們在設(shè)計(jì)系統(tǒng)的時候，系統(tǒng)的完善度和業(yè)務(wù)的滿足度是互相關(guān)聯(lián)影響的，單從上述的設(shè)計(jì)看，是會有些問題的，比如使用IP作為緩存的key，如果集群發(fā)生變更便會導(dǎo)致數(shù)據(jù)不會被消費(fèi)；使用線程池異步處理也有概率導(dǎo)致數(shù)據(jù)不會被消費(fèi)。這些不會被消費(fèi)的數(shù)據(jù)會進(jìn)入到搶單池中。從派單場景的需求來看，這些場景是可以被接受的，當(dāng)然了，我們系統(tǒng)會有腳本來進(jìn)行定期的篩選，將那些進(jìn)入搶單池的訂單進(jìn)行再次派單。
* 思考：為什么不使用ScheduledThreadPoolExecutor來定時輪詢redis?
原因是即便這樣可以完成業(yè)務(wù)上的需求，獲取定時觸發(fā)的任務(wù)，但是帶來的空查詢不但會拉高服務(wù)的CPU，redis的QPS也會被拉高，可能會導(dǎo)致redis的慢查詢會顯著增多。
6、結(jié)語
我們在完成一個功能的時候，往往需要一些可視化的數(shù)據(jù)來確定業(yè)務(wù)發(fā)展的正確性。因此我們在開發(fā)的時候，也相應(yīng)的記錄了一些訂單與騎士的交互動作。從每天的報(bào)表數(shù)據(jù)可以看出來，90% 以上的訂單是通過派單發(fā)出并且被騎士認(rèn)可接單。
訂單派發(fā)的模式是提升訂單曝光率有效的技術(shù)手段，我們一直結(jié)合大數(shù)據(jù)、人工智能等技術(shù)手段希望能更好的做好訂單派發(fā)，能提供更加多元化的功能，將達(dá)達(dá)打造成更加一流的配送平臺。
附錄：更多相關(guān)技術(shù)文章
《偽即時通訊：分享滴滴出行iOS客戶端的演進(jìn)過程》
《iOS的推送服務(wù)APNs詳解：設(shè)計(jì)思路、技術(shù)原理及缺陷等》
《信鴿團(tuán)隊(duì)原創(chuàng)：一起走過 iOS10 上消息推送(APNS)的坑》
《Android端消息推送總結(jié)：實(shí)現(xiàn)原理、心跳保活、遇到的問題等》
《掃盲貼：認(rèn)識MQTT通信協(xié)議》
《一個基于MQTT通信協(xié)議的完整Android推送Demo》
《IBM技術(shù)經(jīng)理訪談：MQTT協(xié)議的制定歷程、發(fā)展現(xiàn)狀等》
《求教android消息推送：GCM、XMPP、MQTT三種方案的優(yōu)劣》
《移動端實(shí)時消息推送技術(shù)淺析》
《掃盲貼：淺談iOS和Android后臺實(shí)時消息推送的原理和區(qū)別》
《絕對干貨：基于Netty實(shí)現(xiàn)海量接入的推送服務(wù)技術(shù)要點(diǎn)》
《移動端IM實(shí)踐：谷歌消息推送服務(wù)(GCM)研究（來自微信）》
《為何微信、QQ這樣的IM工具不使用GCM服務(wù)推送消息？》
《極光推送系統(tǒng)大規(guī)模高并發(fā)架構(gòu)的技術(shù)實(shí)踐分享》
《從HTTP到MQTT：一個基于位置服務(wù)的APP數(shù)據(jù)通信實(shí)踐概述》
《魅族2500萬長連接的實(shí)時消息推送架構(gòu)的技術(shù)實(shí)踐分享》
《專訪魅族架構(gòu)師：海量長連接的實(shí)時消息推送系統(tǒng)的心得體會》
《深入的聊聊Android消息推送這件小事》
《基于WebSocket實(shí)現(xiàn)Hybrid移動應(yīng)用的消息推送實(shí)踐(含代碼示例)》
《一個基于長連接的安全可擴(kuò)展的訂閱/推送服務(wù)實(shí)現(xiàn)思路》
《實(shí)踐分享：如何構(gòu)建一套高可用的移動端消息推送系統(tǒng)？》
《Go語言構(gòu)建千萬級在線的高并發(fā)消息推送系統(tǒng)實(shí)踐(來自360公司)》
《騰訊信鴿技術(shù)分享：百億級實(shí)時消息推送的實(shí)戰(zhàn)經(jīng)驗(yàn)》
《百萬在線的美拍直播彈幕系統(tǒng)的實(shí)時推送技術(shù)實(shí)踐之路》
《京東京麥商家開放平臺的消息推送架構(gòu)演進(jìn)之路》
《了解iOS消息推送一文就夠：史上最全iOS Push技術(shù)詳解》
《基于APNs最新HTTP/2接口實(shí)現(xiàn)iOS的高性能消息推送(服務(wù)端篇)》
《解密“達(dá)達(dá)-京東到家”的訂單即時派發(fā)技術(shù)原理和實(shí)踐》
>> 更多同類文章 ……
（本文同步發(fā)布于：http://www.52im.net/thread-1928-1-1.html）