如何用Go實(shí)現(xiàn)一款類(lèi)似滴滴優(yōu)步的網(wǎng)絡(luò)約車(chē)軟件(含源碼)

導(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)單:


  1. 處理請(qǐng)求并保存坐標(biāo)泰佳。

  2. 創(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è)置徽惋。


  1. 發(fā)起請(qǐng)求。

  2. 獲取坐標(biāo)座韵。

  3. 將保存的坐標(biāo)發(fā)送到服務(wù)器险绘。

  4. 通過(guò) OSRM 構(gòu)建路線(xiàn)。

  5. 返回?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)行第二次迭代景埃。


  1. 第一是車(chē)費(fèi)計(jì)算器媒至,計(jì)算是在司機(jī)端(客戶(hù)端)完成,這樣避免發(fā)送無(wú)用的請(qǐng)求谷徙,可以節(jié)約很多服務(wù)端資源拒啰。 另一方面,為了安全等方面考慮蒂胞,我們需要在服務(wù)器端復(fù)制數(shù)據(jù)并保存它图呢。

  2. 此外,我們意識(shí)到每 15 秒一次上報(bào)太少骗随,因?yàn)橛脩?hù)在屏幕打開(kāi)后蛤织,15秒后才會(huì)看到車(chē)在移動(dòng)。

  3. 此外鸿染,我們?cè)谒緳C(jī)端的 GPS 模塊有很多問(wèn)題指蚜,這個(gè)可能跟司機(jī)的手機(jī)設(shè)備相關(guān)。

  4. 最后涨椒,我們想要在主屏幕上渲染動(dòng)畫(huà)車(chē)摊鸡。


還需要解決的問(wèn)題


  1. 從司機(jī)收集更多的數(shù)據(jù)

  2. 在主屏幕上顯示動(dòng)畫(huà)車(chē)

  3. 在服務(wù)器端存儲(chǔ)行車(chē)過(guò)程中計(jì)費(fèi)數(shù)據(jù)

  4. 節(jié)約移動(dòng)流量

  5. 每秒收集一次數(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ù)追蹤


  1. 司機(jī)位置(緯度,經(jīng)度)

  2. 司機(jī)當(dāng)前的 session 信息伞租,在登錄時(shí)我們會(huì)給司機(jī)端提供 session id

  3. 訂單信息(訂單 ID 和車(chē)費(fèi))


我們決定每一次數(shù)據(jù)上報(bào)應(yīng)小于 100 字節(jié)贞谓。 我們尋找傳輸協(xié)議來(lái)解決這個(gè)問(wèn)題

正如你可以看到,我們審視了以下幾個(gè)協(xié)議:


  1. HTTP

  2. WebSockets

  3. TCP

  4. UDP


對(duì)我們來(lái)說(shuō)理想的選擇是 UDP葵诈,因?yàn)椋?br>


  1. 我們只發(fā)送數(shù)據(jù)報(bào)

  2. 我們不需要保證送達(dá)

  3. 極簡(jiǎn)主義

  4. 保存大量數(shù)據(jù)

  5. 只有 20 字節(jié)開(kāi)銷(xiāo)

  6. 在我們的國(guó)家的移動(dòng)網(wǎng)絡(luò)沒(méi)有被阻止


至于數(shù)據(jù)序列化裸弦,我們考察了:


  1. JSON

  2. MsgPack

  3. Protobuf


我們選擇 ProtoBuf,因?yàn)樗鼘?duì)小數(shù)據(jù)非常有效驯击。



以看到最近的競(jìng)爭(zhēng)對(duì)手是 PB 的三倍烁兰。(小編:可以參考 TimYang 的一條微博 [3] )


每次上報(bào)總共的數(shù)據(jù)


  1. 42 字節(jié)的業(yè)務(wù)數(shù)據(jù)

  2. 加上 20 字節(jié)的 IP 報(bào)頭

  3. 得到每次上報(bào) 62 字節(jié)數(shù)據(jù)


當(dāng)我們獲得數(shù)據(jù)時(shí),我們考慮如何存儲(chǔ)徊都。


數(shù)據(jù)存儲(chǔ)


我們需要存儲(chǔ)這些數(shù)據(jù):


  1. 標(biāo)識(shí)司機(jī)的會(huì)話(huà)信息 session id

  2. 車(chē)牌號(hào)

  3. 訂單 ID 和計(jì)費(fèi)信息

  4. 執(zhí)行搜索的最后位置

  5. N 次最后位置以規(guī)劃路線(xiàn)


使用的存儲(chǔ)


  1. 使用 Percona 存儲(chǔ)所有數(shù)據(jù)。 我們存儲(chǔ)司機(jī)广辰,訂單暇矫,計(jì)費(fèi)等。

  2. Redis 作為用于緩存择吊。

  3. Elasticsearch 用于地理編碼


如上所述李根,當(dāng)有大量在線(xiàn)司機(jī)時(shí)候,使用這些存儲(chǔ)來(lái)保存數(shù)據(jù)并不方便几睛。 所以我們需要地理索引房轿。

我們?cè)u(píng)估了兩個(gè)地理索引:


  1. KD 樹(shù)

  2. R 樹(shù)。


我們對(duì)地理索引的要求:


  1. 搜索 N 個(gè)最近的點(diǎn)所森。

  2. 我們需要一個(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)。


  1. 我們將所有數(shù)據(jù)存儲(chǔ)在內(nèi)存中藻茂。

  2. 我們使用 R-tree 執(zhí)行搜索最近的司機(jī)驹暑。

  3. 此外,我們使用兩個(gè)檢索圖辨赐,可以并按車(chē)牌號(hào)或session執(zhí)行搜索


我們打車(chē)軟件最終算法


這里是后端的最終算法:


  1. 使用 UDP 傳輸數(shù)據(jù)

  2. 嘗試從存儲(chǔ)獲取司機(jī)

  3. 如果存儲(chǔ)不存在 - 則從 Redis 獲取司機(jī)

  4. 檢查并驗(yàn)證數(shù)據(jù)

  5. 將司機(jī)保存到存儲(chǔ)

  6. 如果不存在 - 初始化 LRU

  7. 更新 r-tree


HTTP 接口


我們實(shí)現(xiàn)了這些接口:


  1. 返回最近的司機(jī)优俘;

  2. 從存儲(chǔ)中刪除司機(jī)(通過(guò)車(chē)牌號(hào)或session id)

  3. 獲取行程信息

  4. 獲取司機(jī)信息


結(jié)論


最后,我想給出我們?cè)诤蠖讼到y(tǒng)中總結(jié)的經(jīng)驗(yàn):


  1. UDP Protobuf 以節(jié)省數(shù)據(jù)

  2. 內(nèi)存存儲(chǔ)

  3. R 樹(shù)獲取最近的司機(jī)

  4. LRU 緩存用于存儲(chǔ)最后的 n 個(gè)位置

  5. OSRM 用于地圖匹配和定制路線(xiàn)




您可以在 github [5]?上查看上面整個(gè)過(guò)程的源代碼∠菩颍現(xiàn)在功能還比較簡(jiǎn)單帆焕,但實(shí)現(xiàn)了文章中描述的許多功能。


參考資源


  1. GIF 動(dòng)畫(huà)下載:https://cdn-images-1.medium.com/max/1600/1*nI6cNApASR1mg6F5Sjgp7Q.gif

  2. https://cdn-images-1.medium.com/max/1600/1*KfGB1SARPoqOUtPtl4NNBg.gif

  3. http://weibo.com/10503/24F1QpDmL

  4. https://github.com/dhconnelly/rtreego

  5. https://github.com/maddevsio/openfreecabs

  6. 本文英文原文: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)

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末折晦,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子沾瓦,更是在濱河造成了極大的恐慌满着,老刑警劉巖,帶你破解...
    沈念sama閱讀 219,270評(píng)論 6 508
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件贯莺,死亡現(xiàn)場(chǎng)離奇詭異风喇,居然都是意外死亡,警方通過(guò)查閱死者的電腦和手機(jī)乖篷,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,489評(píng)論 3 395
  • 文/潘曉璐 我一進(jìn)店門(mén)响驴,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái),“玉大人撕蔼,你說(shuō)我怎么就攤上這事豁鲤』嗵埽” “怎么了?”我有些...
    開(kāi)封第一講書(shū)人閱讀 165,630評(píng)論 0 356
  • 文/不壞的土叔 我叫張陵琳骡,是天一觀(guān)的道長(zhǎng)锅论。 經(jīng)常有香客問(wèn)我,道長(zhǎng)楣号,這世上最難降的妖魔是什么最易? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 58,906評(píng)論 1 295
  • 正文 為了忘掉前任,我火速辦了婚禮炫狱,結(jié)果婚禮上藻懒,老公的妹妹穿的比我還像新娘。我一直安慰自己视译,他們只是感情好嬉荆,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,928評(píng)論 6 392
  • 文/花漫 我一把揭開(kāi)白布。 她就那樣靜靜地躺著酷含,像睡著了一般鄙早。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上椅亚,一...
    開(kāi)封第一講書(shū)人閱讀 51,718評(píng)論 1 305
  • 那天限番,我揣著相機(jī)與錄音,去河邊找鬼呀舔。 笑死弥虐,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的媚赖。 我是一名探鬼主播躯舔,決...
    沈念sama閱讀 40,442評(píng)論 3 420
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼省古!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起丧失,我...
    開(kāi)封第一講書(shū)人閱讀 39,345評(píng)論 0 276
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤豺妓,失蹤者是張志新(化名)和其女友劉穎,沒(méi)想到半個(gè)月后布讹,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體琳拭,經(jīng)...
    沈念sama閱讀 45,802評(píng)論 1 317
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,984評(píng)論 3 337
  • 正文 我和宋清朗相戀三年描验,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了白嘁。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,117評(píng)論 1 351
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡膘流,死狀恐怖絮缅,靈堂內(nèi)的尸體忽然破棺而出鲁沥,到底是詐尸還是另有隱情,我是刑警寧澤耕魄,帶...
    沈念sama閱讀 35,810評(píng)論 5 346
  • 正文 年R本政府宣布画恰,位于F島的核電站,受9級(jí)特大地震影響吸奴,放射性物質(zhì)發(fā)生泄漏允扇。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,462評(píng)論 3 331
  • 文/蒙蒙 一则奥、第九天 我趴在偏房一處隱蔽的房頂上張望考润。 院中可真熱鬧,春花似錦读处、人聲如沸糊治。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 32,011評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)俊戳。三九已至,卻和暖如春馆匿,著一層夾襖步出監(jiān)牢的瞬間抑胎,已是汗流浹背。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,139評(píng)論 1 272
  • 我被黑心中介騙來(lái)泰國(guó)打工渐北, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留阿逃,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 48,377評(píng)論 3 373
  • 正文 我出身青樓赃蛛,卻偏偏與公主長(zhǎng)得像恃锉,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子呕臂,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,060評(píng)論 2 355

推薦閱讀更多精彩內(nèi)容