導(dǎo)讀:我們經(jīng)常使用打車(chē)軟件出行,也經(jīng)常思考其架構(gòu)設(shè)計(jì)迅涮。本文作者在所在國(guó)家也負(fù)責(zé)開(kāi)發(fā)一款打車(chē)軟件废赞,并且開(kāi)源了其中大部分代碼,可以幫助我們更好了解網(wǎng)絡(luò)約車(chē)軟件的架構(gòu)體系叮姑。本文由高可用架構(gòu)翻譯唉地。
各位讀者好据悔,本文將給大家分享我們?nèi)绾瓮ㄟ^(guò)內(nèi)存存儲(chǔ)實(shí)現(xiàn)地圖動(dòng)畫(huà)車(chē)效果。 我們公司也運(yùn)營(yíng)了一個(gè)類(lèi)似 Uber 的軟件 Namba Taxi耘沼,我們需要在客戶(hù)端主屏幕上顯示動(dòng)畫(huà)車(chē)极颓。 這篇文章是關(guān)于功能如何完整實(shí)現(xiàn)的文章,主要目的不是介紹 Go 語(yǔ)言群嗤。
開(kāi)始
這個(gè)故事始于2015年菠隆,我們的移動(dòng)開(kāi)發(fā)人員開(kāi)發(fā)一款軟件,工作主題是為出租車(chē)司機(jī)提供打車(chē)服務(wù)狂秘。 在應(yīng)用程序中骇径,動(dòng)畫(huà)汽車(chē)看起來(lái)像下面的圖中動(dòng)畫(huà)那樣 [1] 。
我們的第一個(gè)挑戰(zhàn)是缺乏地圖跟蹤數(shù)據(jù)赃绊。我們每 15 秒獲取一次位置數(shù)據(jù)既峡。 我們不能簡(jiǎn)單減小上報(bào)間隔,因?yàn)楫?dāng)司機(jī)端程序上行數(shù)據(jù)時(shí)候碧查,同時(shí)需要獲取當(dāng)前訂單,下一個(gè)訂單校仑,以及一些警報(bào)功能(一個(gè)SOS按鈕忠售, 當(dāng)司機(jī)按下它,其他司機(jī)就可以幫助他)迄沫。當(dāng)我們減少更新間隔時(shí)稻扬,系統(tǒng)流量更大。 我們不確認(rèn)我們是否能夠扛住如此大的刷新羊瘩。
實(shí)現(xiàn)的第一步
我們第一次的嘗試比較簡(jiǎn)單:
處理請(qǐng)求并保存坐標(biāo)泰佳。
創(chuàng)建另一個(gè)請(qǐng)求并為汽車(chē)設(shè)置動(dòng)畫(huà)。
顯而易見(jiàn)尘吗,這樣做存在一些問(wèn)題逝她,如大家在一些打車(chē)軟件所見(jiàn),我們不能正確地繪制汽車(chē)路線(xiàn)睬捶,汽車(chē)可能跑在田野黔宛,森林,湖泊和公寓上擒贸,用這種方法后效果看起來(lái)是這樣的 [2]臀晃。
作為問(wèn)題的解決方案,我們使用 OpenStreetMap Routeing Machine(OSRM)來(lái)規(guī)劃線(xiàn)路并改進(jìn)我們的算法介劫,并使用相同的超時(shí)設(shè)置徽惋。
發(fā)起請(qǐng)求。
獲取坐標(biāo)座韵。
將保存的坐標(biāo)發(fā)送到服務(wù)器险绘。
通過(guò) OSRM 構(gòu)建路線(xiàn)。
返回?cái)?shù)據(jù)到客戶(hù)端。
通過(guò)線(xiàn)路規(guī)劃體系隆圆,現(xiàn)在似乎可以工作了漱挚,但我們又面臨單向道路的問(wèn)題
例如,司機(jī)停留在紅點(diǎn)的十字路口渺氧。 但他的設(shè)備位置準(zhǔn)確性有問(wèn)題旨涝,導(dǎo)致數(shù)據(jù)標(biāo)記在十字路口的對(duì)面。 在客戶(hù)端侣背,我們獲取這些坐標(biāo)白华,保存并發(fā)送到后端,OSRM 建立一個(gè)合法的路線(xiàn)贩耐,并返回給應(yīng)用程序弧腥。因?yàn)榭蛻?hù)端移動(dòng)得非常快潮太,所以這種情況路線(xiàn)規(guī)劃很可笑管搪。
我們以一種樸素的方式解決了這個(gè)問(wèn)題。 我們檢查兩點(diǎn)之間的最短距離铡买,并且不建立距離小于 20 米的路線(xiàn)更鲁。 使用該算法經(jīng)過(guò)幾天的測(cè)試后,我們決定發(fā)布我們的應(yīng)用程序并希望獲取一些反饋奇钞。
盡管如此澡为,我們的版本還存在一些問(wèn)題,所以我們決定進(jìn)行第二次迭代景埃。
第一是車(chē)費(fèi)計(jì)算器媒至,計(jì)算是在司機(jī)端(客戶(hù)端)完成,這樣避免發(fā)送無(wú)用的請(qǐng)求谷徙,可以節(jié)約很多服務(wù)端資源拒啰。 另一方面,為了安全等方面考慮蒂胞,我們需要在服務(wù)器端復(fù)制數(shù)據(jù)并保存它图呢。
此外,我們意識(shí)到每 15 秒一次上報(bào)太少骗随,因?yàn)橛脩?hù)在屏幕打開(kāi)后蛤织,15秒后才會(huì)看到車(chē)在移動(dòng)。
此外鸿染,我們?cè)谒緳C(jī)端的 GPS 模塊有很多問(wèn)題指蚜,這個(gè)可能跟司機(jī)的手機(jī)設(shè)備相關(guān)。
最后涨椒,我們想要在主屏幕上渲染動(dòng)畫(huà)車(chē)摊鸡。
還需要解決的問(wèn)題
從司機(jī)收集更多的數(shù)據(jù)
在主屏幕上顯示動(dòng)畫(huà)車(chē)
在服務(wù)器端存儲(chǔ)行車(chē)過(guò)程中計(jì)費(fèi)數(shù)據(jù)
節(jié)約移動(dòng)流量
每秒收集一次數(shù)據(jù)
我想談一談?dòng)嘘P(guān)節(jié)約移動(dòng)流量帶寬的問(wèn)題绽媒。在我們國(guó)家,出租車(chē)收費(fèi)非常便宜免猾,我們像使用公共交通那樣使用出租車(chē)是辕。 例如,從城市的一邊跑到另一邊可能只需要 2 歐元猎提,這就跟在巴黎坐地鐵價(jià)格差不多获三。但另外一方面移動(dòng)帶寬成本還也很高,如果我們每秒節(jié)約 100 字節(jié)锨苏,那么我們將給為公司節(jié)省差不多 2000 美元疙教。
數(shù)據(jù)追蹤
司機(jī)位置(緯度,經(jīng)度)
司機(jī)當(dāng)前的 session 信息伞租,在登錄時(shí)我們會(huì)給司機(jī)端提供 session id
訂單信息(訂單 ID 和車(chē)費(fèi))
我們決定每一次數(shù)據(jù)上報(bào)應(yīng)小于 100 字節(jié)贞谓。 我們尋找傳輸協(xié)議來(lái)解決這個(gè)問(wèn)題
正如你可以看到,我們審視了以下幾個(gè)協(xié)議:
HTTP
WebSockets
TCP
UDP
對(duì)我們來(lái)說(shuō)理想的選擇是 UDP葵诈,因?yàn)椋?br>
我們只發(fā)送數(shù)據(jù)報(bào)
我們不需要保證送達(dá)
極簡(jiǎn)主義
保存大量數(shù)據(jù)
只有 20 字節(jié)開(kāi)銷(xiāo)
在我們的國(guó)家的移動(dòng)網(wǎng)絡(luò)沒(méi)有被阻止
至于數(shù)據(jù)序列化裸弦,我們考察了:
JSON
MsgPack
Protobuf
我們選擇 ProtoBuf,因?yàn)樗鼘?duì)小數(shù)據(jù)非常有效驯击。
以看到最近的競(jìng)爭(zhēng)對(duì)手是 PB 的三倍烁兰。(小編:可以參考 TimYang 的一條微博 [3] )
每次上報(bào)總共的數(shù)據(jù)
42 字節(jié)的業(yè)務(wù)數(shù)據(jù)
加上 20 字節(jié)的 IP 報(bào)頭
得到每次上報(bào) 62 字節(jié)數(shù)據(jù)
當(dāng)我們獲得數(shù)據(jù)時(shí),我們考慮如何存儲(chǔ)徊都。
數(shù)據(jù)存儲(chǔ)
我們需要存儲(chǔ)這些數(shù)據(jù):
標(biāo)識(shí)司機(jī)的會(huì)話(huà)信息 session id
車(chē)牌號(hào)
訂單 ID 和計(jì)費(fèi)信息
執(zhí)行搜索的最后位置
N 次最后位置以規(guī)劃路線(xiàn)
使用的存儲(chǔ)
使用 Percona 存儲(chǔ)所有數(shù)據(jù)。 我們存儲(chǔ)司機(jī)广辰,訂單暇矫,計(jì)費(fèi)等。
Redis 作為用于緩存择吊。
Elasticsearch 用于地理編碼
如上所述李根,當(dāng)有大量在線(xiàn)司機(jī)時(shí)候,使用這些存儲(chǔ)來(lái)保存數(shù)據(jù)并不方便几睛。 所以我們需要地理索引房轿。
我們?cè)u(píng)估了兩個(gè)地理索引:
KD 樹(shù)
R 樹(shù)。
我們對(duì)地理索引的要求:
搜索 N 個(gè)最近的點(diǎn)所森。
我們需要一個(gè)平衡樹(shù)囱持,以在最糟糕的情況下提供最好的搜索
KD 樹(shù)
KD 樹(shù)并不適合我們的需要,因?yàn)樗遣黄胶獾幕兰茫荒芩阉饕粋€(gè)最近的點(diǎn)纷妆。 我們可以在 kd-tree 上實(shí)現(xiàn) k-nearest 鄰居,但是沒(méi)必要重造輪子晴弃,因?yàn)?R-tree 已經(jīng)解決了這個(gè)問(wèn)題掩幢。
R-樹(shù)
它看起來(lái)像這樣逊拍。 我們可以執(zhí)行搜索 N 個(gè)最近點(diǎn)殴蹄,并且它是平衡樹(shù)涩维。 我們選擇了這個(gè)夏漱。
您可以得到它的 Go 語(yǔ)言實(shí)現(xiàn)源碼 [5]躏敢。
另外畅卓,我們需要一個(gè)過(guò)期機(jī)制裕循,因?yàn)槲覀冃枰顾緳C(jī)的超時(shí)機(jī)制串前,比如司機(jī)端 900 秒沒(méi)有響應(yīng)則在服務(wù)器刪除會(huì)話(huà)宵溅。 所以我們需要 LRU 數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)最后的位置度硝。 同時(shí)因?yàn)槲覀冎淮鎯?chǔ) N 個(gè)位置肿轨。 如果我們嘗試添加數(shù)據(jù)時(shí)候,隊(duì)列存儲(chǔ)已滿(mǎn)蕊程,我們則刪除最少使用的那個(gè)條目椒袍。?
下面是我們的存儲(chǔ)架構(gòu)。
我們將所有數(shù)據(jù)存儲(chǔ)在內(nèi)存中藻茂。
我們使用 R-tree 執(zhí)行搜索最近的司機(jī)驹暑。
此外,我們使用兩個(gè)檢索圖辨赐,可以并按車(chē)牌號(hào)或session執(zhí)行搜索
我們打車(chē)軟件最終算法
這里是后端的最終算法:
使用 UDP 傳輸數(shù)據(jù)
嘗試從存儲(chǔ)獲取司機(jī)
如果存儲(chǔ)不存在 - 則從 Redis 獲取司機(jī)
檢查并驗(yàn)證數(shù)據(jù)
將司機(jī)保存到存儲(chǔ)
如果不存在 - 初始化 LRU
-
更新 r-tree
HTTP 接口
我們實(shí)現(xiàn)了這些接口:
返回最近的司機(jī)优俘;
從存儲(chǔ)中刪除司機(jī)(通過(guò)車(chē)牌號(hào)或session id)
獲取行程信息
獲取司機(jī)信息
結(jié)論
最后,我想給出我們?cè)诤蠖讼到y(tǒng)中總結(jié)的經(jīng)驗(yàn):
UDP Protobuf 以節(jié)省數(shù)據(jù)
內(nèi)存存儲(chǔ)
R 樹(shù)獲取最近的司機(jī)
LRU 緩存用于存儲(chǔ)最后的 n 個(gè)位置
-
OSRM 用于地圖匹配和定制路線(xiàn)
您可以在 github [5]?上查看上面整個(gè)過(guò)程的源代碼∠菩颍現(xiàn)在功能還比較簡(jiǎn)單帆焕,但實(shí)現(xiàn)了文章中描述的許多功能。
參考資源
GIF 動(dòng)畫(huà)下載:https://cdn-images-1.medium.com/max/1600/1*nI6cNApASR1mg6F5Sjgp7Q.gif
https://cdn-images-1.medium.com/max/1600/1*KfGB1SARPoqOUtPtl4NNBg.gif
http://weibo.com/10503/24F1QpDmL
https://github.com/dhconnelly/rtreego
https://github.com/maddevsio/openfreecabs
本文英文原文:https://blog.maddevs.io/how-we-built-a-backend-system-for-uber-like-map-with-animated-cars-on-it-using-go-29d5dcd517a#.npo2x5788
推薦閱讀
本文由高可用架構(gòu)翻譯不恭,轉(zhuǎn)載請(qǐng)注明出處叶雹,技術(shù)原創(chuàng)及架構(gòu)實(shí)踐文章,歡迎通過(guò)公眾號(hào)菜單「聯(lián)系我們」進(jìn)行投稿换吧。
高可用架構(gòu)
改變互聯(lián)網(wǎng)的構(gòu)建方式
長(zhǎng)按二維碼 關(guān)注「高可用架構(gòu)」公眾號(hào)