58速運“里程計算”優(yōu)化與演進(jìn)
58速運貨物運輸，滴滴快遞網(wǎng)約車，司機端都是按照行駛公里數(shù)收費的，所以“里程”的準(zhǔn)確性，是這類業(yè)務(wù)的一個核心難題，“里程計算”方案演進(jìn)，以及其中優(yōu)化思想，是本文要討論的問題。
一、直接調(diào)用地圖API
這是最容易想到的方法，最省事，但司機往往不是按照預(yù)定的路線行駛的，很有可能因為堵車、道路封閉等改變路線，所以直接調(diào)用地圖API，一次性計算出一個預(yù)估值，不太靠譜
優(yōu)化方案：根據(jù)實際路線計算里程
二、司機APP實時計算增量里程，服務(wù)端存儲總里程
過程如下：
(1)貨車位置不停的在改變，司機APP每隔一段時間(例如1s)記錄一次GPS，即打點
(2)實時計算相鄰兩點的距離，上報服務(wù)端
(3)服務(wù)端存儲總里程
潛在問題：GPS可能不準(zhǔn)確，偶爾會有噪點，一旦有噪點，相鄰兩點的距離會很遠(yuǎn)，導(dǎo)致最終總里程可能比實際里程遠(yuǎn)
優(yōu)化方案：不能實時計算增量，而應(yīng)該先打點，最終統(tǒng)一計算，這樣才有機會去除噪點
三、打點上報服務(wù)端，服務(wù)端統(tǒng)一計算里程
過程如下：
(1)貨車位置不停的在改變，司機APP每秒打一個點，上報服務(wù)端
(2)服務(wù)端將打點落地，記錄數(shù)據(jù)庫
(3)到達(dá)目的地后，服務(wù)端對于所有點進(jìn)行統(tǒng)一處理，一次性計算里程，可以去除噪點
潛在問題：假設(shè)每單平均貨運時長1小時，即每單要打3600個點，58速運每天100w訂單，即總共要打36億個點，每個點對應(yīng)數(shù)據(jù)庫一個寫請求，則數(shù)據(jù)庫的寫壓力大概在每秒4w次，扛不住
優(yōu)化方案：批量寫是一種常見的降低數(shù)據(jù)庫壓力的方案
四、客戶端實時打點，壓縮后批量上傳
過程如下：
(1)司機APP每秒在本地打點，每隔一段時間(例如20s)，壓縮，上報服務(wù)端，服務(wù)端壓力從4w降低到2k
(2)服務(wù)端解壓，批量寫入隊列
(3)隊列中的點，每隔一段時間(例如2s)再寫入數(shù)據(jù)庫
優(yōu)化成果：大大降低了數(shù)據(jù)庫壓力(由于存儲量較大，實際優(yōu)化的過程中，使用Hbase進(jìn)行了優(yōu)化存儲)
其他問題：數(shù)據(jù)庫壓力降下來了，但到達(dá)目的地后，一個訂單打的所有點計算里程，成本較高，如何減少計算量
優(yōu)化方案：去除無效點
五、打點過濾，提高效率
什么樣的打點是無效點，需要去除呢?
(1)噪點原則：連續(xù)打點，偏移量較大的噪點，需要去除
(2)同點原則：相同位置的點可以去除，因為移動路徑為0
(3)速度原則：行駛速度超過合理范圍的點，需要去除
(4)角度原則：理論上訂單軌跡是平滑有序的，如果角度反復(fù)折回，可以視為無效點
潛在問題：如果司機APP有斷網(wǎng)或者信號不好，可能會漏點，導(dǎo)致計算出的總距離小于實際距離，給司機帶來損失
優(yōu)化方案：補點
六、事后補點，數(shù)據(jù)修正，計算里程
如何進(jìn)行補點，如何進(jìn)行數(shù)據(jù)修正呢?
(1)補點：車輛行駛過程中，如果有中斷路線，采用“地圖路徑規(guī)劃”的方式補點
(2)修正：采用卡爾曼濾波算法，對軌跡進(jìn)行整形
(3)計算里程：按照點到點的距離，進(jìn)行累加
總結(jié)
“里程計算”的優(yōu)化歷程：
- 直接調(diào)用地圖API
- 司機APP實時計算增量里程，服務(wù)端存儲總里程
- 打點上報服務(wù)端，服務(wù)端統(tǒng)一計算里程
- 客戶端實時打點，壓縮后批量上傳
- 打點過濾，提高效率
- 事后補點，數(shù)據(jù)修正，計算里程
“里程計算”業(yè)務(wù)并不是所有公司都會涉及到，但其中的優(yōu)化思路，很多還是可以借鑒的：
- 單次與統(tǒng)籌：客戶端單次記錄與計算是不靠譜的，應(yīng)該由服務(wù)端來實施，綜合所有數(shù)據(jù)，去除噪點
- 單次與批量：單次操作，壓力較大，不好壓縮;批量操作能大大降低壓力，并且壓縮比高
- 全量與過濾：全量計算成本較高，過濾掉無效數(shù)據(jù)，能夠降低計算量，提高精確性
- 補充與修正：對于少量缺少的數(shù)據(jù)，可以預(yù)測補充，平滑修正
【本文為51CTO專欄作者“58沈劍”原創(chuàng)稿件，轉(zhuǎn)載請聯(lián)系原作者】
