Uber QPS最高的服務(wù)建立的背景及未來

　　2015年初，我們建立了一個(gè)微服務(wù)來負(fù)責(zé)這項(xiàng)任務(wù)：地理圍欄查找（geofence lookups），結(jié)果完成很出色。如今已過一年，這項(xiàng)技術(shù)在Uber數(shù)以百計(jì)的生產(chǎn)應(yīng)用中脫穎而出，成為了每秒查詢量最高（QPS）的服務(wù)。本文講述了我們建立這個(gè)服務(wù)的原因，還有近來Go語言對構(gòu)建和擴(kuò)展該服務(wù)速度的貢獻(xiàn)。
　　背景
　　在Uber，地理圍欄指的是地面上由人為定義的地理區(qū)域（或幾何術(shù)語中的多邊形），廣泛用于地理位置的配置中。向用戶展示在指定位置上有哪些產(chǎn)品可用，根據(jù)特定需求（比如機(jī)場）定義區(qū)域，在同時(shí)有多人請求搭車的周邊區(qū)域執(zhí)行動態(tài)定價(jià)，這些都非常重要。下圖是位于科羅拉多州的一個(gè)地理圍欄樣例：
　　
　　第一步是檢索地理位置的配置，根據(jù)用戶的手機(jī)定位，查找經(jīng)緯度之類的信息，以確定該位置處于哪個(gè)地理圍欄中。這個(gè)功能曾經(jīng)在多個(gè)服務(wù)/模塊中都有實(shí)現(xiàn)，不過隨著從單體架構(gòu)遷移到面向（微）服務(wù)架構(gòu)，我們選擇將這個(gè)功能集成在新的單體微服務(wù)中。
　　準(zhǔn)備出發(fā)！
　　根據(jù)我們的評估，那時(shí)最適合市場團(tuán)隊(duì)的語言是Node.js，因?yàn)槲覀冊谶@種語言上有更多的內(nèi)部知識和經(jīng)驗(yàn)。但是，出于下面這些原因，Go更符合我們的需求：
　　高吞吐量、低延遲的需求：從Uber移動應(yīng)用發(fā)出的每個(gè)請求都需要查找地理圍欄，而且必須在很短時(shí)間內(nèi)（第99個(gè)百分位《 100毫秒）快速對大量（每秒成千上萬個(gè)）查詢作出響應(yīng)；
　　CPU密集型的工作負(fù)載：地理圍欄查找需要使用大量占用CPU資源的算法來查找點(diǎn)是否在多邊形內(nèi)（point-in-polygon）。盡管Node.js在輸入/輸出密集型的服務(wù)中使用效果良好，但由于Node本質(zhì)上屬于解釋型和動態(tài)類型的語言，在這種用例中并非最佳選擇；
　　無干擾后臺加載：為了確保我們獲取并執(zhí)行查找的地理圍欄數(shù)據(jù)是最新的，該服務(wù)必須后臺讀取多個(gè)來源的數(shù)據(jù)，持續(xù)刷新內(nèi)存中的地理圍欄數(shù)據(jù)。由于Node.js是單線程的，后臺刷新會在相當(dāng)長的時(shí)間內(nèi)占用CPU（例如CPU密集型的JSON解析工作），從而延遲對查詢的響應(yīng)時(shí)間。對于Go來說這不是問題，用goroutines就可以通過多核CPU執(zhí)行，后臺任務(wù)與前臺查詢并行執(zhí)行。
　　Geo索引：用還是不用，這是個(gè)問題
　　我們?nèi)绾胃鶕?jù)經(jīng)緯度指定的位置，在成千上萬個(gè)地理圍欄中查找它屬于其中的哪一個(gè)？使用簡單匹配算法（brute-force）非常簡單：只要一一查看所有地理圍欄，并使用算法（比如光線投射算法）進(jìn)行點(diǎn)是否在多邊形內(nèi)的比對。不過這個(gè)辦法速度太慢。那么，如何有效地縮小搜索范圍呢？
　　我們沒有使用R-tree或復(fù)雜的S2算法，而是選擇了更簡單的辦法來找出地理圍欄：Uber的商業(yè)模型是以城市為中心的，其商業(yè)規(guī)則還有定義商業(yè)規(guī)則的地理圍欄一般都與城市密切相關(guān)。這樣我們就可以將地理圍欄分為兩種層級，第一層是城市地理圍欄（定義城市邊界的地理圍欄），第二層是城市間的地理圍欄。
　　每次查找，我們首先會通過線性掃描，查找所有的城市地理圍欄，定位所在城市；然后再次通過線性掃描，找出其中包含的地理圍欄。根據(jù)該解決方案的復(fù)雜程度，運(yùn)行時(shí)長為O（n），n被大幅縮減到100s到10000s的數(shù)量級。
　　架構(gòu)
　　我們希望這項(xiàng)服務(wù)是無狀態(tài)的，以便適用于所有請求；同時(shí)在所有的服務(wù)實(shí)例中，每個(gè)請求的結(jié)果相同。這意味著每個(gè)服務(wù)實(shí)例都必須有全世界的信息，而不是某個(gè)分區(qū)的。我們使用確定性輪詢調(diào)度，確保來自不同服務(wù)實(shí)例的地理圍欄數(shù)據(jù)保持同步。這樣一來，該服務(wù)的架構(gòu)就非常簡單了。后臺任務(wù)定期對不同的數(shù)據(jù)庫的地理圍欄數(shù)據(jù)進(jìn)行輪詢，并將這些數(shù)據(jù)存儲在主內(nèi)存中，為查詢提供服務(wù)；同時(shí)序列化到本地文件系統(tǒng)中，在服務(wù)重啟時(shí)快速引導(dǎo)載入：
　　
　　上圖是我們的地理圍欄查找服務(wù)架構(gòu)。
　　處理Go內(nèi)存模型
　　我們的架構(gòu)需要讀取/寫入并發(fā)訪問內(nèi)存中的geo索引，特別是：在前臺查詢引擎從索引讀取時(shí)，后臺輪詢?nèi)蝿?wù)會對索引執(zhí)行寫入。對于習(xí)慣Node.js單線程的用戶來說，Go的內(nèi)存模型可能會構(gòu)成挑戰(zhàn)。在Go中，常用的方式是通過goroutines與channels同步并發(fā)讀取/寫入任務(wù)，出于對性能負(fù)面影響的擔(dān)心，我們嘗試使用sync/atomic數(shù)據(jù)包的StorePointer/LoadPointer基元自行管理內(nèi)存屏障，卻導(dǎo)致代碼脆弱且難以維護(hù)。
　　最后我們進(jìn)行了妥協(xié)，使用讀寫鎖來同步到geo索引的訪問。為了將鎖定等待的時(shí)間減到最短，在轉(zhuǎn)到主索引之前，我們另外構(gòu)建了新的索引區(qū)段為查詢提供服務(wù)。使用鎖定導(dǎo)致查詢的延遲相對于StorePointer/LoadPointer的辦法來說有稍許增加，不過在我們看來利大于弊：代碼簡單化和可維護(hù)性的好處值得用稍許性能來換。
　　我們的經(jīng)驗(yàn)
　　回顧之前的工作，我們非常慶幸選擇了Go這種新語言來編寫服務(wù)。
　　優(yōu)勢：
　　開發(fā)人員工作效率很高：C++、Java或Node.js開發(fā)人員一般只需數(shù)日便可學(xué)會使用Go語言，而且這種語言的代碼易于維護(hù)。（多虧了這種語言是靜態(tài)類型的，免去了很多猜測和意外）。
　　吞吐量和延遲表現(xiàn)都很好：僅在我們服務(wù)于非中國區(qū)的主數(shù)據(jù)中心上，在2015年新年前夜，該服務(wù)所處理查詢數(shù)據(jù)的峰值負(fù)載就達(dá)到每秒查詢量（QPS）17萬，40臺機(jī)器都占用了35%的CPU。第95個(gè)百分位響應(yīng)時(shí)間小于5毫秒，第99個(gè)百分位響應(yīng)時(shí)間小于50毫秒。
　　超級可靠：從一開始該服務(wù)的正常運(yùn)行時(shí)間就達(dá)到99.99%。唯一一次停機(jī)是由于初學(xué)者的編程錯誤，一個(gè)文件描述符將bug引入第三方數(shù)據(jù)庫。重要的是：在Go運(yùn)行時(shí)我們還沒發(fā)現(xiàn)什么問題。
　　下一步的未來
　　盡管之前Uber的服務(wù)大多使用Node.js和Python，但Go語言逐漸成為許多Uber工程服務(wù)的新選擇。