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 倍,記錄的位置點一個都沒少。

0下載過的圖塊0記錄的位置點0送出的 request

學習地圖本章的概念階梯

今天爬 13 階。每一階只用前面講過的東西。

  1. 1前幾章的基礎DAU、CDN…
  2. 2經緯度地球上的座位號碼
  3. 3geocoding地址翻成座標
  4. 4map tile一片拼圖
  5. 5zoom level放大鏡的倍率
  6. 6graph路口和馬路
  7. 7shortest path把分鐘數加起來
  8. 8A*朝目的地找
  9. 9routing tile路網也切塊
  10. 10分層 tiles小巷、大路、高速
  11. 11batching存一批再送
  12. 12路況更新車隊回報車速
  13. 13ETA還要多久到

第 1–3 階 · 地點怎麼說

要回答:手機怎麼說出「我在哪」、「我要去哪」?

第 4–5 階 · 地圖怎麼畫

要回答:100 PB 的地圖,手機怎麼只拿需要的那幾片?

第 6–10 階 · 路怎麼找

要回答:全世界的路網,怎麼在幾秒內找出一條路?

第 11–13 階 · 路況怎麼更新

要回答:10 億人的位置怎麼送回來,變成「還要 12 分鐘」?

全程只跟一台車:阿明的計程車(虛構)

地圖冊的一頁 = map tile換一本更細的分冊 = zoom level路口 / 馬路 = node / edge腦中的路網分冊 = routing tile無線電回報 = location update「還要幾分鐘」= ETA

阿明每天從台北車站載客到動物園。每爬 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 階 · 前幾章的基礎懂的人可以跳過

  1. 前幾章的基礎
  2. 經緯度
  3. geocoding
  4. map tile
  5. zoom level
  6. graph
  7. shortest path
  8. A*
  9. routing tile
  10. 分層 tiles
  11. batching
  12. 路況更新
  13. ETA

「10 億人每天開地圖」:先複習前幾份簡報的五個詞

① 先想像

全台 1,000 萬人,每人每天打開地圖查一次路。

你猜猜看:一天 1,000 萬次查路,平均每秒大約幾次?

④ 跟這章的關係

原書第一句就是 10 億 DAU(下一頁);load balancer 和 CDN 是高階設計圖(第 29 頁)的主角。

② 動手玩:每天的查路次數,換成每秒

平均每秒
100
最忙時(×5)
500

原書 Step 1釐清需求

10 億 DAU;只做位置更新、導航與 ETA、地圖渲染

這一步要解決的問題面試一開始:這個 Google Maps 要做到多大、做哪幾件事?

📖 原書 應徵者 × 面試官

應徵者問面試官答
預期每日活躍用戶數?1 billion DAU
要專注哪些功能?路線指引、導航、ETA?聚焦位置更新、導航、ETA、地圖渲染
路網資料多大?可以假設拿得到嗎?好問題。假設已從不同來源取得,原始資料有數 TB
要考慮交通狀況嗎?要,交通狀況對準確估時非常重要
不同交通模式:開車、走路、公車?要支援不同交通模式
要支援多點停靠嗎?可以讓使用者設多個停靠點,但先不專注
商家地點和照片呢?預期多少照片?很高興你想到,但不用設計

白話:DAU=每天實際打開 app 的人數;ETA=預計抵達時間(第 46 頁);地圖渲染(map rendering)=把資料畫成手機上看得到的地圖;TB=1,000 GB。

📖 原書 三個關鍵功能(主要裝置:手機)

  1. 使用者位置更新
  2. 導航服務,包含 ETA 服務
  3. 地圖渲染

📖 原書 非功能需求與限制

  • Accuracy:不能給使用者錯的路線
  • Smooth navigation:client 端的地圖渲染要非常流暢
  • Data and battery usage:盡量少用流量和電,對手機非常重要
  • 一般的可用性與擴展性需求

📖 原書 開場數字:截至 2021 年 3 月,Google Maps 有 10 億日活、覆蓋全球 99%、每天 2,500 萬筆即時位置資訊更新。本章地圖圖塊來自 Stamen Design,資料來自 OpenStreetMap。

延伸基礎第 2 階 · 經緯度懂的人可以跳過

  1. 前幾章的基礎
  2. 經緯度
  3. geocoding
  4. map tile
  5. zoom level
  6. graph
  7. shortest path
  8. A*
  9. routing tile
  10. 分層 tiles
  11. batching
  12. 路況更新
  13. ETA

地球上的「座位號碼」

① 先想像

電影票寫「第 7 排 12 號」,兩個數字就找到你的座位。地球上也畫好了排和號。

你猜猜看:「第 3 排 5 號」和「第 5 排 3 號」是同一個位子嗎?

③ 這叫做 latitude、longitude

latitude(緯度):往北或往南幾度,像「第幾排」。longitude(經度):往東或往西幾度,像「第幾號」。

④ 跟這章的關係

手機 GPS 每秒給的就是這兩個數字。整章每個服務吃的都是(緯度, 經度)。

② 動手玩:點地圖上任一處

25.0°N緯度(第幾排)121.5°E經度(第幾號)台北最近的城市

原書 Map 101Positioning system · Going from 3D to 2D · Figure 1、2

經緯度定位置;把球壓成平面,一定會變形

這一步要解決的問題地球是圓的、螢幕是平的。怎麼說出一個位置,又怎麼把它畫到平面上?

📖 原書 Figure 1Latitude and Longitude(依原書內容重繪)

📖 原書 地球是繞軸自轉的球體,最上面是北極、最下面是南極。Lat(緯度)表示偏北或偏南多少;Long(經度)表示偏東或偏西多少。

📖 原書 把 3D 球面上的點轉到 2D 平面叫 Map Projection。做法很多、各有優缺點,幾乎都會扭曲實際幾何。Google Maps 選的是 Mercator 的修改版:Web Mercator。

文組翻譯:剝橘子皮

把橘子皮壓平,不是裂開就是被拉長。Mercator 是「越往兩極拉得越大」。拖拖看:

延伸基礎第 3 階 · geocoding懂的人可以跳過

  1. 前幾章的基礎
  2. 經緯度
  3. geocoding
  4. map tile
  5. zoom level
  6. graph
  7. shortest path
  8. A*
  9. routing tile
  10. 分層 tiles
  11. batching
  12. 路況更新
  13. ETA

「中山路 100 號」在地圖上的哪一點?

① 先想像

你上車跟阿明說「去動物園」。他得先把這三個字,換成地圖上的一個點。

你猜猜看:1 號在路口 A,199 號在 200 公尺外的路口 B。99 號大約在哪?

③ 這叫做 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懂的人可以跳過

  1. 前幾章的基礎
  2. 經緯度
  3. geocoding
  4. map tile
  5. zoom level
  6. graph
  7. shortest path
  8. A*
  9. routing tile
  10. 分層 tiles
  11. batching
  12. 路況更新
  13. ETA

一幅超大拼圖,你只要看其中 9 片

① 先想像

全世界的地圖是一幅超大拼圖。阿明的手機只看得到車子附近那一小塊。

你猜猜看:拼圖有 8 × 6 = 48 片,手機畫面一次蓋住 3 × 3 片。一開始要拿幾片?

③ 這叫做 map tile、tiling

map tile:地圖切成的一小片、大小固定的圖(原書是 256 × 256 個像素點)。tiling:切成小片,只拿需要的。

④ 跟這章的關係

原書的地圖就是這樣送到手機(第 14 頁)。每一片事先畫好,放在 CDN。

② 動手玩:移動手機畫面

9拿過的片數48全部的片數9這一步新拿的

原書 Map 101Geohashing · Figure 3

Geohashing:一直切四塊,每塊用 00、01、10、11 命名

這一步要解決的問題世界要切成格子。每一格怎麼取一個好算、好查的名字?

📖 原書 Geohashing 把一塊地理區域編碼成一小串字母和數字。核心是把地球當成攤平的表面,遞迴地把格子切成子格(正方形或長方形),每格用 0 到 3 之間的數字遞迴命名。

切幾次格子大小編碼
020,000 km × 10,000 km(整個平面)
110,000 km × 5,000 km00、01、10、11
25,000 km × 2,500 km每格再用同樣規則
…直到格子小於某個門檻

📖 原書 Geohashing 用途很多;本章用它來做 map tiling。細節原書請讀者看參考資料 [11] 和 Proximity Service 那章。

注意:這裡的編碼是四進位(每層兩個 bit),Proximity 章和後面的 tile URL 9q9hvu 用的是 base32 geohash:同一個「一直切一半」的想法,兩種寫法。

白話:遞迴=同一個規則一直重複做;bit=0 或 1 的一個小開關。

延伸基礎第 5 階 · zoom level懂的人可以跳過

  1. 前幾章的基礎
  2. 經緯度
  3. geocoding
  4. map tile
  5. zoom level
  6. graph
  7. shortest path
  8. A*
  9. routing tile
  10. 分層 tiles
  11. batching
  12. 路況更新
  13. ETA

放大鏡每轉一格,一片拆成四片

① 先想像

從太空看,台灣只是一小塊。放大一點看到縣市,再放大才看到街名。

你猜猜看:看全世界時只有 1 片。每放大一層,每片拆成 4 片。第 3 層共幾片?

③ 這叫做 zoom level

zoom level(縮放層級):放大到第幾層。第 0 層最遠、只有 1 片;層數越大越細,每片的大小不變。

④ 跟這章的關係

Google Maps 用 21 層(Table 1,第 25 頁)。所有層加起來,約 100 PB。

② 動手玩:轉放大鏡

或直接點一片放大
0zoom level1這一層全世界幾片整個世界這一層看得到

原書 Map 101Map rendering

地圖是一片一片拼起來的;放大到哪一層,就拿那一層的圖塊

這一步要解決的問題全世界的地圖太大。手機要怎麼只拿需要的那一小部分?

📖 原書 地圖渲染的一個基礎概念是 tiling:不把整個世界畫成一張大圖,而是切成小圖塊。Client 只下載使用者所在區域相關的圖塊,像馬賽克一樣拼起來顯示。

📖 原書 不同的 zoom level 有不同的一套圖塊。Client 依 viewport 的縮放層級選對的那一套,細節剛好、又不浪費頻寬。

📖 原書 極端的例子:縮到看全世界時,不該下載高縮放層級的幾十萬張圖塊,細節全浪費;而是下載最低層級的一張,用一張 256×256 像素的圖代表整個世界。

文組翻譯:地圖冊有「全台灣」一頁、「台北市」幾頁、「大安區」幾十頁。看全台灣就翻那一頁,不會把幾十頁大安區攤滿整個客廳。

白話:viewport=手機畫面現在看到的範圍;像素=螢幕上的一個小點。

64這一層全世界的圖塊9畫面要下載的

到這裡你已經會了小結 1 / 4

  1. 前幾章的基礎
  2. 經緯度
  3. geocoding
  4. map tile
  5. zoom level
  6. graph
  7. shortest path
  8. A*
  9. routing tile
  10. 分層 tiles
  11. batching
  12. 路況更新
  13. ETA

到這裡你已經會了:地點怎麼說、地圖怎麼畫

下一階要解決的問題

地圖會畫了,可是「怎麼走」?全世界幾億個路口,要怎麼找出一條路?

延伸基礎第 6 階 · graph懂的人可以跳過

  1. 前幾章的基礎
  2. 經緯度
  3. geocoding
  4. map tile
  5. zoom level
  6. graph
  7. shortest path
  8. A*
  9. routing tile
  10. 分層 tiles
  11. batching
  12. 路況更新
  13. ETA

捷運路線圖不管路多彎,只畫站和線

① 先想像

捷運路線圖不畫真實的彎曲,只畫站和站之間的線。要知道怎麼轉車,這樣就夠了。

你猜猜看:一條馬路從路口 A 通到路口 B,中間經過路口 C。只畫點和線,這條馬路變成幾條線?

③ 這叫做 graph、node / edge

graph(圖):一群點和連接它們的線。點叫 node(路口),線叫 edge(路段),線上可以寫開幾分鐘。

④ 跟這章的關係

導航演算法只認得 graph(Figure 4,第 19 頁)。全世界的路口太多,圖太大就跑不動。

② 動手玩:把街道變成點和線

6node(路口)7edge(路段)切到「只剩點和線」看看。

延伸基礎 · 動手算第 7 階 · shortest path懂的人可以跳過

  1. 前幾章的基礎
  2. 經緯度
  3. geocoding
  4. map tile
  5. zoom level
  6. graph
  7. shortest path
  8. A*
  9. routing tile
  10. 分層 tiles
  11. batching
  12. 路況更新
  13. ETA

從車站到動物園,哪一條最快?用加法就知道

① 先想像

阿明從車站 S 開到動物園 T。每段路寫著要開幾分鐘,加起來就是整條路的時間。

你猜猜看:S→A 2 分、S→B 5 分、A→B 1 分、A→T 6 分、B→T 2 分。哪條最快?

③ 這叫做 shortest path、Dijkstra

shortest path:加總最小的那條路。Dijkstra:從起點一圈一圈往外,每次先確定「目前最近」的路口。

④ 跟這章的關係

原書的 shortest-path service 就在做這件事,一次給前幾名(top-k)(第 45 頁)。

② 動手玩:自己走一遍,再看 Dijkstra 怎麼算

或從 S 開始依序點路口

延伸基礎第 8 階 · A*懂的人可以跳過

  1. 前幾章的基礎
  2. 經緯度
  3. geocoding
  4. map tile
  5. zoom level
  6. graph
  7. shortest path
  8. A*
  9. routing tile
  10. 分層 tiles
  11. batching
  12. 路況更新
  13. ETA

動物園在東邊,就先往東找

① 先想像

漣漪往四面八方一樣用力擴,連背對動物園的路都去看。人找路會先往動物園的方向試。

你猜猜看:起點在西、動物園在東。Dijkstra 會不會去看起點西邊的路口?

③ 這叫做 A*(A-star)

A*:每個路口算「已經開了多遠 + 離目的地的直線距離」,先看總和最小的。這個估計值讓它朝目的地找。

④ 跟這章的關係

原書的 shortest-path service 跑的是 A* 的變形(第 45 頁)。看的路口少,要載入的路網也少。

② 動手玩:同一張棋盤路網,兩種找法

0看過的路口—找到的路(格)

原書 Map 101Road data processing for navigation algorithms · Figure 4

導航演算法吃的是「圖」:路口是節點,馬路是邊

這一步要解決的問題地圖是給人看的。導航演算法要的,是什麼形狀的資料?

📖 原書 Figure 4Map as a graph(依原書內容重繪;原圖底圖是真實街道截圖,這裡畫成示意街區,邊上的數字是示意的路段長度)

📖 原書 大部分路徑演算法是 Dijkstra 或 A* 的變形。怎麼選是複雜的題目,本章不深入。重要的是:這些演算法都在圖(graph)上運作,路口是節點、道路是邊。

📖 原書 這些演算法的效能對圖的大小極度敏感。把全世界的路網當成一張圖,記憶體會不夠,也大到跑不動。圖必須拆成可管理的單位,演算法才能在我們的規模下運作。

文組翻譯:Dijkstra 在做什麼

從起點像漣漪一樣往外擴:每次挑「目前離起點最近、還沒確定」的路口,把它確定下來,再更新它鄰居的距離。按「下一步」看漣漪一圈一圈擴到 H。

到這裡你已經會了小結 2 / 4

  1. 前幾章的基礎
  2. 經緯度
  3. geocoding
  4. map tile
  5. zoom level
  6. graph
  7. shortest path
  8. A*
  9. routing tile
  10. 分層 tiles
  11. batching
  12. 路況更新
  13. ETA

到這裡你已經會了:路怎麼找(上)

下一階要解決的問題

全世界的 graph 塞不進一台電腦的記憶體。原書怎麼辦?答案又是「切格子」。

延伸基礎第 9 階 · routing tile懂的人可以跳過

  1. 前幾章的基礎
  2. 經緯度
  3. geocoding
  4. map tile
  5. zoom level
  6. graph
  7. shortest path
  8. A*
  9. routing tile
  10. 分層 tiles
  11. batching
  12. 路況更新
  13. ETA

去新竹,不用把全台灣的路都背在身上

① 先想像

全國路網是很厚的一大本,背不動。拆成很多分冊,開到哪一區,才翻出那一區的分冊。

你猜猜看:全國路網切成 100 塊,每塊 10 MB。台北到新竹只經過 3 塊。記憶體要放多少?

③ 這叫做 routing tile

routing tile:一塊區域裡的路口和路段(一小張 graph),存成一個檔案,用到才載入。

④ 跟這章的關係

它和 map tile 都是格子;但 map tile 是圖片,routing tile 是道路資料(第 22 頁)。

② 動手玩:從台北出發

3載入的塊30 MB記憶體1,000 MB全部載入

原書 Map 101Routing tiles · Figure 5 · Reminder

把路網也切成格子:routing tiles,用到哪塊才載入哪塊

這一步要解決的問題全世界的路網是一張太大的 graph。怎麼讓演算法跑得動?

📖 原書 Figure 5Routing tiles(依原書內容重繪;原圖底圖是真實街道截圖,這裡畫成示意)

📖 原書 拆路網的一種方法和地圖 tiling 很像:用類似 geohashing 的細分方式把世界切成小格。每一格裡的道路轉成一張小圖(格子裡的節點和邊),叫 routing tile。

📖 原書 每個 routing tile 都存著它連到的其他 tiles 的參考。演算法走過這些互相連結的 tiles 時,就能拼出更大的路網。

📖 原書 拆成可以按需載入的 routing tiles 後,演算法一次只用一小部分,需要時才載入更多,記憶體大降、搜尋變快。

📖 原書 Reminder

Routing tiles 和 map tiles 很像,都是蓋住某塊地理區域的格子。差別:map tiles 是 PNG 圖片;routing tiles 是這塊區域道路資料的二進位檔。

白話:二進位檔=給電腦讀的檔案,不是圖片也不是文字。

延伸基礎第 10 階 · 分層 tiles懂的人可以跳過

  1. 前幾章的基礎
  2. 經緯度
  3. geocoding
  4. map tile
  5. zoom level
  6. graph
  7. shortest path
  8. A*
  9. routing tile
  10. 分層 tiles
  11. batching
  12. 路況更新
  13. ETA

台北到高雄:出巷子、上高速公路、再下交流道

① 先想像

長途不會一路鑽小巷。先出巷子、上大馬路、上高速公路,快到了才下交流道。

你猜猜看:台北到高雄,中間那 300 公里最需要哪一層的細節?

③ 這叫做 hierarchical routing tiles

分層 routing tiles:三套粗細不同的 tiles:小巷層、主幹道層、高速公路層。交流道就是「從小 tile 跳到大 tile」的連結。

④ 跟這章的關係

這就是原書的 Figure 6(第 24 頁)。A* 會從小 tile「進入」只有高速公路的大 tile(第 45 頁)。

② 動手玩:去三個地方,要看幾個路口?

只用小巷層
5
分三層
5

原書 Map 101Hierarchical routing tiles · Figure 6

三層 routing tiles:小巷、主幹道、高速公路

這一步要解決的問題跨國的長途路線,用最細的街道資料會太大。怎麼辦?

📖 原書 Figure 6Routing tiles of varying sizes(依原書內容重繪;原圖是紐約曼哈頓一帶的真實地圖截圖,這裡畫成示意:大藍框、裡面一塊切成小格的綠色區域)

📖 原書 有效率的導航也需要對的細節層級。跨國路線若用很細的街道級 tiles 跑,拼出來的圖太大、太耗記憶體。通常有三組不同細節的 routing tiles:最細的 tile 小、只有地方道路;下一層較大、只有連接各區的主幹道;最粗的 tile 涵蓋大範圍、只有連接城市與州的主要高速公路。

0要載入的 tiles(示意)

📖 原書 每一層都可能有連到另一個縮放層級的邊:從地方街道 A 上高速公路 F 的交流道,小 tile 裡的節點(street A)會有一個參考,指向大 tile 裡的節點(freeway F)。

原書 Step 1Back-of-the-envelope estimation · Storage · Table 1

全世界的地圖圖塊:大約 100 PB

這一步要解決的問題全世界、所有縮放層級的地圖圖塊,總共要存多少?

📖 原書 Table 1Zoom levels(點一列)

📖 原書 換算: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懂的人可以跳過

  1. 前幾章的基礎
  2. 經緯度
  3. geocoding
  4. map tile
  5. zoom level
  6. graph
  7. shortest path
  8. A*
  9. routing tile
  10. 分層 tiles
  11. batching
  12. 路況更新
  13. ETA

每到一站寄一張明信片,還是回家一次寄一疊?

① 先想像

阿明的手機每秒記下一次「我在哪」。可以每秒打一通無線電,也可以每 15 秒把 15 個點一起報。

你猜猜看:10 台車每秒各報一次,總台每秒接 10 通。改成每 5 秒報一次(一次帶 5 個點),每秒接幾通?

③ 這叫做 batching

batching(批次):先在手機上存一批,再一次送出去。request 變少,點數不變。

④ 跟這章的關係

原書每 15 秒一批:3M QPS 變成 200K QPS(下一頁)。代價是資料晚一點到。

② 動手玩:車隊的無線電

10總台每秒接幾通10每秒收到的位置點0 秒最舊的點最晚等多久

原書 Step 1Back-of-the-envelope estimation · Server throughput

位置更新:每秒送是 3M QPS,每 15 秒一批是 200K,尖峰 1M

這一步要解決的問題10 億人邊開車邊回報位置,server 每秒要接多少 request?

📖 原書 兩種主要 request:navigation requests(client 開始一次導航)和 location update requests(導航中邊走邊送)。位置資料下游有很多用途,例如它是即時路況的輸入之一。

  1. 1 billion DAU,每人每週導航 35 分鐘 → 每週 350 億分鐘 → 每天 50 億分鐘
  2. 每秒送一次 GPS:50 億 × 60 = 每天 3,000 億 request → 3,000 億 ÷ 105 = 3 million QPS
  3. 其實不用每秒送:在 client 批次,每 15 或 30 秒送一次;頻率可依移動速度調,塞車時就放慢。本設計假設每 15 秒 → 3M ÷ 15 = 200,000 QPS
  4. 尖峰假設是平均的 5 倍 → 200,000 × 5 = 1 million QPS

白話:GPS=手機用衛星訊號定位;105=一天約 10 萬秒(實際 86,400)。

動手算

批次間隔
200,000平均 QPS1,000,000尖峰 QPS

這個 1M 會在 deep dive(第 38 頁)決定資料庫選型,也會在 Triton 那頁(第 55 頁)拿來和 Kafka 的門檻比。

到這裡你已經會了小結 3 / 4

  1. 前幾章的基礎
  2. 經緯度
  3. geocoding
  4. map tile
  5. zoom level
  6. graph
  7. shortest path
  8. A*
  9. routing tile
  10. 分層 tiles
  11. batching
  12. 路況更新
  13. ETA

到這裡你已經會了:路網怎麼切、位置怎麼送

下一階要解決的問題

零件都有了。原書接著把三個功能畫成一張架構圖:位置、導航、地圖各走哪條路?

原書 Step 2High-level design · Figure 7

三條路:位置更新、導航都經過 LB;地圖圖塊直接找 CDN

這一步要解決的問題三個功能各自要走哪一條路、經過哪些元件?

📖 原書 Figure 7High-level design(依原書內容重繪)

📖 原書 有了 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 秒送一批

這一步要解決的問題位置回報的量很大。怎麼送比較省,又要存在哪裡?

📖 原書 Figure 9Batch requests(依原書內容重繪)
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?

這一步要解決的問題圖塊要等使用者要的時候現畫,還是事先畫好?

📖 原書 Figure 10CDN(依原書內容重繪)

📖 原書 所有縮放層級的圖塊加起來約一百 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 會少很多。在這個規模,成本是重要考量。

動手算

1.25 MB每分鐘手機流量62,500CDN 每秒 MB313每個 POP 每秒 MB

原書 Step 2Tile URL:client 自己算,還是問 map tile service · Figure 12

手機怎麼知道要抓哪張圖?

這一步要解決的問題手機要下載哪幾張圖塊?網址由誰來算?

📖 原書 Figure 12Map rendering(依原書內容重繪)
  1. 手機呼叫 map tile service 拿 tile URLs,request 先到 load balancer
  2. Load balancer 把 request 轉給 map tile service
  3. Map tile service 以 client 的位置與縮放層級為輸入,回傳 9 個 tile URL:要畫的那張 + 周圍 8 張
  4. 手機從 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 張圖塊的網址,到底怎麼從經緯度算出來?

Geohash 長度


      

🔭 依 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 這類雲端儲存。

(object key 的格式是示意)
📖 原書 Figure 13Precomputed tiles(依原書內容重繪;原圖是一張真實住宅區地圖圖塊,這裡畫成示意街區)

原書 Step 3Data model:User location · Geocoding database · Table 4

四種資料(下):位置寫很多,地點讀很多

這一步要解決的問題使用者位置和地點資料,各自需要什麼樣的資料庫?

📖 原書 使用者位置資料很有價值:用來更新道路資料和 routing tiles,建立即時與歷史路況資料庫,也被多個串流處理服務拿去更新地圖資料。

📖 原書 需要能處理大量寫入、可以水平擴展的資料庫,Cassandra 是不錯的候選。一列長這樣:

📖 原書 Table 4Location table
user_idtimestampuser_modedriving_modelocation
1011635740977activedriving(20.0, 30.5)

📖 原書 Geocoding database:存地點和對應的經緯度。讀很頻繁、寫很少,可以用 Redis 這類 key-value 資料庫加快讀取。用途:把起點、終點轉成經緯度,再交給 route planner service。

白話:水平擴展=加機器來分擔;key-value 資料庫=用一個名字(key)查一個值,像查字典。

原書這樣做會出什麼事?你猜猜看:地點資料只放在 Redis。Redis 當機重開,裡面的「Disneyland」會怎樣?

🔭 依 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 排序,所以很快讀到某人的最新位置,查某人某段時間的位置也很有效率。

📖 原書 Table 5Location data
key (user_id)timestamplatlonguser_modenavigation_mode
5113205300021.989.8activedriving

白話:CAP 見 06 章第 7 頁;partition key=決定資料放哪一格(同一人放一起);clustering key=格子裡依什麼排好(時間)。

延伸基礎第 12 階 · 路況更新懂的人可以跳過

  1. 前幾章的基礎
  2. 經緯度
  3. geocoding
  4. map tile
  5. zoom level
  6. graph
  7. shortest path
  8. A*
  9. routing tile
  10. 分層 tiles
  11. batching
  12. 路況更新
  13. ETA

一條路塞不塞,看路上的車回報走多快

① 先想像

同一條路上有 5 台計程車。總台看每台一分鐘走了多遠,不用派人去看,就知道這條路順不順。

你猜猜看:這條路平常 1 分鐘走 1,000 公尺。5 台車回報 1 分鐘走了 300、200、100、200、200 公尺。路況是?

③ 這叫做 live traffic、stream

live traffic(即時路況):從很多車的回報算出「這條路現在多快」。stream(資料流):回報像水流一樣一直流進來,邊流邊算。

④ 跟這章的關係

原書把位置丟進 Kafka(車隊的廣播站,見 01 章 message queue),路況服務邊收邊更新(下一頁)。

② 動手玩:前方出了車禍

920平均每分鐘(公尺)順暢路況

原書 Step 3How do we use the user location data? · Figure 15

位置寫進 DB 之外,再丟一份到 Kafka 給大家用

這一步要解決的問題位置資料除了存起來,還有哪些服務要用?怎麼分給它們?

📖 原書 Figure 15Location data is used by other services(依原書內容重繪)

📖 原書 位置資料支援很多用途:偵測新開和最近封閉的道路;當成長期提升地圖準確度的輸入之一;也是即時路況的來源。

📖 原書 為了這些用途,除了把目前位置寫進資料庫,還把它記錄到 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 個縮放層級,每一層的圖塊怎麼排?

📖 原書 Figure 16Zoom levels(依原書內容重繪;alt 把第 0 層描述成切成四塊、第 2 層 64 張,和內文不一致,這裡依內文:第 1 層 2×2、第 2 層 4×4;原圖底圖是世界地圖,這裡只畫格子)

📖 原書 這段主要參考 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

這一步要解決的問題「找一條最快的路」要拆成哪幾個服務,各做什麼?

📖 原書 Figure 17Navigation service(依原書內容重繪)

📖 原書 這個服務負責找最快的路線。逐一看元件:

元件做什麼頁
Geocoding service地址 → 經緯度44
Route planner service依目前路況和道路狀況,算出旅行時間最佳化的建議路線;呼叫下面三個45
Shortest-path servicetop-k 最短路徑,不看路況;跑 A* 變形45
ETA service每條路線估時間,用 ML47
Ranker(+ Filter service)套用使用者篩選,排序回傳 top-k47
Updater services從 Kafka 非同步更新 Traffic DB、Routing tiles47

白話: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 上,怎麼找出最短的幾條路?

0展開的路口0載入的 tiles(共 24)—路線長度

📖 原書 Route planner service 依目前路況和道路狀況,算出旅行時間最佳化的建議路線,會和下面幾個服務互動。

📖 原書 Shortest-path service 收到起點、終點的經緯度,回傳 top-k 最短路徑,不考慮路況,只看道路結構。圖很少變,所以cache 路線可能有幫助。它對 object storage 裡的 routing tiles 跑 A* 的變形:

  1. 經緯度轉成 geohash,用來載入起點和終點的 routing tiles
  2. 從起點的 tile 開始走圖,擴大搜尋範圍時,從 object store(或之前載入過的本地 cache)hydrate 鄰近的 tiles
  3. 同一塊區域的不同層級 tiles 之間有連結,所以演算法可以「進入」只有高速公路的大 tile
  4. 需要時繼續載入更多鄰近 tiles(或不同解析度的 tiles),直到找到一組最佳路線

白話:hydrate=把需要的 tile 從倉庫載入記憶體;A* 見第 18 頁。

延伸基礎 · 動手算第 13 階 · ETA懂的人可以跳過

  1. 前幾章的基礎
  2. 經緯度
  3. geocoding
  4. map tile
  5. zoom level
  6. graph
  7. shortest path
  8. A*
  9. routing tile
  10. 分層 tiles
  11. batching
  12. 路況更新
  13. ETA

「還有 4 公里,大概 10 分鐘到」是怎麼算的?

① 先想像

把路線切成幾段。每段的長度除以那段現在的速度,再加起來。

你猜猜看:路線 A 3 公里,全塞車,時速 15。路線 B 5 公里,走高速公路,時速 60。哪條先到?

③ 這叫做 ETA

ETA(estimated time of arrival):預計抵達時間。每段距離 ÷ 那段的速度,全部加起來。

④ 跟這章的關係

原書的 ETA service 還用機器學習,猜 10–20 分鐘後的路況(下一頁)。

② 動手玩:點每一段,換它的路況

10 分ETA(三段加起來)

原書 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:百萬條導航裡,誰會被影響?

這一步要解決的問題路上出車禍:百萬條導航裡,怎麼快速找出受影響的人?

0比對次數0被篩成「受影響」0路線真的經過

📖 原書 目前的設計不支援自適應 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 pollingWebSocket 通常被認為比它好,因為 WebSocket 對 server 的負擔很輕
WebSocket傾向選它:支援雙向通訊;last-mile delivery 這類功能可能需要雙向即時通訊
SSE和 WebSocket 都可以用

ETA 與改道的更多細節見參考資料 [16]。

白話:push notification=手機跳出來的通知(10 章);long polling=一直問「有新的嗎」(12 章);WebSocket=一直開著的雙向電話線(12 章);SSE=server 單向一直推。

到這裡你已經會了小結 4 / 4

  1. 前幾章的基礎
  2. 經緯度
  3. geocoding
  4. map tile
  5. zoom level
  6. graph
  7. shortest path
  8. A*
  9. routing tile
  10. 分層 tiles
  11. batching
  12. 路況更新
  13. ETA

到這裡你已經會了:路況怎麼變成「還要幾分鐘」

13 階全部走完了

下一頁是原書的最終設計圖;最後看 Triton 在別的題目講過的原則,怎麼對照這章的數字。

原書 Step 3Final design · Figure 21

全部拼起來:最終設計

這一步要解決的問題全部元件拼起來,長什麼樣子?

📖 原書 Figure 21Final design(依原書內容重繪;alt 說使用者位置先送到 Geocoding Service,這裡依內文與 Figure 17:Navigation Service 呼叫 Geocoding Service;路況更新的方向依 Figure 17:Location DB → Update Traffic Service → Traffic DB)

📖 原書 每一塊都齊了,原書把它們合成 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

種拜訪順序

📖 原書 Chapter summary章末心智圖(依原書內容重繪;分支歸類照 alt,alt 把 map 101 放在 Step 2、navigation service 放在 Step 4,和正文順序不同)

補充 · 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 擋下來?

「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。

「到底這份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:正本要在別處

本章名詞小卡課後複習用 · 每個名詞一句白話

今天出現的名詞,一句話講完

DAU每天實際打開 app 的人數
QPS、尖峰每秒幾個 request;原書用平均 ×5 當尖峰
latitude / longitude緯度(往北幾度)/經度(往東幾度)
map projection把球面攤平的畫法,一定會變形;Google 用 Web Mercator
geocoding地址或地名 → 經緯度;反過來叫 reverse geocoding
interpolation知道兩端,按比例推中間(門牌)
geohash把世界一直切成小格,每格一個好算的編號
map tile地圖切成的一片固定大小的圖(256 × 256 像素)
zoom level放大到第幾層;每升一層片數 ×4,共 21 層
viewport手機畫面現在看到的範圍
CDN、POP開在各地的巷口小店/它的每一個據點
vector tile不傳圖片,傳「怎麼畫」,放大不會糊

給工程師的重點出處與標籤

引述來源與原書對照

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 章的延伸基礎頁。

← → 翻頁 · S 講者備註 · D 深/淺色
1 / 1目錄