System Design Interview Vol. 2 · 第 3 章Triton 覆蓋度:⚪ 無Triton 線
Design Google Maps
手機上那張地圖,背後是三套系統
原書做一個簡化版 Google Maps,只做三件事:位置更新、導航(含 ETA)、地圖渲染。整章靠三個「切格子」的點子撐起來:地圖切成 map tiles 交給 CDN、路網切成 routing tiles 讓 A* 一次只載入一小塊、位置在手機上先存 15 秒再一起送。Triton 沒有寫過地圖或導航的講義,所以這份幾乎全是原書,只在 CDN、寫入量、Kafka 門檻三個地方加上 🔭 推論。
給文組
全程用「紙本地圖冊 + 計程車司機回報」比喻,十幾個可以動手玩的互動:縮放金字塔、儲存計算機、A* 一格一格載入、車禍改道。一階一階爬 13 個概念,頁首標 延伸基礎 的頁是補基礎,懂的人可以跳過。
給工程師
原書 21 張圖、章末心智圖與 5 張表全部依描述重繪;真實地圖截圖一律改畫成示意圖。最後一頁有原書段落對照與出處。
標籤怎麼看
📖 原書 🗣️ Triton 本人說 🔭 依 Triton 原則推論
先用生活理解三個功能 = 三樣老司機的工具
一本地圖冊、腦中的路網、和每 15 秒一次的無線電
以前的計程車司機要三樣東西:地圖冊(只翻到現在這一頁和隔壁幾頁,不會整本攤開)、腦中的路網(哪條巷子接上大馬路)、無線電(每隔一陣子跟車隊說「我在哪」,車隊才知道哪裡塞車)。
原書的三個功能剛好對上:map rendering = 地圖冊翻頁;navigation = 腦中的路網;location update = 無線電回報。
試試看:按「開車」。灰色是全世界的圖塊,藍色是手機真的下載過的。把回報方式從「每秒送一次」切到「存 15 秒一起送」:request 少 15 倍,記錄的位置點一個都沒少。
學習地圖本章的概念階梯
今天爬 13 階。每一階只用前面講過的東西。
- 1前幾章的基礎DAU、CDN…
- 2經緯度地球上的座位號碼
- 3geocoding地址翻成座標
- 4map tile一片拼圖
- 5zoom level放大鏡的倍率
- 6graph路口和馬路
- 7shortest path把分鐘數加起來
- 8A*朝目的地找
- 9routing tile路網也切塊
- 10分層 tiles小巷、大路、高速
- 11batching存一批再送
- 12路況更新車隊回報車速
- 13ETA還要多久到
第 1–3 階 · 地點怎麼說
要回答:手機怎麼說出「我在哪」、「我要去哪」?
第 4–5 階 · 地圖怎麼畫
要回答:100 PB 的地圖,手機怎麼只拿需要的那幾片?
第 6–10 階 · 路怎麼找
要回答:全世界的路網,怎麼在幾秒內找出一條路?
第 11–13 階 · 路況怎麼更新
要回答:10 億人的位置怎麼送回來,變成「還要 12 分鐘」?
全程只跟一台車:阿明的計程車(虛構)
阿明每天從台北車站載客到動物園。每爬 3–5 階,有一頁「到這裡你已經會了」。
路線圖Triton 覆蓋度:⚪ 無
這份簡報怎麼走
📖 原書 Step 1:需求與 Map 101
- 面試問答、三個功能(第 6 頁)
- 定位、投影、geocoding(8–10)
- Geohashing、地圖渲染(12–14)
- 路網變成圖、routing tiles、分層(19–24)
- 估算:100 PB、1M QPS(25–27)
📖 原書 Step 2–4:設計
- 高階設計、位置與導航服務(29–31)
- 地圖:CDN、流量、tile URL(32–35)
- 資料模型(36–37)、位置 deep dive(38–40)
- 縮放層級與向量圖塊(41–42)
- 導航 deep dive:geocoding、A*、ETA、改道(43–49)
- 最終設計、wrap up(51–52)
🔭 依 Triton 原則推論 三頁
- Triton 談過什麼、沒談過什麼(53)
- 讀走 CDN、寫不行:流量分兩半(54)
- 位置資料可遺失、Kafka 的 1K 門檻(55)
另有兩張小卡:geocoding DB 用 Redis(第 37 頁)、9 格 URL 與 064(第 35 頁)。
為什麼覆蓋度是「無」:materials/core 裡沒有任何談地圖、導航、路徑規劃、ETA 或 map tile 的講義、文章或留言。唯一沾到邊的是 064 講 geohash 的兩頁,而那是在回答「1 萬個點找最近鄰居」。能用的只有 Triton 在別的題目講的原則,套到這章一律標 🔭,不寫成「Triton 認為 Google Maps 應該……」。
延伸基礎 · 複習第 1 階 · 前幾章的基礎懂的人可以跳過
- 前幾章的基礎
- 經緯度
- geocoding
- map tile
- zoom level
- graph
- shortest path
- A*
- routing tile
- 分層 tiles
- batching
- 路況更新
- ETA
「10 億人每天開地圖」:先複習前幾份簡報的五個詞
① 先想像
全台 1,000 萬人,每人每天打開地圖查一次路。
你猜猜看:一天 1,000 萬次查路,平均每秒大約幾次?
一天 86,400 秒,大約 10 萬秒。1,000 萬 ÷ 10 萬 = 100。最忙的時候是好幾倍。
③ 這叫做 DAU、QPS、database、load balancer、CDN(複習)
DAU:每天實際來用的人數QPS:每秒幾個 request;要看最忙那一秒database:記正本的帳本,停電也不會忘load balancer:帶位員,把流量分給好幾台CDN:開在各地的巷口小店,放大家都要的同一份東西
④ 跟這章的關係
原書第一句就是 10 億 DAU(下一頁);load balancer 和 CDN 是高階設計圖(第 29 頁)的主角。
② 動手玩:每天的查路次數,換成每秒
原書 Step 1釐清需求
10 億 DAU;只做位置更新、導航與 ETA、地圖渲染
這一步要解決的問題面試一開始:這個 Google Maps 要做到多大、做哪幾件事?
📖 原書 應徵者 × 面試官
| 應徵者問 | 面試官答 |
|---|---|
| 預期每日活躍用戶數? | 1 billion DAU |
| 要專注哪些功能?路線指引、導航、ETA? | 聚焦位置更新、導航、ETA、地圖渲染 |
| 路網資料多大?可以假設拿得到嗎? | 好問題。假設已從不同來源取得,原始資料有數 TB |
| 要考慮交通狀況嗎? | 要,交通狀況對準確估時非常重要 |
| 不同交通模式:開車、走路、公車? | 要支援不同交通模式 |
| 要支援多點停靠嗎? | 可以讓使用者設多個停靠點,但先不專注 |
| 商家地點和照片呢?預期多少照片? | 很高興你想到,但不用設計 |
白話:DAU=每天實際打開 app 的人數;ETA=預計抵達時間(第 46 頁);地圖渲染(map rendering)=把資料畫成手機上看得到的地圖;TB=1,000 GB。
📖 原書 三個關鍵功能(主要裝置:手機)
- 使用者位置更新
- 導航服務,包含 ETA 服務
- 地圖渲染
📖 原書 非功能需求與限制
- Accuracy:不能給使用者錯的路線
- Smooth navigation:client 端的地圖渲染要非常流暢
- Data and battery usage:盡量少用流量和電,對手機非常重要
- 一般的可用性與擴展性需求
📖 原書 開場數字:截至 2021 年 3 月,Google Maps 有 10 億日活、覆蓋全球 99%、每天 2,500 萬筆即時位置資訊更新。本章地圖圖塊來自 Stamen Design,資料來自 OpenStreetMap。
延伸基礎第 2 階 · 經緯度懂的人可以跳過
- 前幾章的基礎
- 經緯度
- geocoding
- map tile
- zoom level
- graph
- shortest path
- A*
- routing tile
- 分層 tiles
- batching
- 路況更新
- ETA
地球上的「座位號碼」
① 先想像
電影票寫「第 7 排 12 號」,兩個數字就找到你的座位。地球上也畫好了排和號。
你猜猜看:「第 3 排 5 號」和「第 5 排 3 號」是同一個位子嗎?
順序有意義:一個數字管上下(排),一個管左右(號)。地球上的兩個數字也一樣。
③ 這叫做 latitude、longitude
latitude(緯度):往北或往南幾度,像「第幾排」。longitude(經度):往東或往西幾度,像「第幾號」。
④ 跟這章的關係
手機 GPS 每秒給的就是這兩個數字。整章每個服務吃的都是(緯度, 經度)。
② 動手玩:點地圖上任一處
原書 Map 101Positioning system · Going from 3D to 2D · Figure 1、2
經緯度定位置;把球壓成平面,一定會變形
這一步要解決的問題地球是圓的、螢幕是平的。怎麼說出一個位置,又怎麼把它畫到平面上?
📖 原書 地球是繞軸自轉的球體,最上面是北極、最下面是南極。Lat(緯度)表示偏北或偏南多少;Long(經度)表示偏東或偏西多少。
📖 原書 把 3D 球面上的點轉到 2D 平面叫 Map Projection。做法很多、各有優缺點,幾乎都會扭曲實際幾何。Google Maps 選的是 Mercator 的修改版:Web Mercator。
文組翻譯:剝橘子皮
把橘子皮壓平,不是裂開就是被拉長。Mercator 是「越往兩極拉得越大」。拖拖看:
延伸基礎第 3 階 · geocoding懂的人可以跳過
- 前幾章的基礎
- 經緯度
- geocoding
- map tile
- zoom level
- graph
- shortest path
- A*
- routing tile
- 分層 tiles
- batching
- 路況更新
- ETA
「中山路 100 號」在地圖上的哪一點?
① 先想像
你上車跟阿明說「去動物園」。他得先把這三個字,換成地圖上的一個點。
你猜猜看:1 號在路口 A,199 號在 200 公尺外的路口 B。99 號大約在哪?
99 號差不多在 1 號和 199 號的正中間,就是 200 公尺的一半。不用量每一戶,按比例推(下一頁的 interpolation)。
③ 這叫做 geocoding、reverse geocoding
geocoding:把地址或地名翻成經緯度。reverse geocoding:反過來,從經緯度翻回地址。
④ 跟這章的關係
導航的第一步就是 geocoding(第 44 頁):先把起點、終點翻成座標,才能找路。
② 動手玩:阿明的地址簿
原書 Map 101Geocoding
Geocoding:地址 → 經緯度;反過來叫 reverse geocoding
這一步要解決的問題使用者打的是地址,電腦要的是經緯度。兩邊怎麼互相翻譯?
📖 原書 Geocoding 是把地址轉成地理座標。例如:
"1600 Amphitheatre Parkway, Mountain View, CA"
→ (latitude 37.423021, longitude -122.083739)
📖 原書 反方向,從經緯度轉回人看得懂的地址,叫 reverse geocoding。
📖 原書 一種做法是 interpolation(插值):利用地理資訊系統(GIS)等不同來源的資料,那裡面的街道網路已經對應到地理座標空間。
文組翻譯
知道一條街「1 號在路口 A、199 號在路口 B」,那 100 號大概就在中間。不用每一戶都量座標,按比例推就好。
白話:GIS(地理資訊系統)=記著每條街、每個路口在哪裡的資料。
動手玩:插值找門牌
點一下街上任一點,就是 reverse geocoding:從座標推回最近的門牌。街名與兩端座標是示意,不是真實資料。
延伸基礎第 4 階 · map tile懂的人可以跳過
- 前幾章的基礎
- 經緯度
- geocoding
- map tile
- zoom level
- graph
- shortest path
- A*
- routing tile
- 分層 tiles
- batching
- 路況更新
- ETA
一幅超大拼圖,你只要看其中 9 片
① 先想像
全世界的地圖是一幅超大拼圖。阿明的手機只看得到車子附近那一小塊。
你猜猜看:拼圖有 8 × 6 = 48 片,手機畫面一次蓋住 3 × 3 片。一開始要拿幾片?
只拿畫面蓋到的 3 × 3 = 9 片。往旁邊移,才再拿新露出來的那幾片。
③ 這叫做 map tile、tiling
map tile:地圖切成的一小片、大小固定的圖(原書是 256 × 256 個像素點)。tiling:切成小片,只拿需要的。
④ 跟這章的關係
原書的地圖就是這樣送到手機(第 14 頁)。每一片事先畫好,放在 CDN。
② 動手玩:移動手機畫面
原書 Map 101Geohashing · Figure 3
Geohashing:一直切四塊,每塊用 00、01、10、11 命名
這一步要解決的問題世界要切成格子。每一格怎麼取一個好算、好查的名字?
📖 原書 Geohashing 把一塊地理區域編碼成一小串字母和數字。核心是把地球當成攤平的表面,遞迴地把格子切成子格(正方形或長方形),每格用 0 到 3 之間的數字遞迴命名。
| 切幾次 | 格子大小 | 編碼 |
|---|---|---|
| 0 | 20,000 km × 10,000 km | (整個平面) |
| 1 | 10,000 km × 5,000 km | 00、01、10、11 |
| 2 | 5,000 km × 2,500 km | 每格再用同樣規則 |
| … | 直到格子小於某個門檻 | |
📖 原書 Geohashing 用途很多;本章用它來做 map tiling。細節原書請讀者看參考資料 [11] 和 Proximity Service 那章。
注意:這裡的編碼是四進位(每層兩個 bit),Proximity 章和後面的 tile URL 9q9hvu 用的是 base32 geohash:同一個「一直切一半」的想法,兩種寫法。
白話:遞迴=同一個規則一直重複做;bit=0 或 1 的一個小開關。
延伸基礎第 5 階 · zoom level懂的人可以跳過
- 前幾章的基礎
- 經緯度
- geocoding
- map tile
- zoom level
- graph
- shortest path
- A*
- routing tile
- 分層 tiles
- batching
- 路況更新
- ETA
放大鏡每轉一格,一片拆成四片
① 先想像
從太空看,台灣只是一小塊。放大一點看到縣市,再放大才看到街名。
你猜猜看:看全世界時只有 1 片。每放大一層,每片拆成 4 片。第 3 層共幾片?
1 → 4 → 16 → 64,每層 ×4。到第 21 層是 4 的 21 次方,約 4.4 兆片。
③ 這叫做 zoom level
zoom level(縮放層級):放大到第幾層。第 0 層最遠、只有 1 片;層數越大越細,每片的大小不變。
④ 跟這章的關係
Google Maps 用 21 層(Table 1,第 25 頁)。所有層加起來,約 100 PB。
② 動手玩:轉放大鏡
原書 Map 101Map rendering
地圖是一片一片拼起來的;放大到哪一層,就拿那一層的圖塊
這一步要解決的問題全世界的地圖太大。手機要怎麼只拿需要的那一小部分?
📖 原書 地圖渲染的一個基礎概念是 tiling:不把整個世界畫成一張大圖,而是切成小圖塊。Client 只下載使用者所在區域相關的圖塊,像馬賽克一樣拼起來顯示。
📖 原書 不同的 zoom level 有不同的一套圖塊。Client 依 viewport 的縮放層級選對的那一套,細節剛好、又不浪費頻寬。
📖 原書 極端的例子:縮到看全世界時,不該下載高縮放層級的幾十萬張圖塊,細節全浪費;而是下載最低層級的一張,用一張 256×256 像素的圖代表整個世界。
文組翻譯:地圖冊有「全台灣」一頁、「台北市」幾頁、「大安區」幾十頁。看全台灣就翻那一頁,不會把幾十頁大安區攤滿整個客廳。
白話:viewport=手機畫面現在看到的範圍;像素=螢幕上的一個小點。
到這裡你已經會了小結 1 / 4
- 前幾章的基礎
- 經緯度
- geocoding
- map tile
- zoom level
- graph
- shortest path
- A*
- routing tile
- 分層 tiles
- batching
- 路況更新
- ETA
到這裡你已經會了:地點怎麼說、地圖怎麼畫
- 一個位置就是一組經緯度(latitude, longitude),像地球上的座位號碼。
- geocoding 把「動物園」翻成座標;反過來叫 reverse geocoding。
- 地圖切成 map tiles;每升一個 zoom level,片數 ×4。手機只拿畫面附近那 9 片。
下一階要解決的問題
地圖會畫了,可是「怎麼走」?全世界幾億個路口,要怎麼找出一條路?
延伸基礎第 6 階 · graph懂的人可以跳過
- 前幾章的基礎
- 經緯度
- geocoding
- map tile
- zoom level
- graph
- shortest path
- A*
- routing tile
- 分層 tiles
- batching
- 路況更新
- ETA
捷運路線圖不管路多彎,只畫站和線
① 先想像
捷運路線圖不畫真實的彎曲,只畫站和站之間的線。要知道怎麼轉車,這樣就夠了。
你猜猜看:一條馬路從路口 A 通到路口 B,中間經過路口 C。只畫點和線,這條馬路變成幾條線?
路口才是點。A–C 一條、C–B 一條,共 2 條。路口越多,線就越多。
③ 這叫做 graph、node / edge
graph(圖):一群點和連接它們的線。點叫 node(路口),線叫 edge(路段),線上可以寫開幾分鐘。
④ 跟這章的關係
導航演算法只認得 graph(Figure 4,第 19 頁)。全世界的路口太多,圖太大就跑不動。
② 動手玩:把街道變成點和線
延伸基礎 · 動手算第 7 階 · shortest path懂的人可以跳過
- 前幾章的基礎
- 經緯度
- geocoding
- map tile
- zoom level
- graph
- shortest path
- A*
- routing tile
- 分層 tiles
- batching
- 路況更新
- ETA
從車站到動物園,哪一條最快?用加法就知道
① 先想像
阿明從車站 S 開到動物園 T。每段路寫著要開幾分鐘,加起來就是整條路的時間。
你猜猜看:S→A 2 分、S→B 5 分、A→B 1 分、A→T 6 分、B→T 2 分。哪條最快?
S→B→T = 5 + 2 = 7;S→A→T = 2 + 6 = 8;S→A→B→T = 2 + 1 + 2 = 5。多轉一次彎,反而最快。
③ 這叫做 shortest path、Dijkstra
shortest path:加總最小的那條路。Dijkstra:從起點一圈一圈往外,每次先確定「目前最近」的路口。
④ 跟這章的關係
原書的 shortest-path service 就在做這件事,一次給前幾名(top-k)(第 45 頁)。
② 動手玩:自己走一遍,再看 Dijkstra 怎麼算
延伸基礎第 8 階 · A*懂的人可以跳過
- 前幾章的基礎
- 經緯度
- geocoding
- map tile
- zoom level
- graph
- shortest path
- A*
- routing tile
- 分層 tiles
- batching
- 路況更新
- ETA
動物園在東邊,就先往東找
① 先想像
漣漪往四面八方一樣用力擴,連背對動物園的路都去看。人找路會先往動物園的方向試。
你猜猜看:起點在西、動物園在東。Dijkstra 會不會去看起點西邊的路口?
Dijkstra 只看「離起點多近」,不知道目的地在哪,所以西邊的近路口也會先看。右邊比比看。
③ 這叫做 A*(A-star)
A*:每個路口算「已經開了多遠 + 離目的地的直線距離」,先看總和最小的。這個估計值讓它朝目的地找。
④ 跟這章的關係
原書的 shortest-path service 跑的是 A* 的變形(第 45 頁)。看的路口少,要載入的路網也少。
② 動手玩:同一張棋盤路網,兩種找法
原書 Map 101Road data processing for navigation algorithms · Figure 4
導航演算法吃的是「圖」:路口是節點,馬路是邊
這一步要解決的問題地圖是給人看的。導航演算法要的,是什麼形狀的資料?
📖 原書 大部分路徑演算法是 Dijkstra 或 A* 的變形。怎麼選是複雜的題目,本章不深入。重要的是:這些演算法都在圖(graph)上運作,路口是節點、道路是邊。
📖 原書 這些演算法的效能對圖的大小極度敏感。把全世界的路網當成一張圖,記憶體會不夠,也大到跑不動。圖必須拆成可管理的單位,演算法才能在我們的規模下運作。
文組翻譯:Dijkstra 在做什麼
從起點像漣漪一樣往外擴:每次挑「目前離起點最近、還沒確定」的路口,把它確定下來,再更新它鄰居的距離。按「下一步」看漣漪一圈一圈擴到 H。
到這裡你已經會了小結 2 / 4
- 前幾章的基礎
- 經緯度
- geocoding
- map tile
- zoom level
- graph
- shortest path
- A*
- routing tile
- 分層 tiles
- batching
- 路況更新
- ETA
到這裡你已經會了:路怎麼找(上)
- 路口是 node、路段是 edge,整張路網是一張 graph。
- shortest path:每段分鐘數加起來最小。Dijkstra 從起點一圈一圈往外確定。
- A* 多看「離目的地多遠」,朝目的地找,看的路口少很多。
下一階要解決的問題
全世界的 graph 塞不進一台電腦的記憶體。原書怎麼辦?答案又是「切格子」。
延伸基礎第 9 階 · routing tile懂的人可以跳過
- 前幾章的基礎
- 經緯度
- geocoding
- map tile
- zoom level
- graph
- shortest path
- A*
- routing tile
- 分層 tiles
- batching
- 路況更新
- ETA
去新竹,不用把全台灣的路都背在身上
① 先想像
全國路網是很厚的一大本,背不動。拆成很多分冊,開到哪一區,才翻出那一區的分冊。
你猜猜看:全國路網切成 100 塊,每塊 10 MB。台北到新竹只經過 3 塊。記憶體要放多少?
只載入路上碰到的 3 塊:3 × 10 = 30 MB。全部載入要 100 × 10 = 1,000 MB。
③ 這叫做 routing tile
routing tile:一塊區域裡的路口和路段(一小張 graph),存成一個檔案,用到才載入。
④ 跟這章的關係
它和 map tile 都是格子;但 map tile 是圖片,routing tile 是道路資料(第 22 頁)。
② 動手玩:從台北出發
原書 Map 101Routing tiles · Figure 5 · Reminder
把路網也切成格子:routing tiles,用到哪塊才載入哪塊
這一步要解決的問題全世界的路網是一張太大的 graph。怎麼讓演算法跑得動?
📖 原書 拆路網的一種方法和地圖 tiling 很像:用類似 geohashing 的細分方式把世界切成小格。每一格裡的道路轉成一張小圖(格子裡的節點和邊),叫 routing tile。
📖 原書 每個 routing tile 都存著它連到的其他 tiles 的參考。演算法走過這些互相連結的 tiles 時,就能拼出更大的路網。
📖 原書 拆成可以按需載入的 routing tiles 後,演算法一次只用一小部分,需要時才載入更多,記憶體大降、搜尋變快。
📖 原書 Reminder
Routing tiles 和 map tiles 很像,都是蓋住某塊地理區域的格子。差別:map tiles 是 PNG 圖片;routing tiles 是這塊區域道路資料的二進位檔。
白話:二進位檔=給電腦讀的檔案,不是圖片也不是文字。
延伸基礎第 10 階 · 分層 tiles懂的人可以跳過
- 前幾章的基礎
- 經緯度
- geocoding
- map tile
- zoom level
- graph
- shortest path
- A*
- routing tile
- 分層 tiles
- batching
- 路況更新
- ETA
台北到高雄:出巷子、上高速公路、再下交流道
① 先想像
長途不會一路鑽小巷。先出巷子、上大馬路、上高速公路,快到了才下交流道。
你猜猜看:台北到高雄,中間那 300 公里最需要哪一層的細節?
中間只要知道高速公路怎麼接。小巷只有在出發和抵達附近才用得到。
③ 這叫做 hierarchical routing tiles
分層 routing tiles:三套粗細不同的 tiles:小巷層、主幹道層、高速公路層。交流道就是「從小 tile 跳到大 tile」的連結。
④ 跟這章的關係
這就是原書的 Figure 6(第 24 頁)。A* 會從小 tile「進入」只有高速公路的大 tile(第 45 頁)。
② 動手玩:去三個地方,要看幾個路口?
原書 Map 101Hierarchical routing tiles · Figure 6
三層 routing tiles:小巷、主幹道、高速公路
這一步要解決的問題跨國的長途路線,用最細的街道資料會太大。怎麼辦?
📖 原書 有效率的導航也需要對的細節層級。跨國路線若用很細的街道級 tiles 跑,拼出來的圖太大、太耗記憶體。通常有三組不同細節的 routing tiles:最細的 tile 小、只有地方道路;下一層較大、只有連接各區的主幹道;最粗的 tile 涵蓋大範圍、只有連接城市與州的主要高速公路。
📖 原書 每一層都可能有連到另一個縮放層級的邊:從地方街道 A 上高速公路 F 的交流道,小 tile 裡的節點(street A)會有一個參考,指向大 tile 裡的節點(freeway F)。
原書 Step 1Back-of-the-envelope estimation · Storage · Table 1
全世界的地圖圖塊:大約 100 PB
這一步要解決的問題全世界、所有縮放層級的地圖圖塊,總共要存多少?
📖 原書 換算:1 foot = 0.3048 m;1 km = 0.6214 miles;1 km = 1,000 m。三種資料:世界地圖(下面算)、metadata(每張很小,略過)、道路資訊(外部來的數 TB,轉成 routing tiles 也是 TB 級)。
動手算:📖 原書的算法
📖 原書 第 21 層約 4.4 兆張 × 100 KB = 440 PB。世界表面約 90% 是海洋、沙漠、湖泊、山脈這種幾乎沒人住的地方,圖很好壓縮,保守地減 80–90% → 44 到 88 PB,取整數 50 PB。每往下一層,南北、東西的張數各減半 → 張數與大小都 ÷4:50 + 50/4 + 50/16 + … ≈ 67 PB。粗估就夠,記住大約 100 PB。
白話:PNG=一種圖片格式;PB=1,000 TB(02 章第 6 頁)。
延伸基礎第 11 階 · batching懂的人可以跳過
- 前幾章的基礎
- 經緯度
- geocoding
- map tile
- zoom level
- graph
- shortest path
- A*
- routing tile
- 分層 tiles
- batching
- 路況更新
- ETA
每到一站寄一張明信片,還是回家一次寄一疊?
① 先想像
阿明的手機每秒記下一次「我在哪」。可以每秒打一通無線電,也可以每 15 秒把 15 個點一起報。
你猜猜看:10 台車每秒各報一次,總台每秒接 10 通。改成每 5 秒報一次(一次帶 5 個點),每秒接幾通?
每台 5 秒 1 通,10 台就是 5 秒 10 通,每秒 2 通。記下來的點一個都沒少,只是一起送。
③ 這叫做 batching
batching(批次):先在手機上存一批,再一次送出去。request 變少,點數不變。
④ 跟這章的關係
原書每 15 秒一批:3M QPS 變成 200K QPS(下一頁)。代價是資料晚一點到。
② 動手玩:車隊的無線電
原書 Step 1Back-of-the-envelope estimation · Server throughput
位置更新:每秒送是 3M QPS,每 15 秒一批是 200K,尖峰 1M
這一步要解決的問題10 億人邊開車邊回報位置,server 每秒要接多少 request?
📖 原書 兩種主要 request:navigation requests(client 開始一次導航)和 location update requests(導航中邊走邊送)。位置資料下游有很多用途,例如它是即時路況的輸入之一。
- 1 billion DAU,每人每週導航 35 分鐘 → 每週 350 億分鐘 → 每天 50 億分鐘
- 每秒送一次 GPS:50 億 × 60 = 每天 3,000 億 request → 3,000 億 ÷ 105 = 3 million QPS
- 其實不用每秒送:在 client 批次,每 15 或 30 秒送一次;頻率可依移動速度調,塞車時就放慢。本設計假設每 15 秒 → 3M ÷ 15 = 200,000 QPS
- 尖峰假設是平均的 5 倍 → 200,000 × 5 = 1 million QPS
白話:GPS=手機用衛星訊號定位;105=一天約 10 萬秒(實際 86,400)。
動手算
這個 1M 會在 deep dive(第 38 頁)決定資料庫選型,也會在 Triton 那頁(第 55 頁)拿來和 Kafka 的門檻比。
到這裡你已經會了小結 3 / 4
- 前幾章的基礎
- 經緯度
- geocoding
- map tile
- zoom level
- graph
- shortest path
- A*
- routing tile
- 分層 tiles
- batching
- 路況更新
- ETA
到這裡你已經會了:路網怎麼切、位置怎麼送
- 路網切成 routing tiles,用到哪塊才載入哪塊。
- 分三層:小巷、主幹道、高速公路。長途走大 tile,經由交流道換層。
- 位置每秒記一次、每 15 秒一批送(batching):3M QPS → 200K,尖峰 1M。
下一階要解決的問題
零件都有了。原書接著把三個功能畫成一張架構圖:位置、導航、地圖各走哪條路?
原書 Step 2High-level design · Figure 7
三條路:位置更新、導航都經過 LB;地圖圖塊直接找 CDN
這一步要解決的問題三個功能各自要走哪一條路、經過哪些元件?
📖 原書 有了 Map 101 的背景,就可以提出高階設計。它支援三個功能,下面一個一個看:
Location service
記錄使用者的位置更新 → User Location DB(第 30 頁)
Navigation service
找 A 到 B 的路,用到 Geocoding DB 和 Routing Tiles(object storage)(第 31 頁)
Map rendering
手機向 CDN 拿 precomputed map images,CDN 背後是 origin(第 32 頁)
白話:object storage=放大量檔案的雲端倉庫(例如 S3);origin=CDN 背後放正本的地方。
原書 Step 2Location service · Figure 8、9
位置服務:每秒記一次,每 15 秒送一批
這一步要解決的問題位置回報的量很大。怎麼送比較省,又要存在哪裡?
POST /v1/locations Parameters locs: JSON encoded array of (latitude, longitude, timestamp) tuples.
📖 原書 Client 每 t 秒送一次位置(t 可設定)。好處一:用位置資料流長期改善系統,例如監控即時路況、偵測新開或封閉的道路、分析使用者行為做個人化。好處二:用近即時的位置給更準的 ETA,必要時繞開塞車改道。
📖 原書 真的要每次一更新就立刻送嗎?大概不用。位置歷史可以在 client 緩衝,以低很多的頻率批次送:每秒記一次,每 15 秒一批(Figure 9),所有 client 的總流量大降。
📖 原書 即使批次,像 Google Maps 這種系統的寫入量還是非常高,需要為大量寫入優化、能高度擴展的資料庫,例如 Cassandra;也可能要用 Kafka 這種串流處理引擎記錄位置,供後續處理(deep dive 再談)。
📖 原書 協定:HTTP + keep-alive 是好選擇,因為非常有效率。
白話:Cassandra=為大量寫入設計的資料庫(第 38 頁);Kafka=像車隊廣播站的資料流平台(第 40 頁);keep-alive=同一條連線重複用,不用每 15 秒重新打招呼。
原書 Step 2Navigation service · API
導航服務:可以慢一點,但不能錯
這一步要解決的問題使用者要從 A 到 B:API 長什麼樣、回傳什麼?
📖 原書 這個元件負責找出 A 到 B 還算快的路線。可以容忍一點延遲;算出的路線不一定要最快,但準確性至關重要。使用者經 load balancer 向導航服務送 HTTP request,參數是起點和終點:
GET /v1/nav?origin=1355+market+street,SF&destination=Disneyland
📖 原書 官方 API 細節見參考資料 [13]。到目前為止還沒考慮改道和路況變化,這些由 deep dive 的 Adaptive ETA service 處理(第 48 頁)。
原書這裡寫「As shown in Figure 8」,但 Figure 8 是 location service;畫出導航服務的是 Figure 7。回應裡的 'Ing' 是原書原文(應是 lng),照原書保留。
動手拆:polyline 是什麼?
回應裡的 '_fhcFjbhgVuAwDsCal' 是把一串經緯度壓縮成的文字。按下去解碼看看:
{
'distance': {'text':'0.2 mi', 'value': 259},
'duration': {'text': '1 min', 'value': 83},
'end_location': {'lat': 37.4038943, 'Ing': -121.9410454},
'html_instructions': 'Head <b>northeast</b> on <b>Brandon St</b> toward
<b>Lumin Way</b><div style="font-size:0.9em">Restricted usage road</div>',
'polyline': {'points': '_fhcFjbhgVuAwDsCal'},
'start_location': {'lat': 37.4027165, 'lng': -121.9435809},
'geocoded_waypoints': [
{
"geocoder_status" : "OK",
"partial_match" : true,
"place_id" : "ChIJwZNMti1fawwRO2aVVVX2yKg",
"types" : [ "locality", "political" ]
},
{
"geocoder_status" : "OK",
"partial_match" : true,
"place_id" : "ChIJ3aPgQGtXawwRLYeiBMUi7bM",
"types" : [ "locality", "political" ]
}
],
'travel_mode': 'DRIVING'
}
原書 Step 2Map rendering · Option 1 vs 2 · Figure 10、11
圖塊要即時畫,還是先畫好放 CDN?
這一步要解決的問題圖塊要等使用者要的時候現畫,還是事先畫好?
📖 原書 所有縮放層級的圖塊加起來約一百 PB,不可能全放在 client,必須依 client 的位置和縮放層級按需向 server 拿。什麼時候拿?使用者縮放、拖動地圖看周邊;導航中從目前圖塊走到隔壁圖塊。
Option 1:即時畫
Server 依位置和縮放層級動態產生圖塊。組合無限多,所以:叢集負擔巨大;動態產生很難用 cache。
Option 2:先畫好
每層一套預先產生的靜態圖塊,每張蓋住一塊固定格子,用 geohash 這類切法,所以每張都有唯一的 geohash,交給 CDN。
📖 原書 CDN 沒送過這張,就去 origin 拿一份、存在本地、再回傳;之後的 request 即使來自別的使用者,也直接回 cached copy。圖塊從最近的 POP 送出,更快也更能擴展;圖塊是靜態的,所以非常好 cache。
白話:POP(point of presence)=CDN 在各地的據點;cache=放在手邊的一份複本(01 章第 18 頁)。
原書 Step 2Data usage · Traffic through CDN · Table 2、3
一分鐘 1.25 MB;全世界每秒 62,500 MB,200 個 POP 分
這一步要解決的問題手機流量要花多少?CDN 每秒要送出多少?
📖 原書 Table 2 Data usage
假設使用者時速 30 km,在每張圖塊蓋住 200 m × 200 m 的縮放層級(一塊用 256 × 256 像素的圖表示,平均 100 KB)。1 km × 1 km 要 25 張,也就是 2.5 MB(25 × 100 KB)。時速 30 km,每小時 75 MB(30 × 2.5 MB),每分鐘 1.25 MB。
📖 原書 Table 3 Traffic through CDN
每天 50 億分鐘導航 → 50 億 × 1.25 MB = 每天 6.25 billion MB → 每秒 62,500 MB(6.25 billion ÷ 一天 105 秒)。由全世界的 POP 送出,假設 200 個 POP,每個每秒只要送幾百 MB(62,500 ÷ 200)。
📖 原書 手機流量要省;以上沒算 client 端 cache。使用者每天的路線可能差不多,有 cache 會少很多。在這個規模,成本是重要考量。
動手算
原書 Step 2Tile URL:client 自己算,還是問 map tile service · Figure 12
手機怎麼知道要抓哪張圖?
這一步要解決的問題手機要下載哪幾張圖塊?網址由誰來算?
- 手機呼叫 map tile service 拿 tile URLs,request 先到 load balancer
- Load balancer 把 request 轉給 map tile service
- Map tile service 以 client 的位置與縮放層級為輸入,回傳 9 個 tile URL:要畫的那張 + 周圍 8 張
- 手機從 CDN 下載這些圖塊
📖 原書 用 Option 2,圖塊是靜態的、依固定格子預先產生,每層一套。格子用 geohash 編碼,一格一個 geohash,從經緯度 + 縮放層級算 geohash 非常有效率,可以在 client 算,例如 Google 總部那張:
https://cdn.map-provider.com/tiles/9q9hvu.png
📖 原書 但這個演算法就寫死在所有平台的所有 client。推 app 更新耗時又有點風險,必須確定 geohash 是長期要用、不太會改的編碼方式;真要換,工很大、風險不低。
📖 原書 另一個選項:加一個 map tile service 當中介,用同樣的輸入組出 tile URLs。這是個非常簡單的服務,多出來的維運彈性可能值得。這是可以和面試官好好討論的取捨。使用者移到新位置或新縮放層級時,它決定要哪些圖塊,轉成一組 URL。
動手玩從經緯度算出 9 張圖塊的 URL
點地圖:這一格加周圍 8 格,就是要下載的 9 張
這一步要解決的問題9 張圖塊的網址,到底怎麼從經緯度算出來?
🔭 依 Triton 原則推論 9 格很便宜
「每一個 geohash 都是一個長方形 – 在一個長方形內的點,其最近鄰居一定是…… 在同一長方形內,或在鄰近八個長方形內 – 對於一個 geohash ,要找出鄰近8個長方形的所需時間是: O(1) ,真的是 O(1)」「Geohash 有現有 library ,不用自己來寫」🗣️ Triton 本人說 064-introToAlgorithm.pdf.md · 回答「1 萬個點找最近鄰居」
🔭 064 講的是找最近鄰居,不是地圖。但同一個性質讓原書的 map tile service 真的「very simple」:算 9 格是 O(1)、有現成 library。所以加這一層的代價主要是多一次 request,不是運算。
原書 Step 3Data model:Routing tiles · Precomputed images · Figure 13
四種資料(上):routing tiles 放 S3,地圖圖片預先算好
這一步要解決的問題道路資料和地圖圖片,要用什麼格式、存在哪裡?
📖 原書 要處理四種資料:routing tiles、使用者位置、geocoding 資料、預先算好的世界地圖圖塊。
📖 原書 Routing tiles:最初的道路資料集來自不同來源與主管機關,數 TB,之後用 app 持續收集的使用者位置改善。裡面是大量道路和 metadata(名稱、郡縣、經緯度),不是圖的結構,大多數路由演算法用不了。所以跑一條定期的離線管線,叫 routing tile processing service,轉成 routing tiles,並定期捕捉道路變更。
📖 原書 輸出有三組不同解析度;每個 tile 有節點與邊的清單,還有它的道路連到的其他 tiles 的參考,合起來是演算法可以逐步吃的互連路網。
📖 原書 存哪?圖通常在記憶體用 adjacency list 表示,但 tiles 太多放不下。存成 DB 的 rows?只把 DB 當儲存,很貴,而且用不到任何 DB 功能。更有效率:放 S3 這類 object storage,在用它的 routing service 上積極 cache;用高效能套件把 adjacency list 序列化成二進位檔;在 object storage 裡依 geohash 組織,用經緯度就能快速找到 tile。
白話:adjacency list=每個路口列出它連到哪些路口;序列化=把記憶體裡的資料存成一個檔案;S3=Amazon 的 object storage。
📖 原書 裝置要某區地圖時,得拿附近道路、算出一張含所有道路與細節的圖。這種計算又重又重複,所以算一次就 cache:在不同縮放層級預先算好,放在 CDN,背後是 Amazon S3 這類雲端儲存。
原書 Step 3Data model:User location · Geocoding database · Table 4
四種資料(下):位置寫很多,地點讀很多
這一步要解決的問題使用者位置和地點資料,各自需要什麼樣的資料庫?
📖 原書 使用者位置資料很有價值:用來更新道路資料和 routing tiles,建立即時與歷史路況資料庫,也被多個串流處理服務拿去更新地圖資料。
📖 原書 需要能處理大量寫入、可以水平擴展的資料庫,Cassandra 是不錯的候選。一列長這樣:
| user_id | timestamp | user_mode | driving_mode | location |
|---|---|---|---|---|
| 101 | 1635740977 | active | driving | (20.0, 30.5) |
📖 原書 Geocoding database:存地點和對應的經緯度。讀很頻繁、寫很少,可以用 Redis 這類 key-value 資料庫加快讀取。用途:把起點、終點轉成經緯度,再交給 route planner service。
白話:水平擴展=加機器來分擔;key-value 資料庫=用一個名字(key)查一個值,像查字典。
原書這樣做會出什麼事?你猜猜看:地點資料只放在 Redis。Redis 當機重開,裡面的「Disneyland」會怎樣?
Redis 把資料放在記憶體裡,為了快,不保證當機後還在。所以它比較像小抄(cache),正本要放在一個主資料庫。右邊是 Triton 怎麼說 Redis。
🔭 依 Triton 原則推論 Redis 當 geocoding DB:正本在哪?
「Redis的設計目標是用作 caching / hot data的短期儲存 – 因為 caching / hot data都可以從資料庫重建 – 為了效能, Redis不重視資料 Durability」🗣️ Triton 本人說 088-redis-intro.pdf.md · 「Redis不是資料庫」
「如果 Redis當掉,一定會有 data loss的 – 所以,正常人使用 Redis…… – 用作 caching,資料同時存放於主資料庫」🗣️ Triton 本人說 087-redis-2019.pdf.md · Redis 的取向
- 🔭 原書選 Redis 的理由是「讀多寫少、要快」,這正是 cache 的條件,和 088 不衝突。
- 🔭 但原書沒說地點資料的正本放哪。依 087,Redis 裡的這份應該能從一個主資料庫重建;Redis 當掉時,導航不能因此找不到「Disneyland」。
第四種資料「預先算好的地圖圖片」在上一頁(第 36 頁)。位置資料怎麼存,deep dive 下一頁再細講。
原書 Step 3Location service deep dive · Figure 14 · Table 5
每秒 100 萬筆位置:選 AP,用 Cassandra
這一步要解決的問題每秒 100 萬筆位置寫入:資料庫怎麼選、key 怎麼設?
📖 原書 每秒 100 萬次位置更新,需要支援快速寫入的資料庫:NoSQL key-value 或 column-oriented 資料庫都好。使用者位置一直在變,新的一到,舊的就過時,所以可以把 availability 放在 consistency 前面。CAP theorem 說 consistency、availability、partition tolerance 只能選兩個;依我們的限制選 A + P。很適合的是 Cassandra,能在我們的規模下提供強可用性保證。
📖 原書 key 是 (user_id, timestamp),value 是經緯度。user_id 是 primary(partition)key,timestamp 是 clustering key。好處:同一個 partition key 的資料存在一起、依 timestamp 排序,所以很快讀到某人的最新位置,查某人某段時間的位置也很有效率。
| key (user_id) | timestamp | lat | long | user_mode | navigation_mode |
|---|---|---|---|---|---|
| 51 | 132053000 | 21.9 | 89.8 | active | driving |
白話:CAP 見 06 章第 7 頁;partition key=決定資料放哪一格(同一人放一起);clustering key=格子裡依什麼排好(時間)。
延伸基礎第 12 階 · 路況更新懂的人可以跳過
- 前幾章的基礎
- 經緯度
- geocoding
- map tile
- zoom level
- graph
- shortest path
- A*
- routing tile
- 分層 tiles
- batching
- 路況更新
- ETA
一條路塞不塞,看路上的車回報走多快
① 先想像
同一條路上有 5 台計程車。總台看每台一分鐘走了多遠,不用派人去看,就知道這條路順不順。
你猜猜看:這條路平常 1 分鐘走 1,000 公尺。5 台車回報 1 分鐘走了 300、200、100、200、200 公尺。路況是?
平均 1 分鐘 200 公尺,是平常的五分之一。車子的位置回報,就是路況的來源。
③ 這叫做 live traffic、stream
live traffic(即時路況):從很多車的回報算出「這條路現在多快」。stream(資料流):回報像水流一樣一直流進來,邊流邊算。
④ 跟這章的關係
原書把位置丟進 Kafka(車隊的廣播站,見 01 章 message queue),路況服務邊收邊更新(下一頁)。
② 動手玩:前方出了車禍
原書 Step 3How do we use the user location data? · Figure 15
位置寫進 DB 之外,再丟一份到 Kafka 給大家用
這一步要解決的問題位置資料除了存起來,還有哪些服務要用?怎麼分給它們?
📖 原書 位置資料支援很多用途:偵測新開和最近封閉的道路;當成長期提升地圖準確度的輸入之一;也是即時路況的來源。
📖 原書 為了這些用途,除了把目前位置寫進資料庫,還把它記錄到 message queue,例如 Kafka。Kafka 是統一的低延遲、高吞吐量資料串流平台,為即時資料流設計。
📖 原書 其他服務從 Kafka 消費位置資料流:live traffic service 解析串流、更新即時路況資料庫;routing tile processing service 偵測新開或封閉的道路,更新 object storage 裡受影響的 routing tiles;其他服務也能為不同目的接上這條串流。
文組翻譯:司機的回報先記到車隊的日誌本(DB),同時用廣播喊一次(Kafka)。路況組、地圖組、分析組各自聽廣播做自己的事,誰慢了也不會卡住司機。
原書 Step 3Rendering map · Precomputed tiles · Figure 16
21 個縮放層級:每升一層,張數 ×4,每張還是 256 × 256
這一步要解決的問題21 個縮放層級,每一層的圖塊怎麼排?
📖 原書 這段主要參考 Google Design 的文章 [5]。依 client 的 viewport 大小和縮放層級,給不同的預先算好的圖塊組。Google Maps 用 21 個縮放層級(Table 1),我們也一樣。
📖 原書 Level 0 是縮得最遠的一層,整張地圖是一張 256 × 256 的圖塊。每升一層,南北、東西方向的張數各加倍,每張仍是 256 × 256:Level 1 是 2 × 2 張、合起來 512 × 512;Level 2 是 4 × 4 張、合起來 1024 × 1024。每升一層,整組像素是上一層的 4 倍,細節更多;client 依縮放層級用最適合的細緻度,不必下載過多細節浪費頻寬。
原書 Step 3Optimization: use vectors
不傳圖片,改傳「怎麼畫」:向量圖塊
這一步要解決的問題圖片很佔流量、放大又會糊。有沒有更好的方式?
點陣圖塊(PNG)
向量圖塊(paths + polygons)
示意:同一塊街區,左邊是一張小 PNG 被拉大,右邊是 client 依向量資料重畫。
📖 原書 隨著 WebGL 的發展,一個可能的改進是:不再透過網路傳圖片,改傳向量資訊(paths 和 polygons),由 client 自己畫。
白話:WebGL=讓瀏覽器直接用顯示卡畫圖的技術;paths、polygons=線條和多邊形。
明顯的好處
向量資料的壓縮效果遠好於圖片,省下的頻寬很可觀。
不那麼明顯的好處
縮放體驗好很多。點陣圖從一層放大到下一層時,所有東西被拉伸、出現像素格,視覺上很刺眼;向量圖可以把每個元素適當縮放,放大很順。
文組翻譯:點陣圖是「照片」,放大就糊;向量圖是「食譜」,放大就照食譜重煮一份,永遠是新鮮的。
原書 Step 3Navigation service deep dive · Figure 17
導航服務拆開來:geocoding、route planner、三個幫手、updater
這一步要解決的問題「找一條最快的路」要拆成哪幾個服務,各做什麼?
📖 原書 這個服務負責找最快的路線。逐一看元件:
| 元件 | 做什麼 | 頁 |
|---|---|---|
| Geocoding service | 地址 → 經緯度 | 44 |
| Route planner service | 依目前路況和道路狀況,算出旅行時間最佳化的建議路線;呼叫下面三個 | 45 |
| Shortest-path service | top-k 最短路徑,不看路況;跑 A* 變形 | 45 |
| ETA service | 每條路線估時間,用 ML | 47 |
| Ranker(+ Filter service) | 套用使用者篩選,排序回傳 top-k | 47 |
| Updater services | 從 Kafka 非同步更新 Traffic DB、Routing tiles | 47 |
白話:top-k=前 k 名;ML(機器學習)=從大量歷史資料學出規律來預測;非同步=不用等它做完,先回應再說。
原書 Step 3Geocoding service
Geocoding service:先把「地址」翻成「座標」
這一步要解決的問題導航的第一步:使用者給的地址,怎麼變成座標?
📖 原書 第一步需要一個服務,把地址解析成經緯度。地址格式可能不同:可能是地名,也可能是文字地址。以下是 Google geocoding API 的 request 和 response 範例:
https://maps.googleapis.com/maps/api/geocode/json?address=1600+Amphitheatre+Parkway,+Mountain+View,+CA
📖 原書 Navigation service 在把經緯度往下游傳、去找路線之前,會先呼叫這個服務把起點和終點 geocode。
原書 Step 3Route planner · Shortest-path service · Figure 18
A* 從起點的 tile 出發,走到哪就載入哪
這一步要解決的問題在 routing tiles 上,怎麼找出最短的幾條路?
📖 原書 Route planner service 依目前路況和道路狀況,算出旅行時間最佳化的建議路線,會和下面幾個服務互動。
📖 原書 Shortest-path service 收到起點、終點的經緯度,回傳 top-k 最短路徑,不考慮路況,只看道路結構。圖很少變,所以cache 路線可能有幫助。它對 object storage 裡的 routing tiles 跑 A* 的變形:
- 經緯度轉成 geohash,用來載入起點和終點的 routing tiles
- 從起點的 tile 開始走圖,擴大搜尋範圍時,從 object store(或之前載入過的本地 cache)hydrate 鄰近的 tiles
- 同一塊區域的不同層級 tiles 之間有連結,所以演算法可以「進入」只有高速公路的大 tile
- 需要時繼續載入更多鄰近 tiles(或不同解析度的 tiles),直到找到一組最佳路線
白話:hydrate=把需要的 tile 從倉庫載入記憶體;A* 見第 18 頁。
延伸基礎 · 動手算第 13 階 · ETA懂的人可以跳過
- 前幾章的基礎
- 經緯度
- geocoding
- map tile
- zoom level
- graph
- shortest path
- A*
- routing tile
- 分層 tiles
- batching
- 路況更新
- ETA
「還有 4 公里,大概 10 分鐘到」是怎麼算的?
① 先想像
把路線切成幾段。每段的長度除以那段現在的速度,再加起來。
你猜猜看:路線 A 3 公里,全塞車,時速 15。路線 B 5 公里,走高速公路,時速 60。哪條先到?
A:3 ÷ 15 = 0.2 小時 = 12 分鐘。B:5 ÷ 60 小時 = 5 分鐘。最短的路不一定最快。
③ 這叫做 ETA
ETA(estimated time of arrival):預計抵達時間。每段距離 ÷ 那段的速度,全部加起來。
④ 跟這章的關係
原書的 ETA service 還用機器學習,猜 10–20 分鐘後的路況(下一頁)。
② 動手玩:點每一段,換它的路況
原書 Step 3ETA service · Ranker service · Updater services
最短的路不一定最快:估時間、篩條件、排名次
這一步要解決的問題最短的路不一定最快。怎麼把路況算進去,再挑出前幾名?
三條候選路線與所有分鐘數都是示意。流程:shortest-path(top-k,不看路況)→ ETA(每條估時間)→ ranker(篩選 + 由快到慢)→ 回傳 top-k。
📖 原書 ETA service:route planner 拿到可能的最短路徑清單後,對每條路線呼叫 ETA service 估時間。ETA service 用機器學習,依目前路況和歷史資料預測。挑戰之一是不只要即時路況,還要預測 10 或 20 分鐘後的路況;這要在演算法層面解決,本節不談(參考 [16]、[17])。
📖 原書 Ranker service:route planner 拿到 ETA 預測後交給 ranker,套用使用者定義的篩選,例如避開收費道路、避開高速公路。Ranker 把可能路線由快到慢排序,回傳 top-k 給 navigation service。
📖 原書 Updater services:接上 Kafka 的位置更新串流,非同步更新重要的資料庫,例如:
- Routing tile processing service:把新發現的道路和封路轉成持續更新的 routing tiles,讓 shortest path service 更準
- Traffic update service:從活躍使用者送來的位置串流萃取路況,寫進即時路況資料庫,讓 ETA service 估得更準
原書 Step 3Improvement: adaptive ETA and rerouting · Figure 19、20
車禍在 r_2:百萬條導航裡,誰會被影響?
這一步要解決的問題路上出車禍:百萬條導航裡,怎麼快速找出受影響的人?
📖 原書 目前的設計不支援自適應 ETA 與改道。要做到,server 得追蹤所有正在導航的使用者,路況一變就持續更新他們的 ETA。要回答:怎麼追蹤?怎麼存,才能在數百萬條路線裡有效率地找到受影響的人?
📖 原書 天真解:user_1 的路線是 routing tiles r_1…r_7(Figure 19)。資料庫每人一列:
user_1: r_1, r_2, r_3, …, r_k user_2: r_4, r_6, r_9, …, r_n user_3: r_2, r_8, r_9, …, r_m … user_n: r_2, r_10, r_21, ..., r_l
r_2 出事,就逐列檢查清單裡有沒有 r_2。n 列、平均長度 m:O(n × m)。
📖 原書 更快:每人只存目前的 tile、包含它的上一層 tile、再上一層……直到某一層的 tile 連目的地也包含(Figure 20):
user_1, r_1, super(r_1), super(super(r_1)), …
只要檢查出事的 tile 在不在這列最後那個 tile 裡:不在,就不受影響;在,就受影響。這樣能很快篩掉很多使用者。
原書 Step 3交通恢復之後 · Delivery protocols
改道要「推」給手機:選 WebSocket
這一步要解決的問題新的路線,要怎麼主動送到正在開車的手機上?
📖 原書 上一頁的方法沒說交通恢復時怎麼辦。例如 r_2 恢復了,使用者可以回到舊路線,他們怎麼知道?一個想法:追蹤導航使用者所有可能的路線,定期重算 ETA,發現 ETA 更短的新路線就通知使用者。
📖 原書 導航中路況會變,server 需要可靠的方式把資料推到手機。選項:mobile push notification、long polling、WebSocket、Server-Sent Events (SSE)。
| 選項 | 原書的評語 |
|---|---|
| Mobile push notification | 不理想:payload 很有限(iOS 4,096 bytes),也不支援 web 應用 |
| Long polling | WebSocket 通常被認為比它好,因為 WebSocket 對 server 的負擔很輕 |
| WebSocket | 傾向選它:支援雙向通訊;last-mile delivery 這類功能可能需要雙向即時通訊 |
| SSE | 和 WebSocket 都可以用 |
ETA 與改道的更多細節見參考資料 [16]。
白話:push notification=手機跳出來的通知(10 章);long polling=一直問「有新的嗎」(12 章);WebSocket=一直開著的雙向電話線(12 章);SSE=server 單向一直推。
到這裡你已經會了小結 4 / 4
- 前幾章的基礎
- 經緯度
- geocoding
- map tile
- zoom level
- graph
- shortest path
- A*
- routing tile
- 分層 tiles
- batching
- 路況更新
- ETA
到這裡你已經會了:路況怎麼變成「還要幾分鐘」
- 位置流進 Kafka;路況服務從車速算出 live traffic,寫進 Traffic DB。
- ETA = 每段距離 ÷ 速度再加總。最短不一定最快,ranker 依 ETA 排名次。
- 路況一變,server 用 super tile 快篩出受影響的人,再用 WebSocket 推改道。
13 階全部走完了
下一頁是原書的最終設計圖;最後看 Triton 在別的題目講過的原則,怎麼對照這章的數字。
原書 Step 3Final design · Figure 21
全部拼起來:最終設計
這一步要解決的問題全部元件拼起來,長什麼樣子?
📖 原書 每一塊都齊了,原書把它們合成 Figure 21:
- 導航:Geocoding Service(Geocoding DB)→ Navigation Service → Route Planner Service → Shortest Path Service(Routing Tiles)、ETA Service(Traffic DB)、Ranker(Filter Service:避開收費等)
- 自適應 ETA 與改道:同時看 ETA Service 和 Active Users 資料庫,依即時路況動態調整路線
- 路況回饋:Update Traffic Service 讓 Traffic DB 跟著位置資料持續更新,形成回饋迴圈
Figure 21 只畫了導航那一半。位置更新那一半(Location service、Cassandra、Kafka)在 Figure 15(第 40 頁),地圖那一半(CDN)在 Figure 10、12(第 32、34 頁)。
原書 Step 4Wrap up · Chapter summary
收尾:加分題是「多點停靠」
這一步要解決的問題主體設計完,還有什麼可以加分?
📖 原書 本章設計了簡化版 Google Maps,關鍵功能:位置更新、ETA、路線規劃、地圖渲染。
📖 原書 想擴充的話,一個可能的改進是替企業客戶提供多點停靠導航:給一組目的地,依即時路況找出拜訪的最佳順序並提供導航。對 DoorDash、Uber、Lyft 這類配送服務很有幫助。
為什麼這是加分題?
120
種拜訪順序
補充 · Triton 線先講清楚出處的邊界
Triton 談過什麼、沒談過什麼
沒有出處的部分(不推論)
- 地圖投影、geocoding、map tile 的切法與縮放層級
- Dijkstra、A*、routing tiles、分層路網
- ETA 的機器學習、ranker、改道演算法
- 向量圖塊、WebGL
- WebSocket vs SSE vs long polling 的選擇
這些主題在這份簡報裡只有原書的說法。materials/core 裡搜不到 Google Maps、導航、routing、ETA 的講義或文章。
讀法:每張卡上 🗣️ 的引文是 Triton 在別的題目說的話,原題目寫在出處旁邊;🔭 那段才是我們拿原書的數字去對照的推論。
🔭 有原則、也有原書數字可以對照的地方
- 讀可以走 CDN、寫不行(166、059、126):原書 62,500 MB/s 的圖塊走 CDN,1M QPS 的位置寫入不能 → 第 54 頁
- 可遺失的資料怎麼存(117、080、106):位置「新的一到舊的就過時」,原書選 AP 的 Cassandra → 第 55 頁
- Kafka 的門檻(138):每秒 1K message 以下是 overkill;原書是 200K–1M → 第 55 頁
- 小卡:geocoding DB 用 Redis 時正本在哪(088、087)→ 第 37 頁;9 格 URL 與 geohash 鄰格(064)→ 第 35 頁
補充 · Triton 線讀與寫分開算
看起來是「看地圖」的系統,最重的卻是寫入
原書這樣做會出什麼事?你猜猜看:地圖圖塊每秒 62,500 MB 交給 CDN。位置更新尖峰每秒 100 萬筆,能不能也交給 CDN 擋下來?
CDN 只能先放好「大家拿的都一樣」的東西。每個人的位置都是新的,必須送進 location service 寫進資料庫。所以這題最重的是寫,不是讀。
「Write不能用CDN,Read可以。所以Write越重的系統(像是電商購物),比單純的blogging / 討論區(像某mobile01)更花錢」🗣️ Triton 本人說 166-有人問一個系統的server cost要用上多少錢。.md · per user server cost 的因素 2
「Read-only request 請善用 CDN」🗣️ Triton 本人說 059-ecom-system design.pdf.md · ratelimiting 那頁
「「商品狀態」的頁面是完全地read-only的,頁面本身有設定好CDN嗎?……現在搶買時段,資料庫100%忙碌於write上面,好的系統應該讓read-only traffic相對上不受影響的。」🗣️ Triton 本人說 126-喵談 Keep it simple, stupid….md · 限量商品搶購
🔭 推論 用原書的數字分開算
- 🔭 原書的 Option 2(靜態、預先算好、用 geohash 當 URL)就是把地圖做成 059、126 說的 read-only 內容,讓 CDN 吃下 62,500 MB/s。Option 1 動態產生「很難 cache」,等於放棄這個槓桿。
- 🔭 166 說寫越重越花錢。這題的寫入(尖峰 1M QPS 位置更新)無論如何都要進 location service 和資料庫,整章 deep dive 一半在處理它。
- 🔭 Figure 7 裡圖塊不經過 LB,和位置寫入走不同路;126 的「write 忙時 read-only 不受影響」在這裡是架構自帶的。
補充 · Triton 線可遺失的寫入 · Kafka 的門檻
位置掉一點也死不了人:Cassandra + Kafka 落在適用範圍
原書這樣做會出什麼事?你猜猜看:一個 10 萬 DAU 的外送 app,照抄原書的 Cassandra + Kafka。
用原書的參數算:10 萬 DAU 平均每秒約 20 批、尖峰約 100 批,離每秒 1K 還差 10 倍。同一個點子,規模不到就是殺雞用牛刀。下面是 Triton 在別的題目講的門檻。
「到底這份data是否錯一點也沒所謂的?……還是他絕對不能錯」「不需要Consistency的東西就別用RDBMS來存啦。……(當然,如果你的系統流量是 100 RPS以下的,你所有東西全用postgresql也沒什麼差)」「(再三警告:流量不夠大請勿用上noSQL)」🗣️ Triton 本人說 117-喵看Data 的思維.md · 回答 UserStatistics table
「Cassandra是AP向的 – 即是說:你一點也不介意 data consistency」「現實上,毫不介意 consistency的商業應用很少的」🗣️ Triton 本人說 080-nosql-intro.pdf.md · Cassandra適用場景
「主要還是一句:不能不見的data,我一定存到RDBMS」🗣️ Triton 本人說 106-喵 data.md
「如果系統還沒到每秒1K Message的,kafka對你會是overkill。」🗣️ Triton 本人說 138-喵談 rabbitMQ 和 kafka.md
🔭 推論 你的位置更新是每秒幾則?
其他參數照原書:每週導航 35 分、每 15 秒一批、尖峰 5 倍、一天 105 秒。
- 🔭 原書選 AP 的理由「新的一到舊的就過時」,正是 117 的「錯一點也沒所謂」,也是 080 說「很少」的那種應用;而且 1M QPS 遠超過 117 的 100 RPS。原書在這個規模選 Cassandra,在 Triton 的分類裡站得住。
- 🔭 原書尖峰 1M、平均 200K,是 138 門檻的 1,000 倍和 200 倍。用原書參數,平均要約 500 萬 DAU、尖峰要約 100 萬 DAU 才碰到 1K。一個 10 萬 DAU 的外送 app 照抄 Cassandra + Kafka,就是 117、138 警告的情況。
- 🔭 同一章「不能不見」的是道路與地點的正本(106);Redis 那份見第 37 頁。
一句話記住
把世界切成格子:
圖片的格子交給 CDN,路網的格子用到才載入,位置先存一批再送。
原書的骨架
- 10 億 DAU;位置更新、導航與 ETA、地圖渲染
- 21 層 map tiles ≈ 100 PB,預先算好、geohash 當 URL、CDN 送
- Routing tiles 三層,放 S3,A* 走到哪載入哪
- 位置 15 秒一批,尖峰 1M QPS → Cassandra(AP)+ Kafka
- Geocoding → shortest path → ETA → ranker;WebSocket 推改道
原書承認的取捨
- Client 算 geohash 快,但換編碼要等所有 app 更新
- Shortest path 不看路況,最快要靠 ETA
- 只看最後一個 super tile 能快篩,但交通恢復時要另外重算
- Push notification 有 4 KB 上限、不支援 web
🔭 拿 Triton 的原則對照
- 讀走 CDN、寫不行:這題最重的是寫
- 位置是可遺失資料,AP 合理;規模小時 PostgreSQL 就好
- Kafka 的 1K 門檻:原書 200–1,000 倍,小 app 別照抄
- Redis 當 geocoding DB:正本要在別處
本章名詞小卡課後複習用 · 每個名詞一句白話
今天出現的名詞,一句話講完
給工程師的重點出處與標籤
引述來源與原書對照
Triton 本人的講義 / 文章(都不是講地圖)
- 166-有人問一個系統的server cost要用上多少錢。.md — 「Write不能用CDN,Read可以」、Write 越重越花錢
- 059-ecom-system design.pdf.md — 「Read-only request 請善用 CDN」
- 126-喵談 Keep it simple, stupid….md — 「商品狀態」頁 read-only + CDN;write 忙時 read-only traffic 不受影響
- 117-喵看Data 的思維.md — Consistency / Durability / Usage 三問;不需 consistency 別用 RDBMS;100 RPS 以下全用 PostgreSQL;流量不夠大勿用 NoSQL;AS buffer 會掉資料
- 080-nosql-intro.pdf.md — Cassandra 是 AP 向、毫不介意 consistency 的商業應用很少
- 106-喵 data.md — 「不能不見的data,我一定存到RDBMS」(從「主要還是一句」起才確定是 Triton)
- 138-喵談 rabbitMQ 和 kafka.md — 每秒 1K message 以下 Kafka 是 overkill
- 088-redis-intro.pdf.md、087-redis-2019.pdf.md — Redis 是 caching / hot data、可從資料庫重建、當掉一定 data loss
- 064-introToAlgorithm.pdf.md — geohash 鄰近 8 格 O(1)、有現成 library(原本回答 1 萬點找最近鄰居)
一個可以直接問自己的問題
你的系統每秒有幾則寫入?其中有多少是「掉一點也死不了人」的?先算這兩個數,再決定要不要 Cassandra 和 Kafka。
原書對照
Alex Xu & Sahn Lam, System Design Interview Vol.2 Ch.3。Step 1 問答與需求(第 6 頁)、Positioning、3D to 2D 與 Figure 1–2(8)、Geocoding(10)、Geohashing 與 Figure 3(12)、Map rendering(14)、Road data 與 Figure 4(19)、Routing tiles、Figure 5 與 Reminder(22)、Hierarchical routing tiles 與 Figure 6(24)、Storage 與 Table 1(25)、Server throughput(27)、High-level design 與 Figure 7(29)、Location service 與 Figure 8–9(30)、Navigation service API(31)、Map rendering Option 1/2 與 Figure 10–11(32)、Table 2–3(33)、tile URL 與 Figure 12(34–35)、Data model 與 Figure 13、Table 4(36–37)、Location service deep dive、Figure 14、Table 5(38)、Figure 15(40)、Precomputed tiles 與 Figure 16(41)、Use vectors(42)、Navigation service 與 Figure 17(43)、Geocoding service(44)、Route planner、Shortest-path 與 Figure 18(45)、ETA、Ranker、Updater(47)、Adaptive ETA 與 Figure 19–20(48)、Delivery protocols(49)、Final design 與 Figure 21(51)、Wrap up 與章末心智圖(52)。21 張圖與心智圖都依原書圖說和 alt 重繪,不是原圖;Figure 2、3、4、5、6、13、16、18 原圖有地圖或地圖截圖當底,改畫成示意。
循序漸進(文組版)的頁面
學習地圖(第 3 頁);延伸基礎 13 階:前幾章的基礎(5)、經緯度(7)、geocoding(9)、map tile(11)、zoom level(13)、graph(16)、shortest path(17)、A*(18)、routing tile(21)、分層 tiles(23)、batching(26)、路況更新(39)、ETA(46);小結(15、20、28、50);名詞小卡(57)。阿明的計程車是虛構情境,延伸基礎頁的數字都是示意。DAU、QPS、CDN、message queue、CAP、WebSocket 連到 01、02、06、10、12 章的延伸基礎頁。