概述#
設計一個類似 Uber 的共乘服務，將需要搭車的乘客與擁有車輛的司機連結起來。
- 類似服務：Lyft、Didi、Via、Sidecar 等
- 難度：困難
- 前置知識：Designing Yelp
什麼是 Uber#
Uber 讓使用者可以透過手機 App 預約司機來載送。Uber 司機使用自己的私人車輛載送乘客，雙方透過智慧型手機上的 Uber App 進行溝通。
系統需求與目標#
系統中有兩種使用者：司機（Drivers） 與 乘客（Customers）。
- 司機需要定期回報目前位置與是否可接單
- 乘客可以查看所有附近可用的司機
- 乘客可以發出搭車請求，系統會通知附近的司機有乘客等待接送
- 一旦司機與乘客確認搭車，雙方可以即時查看對方目前位置，直到行程結束
- 到達目的地後，司機標記行程完成，即可接受下一筆訂單
容量估算與限制#
- 假設有 3 億 名乘客與 100 萬 名司機；每日活躍乘客 100 萬，每日活躍司機 50 萬
- 假設每日 100 萬 筆搭車紀錄
- 所有活躍司機每 3 秒回報一次目前位置
- 乘客發出搭車請求後，系統必須能即時聯繫司機
基礎系統設計與演算法#
以 Designing Yelp 的方案為基礎進行修改。最大的差異在於，原本的 QuadTree 並非設計來應對頻繁更新的場景。Dynamic Grid 方案存在兩個問題：
- 頻繁更新的效能問題：所有活躍司機每 3 秒回報一次位置，若每次都更新 QuadTree 會消耗大量時間與資源。更新流程需要：根據舊位置找到對應網格 → 判斷新位置是否在同一網格 → 若不同則移除並重新插入 → 若新網格超過上限還需重新分割
- 即時推播的需求：需要快速將附近所有司機的即時位置傳送給活躍乘客；行程進行中，也需同時通知司機與乘客車輛目前位置
雖然 QuadTree 能快速找到附近司機，但無法保證快速更新。
是否需要每次都更新 QuadTree#
由於司機位置更新的頻率遠高於查詢附近司機的頻率，可以採取折衷方案：
- 將所有司機最新位置存入一個 Hash Table（稱為 DriverLocationHT）
- QuadTree 每 15 秒才同步更新一次
- 兩者搭配使用，在即時性與效能之間取得平衡
DriverLocationHT 記憶體需求#
每筆記錄需要儲存 DriverID、舊位置與新位置，共 35 bytes：
- DriverID：3 bytes（涵蓋 100 萬名司機）
- 舊緯度（Old latitude）：8 bytes
- 舊經度（Old longitude）：8 bytes
- 新緯度（New latitude）：8 bytes
- 新經度（New longitude）：8 bytes
100 萬名司機的總記憶體需求（忽略 Hash Table 額外開銷）：
1,000,000 × 35 bytes = 35 MB
頻寬需求#
每次位置更新傳送 DriverID + 位置 = 3 + 16 = 19 bytes。100 萬名司機每 3 秒回報一次：
19 MB / 3 秒
是否需要將 DriverLocationHT 分散到多台伺服器#
雖然記憶體與頻寬需求不大，但為了可擴展性、效能與容錯，仍應將 Hash Table 分散到多台伺服器。可依 DriverID 進行分散以確保隨機分佈。這些伺服器稱為 Driver Location Server，除了儲存司機位置外，還負責：
- 收到司機位置更新後，即時廣播給所有感興趣的乘客
- 通知對應的 QuadTree Server 刷新司機位置（約每 10 秒一次）
如何有效廣播司機位置給乘客#
採用 Push Model，透過專門的 Notification Service 來廣播：
- 基於 Publisher/Subscriber 模式建構
- 乘客開啟 App 時，查詢附近司機並訂閱這些司機的位置更新
- 系統維護一份訂閱者清單，每當 DriverLocationHT 有更新，就廣播給所有訂閱的乘客
訂閱機制的記憶體需求#
假設 100 萬日活乘客、50 萬日活司機，平均每位司機有 5 位乘客訂閱：
- DriverID：3 bytes，CustomerID：8 bytes
(500K × 3) + (500K × 5 × 8) ≈ 21 MB
廣播的頻寬需求#
每位活躍司機有 5 位訂閱者，共 250 萬 位訂閱者。每秒傳送 DriverID（3 bytes）+ 位置（16 bytes）= 19 bytes：
2,500,000 × 19 bytes = 47.5 MB/s
Notification Service 的實作方式#
可使用 HTTP Long Polling 或 Push Notification。
如何動態新增訂閱#
當新司機進入乘客正在查看的區域時，需要動態新增訂閱關係。為了簡化方案，可改用 Pull Model：
- 乘客定期（例如每 5 秒）傳送目前位置給伺服器
- 伺服器從 QuadTree 中找出附近司機並回傳
- 乘客端更新畫面上的司機位置
相較於 Push Model，Pull Model 的實作更為簡單，且能自然處理新司機進入視野的情境。
網格重新分割的緩衝機制#
不需要在網格達到上限時立即重新分割，可設定 10% 的緩衝區間，讓每個網格在超過或低於上限 10% 時才執行分割或合併。這能降低高流量網格的分割負擔。
「Request Ride」的運作流程#
- 乘客發出搭車請求
- 某台 Aggregator Server 接收請求，向 QuadTree Server 查詢附近司機
- Aggregator Server 彙整結果並依評分排序
- 同時通知排名前三的司機，最先接受的司機獲得該筆訂單；其餘司機收到取消通知。若三位司機均未回應，則通知下三位
- 一旦司機接受請求，乘客收到通知
圖 24.1：系統架構圖（上半：Customers → Load Balancer → Aggregation Server → QuadTree Server → QuadTree Index + DB；下半：Drivers → Load Balancer → Driver Location Server → SSD Storage + DB）
容錯與複寫#
- Driver Location Server 或 Notification Server 故障時，需有副本伺服器接管
- 資料同時存入 SSD 等持久儲存，即使主備伺服器都故障，仍可從持久儲存恢復資料
排名機制#
除了依距離排序，還可依人氣或相關性進行排名：
- 在資料庫和 QuadTree 中維護每位司機的整體評分（例如滿分 10 星）
- 搜尋指定半徑內前 10 名司機時，讓每個 QuadTree 分區各自回傳評分最高的 10 位司機
- 由 Aggregator Server 在所有分區結果中選出最終前 10 名
進階議題#
- 如何處理網路緩慢或斷線的客戶端？
- 行程進行中客戶端斷線，如何處理計費問題？
- 是否改用客戶端主動拉取所有資訊，取代伺服器持續推送？