導(dǎo)讀：我們經(jīng)常使用打車軟件出行，也經(jīng)常思考其架構(gòu)設(shè)計(jì)。本文作者在所在國(guó)家也負(fù)責(zé)開發(fā)一款打車軟件，并且開源了其中大部分代碼，可以幫助我們更好了解網(wǎng)絡(luò)約車軟件的架構(gòu)體系。本文由高可用架構(gòu)翻譯。

各位讀者好，本文將給大家分享我們?nèi)绾瓮ㄟ^內(nèi)存存儲(chǔ)實(shí)現(xiàn)地圖動(dòng)畫車效果。 我們公司也運(yùn)營(yíng)了一個(gè)類似 Uber 的軟件 Namba Taxi，我們需要在客戶端主屏幕上顯示動(dòng)畫車。 這篇文章是關(guān)于功能如何完整實(shí)現(xiàn)的文章，主要目的不是介紹 Go 語言。

開始

這個(gè)故事始于2015年，我們的移動(dòng)開發(fā)人員開發(fā)一款軟件，工作主題是為出租車司機(jī)提供打車服務(wù)。 在應(yīng)用程序中，動(dòng)畫汽車看起來像下面的圖中動(dòng)畫那樣 [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)求并為汽車設(shè)置動(dòng)畫。

顯而易見，這樣做存在一些問題，如大家在一些打車軟件所見，我們不能正確地繪制汽車路線，汽車可能跑在田野，森林，湖泊和公寓上，用這種方法后效果看起來是這樣的 [2]。

作為問題的解決方案，我們使用 OpenStreetMap Routeing Machine（OSRM）來規(guī)劃線路并改進(jìn)我們的算法，并使用相同的超時(shí)設(shè)置。

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

獲取坐標(biāo)。

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

通過 OSRM 構(gòu)建路線。

返回?cái)?shù)據(jù)到客戶端。

通過線路規(guī)劃體系，現(xiàn)在似乎可以工作了，但我們又面臨單向道路的問題

例如，司機(jī)停留在紅點(diǎn)的十字路口。 但他的設(shè)備位置準(zhǔn)確性有問題，導(dǎo)致數(shù)據(jù)標(biāo)記在十字路口的對(duì)面。 在客戶端，我們獲取這些坐標(biāo)，保存并發(fā)送到后端，OSRM 建立一個(gè)合法的路線，并返回給應(yīng)用程序。因?yàn)榭蛻舳艘苿?dòng)得非常快，所以這種情況路線規(guī)劃很可笑。

我們以一種樸素的方式解決了這個(gè)問題。?我們檢查兩點(diǎn)之間的最短距離，并且不建立距離小于 20 米的路線。?使用該算法經(jīng)過幾天的測(cè)試后，我們決定發(fā)布我們的應(yīng)用程序并希望獲取一些反饋。

盡管如此，我們的版本還存在一些問題，所以我們決定進(jìn)行第二次迭代。

第一是車費(fèi)計(jì)算器，計(jì)算是在司機(jī)端（客戶端）完成，這樣避免發(fā)送無用的請(qǐng)求，可以節(jié)約很多服務(wù)端資源。 另一方面，為了安全等方面考慮，我們需要在服務(wù)器端復(fù)制數(shù)據(jù)并保存它。

此外，我們意識(shí)到每 15 秒一次上報(bào)太少，因?yàn)橛脩粼谄聊淮蜷_后，15秒后才會(huì)看到車在移動(dòng)。

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

最后，我們想要在主屏幕上渲染動(dòng)畫車。

還需要解決的問題

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

在主屏幕上顯示動(dòng)畫車

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

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

每秒收集一次數(shù)據(jù)

我想談一談?dòng)嘘P(guān)節(jié)約移動(dòng)流量帶寬的問題。在我們國(guó)家，出租車收費(fèi)非常便宜，我們像使用公共交通那樣使用出租車。 例如，從城市的一邊跑到另一邊可能只需要 2 歐元，這就跟在巴黎坐地鐵價(jià)格差不多。但另外一方面移動(dòng)帶寬成本還也很高，如果我們每秒節(jié)約 100 字節(jié)，那么我們將給為公司節(jié)省差不多 2000 美元。

數(shù)據(jù)追蹤

司機(jī)位置（緯度，經(jīng)度）

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

訂單信息（訂單 ID 和車費(fèi)）

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

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

HTTP

WebSockets

TCP

UDP

對(duì)我們來說理想的選擇是 UDP，因?yàn)?#xff1a;

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

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

極簡(jiǎn)主義

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

只有 20 字節(jié)開銷

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

至于數(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ì)話信息 session id

車牌號(hào)

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

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

N 次最后位置以規(guī)劃路線

使用的存儲(chǔ)

使用 Percona 存儲(chǔ)所有數(shù)據(jù)。 我們存儲(chǔ)司機(jī)，訂單，計(jì)費(fèi)等。

Redis 作為用于緩存。

Elasticsearch 用于地理編碼

如上所述，當(dāng)有大量在線司機(jī)時(shí)候，使用這些存儲(chǔ)來保存數(shù)據(jù)并不方便。 所以我們需要地理索引。

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

KD 樹

R 樹。

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

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

我們需要一個(gè)平衡樹，以在最糟糕的情況下提供最好的搜索

KD 樹

KD 樹并不適合我們的需要，因?yàn)樗遣黄胶獾?#xff0c;只能搜索一個(gè)最近的點(diǎn)。 我們可以在 kd-tree 上實(shí)現(xiàn) k-nearest 鄰居，但是沒必要重造輪子，因?yàn)?R-tree 已經(jīng)解決了這個(gè)問題。

R-樹

它看起來像這樣。 我們可以執(zhí)行搜索 N 個(gè)最近點(diǎn)，并且它是平衡樹。 我們選擇了這個(gè)。

您可以得到它的 Go 語言實(shí)現(xiàn)源碼 [5]。

另外，我們需要一個(gè)過期機(jī)制，因?yàn)槲覀冃枰顾緳C(jī)的超時(shí)機(jī)制，比如司機(jī)端 900 秒沒有響應(yīng)則在服務(wù)器刪除會(huì)話。 所以我們需要 LRU 數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)最后的位置。 同時(shí)因?yàn)槲覀冎淮鎯?chǔ) N 個(gè)位置。 如果我們嘗試添加數(shù)據(jù)時(shí)候，隊(duì)列存儲(chǔ)已滿，我們則刪除最少使用的那個(gè)條目。?

下面是我們的存儲(chǔ)架構(gòu)。

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

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

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

我們打車軟件最終算法

這里是后端的最終算法：

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

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

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

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

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

如果不存在 - 初始化 LRU

更新 r-tree

HTTP 接口

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

返回最近的司機(jī)；

從存儲(chǔ)中刪除司機(jī)（通過車牌號(hào)或session id）

獲取行程信息

獲取司機(jī)信息

結(jié)論

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

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

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

R 樹獲取最近的司機(jī)

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

OSRM 用于地圖匹配和定制路線

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

參考資源

• GIF 動(dòng)畫下載
• http://weibo.com/10503/24F1QpDmL
• https://github.com/dhconnelly/rtreego
• https://github.com/maddevsio/openfreecabs

總結(jié)

以上是生活随笔為你收集整理的如何用Go实现一款类似滴滴优步的网络约车软件(含源码)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。