Uber是如何擴展他們的實時市場平臺的

來自：http://www.infoq.com/cn/articles/how-buer-expand-their-real-time-market-platform

據了解，在短短四年間， Uber已經 驚人地增長了38倍。最近，Uber的首席系統架構師 Matt Ranney 在他的報告“ 擴展Uber的實時市場平臺”中，對Uber軟件系統的工作原理進行了一個有趣而又詳細的介紹。本文對Matt的報告內容作了一個簡單的總結。本文是一篇翻譯稿，原文題目為“ How Uber Scales Their Real-Time Market Platform”，已獲得作者授權。

在Matt的報告中，給人印象最深刻的是Uber的快速增長。他們對于系統架構所做的很多選擇都是基于公司規模的快速增長。很多技術都運行在后臺，因為盡可能地讓團隊快速運轉一直是他們的主要目標。

經過開始時期一個短暫的混亂階段之后，Uber已經從自身的業務中學習到了很多，包括成功所真正需要的東西。他們早期的調度系統主要是面向移動的 人。而現在，除了人之外，Uber的任務已經發展到處理箱子和雜貨，他們的調度系統已經被抽象化，并且構建了非常堅實和智能化的基礎架構。

雖然Matt認為，他們的架構可能有一些瘋狂，但是使用附帶gossip協議的一致性哈希ring的想法似乎正好符合他們的實際情況。

不被Matt的工作熱情所吸引是很困難的。在談到他們的調度系統DISCO的時候，他非常興奮地說到，這實際上就像一個很酷的計算機科學問題，即旅 行商問題。盡管該解決方案不是最佳的，但將其想象為一個真實世界中旅行商，他具有一個有趣的規模，而且是實時的，內置了容錯可伸縮的組件。這多酷啊！

本文中，我們介紹了Uber的調度系統，他們是如何實現地理空間索引，他們是如何擴展他們的系統，他們是如何實現高可用性，以及他們如何處理系統故 障，包括當出現數據中心故障的時候，通過將司機的手機作為一個外部分布式存儲系統，Uber采用了一種非常出色的系統恢復方式。

統計

• Uber地理空間索引的目標是以每秒百萬次的速度寫入，以及以寫入速度數倍的速度讀出。
• 該調度系統具有數千個節點。

平臺

• Node.js
• Python
• Java
• Go
• iOS和Android系統上的本地應用程序
• Microservices
• Redis
• Postgres
• MySQL
• Riak
• 推ter Twemproxy
• Google的S2 Geometry Library
• ringpop—一致性哈希ring
• TChannel—RPC網絡復用和成幀協議
• Thrift

架構概述

• 驅動這一切的是使用移動電話運行原生應用程序的乘客和司機。
• 后端主要為移動電話之間的信息處理服務。客戶端與后端之間的通信是通過移動數據和盡力而為的互聯網。
• 客戶端連接到調度系統，以匹配乘客和司機之間的供應和需求。
• 調度系統幾乎完全用Node.js編寫。
  • 過去計劃將其移動到io.js，但之后io.js和Node.js合并所以放棄了。
  • 你可以在JavaScript上做一些有趣的分布式系統工作。
• 整個Uber系統可能看起來很簡單。但這種簡單的方式就是成功的標志。只要它看起來足夠簡單，他們的工作就完成了。
• 地圖/ ETA（預計到達時間）。在調度過程中，獲取地圖和路由信息對于最終做出明智的選擇是非常必要的。
  • 街道地圖和歷史出行時間被用來估計當前的出行時間。
  • 使用的語言很大程度上取決于系統所要集成的內容。因此，語言包括Python，C ++和Java。
• 服務。存在大量的業務邏輯服務。
  • 微服務。
  • 大多用Python編寫。
• 數據庫
  • 最早的系統是用Postgres編寫。
  • 使用Redis。一些是在Twemproxy中，一些是在自定義集群系統中。
  • MySQL
  • Uber 正在構建自己分布式列存儲，以存儲MySQL實例。
  • 一些調度服務保存狀態在Riak中。
• 評論和反饋。一次出行完成之后還需要大量的處理。
  • 收集評分。
  • 發送電子郵件。
  • 更新數據庫。
  • 計劃付款。
  • 用Python編寫。
• 費用。Uber集成了多種支付系統。

舊的調度系統

• 原來的調度系統中的不足已經開始限制公司的增長，所以它不得不改變。
• 系統的大部分都需要重寫。
• 舊的系統是專為個人出行而設計，它做了很多假設：
  • 每輛車只有一個乘客，這種假設不適合Uber Pool。
  • 只有移動的人被考慮到數據模型和接口中。這限制了公司進軍新市場和新產品，如需要運輸的食品和箱子。
  • 最初的版本是按城市進行分片。這具有很好的可擴展性，因為每個城市可以獨立運行。但隨著越來越多城市的加入，它變得越來越難以管理。城市有大有小，不同城市的交通負荷也不同。
• 因為很多東西都是被快速構建起來，因此一旦出現故障，都會相互影響。

新的調度系統

• 為了解決城市分片問題以及支持更多類型的產品，供應和需求的概念必須被擴展，所以一個供應服務和一個需求服務應該被創建。
• 供應服務跟蹤所有供應的數量，以及它們的狀態。
  • 跟蹤車輛需要建模很多屬性：座位數，車輛的類型，車輛是否有兒童專座，是否能容納一個輪椅，等等。
  • 車輛的容量需要被跟蹤。例如一輛車輛，可能有三個席位，但其中兩個已經被占用了。
• 需求服務跟蹤所有請求和訂單，以及方方面面的要求。
  • 如果一個乘客需要一個汽車座位，那么請求必須與庫存相匹配。
  • 如果乘客不介意以一個更便宜的價格分享車輛座位，這種情況也需要被建模。
  • 如果有箱子或食物需要運送怎么辦？
• 匹配所有需求與供應的方法是一種被稱為DISCO的服務（調度優化）
  • 舊的系統僅僅是匹配現有的供應量，這意味著僅僅針對在路上等待工作的車輛。
  • DISCO支持對未來的預測，一旦車輛變成可用，系統就馬上利用這些信息。
  • 汽車地理位置索引（geo by supply）。DISCO需要一個地理空間索引，以基于所有供應的位置以及它們預計所在的地點來進行決策。
  • 需求地理位置索引（geo by demand）。需求也需要地理空間索引
  • 一個更好的路由引擎需要利用所有這些信息。

調度

• 當車輛在周圍移動的時候，位置更新將發送給geo by supply。為了將乘客與司機進行匹配，或將汽車顯示在地圖上，DISCO發送一個請求給geo by supply。
• Geo by supply進行一個簡單的初步過濾，以獲得附近的符合要求的候選車輛。
• 然后列表和要求被發送到路由/ETA，以計算它們目前的距離有多近。距離并不是地理上的，而是通過道路系統計算得到。
• ETA的排序結果被發送回供應系統，然后將結果提供給司機。

地理空間索引

• 必須有很高的可擴展性。設計目標是每秒處理百萬次寫入。當司機在移動的時候每4秒發送一次位置更新，寫入速度由此計算出來。
• 對于讀出來說，每秒讀出的次數應該遠多于每秒寫入的次數，因為每個開放的app用戶都在進行讀出操作。大部分供應都處于繁忙狀態，所以有效供應中只有一部分能夠利用。
• 通過一個簡單的假設，舊的地理空間索引運行良好，即它只追蹤可調度的供應。大部分供應都處于繁忙狀態，所以有效供應中只有一部分能夠利用。在幾 個進程中存在一個全局索引存儲在內存中。因此做一些簡單的匹配是比較容易的。舊的地理空間索引只追蹤可調度的供應。大部分供應都處于繁忙狀態，所以有效供 應中只有一部分能夠利用。
• 在新的系統中，不同狀態的所有供應都必須被跟蹤。此外，它們的規劃路由也必須被跟蹤。
• 新的服務運行了數百個進程。
• 地球是一個球體。很難純粹基于經度和緯度做計算和近似。所以Uber通過使用Google S2 library把地球分成小的單元。每個單元都有一個唯一的ID號。
• 使用一個64位數，地球上的每一平方厘米都可以被表示。對于每個單元的大小，Uber分成了12個層次，從3.31平方公里到6.38平方公里，每個單元的形狀和大小也不同，這些都取決于你在地球上的位置。
• S2可以為一個具體的形狀給出覆蓋單元。如果你想在倫敦繪制一個半徑為1公里的圓圈，S2可以告訴你需要哪些單元來完全覆蓋這個形狀。
• 由于每個單元都有一個ID號，而ID號被用作一個分片密鑰。當一個位置加入到供給中時，這個位置的ID就確定了。
• 當DISCO需要在位置附近找到供應的時候，以司機所在位置為中心進行畫圈，計算不同位置的價值。使用圓圈區域內的單元ID，集合所有相關的分片，然后返回供應數據。
• 所有都是可擴展的。通過增加更多的節點寫入負載總是能被擴展。通過使用副本讀出負載也能被擴展。如果需要更高的讀出能力，可以增加更多的副本。
• 單元大小被固定在12個層次也存在不足。未來可能支持動態單元大小。

路由

• 存在幾個高層次的目標：
  • 減少額外的駕駛。理想的情況下，司機應該一直載著乘客，但現實中總是存在排隊等事情，司機應該為所有事情獲得報酬。
  • 減少等待。司機應當等待的盡可能少。
  • ETA總量應該最小。
• 舊的系統按要求搜索當前可用的供應，然后找到最匹配的
• 僅僅查看當前可用的供應還不能做出好的選擇。
• 我們的想法是，對于一個客戶來說，問一個正載著乘客的司機比問一個閑置的但距離很遠的司機要更好。
• 通過這個預測模型，動態條件能夠被更好地處理。
  • 例如，如果一個司機正好在一個顧客附近，但是另一個司機已經從遠處被調度過來，沒有辦法改變這種調度決策。
  • 舉另一個例子，對于那些想分享車輛的顧客。在很多復雜的場景中，通過盡力地對未來進行預測，更多的優化是可能的。
• 當考慮箱子或食品的運輸時，所有這些決策將變得更加有趣。

擴展調度

• 使用Node.js構建。
• 他們正在構建一個有狀態的服務，因此無狀態的擴展方法將無法正常工作。
• Node是單進程運行的，因此需要設計方法讓Node運行在一臺機器的多個cpu上，以及運行在多臺機器上。
• 使用JavaScript重新實現所有的Erlang是一個笑話。
• 擴展Node的解決辦法是ringpop，其是一個附帶gossip協議的一致哈希ring，實現一個可擴展的，容錯的應用層分片。
• 在CAP術語中，ringpop是一個AP系統,犧牲一致性來換取可用性。這就容易解釋偶爾出現些小的不一致比一個越變越差的服務要好。雖然偶爾犯錯，但如果總體上越變越好，這是沒關系的。
• ringpop是一個可嵌入的模塊，包含在每個Node進程中。
• Node實例閑置在一個隸屬集附近。
• 這是可伸縮的。通過添加更多的進程，可以完成更多的工作。添加的進程可以用來對數據進行分片，或者作為一個分布式鎖定系統，或者為發布/訂閱協調一個集合點。
• gossip協議是基于SWIM。為減少收斂時間，有幾個方面做了改進。
• 很多成員在周圍閑置。通過加入越來越多的節點，它就實現了擴展的目標。SWIM中的“S”代表可擴展。目前，它已經可以擴展到數千個節點。
• SWIM結合了健康檢查與成員變更作為同一協議的一部分
• 在ringpop系統中，存在包含ringpop模塊的所有Node進程。他們閑置在當前的成員周圍。
• 從外部看，如果DISCO要消耗地理空間，每個Node是等價的。一個健康節點是隨機選擇的。無論該請求出現在哪，都通過使用hash ring查詢負責將請求轉發到正確的節點。看起來像：

  

• 讓所有這些hop和peer互相對話，可能聽起來很瘋狂。但它達到了非常不錯的性能，例如，通過在任何機器上添加實例，服務可以被擴展。
• ringpop是構建在Uber自己的RPC機制，稱為TChannel。
  • 這是一個雙向的請求/響應協議，它的靈感來自于推ter的Finagle。
  • 一個重要的目標是跨很多不同的語言控制性能。特別是在Node和Python中，很多現有的RPC機制工作得并不是很好。想要獲取Redis級別的性能.TChannel已經比HTTP快20倍。
  • 希望獲取一個高性能的轉發路徑，因此中間層可以讓決策轉發變得容易一些，而不必了解全部有效載荷。
  • 希望獲取合適的流水線，因此沒有隊頭阻塞，請求和響應可以在任何時間往任何一個方向發送。
  • 希望獲取有效的載荷校驗與跟蹤，以及一流的功能。每個請求都應該是可追溯的。
  • 希望獲取一條遷移HTTP的清晰路徑。HTTP可以在TChannel中被自然封裝。
  • Uber正在擺脫HTTP和Json業務。TChannel上的所有技術正往Thrift上遷移。
• ringpop基于持久連接處理所有TChannel中的gossip。這些相同的持久連接用來扇出或轉發應用數據。TChannel也用于服務之間的對話。

調度可用性

• 可用性是相當重要的。Uber有競爭對手，用戶變更產品的成本是非常低的。如果Uber不行，利益就會流向其他競爭對手。
• 讓一切可重試。如果有什么不能工作了，它必須是可重試的。這要求所有請求冪等。例如，重試一個調度，不能調度他們兩次或刷取別人的信用卡兩次。
• 使所有可關閉。故障是一種常見的情況。隨機殺死進程不應該造成破壞。
• 崩潰。不存在正常關閉。正常關閉沒有什么需要練習。需要練習的是當意外情況發生時。
• 小塊。為了盡量減少故障的代價，將它們切為更小的塊。在一個實例中處理全局業務是可能的，但是實例死亡的時候會發生什么呢？如果兩個里面有一個失敗，則能力會減少一半。因此，服務需要被切分。
• kill一切。即使kill所有的數據庫，也要確保出現故障時系統可以幸免。這需要對使用什么數據庫做決策改變。他們選擇Riak 代替MySQL。這也意味著使用ringpop代替Redis。
• 將其切分成更小的塊。通常，通過一個負載均衡器實現服務之間的對話。如果負載平衡器死去會怎么樣？如果你沒 有實際處理過這種情況，你可能永遠不知道。所以，你不得不kill負載平衡器。這時你怎么解決圍繞負載均衡器關閉而出現的問題？負載均衡邏輯已經在服務中 被采用以解決這個問題。客戶端都被要求有一定的智能，以了解如何找到解決問題的途徑。這在很大程度上類似于Finagle的工作方式。
• 為了擴展整個系統，并處理后端壓力，基于一個ringpop節點集群，創建了一個服務發現和路由系統。

整個數據中心失效

• 這種事情并不會經常發生，但一些意想不到的級聯故障是可能出現的，或者上游網絡提供商也可能會不能工作。
• Uber維護了一個備份數據中心，通過將所有工作轉移到備份數據中心，可以實現及時切換。
• 問題是在進程中的出行數據可能還不在備份數據中心。代替數據副本，他們使用司機手機作為出行數據的來源。
• 當調度系統定期發送一個加密的狀態摘要到司機的手機時，會發生什么。現在，讓我們假設有一個數據中心失效。下一次，司機的手機發送一個位置更新到調度系統，調度系統會檢測到它不知道這次出行的任何信息，這次就可以問狀態摘要。

不足

• Uber解決可擴展性和可用性問題的方法也存在不足，主要表現在Node進程在向彼此轉發請求以及用大的扇出發送消息的過程中，存在潛在的高延遲。
• 在扇出系統中，很小的錯誤都有一個非常大的影響。一個系統的扇出越高，出現高時延請求的機會就越大。
• 一個好的解決辦法是利用交叉服務器對請求進行備份。這作為第一等級的功能被融入到TChannel中。一個請求被發送到服務B（1），同時也附 帶該請求被發送到服務B（2）的信息。等待一些時間之后，請求被發送到服務B（2）。當B（1）完成請求時，它在B（2）上取消這個請求。使用一些延遲意 味著通常情況下B（2）沒有進行任何工作。但是，如果B（1）失敗了，則B（2）將處理該請求，并以一個較低的延遲返回一個回應，如果B（1）第一次嘗試 的過程中，發生超時，然后再讓B（2）嘗試。
• 想了解更多，可以參考 Google On Latency Tolerant Systems: Making A Predictable Whole Out Of Unpredictable Parts。