System Design Interview Vol. 2 · 第 1 章Triton 覆蓋度:🟢 高(窄)Triton 線
Proximity Service
附近有什麼好吃的?
原書把五種空間索引講得很漂亮:二維搜尋、均勻網格、geohash、quadtree、Google S2。Triton 只談了這章的一小塊,但那一句很重:先算 N 和 m。1 萬個點,兩層 for-loop 不到一秒;真的大了,也是用 PostGIS、Elasticsearch 現成的 index,不要自己寫 quadtree。
給文組
全程只用「找 500 公尺內的珍奶店」,一階一階爬 10 個概念。頁首標 延伸基礎 的頁是補基礎,懂的人可以跳過。
給工程師
原書 21 張圖、12 個表全部重繪;最後一頁列出所有出處(materials/core)與頁碼對照。
標籤怎麼看
📖 原書 🗣️ Triton 本人說 🔭 依 Triton 原則推論 📅 2026 補充
先用生活理解為什麼需要「分格」
在台北找 500 公尺內的珍奶店
笨方法:把全台灣每一家店跟你的距離都量一次。聰明一點的方法:先看你在哪一區,只翻你這一格和隔壁 8 格的店。
這就像地址從大寫到小:台北市 → 大安區 → 某某里 → 某條路。同一個里的人一定住得近。等一下的 geohash 就是把「地址從大寫到小」變成一串字,例如 9q8yym:字頭一樣得越多,通常越近。
試試看:點地圖換你的位置,切換兩種找法。兩種找到的店一樣多,但要量距離的店差很多。
學習地圖本章的概念階梯
今天爬 10 階。每一階只用前面講過的東西。
- 1經緯度地球上的座標
- 2index照一種順序排的目錄
- 3read replica多印幾本給人查
- 42D search兩個條件取交集
- 5grid把地圖切成棋盤
- 6geohash地圖對折再對折
- 7鄰格住在格線旁的鄰居
- 8quadtree太擠就加隔板
- 9Hilbert curve一筆畫的蛇
- 10N 和 m先數有幾家
第 1–3 階 · 位置和電話簿
要回答:「附近」要怎麼用數字講?資料庫怎麼找得快?
第 4–7 階 · 把地圖切格子
要回答:兩個方向的條件,怎麼變成一個能查的字串?
第 8–9 階 · 會長大的格子
要回答:店擠在市中心,格子能不能跟著變細?
第 10 階 · Triton 的問題
要回答:你的店真的有 2 億家嗎?
全程只用一件事:你在台北,要找 500 公尺內的珍奶店
每爬 2–4 階,有一頁「到這裡你已經會了」。資料庫、cache、sharding 這些前面章節講過的,只用一句話帶過並附連結。
延伸基礎第 1 階 · 經緯度懂的人可以跳過
- 經緯度
- index
- read replica
- 2D search
- grid
- geohash
- 鄰格
- quadtree
- Hilbert curve
- N 和 m
兩個數字,就能說出你站在地球的哪裡
① 先想像
跟朋友約見面:「我在車站往北 2 條街、往東 3 條街。」兩個數字,就把位置講清楚了。
你猜猜看:台北 101 大約在「緯度 25.03、經度 121.56」。你往正北走一段路,哪個數字會變大?
緯度管南北,經度管東西。往正北走只有緯度變大,經度不動。右邊點地圖試試。
③ 這叫做 latitude、longitude
latitude(緯度):南北,赤道是 0、北極是 90。longitude(經度):東西,英國格林威治是 0,往東、往西各到 180。
④ 跟這章的關係
App 送給後端的就是這兩個數字(原書 Table 1)。「附近」就是兩個數字都差不多。
② 動手玩:點地圖,放下你自己
原書開場Figure 1
Proximity service:找附近的餐廳、加油站
這一步要解決的問題這個服務到底要做什麼?先看一個大家都用過的畫面。
📖 原書 Proximity service(鄰近服務)用來發現附近的地點:餐廳、旅館、劇院、博物館。它是 Yelp「找附近最好的餐廳」、Google Maps「找最近的 k 個加油站」背後的核心元件。
原書 Figure 1 是 Yelp 的搜尋畫面:上方搜尋列(tacos, cheap dinner, Max's、地點 1355 Market St, San Francisco, CA),左邊距離篩選(Bird's-eye View、Driving 5 mi、Biking 2 mi、Walking 1 mi、Within 4 blocks),中間三家店,右邊是標了編號的地圖。
原書註明:本章的地圖圖磚來自 Stamen Design,資料來自 OpenStreetMap。
原圖是產品截圖,這裡只重繪版面線框,不畫照片、商標與真實地圖。
原書 Step 1釐清需求
面試一開始:半徑多大、資料多久要生效?
這一步要解決的問題要找多遠?店家資料改了,多久要看到?問清楚,後面才知道哪裡可以簡單做。
📖 原書 應徵者 × 面試官
| 應徵者問 | 面試官答 |
|---|---|
| 使用者能指定搜尋半徑嗎?半徑內商家不夠,要自動擴大嗎? | 先只管指定半徑內的;有時間再談擴大搜尋 |
| 最大半徑多少?可以假設 20 km(12.5 英里)嗎? | 合理 |
| 使用者能在 UI 上改半徑嗎? | 可以:0.5 km、1 km、2 km、5 km、20 km |
| 商家資訊怎麼新增、刪除、更新?要即時反映嗎? | 商家業主可以增刪改;事先有商業協議:隔天才生效 |
| 使用者邊走邊用,結果會變,要一直刷新嗎? | 假設移動很慢,不用一直刷新 |
📖 原書 功能需求(3 個)
- 依使用者位置(緯度、經度)和半徑,回傳所有商家
- 商家業主可以新增、刪除、更新商家,但不需即時反映
- 顧客可以看商家的詳細資訊
📖 原書 非功能需求
- 低延遲:很快看到附近商家
- 資料隱私:位置是敏感資料,做 LBS 要遵守 GDPR、CCPA 等法規
- 高可用、可擴展:撐得住人口密集區尖峰時段的流量
白話:LBS(location-based service)=依你的位置提供的服務;GDPR、CCPA=歐盟、加州的個資法;低延遲=等待時間短。
原書 Step 1Back-of-the-envelope estimation
1 億日活、2 億商家:搜尋 QPS 是 5,000
這一步要解決的問題一天有多少次搜尋、總共有幾家店?這兩個數字後面會一直用到。
📖 原書 假設:100 million DAU、200 million businesses,每位使用者每天搜尋 5 次。
一天的秒數 = 24 × 60 × 60 = 86,400 ≈ 105
Search QPS = 100 million × 5 ÷ 105 = 5,000
原書說 105 在整本書都用來代表一天的秒數,方便心算。
白話:DAU=每天有幾個人用;QPS=每秒來幾個請求。估算那份有完整的延伸基礎:DAU(第 22 頁)、QPS(第 23 頁)。
文組翻譯
一天大約十萬秒。一億人每天搜五次,就是五億次,平均每秒五千次。這是「平均」,吃飯時間會更高,原書在非功能需求裡已經提醒尖峰。
動手算
5,000
QPS
另一個數字先記住:N = 200 million 家商家。到 Triton 那段(第 45 頁),N 和這個 QPS 會一起決定要不要用索引。
原書 Step 2API design · Table 1、2
兩組 API:搜尋附近、管理商家
這一步要解決的問題App 要怎麼跟後端說「我在這裡、找多遠」?
📖 原書 GET /v1/search/nearby:依搜尋條件回傳商家。實務上結果通常會分頁,原書說分頁不是本章重點,但面試值得提一下。
| Field | Description | Type |
|---|---|---|
latitude | 指定位置的緯度 | decimal |
longitude | 指定位置的經度 | decimal |
radius | 選填,預設 5000 公尺(約 3 英里) | int |
白話:API=App 和後端約好的窗口;decimal=有小數點的數字;int=整數;分頁=結果太多時一次只回一頁。
📖 原書 Response body:business object 只放搜尋結果頁需要的東西;點進詳細頁時,再呼叫另一個 endpoint 拿圖片、評論、星等。
{
"total": 10,
"businesses":[{business object}]
}
| API | Detail |
|---|---|
GET /v1/businesses/{:id} | 回傳某商家的詳細資訊 |
POST /v1/businesses | 新增一個商家 |
PUT /v1/businesses/{:id} | 更新商家的詳細資料 |
DELETE /v1/businesses/{:id} | 刪除一個商家 |
原書推薦參考真實世界的 Google Places API 和 Yelp Reservation API。
延伸基礎第 2 階 · index懂的人可以跳過
- 經緯度
- index
- read replica
- 2D search
- grid
- geohash
- 鄰格
- quadtree
- Hilbert curve
- N 和 m
電話簿照姓氏排:找「王」很快,找「住大安區」很慢
① 先想像
電話簿照姓氏排好。找姓王的,翻到中間、看要往前還是往後,幾下就到。可是要找「住大安區的人」呢?
你猜猜看:1,000 頁的電話簿照姓氏排好。每次翻一半、看要往前還是往後,大約翻幾次就找到?
每翻一次剩一半:1000 → 500 → 250 → … 大約 10 次剩 1 頁。照「住哪一區」找,就沒有這個好處,只能整本翻。
③ 這叫做 index
index(索引):事先照某個欄位排好的目錄,找東西不用整本翻。一個 index 只照一種順序排。
④ 跟這章的關係
店的位置是兩個欄位:緯度、經度。一個 index 只能照其中一個排,這就是原書接下來要解的難題。
② 動手玩:16 張名片,照姓氏排好
按上面兩個按鈕比較。
原書 Step 2Data model · Table 3
讀很多、寫很少:關聯式資料庫就很合適
這一步要解決的問題店家資料要存在哪種資料庫?要哪幾張表?
📖 原書 Read/write ratio
- 讀很多:「搜尋附近」和「看商家詳情」這兩個功能非常常用
- 寫很少:新增、刪除、編輯商家是不常發生的操作
- 讀為主的系統,MySQL 這類關聯式資料庫很合適
📖 原書 兩張主要的表
business table:商家的詳細資訊,主鍵是 business_id(右圖)。
geospatial (geo) index table:用來有效率地處理空間查詢。要先懂 geohash,原書放到 deep dive 的「Scale the database」再講(第 35 頁)。
文組翻譯:這像一本電話簿。全台灣每天有很多人查,但一年只改版幾次。這種東西,最普通的資料庫就做得很好。
白話:關聯式資料庫(RDBMS)=一張張像 Excel 的表;PK(primary key)=每一列獨一無二的編號;index 見上一頁。資料庫是什麼:Vol.1 第 1 章第 8 頁。
| business | |
|---|---|
business_id | PK |
address | |
city | |
state | |
country | |
latitude | |
longitude | |
注意:latitude、longitude 是兩個欄位。下一頁會看到,光在這兩個欄位上各建一個 index,查「附近」還是不夠快。
延伸基礎第 3 階 · read replica懂的人可以跳過
- 經緯度
- index
- read replica
- 2D search
- grid
- geohash
- 鄰格
- quadtree
- Hilbert curve
- N 和 m
名冊一年改幾次,每天卻有上萬人來查:多印幾本
① 先想像
全台珍奶店名冊只有一本,櫃台前大排長龍。反正一年才改版幾次,那就多影印幾本,放在各個櫃台給人查。
你猜猜看:一本名冊每秒能應付 1,000 次查詢。每秒來 5,000 次,至少要幾本?
5,000 ÷ 1,000 = 5。1 本正本 + 4 本影本。右邊拉滑桿驗證。
③ 這叫做 primary、read replica
primary:正本,只有它能改。read replica:影本,只給人查;從正本抄過去,會晚一點才跟上。
④ 跟這章的關係
原書:讀很多、寫很少,商家資料又是「隔天才生效」。影本晚一點跟上,完全沒關係。
② 動手玩:每秒來多少人查?
原書 Step 2High-level design · Figure 2
兩個服務:找附近(LBS)和管商家(Business service)
這一步要解決的問題搜尋和管理商家要分成幾個服務?讀和寫各走哪條路?
📖 原書 Load balancer:通常公司只給一個 DNS 入口,內部依 URL path 把 API 導到對的服務。
📖 原書 LBS(location-based service)是核心:給位置和半徑找附近商家。特性:只讀不寫;QPS 高,密集區尖峰更高;stateless,容易水平擴展。
📖 原書 Business service:業主增刪改(寫為主,QPS 不高)+顧客看詳情(尖峰 QPS 高)。
📖 原書 Database cluster:primary-secondary。primary 處理所有寫入,多個 replica 處理讀取。有 replication delay,所以 LBS 讀到的可能和剛寫進 primary 的不一樣,但商家資訊本來就不用即時,通常不是問題。
📖 原書 擴展:兩個服務都 stateless,用餐時間自動加機器、睡覺時間減機器;在雲端還能用多個 region 和 availability zone 提高可用性(第 39 頁)。
白話:DNS=網址的電話簿;load balancer=帶位員(Vol.1 第 1 章第 12 頁);stateless=機器不記客人的事,壞了換一台就好(第 24 頁);primary、replica 見第 11 頁。
到這裡你已經會了小結 1 / 4
- 經緯度
- index
- read replica
- 2D search
- grid
- geohash
- 鄰格
- quadtree
- Hilbert curve
- N 和 m
到這裡你已經會了:位置、目錄、多印幾本
- 位置就是兩個數字:緯度(南北)和經度(東西)。「附近」= 兩個數字都差不多。
- index 是照一種順序排好的目錄:照那個欄位找很快,換一個欄位就要整本翻。
- 讀很多、寫很少:正本(primary)負責改,多印幾本 read replica 分擔查詢。
下一階要解決的問題
「緯度差不多」而且「經度差不多」,兩個條件一起查,index 能幫多少?先看最直覺的做法。
延伸基礎第 4 階 · 2D search懂的人可以跳過
- 經緯度
- index
- read replica
- 2D search
- grid
- geohash
- 鄰格
- quadtree
- Hilbert curve
- N 和 m
「南北差不多」而且「東西差不多」:兩疊名單取交集
① 先想像
店要在你南北 500 公尺內,也要在你東西 500 公尺內。地圖上是一條橫帶和一條直帶,交叉的那一小塊才是答案。
你猜猜看:城裡 100 家店。南北符合的有 20 家,東西符合的有 20 家。兩個都符合的大概幾家?
店平均散開時,20% × 20% = 4%,也就是 4 家左右。要先撈出兩疊各 20 家,再一家一家比對。
③ 這叫做 2D search
2D search(二維搜尋):同時用兩個方向的條件找東西。index 只能先幫你撈出其中一疊。
④ 跟這章的關係
這就是原書 Option 1。城市一大,兩疊都很厚,交集卻很薄(下一頁)。
② 動手玩:100 家店,一條橫帶、一條直帶
原書 Step 2Algorithms · Option 1:Two-dimensional search · Figure 3、4
最直覺的做法:畫一個圓,找圓裡的店
這一步要解決的問題最直覺的「畫個圓找店」,資料庫做得快嗎?
📖 原書 現實中公司可能直接用現成的地理空間資料庫,例如 Redis 的 Geohash 或 Postgres + PostGIS。面試不用懂它們的內部,但解釋 geospatial index 怎麼運作,比只丟出資料庫名字更能展現能力。
SELECT business_id, latitude, longitude,
FROM business
WHERE (latitude BETWEEN {:my_lat} - radius AND {:my_lat} + radius) AND
(longitude BETWEEN {:my_long} - radius AND {:my_long} + radius)
📖 原書 這個 query 要掃整張表。在經度、緯度上各建 index 呢?原書說「提升不多」:index 能很快拿到 dataset 1(緯度帶)和 dataset 2(經度帶),但要找半徑內的店得把兩個 dataset 取交集,而每個 dataset 都很大。
問題的根源:資料庫 index 一次只能加速一個維度。那能不能把二維資料映射成一維?原書:可以。
白話:query=問資料庫的一句話(這裡是 SQL);PostGIS=PostgreSQL 的地理套件;dataset=撈出來的一疊資料;維度=方向(南北是一個、東西是一個)。
延伸基礎第 5 階 · grid懂的人可以跳過
- 經緯度
- index
- read replica
- 2D search
- grid
- geohash
- 鄰格
- quadtree
- Hilbert curve
- N 和 m
把地圖畫成棋盤:每家店登記在它那一格
① 先想像
把台北地圖畫上棋盤格,每家店記下自己在第幾格。找附近的店,只翻你那一格的名單。
你猜猜看:64 家店,地圖切成 4 × 4 = 16 格。如果店平均分布,一格幾家?
64 ÷ 16 = 4。可是真實城市的店都擠在市中心,右邊看看最擠的那一格有幾家。
③ 這叫做 grid
grid(網格):把地圖切成一樣大的方格。每家店只屬於一格,一格可以有很多家。
④ 跟這章的關係
原書 Option 2「evenly divided grid」。問題就是右邊看到的:市中心塞爆,郊區一格空著。
② 動手玩:64 家店擠在市中心
原書 Step 2索引分類 · Option 2:Evenly divided grid · Figure 5、6
兩大類索引;最簡單的一種:把世界切成一樣大的格子
這一步要解決的問題不畫圓,改成先把地圖切成格子呢?
📖 原書 Hash:even grid、geohash、cartesian tiers;Tree:quadtree、Google S2、R-tree。底層不同,高階概念一樣:把地圖切成小區域,建 index 加速搜尋。業界最常用的是 geohash、quadtree、S2。
📖 原書的 Reminder
真實面試通常不用解釋 index 的實作細節,但要懂:為什麼需要 geospatial index、高階怎麼運作、它的限制。
📖 原書 一格可以有很多商家,每家商家屬於一格。問題:商家分布不均,紐約市中心一格塞爆,沙漠和海洋的格子一家都沒有。理想是密集處用細格、稀疏處用大格。另一個挑戰:找某一格的鄰格不容易。
延伸基礎 · 動手玩第 6 階 · geohash懂的人可以跳過
- 經緯度
- index
- read replica
- 2D search
- grid
- geohash
- 鄰格
- quadtree
- Hilbert curve
- N 和 m
把地圖對折再對折:每折一次,記下 0 或 1
① 先想像
拿一張地圖,左右對折:你在右半記 1、左半記 0。再上下對折:上半 1、下半 0。一直輪流折下去。
你猜猜看:左右、上下輪流,一共折 6 次。地圖被切成幾格?
每折一次格數 × 2:2、4、8、16、32、64。6 個 0/1 就能指出 64 格裡的那一格。
③ 這叫做 geohash
geohash:把對折的 0/1 答案寫成一串字。每 5 個 0/1 換成一個字(base32),例如 9q8yym。
④ 跟這章的關係
兩個數字變成一串字。字頭一樣 = 同一格,一般的 index 就能照字頭查。原書接著照這規則切整個地球。
② 動手玩:對折找出你和珍奶店的位置碼
點地圖可以把「你」換個位置。
原書 Step 2Option 3:Geohash · Figure 7、8
Geohash:每多一個 bit,格子就切一半
這一步要解決的問題怎麼把「兩個數字」變成「一串字」,讓一般 index 能查?
📖 原書 Geohash 把二維的經緯度壓成一維的字串(字母加數字),做法是遞迴地把世界切成越來越小的格子。
- 沿本初子午線和赤道切成四塊:緯度 [-90, 0] → 0、[0, 90] → 1;經度 [-180, 0] → 0、[0, 180] → 1
- 每格再切四格,經度 bit 和緯度 bit 交替
- 重複到格子夠小;通常用 base32 表示
📖 原書 兩個例子(長度 6)
Google 總部
1001 10110 01001 10000 11011 11010 → 9q9hvu
Facebook 總部
1001 10110 01001 10001 10000 10111 → 9q9jhr
兩家都在灣區,前 3 個字 9q9 一樣。原書第一組只寫 4 個 bit,是省略了開頭的 0(01001 = 9)。
白話:bit=一個 0 或 1(第 18 頁的「對折一次」);本初子午線=經度 0 那條線;赤道=緯度 0。
原書 Step 2Geohash 精度 · Table 4、5
長度選幾?選「剛好蓋得住你的圓」的最短長度
這一步要解決的問題geohash 要取幾個字,格子才剛好蓋住你要找的範圍?
| Geohash length | Grid width × height |
|---|---|
| 1 | 5,009.4km × 4,992.6km(the size of the planet) |
| 2 | 1,252.3km × 624.1km |
| 3 | 156.5km × 156km |
| 4 | 39.1km × 19.5km |
| 5 | 4.9km × 4.9km |
| 6 | 1.2km × 609.4m |
| 7 | 152.9m × 152.4m |
| 8 | 38.2m × 19m |
| 9 | 4.8m × 4.8m |
| 10 | 1.2m × 59.5cm |
| 11 | 14.9cm × 14.9cm |
| 12 | 3.7cm × 1.9cm |
📖 原書 Geohash 有 12 個精度(level)。我們只在意長度 4 到 6:超過 6 格子太小,小於 4 格子太大。挑法是「蓋得住使用者半徑那個圓的最短長度」。點一列看圓和格子的比例:
| Radius | Geohash length |
|---|---|
| 0.5 km (0.31 mile) | 6 |
| 1 km (0.62 mile) | 5 |
| 2 km (1.24 mile) | 5 |
| 5 km (3.1 mile) | 4 |
| 20 km (12.42 mile) | 4 |
延伸基礎第 7 階 · 鄰格懂的人可以跳過
- 經緯度
- index
- read replica
- 2D search
- grid
- geohash
- 鄰格
- quadtree
- Hilbert curve
- N 和 m
你住在格線旁邊:對面那家店在隔壁格
① 先想像
你家在大安區最邊邊,過一條馬路就是信義區。對面的珍奶店離你 50 公尺,可是「只查大安區」找不到它。
你猜猜看:一格寬 1 公里。你站在格子最右邊,要找 500 公尺內的店。只查自己這一格,會漏掉嗎?
500 公尺的圓有一半伸進右邊那格。右邊滑桿把「你」拉到最右邊,看看紅點。
③ 這叫做 neighbor、boundary issue
neighbor(鄰格):四周的 8 格。boundary issue(邊界問題):很近的兩點,剛好被格線分開。
④ 跟這章的關係
原書的解法:自己這格 + 8 個鄰格一起查。geohash 算出鄰格只要一瞬間。
② 動手玩:一格 1 公里,找 500 公尺內
動手玩Geohash 地圖:放下你自己,看格子、鄰格和邊界問題
點地圖放下你的位置,看看會漏掉哪些店
這一步要解決的問題只查自己這一格夠不夠?親手放下自己試試。
原書 Step 2Boundary issues · Figure 9、10、11
前綴越長越近;但近的不一定前綴一樣
這一步要解決的問題字頭一樣就一定近;那近的店,字頭一定一樣嗎?
📖 原書 Geohash 保證:兩個 geohash 共享的前綴越長,距離越近(Figure 9 九格都以 9q8zn 開頭)。
📖 原書 Boundary issue 1:反過來不成立。赤道或本初子午線兩側的點屬於世界的不同「半邊」。法國的 La Roche-Chalais(u000)離 Pomerol(ezzz)只有 30 km,前綴卻完全不同。所以這個 query 會漏:
SELECT * FROM geohash_index WHERE geohash LIKE `9q8zn%`
📖 原書 Boundary issue 2:兩個點可能前綴很長,卻屬於不同 geohash(Figure 11)。
📖 原書 常見解法:不只撈自己這格,連鄰格一起撈。鄰格的 geohash 可以在常數時間算出來。上一頁的地圖可以親手試(第 22 頁)。
原書 Step 2Not enough businesses · Figure 12
加分題:附近的店不夠多,怎麼辦?
這一步要解決的問題附近的店太少,怎麼自動把範圍放大?
📖 原書 Option 1:只回傳半徑內的
好做,缺點很明顯:回傳的結果不夠,滿足不了使用者。
📖 原書 Option 2:擴大搜尋半徑
把 geohash 的最後一個字拿掉,用新的(比較短的)geohash 撈附近商家。還不夠就再拿掉一個。格子逐步變大,直到結果比需要的數量多。
用原書的座標算一次
每拿掉一個字,格子面積大約變成 32 倍(base32 一個字 = 5 bit)。
這一招 Triton 的講義裡也有,而且一模一樣:「否則用 i-1 byte 的 geohash 從來~」(第 46 頁)。
到這裡你已經會了小結 2 / 4
- 經緯度
- index
- read replica
- 2D search
- grid
- geohash
- 鄰格
- quadtree
- Hilbert curve
- N 和 m
到這裡你已經會了:把地圖切成能查的格子
- 兩個條件分開查(2D search)會撈出兩大疊再取交集;一樣大的格子(grid)又會市中心塞爆。
- geohash 是把地圖對折再對折的 0/1 答案:字頭一樣 = 同一格,一般 index 就查得到。長度 4–6 依半徑選。
- 格線會把近的店切開,所以要查自己 + 8 個鄰格;店不夠就拿掉最後一碼,格子變大。
下一階要解決的問題
geohash 的格子大小是固定的。能不能讓市中心格子細、郊區格子大?
延伸基礎第 8 階 · quadtree懂的人可以跳過
- 經緯度
- index
- read replica
- 2D search
- grid
- geohash
- 鄰格
- quadtree
- Hilbert curve
- N 和 m
收納盒一格塞太滿,就加一個十字隔板
① 先想像
收納盒一格最多放 4 樣東西。放第 5 樣時,在那格加十字隔板變成 4 小格。東西多的地方隔得很細,空的地方還是一大格。
你猜猜看:一格最多 100 家,全世界 2 億家店。最小的格子大約有幾個?
2 億 ÷ 100 = 200 萬。原書就是用這個數字算 quadtree 要多少記憶體(第 29 頁)。
③ 這叫做 quadtree、leaf
quadtree(四分樹):太擠就切四塊、一路往下切的目錄。leaf(葉子):最小、沒再切的那一格。
④ 跟這章的關係
原書 Option 4。格子大小跟著店的密度變;代價是要在記憶體裡先把這棵樹建好。
② 動手玩:一格最多 4 家
原書 Step 2Option 4:Quadtree · Figure 13、14
Quadtree:一格超過 100 家就切成四格
這一步要解決的問題格子能不能跟著店的多寡,自己變細?
📖 原書 Quadtree 把二維空間遞迴切成四個象限,直到格子內容符合某個條件,例如「一格不超過 100 家」。100 是任意的,依業務需求決定。
📖 原書 重點:quadtree 是記憶體裡的資料結構,不是資料庫。它跑在每一台 LBS 上,server 啟動時建好。根節點是整張世界地圖,假設世界上有 2 億家商家。
public void buildQuadtree(TreeNode node) {
if (countNumberOfBusinessesInCurrentGrid(node) > 100) {
node.subdivide();
for (TreeNode child : node.getChildren()) {
buildQuadtree(child);
}
}
}
下一頁可以自己加點、看它怎麼切。
白話:記憶體(memory)=電腦手邊的工作桌,快,但關機就清空;資料庫存在硬碟上。TreeNode=樹上的一格;subdivide=切成四格。
動手玩Quadtree 自己長出來
點一下加一家店:格子太擠就自動切四塊
這一步要解決的問題照原書 buildQuadtree 的規則,親手看樹怎麼長。
原書上限是 100,這裡用 4 才看得出來。市中心格子細、郊區格子大,這就是原書說的「依人口密度動態調整格子大小」。
注意「內部節點 = (葉節點 − 1) ÷ 3」永遠成立:每切一次,葉子少 1 多 4(淨 +3),內部節點 +1。所以原書說內部節點大約是葉節點的 1/3(下一頁)。
原書 Step 2Quadtree 的記憶體與建樹時間 · Table 6、7
2 億家店的 quadtree,只要大約 1.71 GB
這一步要解決的問題這棵樹要佔多少記憶體?一台機器放得下嗎?
| Name | Size |
|---|---|
| 左上、右下座標(識別格子) | 32 bytes(8 bytes × 4) |
| 格子內的 business ID 清單 | 8 bytes per ID × 100(一格最多 100 家) |
| Total | 832 bytes |
| Name | Size |
|---|---|
| 左上、右下座標(識別格子) | 32 bytes(8 bytes × 4) |
| 指向 4 個子節點的指標 | 32 bytes(8 bytes × 4) |
| Total | 64 bytes |
📖 原書 建樹依格子內的商家數,但這個數字不用存在節點裡,可以從資料庫的紀錄推出來。
動手算(預設就是原書的數字)
📖 原書 面試不用算這麼細,重點是:quadtree index 不太佔記憶體,一台 server 就放得下。但不代表只用一台:依讀取量,一台的 CPU 或網路頻寬可能不夠,就要把讀取分到多台 quadtree server。
📖 原書 建樹時間:O((N/100) lg(N/100)),2 億家要幾分鐘。查詢:從 root 往下走到起點所在的葉節點;那格有 100 家就回傳,否則從鄰格補,補到夠為止。
原書 Step 2Operational considerations · Real-world example · Figure 15
Quadtree 上線之後的麻煩:啟動要幾分鐘、更新要上鎖
這一步要解決的問題樹放在每台 LBS 的記憶體裡,上線後會遇到什麼麻煩?
📖 原書 啟動時間
- 2 億家的 quadtree 在 server 啟動時要建幾分鐘,建樹期間不能接流量
- 新版本要一次只部署一小批 server,避免一大塊 cluster 同時下線造成 brownout(服務沒全掛,但變慢、部分失效)
- 也可以用 blue/green deployment(新舊兩組機器並行、一次切過去),但整批新 server 同時從資料庫抓 2 億筆,會對系統造成很大壓力;做得到,但設計變複雜,面試要提
📖 原書 商家增減時怎麼更新
- 最簡單:分批逐步重建整個 cluster 的 quadtree;部分 server 短時間回傳舊資料,依需求通常可接受
- 再加上「隔天生效」的商業協議,可以用夜間 job 更新 cache;潛在問題是大量 key 同時失效,cache server 負載很重
- 也可以即時更新,但多執行緒存取要上鎖,實作會大幅變複雜
📖 原書 密集區要小而細的格子,稀疏區用大格子。丹佛、Aurora 一帶格子細,往東的 Watkins、Strasburg、Byers 格子很大。
延伸基礎第 9 階 · Hilbert curve懂的人可以跳過
- 經緯度
- index
- read replica
- 2D search
- grid
- geohash
- 鄰格
- quadtree
- Hilbert curve
- N 和 m
一條蛇一筆畫走完棋盤:編號近,位置就近
① 先想像
要把 4 × 4 的棋盤排成一列編號。最直覺是像讀書:一行讀完換下一行。另一種是讓一條蛇一筆畫走完 16 格,不跳格。
你猜猜看:像讀書一樣編號,第一行 0–3、第二行 4–7。3 號和 4 號在棋盤上挨在一起嗎?
3 號在第一行最右邊,4 號在第二行最左邊。編號只差 1,位置卻差很遠。蛇的走法就不會這樣。
③ 這叫做 Hilbert curve
space-filling curve:走遍每一格、一筆畫完的曲線。Hilbert curve 是其中一種:編號相近,位置通常也相近。
④ 跟這章的關係
Google S2 用它把地球上的格子排成一條線,再用一般的一維 index 查(原書 Option 5)。
② 動手玩:兩種編號法,點一格看鄰居
點任一格:編號前後 2 號的格子會亮起來。
原書 Step 2Option 5:Google S2 · Figure 16、17
Google S2:用 Hilbert 曲線把球面攤成一條線
這一步要解決的問題能不能把整個球面,直接排成一條線來查?
點地圖移動使用者,看他在圍欄內還是外。
📖 原書 S2 和 quadtree 一樣是記憶體內的方案。它依 Hilbert curve(一種 space-filling curve)把球面映射成一維 index。重要特性:曲線上相近的兩點,在一維空間也相近;一維搜尋比二維有效率得多。
📖 原書 S2 很複雜,面試不用解釋內部;但 Google、Tinder 都在用,所以介紹兩個優點:
- Geofencing:能用不同層級的格子蓋住任意區域。維基百科:geofence 是真實地理區域的虛擬邊界,可以動態產生(某點周圍的半徑),也可以是預先定義的邊界(學區、社區)。可以對離開區域的使用者發通知,比單純回傳附近商家功能更豐富
- Region Cover 演算法:不像 geohash 固定一個精度,S2 可以指定 min level、max level、max cells,格子大小有彈性,結果更細緻
原書 Step 2Recommendation · Table 8 · Geohash vs quadtree
誰用哪一種?面試建議 geohash 或 quadtree
這一步要解決的問題這麼多種 index,面試該選哪一個?
| Geo Index | Companies |
|---|---|
| Geohash | Bing map、Redis、MongoDB、Lyft |
| Quadtree | Yext |
| Both Geohash and Quadtree | Elasticsearch |
| S2 | Google Maps、Tinder |
📖 原書 面試建議選 geohash 或 quadtree,因為 S2 很難在面試裡講清楚。
📅 2026 補充 Elasticsearch 新版的 geo_point 用 BKD tree 建索引,查詢用 geo_distance;Redis 的 GEO 指令(GEOADD、GEOSEARCH)底層是把 52-bit geohash 當 sorted set 的 score。原書沒提的 Uber H3 用六角形格子,也很常見。
📖 原書 Geohash
- ✓ 好用好實作,不用建樹
- ✓ 支援「指定半徑內」的查詢
- ✗ 精度固定,格子大小就固定,不能依人口密度調整,要更複雜的邏輯
- ✓ 更新 index 很簡單:刪掉那一列(geohash, business_id)就好(Figure 18)
📖 原書 Quadtree
- ✗ 稍難實作,要建樹
- ✓ 支援 k-nearest:車快沒油,只要最近的 k 個加油站,不管多遠;切格子依 k 走,會自動調整範圍到湊滿 k 個
- ✓ 能依人口密度調整格子(Figure 15)
- ✗ 更新比較複雜:從 root 走到 leaf,O(log n);多執行緒要上鎖;重新平衡也複雜(葉子滿了),可能的解法是 over-allocate ranges(Figure 19)
原書 Step 2更新 index · Figure 18、19
刪一家店:geohash 刪一列,quadtree 要從根走到葉
這一步要解決的問題商家新增、刪除時,兩種 index 各要做多少事?
DELETE FROM geospatial_index WHERE geohash = '9q8zn' AND business_id = 8;
SQL 是依原書文字寫的示意:「從對應 geohash 與 business_id 的列刪除即可」。
白話:root=樹的最上層(整張地圖);O(log n)=資料變 2 倍,只多走一層;上鎖=改的時候不讓別人同時改(Vol.1 第 1 章第 44 頁)。
原書 Step 3Scale the database · Table 9、10、11
geo index 表怎麼存:一格一列,還是一店一列?
這一步要解決的問題資料變多時,兩張表各怎麼存、怎麼擴展?
📖 原書 Business table:資料可能放不進一台,適合 shard。最簡單是依 business ID shard:負載平均、維運簡單。
📖 原書 Geospatial index table:geohash 和 quadtree 都很常用,因為 geohash 簡單,以它為例。兩種存法:
白話:shard=把一個大資料庫依規則切成幾台(Vol.1 第 1 章第 34 頁);JSON array=一格裡塞一整串 ID;compound key=兩個欄位合起來當主鍵。
| geospatial_index |
|---|
geohash |
list_of_business_ids |
| geospatial_index |
|---|
geohash |
business_id |
| geohash | business_id |
|---|---|
| 32feac | 343 |
| 32feac | 347 |
| f3lcad | 112 |
| f3lcad | 113 |
📖 原書 推薦 Option 2
- Option 1 要更新一家店:先拿整個 array、掃過一遍找到它;新增時也要掃整個 array 確認沒重複;還要鎖住那一列防止同時更新,邊界情況很多
- Option 2 用
(geohash, business_id)當 compound key,新增和刪除都很簡單,什麼都不用鎖
原書 Table 11 的 f3lcad 含字母 l,嚴格說 geohash 的 base32 不用 a、i、l、o,這裡照原書保留。
原書 Step 3Scale the geospatial index
原書自己說:先別急著 shard,加 read replica 就好
這一步要解決的問題讀取量太大時,該多印幾本影本,還是把資料切開?
📖 原書 常見錯誤:沒看實際資料量就跳到 sharding。這裡 geo index 的完整資料不大(quadtree 只要 1.71 GB,geohash index 的儲存需求差不多),整個放得進一台現代資料庫的 working set。
📖 原書 但依讀取量,一台的 CPU 或網路頻寬可能不夠,就要分散讀取負載。兩種方法:加 read replica,或 shard。
📖 原書 很多工程師面試愛講 sharding,但 shard geohash 表很複雜,例如 sharding 邏輯要寫進應用層。有時 shard 是唯一選擇;但這裡全部放得進 working set,沒有強烈的技術理由 shard。所以推薦用 一系列 read replica,開發、維護都簡單得多。
這頁原書和 Triton 是同一國的。Triton 的版本更直接:「如果是小型系統,單純 scale up 便算了」(第 49 頁)。
原書 Step 3Caching · Cache key
要不要 cache?先問自己;要的話,key 用 geohash
這一步要解決的問題要不要加 cache?要的話,用什麼當 key?
📖 原書 先問:真的需要 cache 嗎?
- 讀為主、資料集相對小,放得進任何一台現代資料庫的 working set,query 不是 I/O bound,應該跑得幾乎和記憶體 cache 一樣快
- 讀取真的是瓶頸,可以加 read replica 提高讀取吞吐量
- 跟面試官談 cache 要小心:要仔細做 benchmark 和成本分析;確認 cache 符合業務需求,才談 cache 策略
📖 原書 Cache key:經緯度不是好 key
- 手機回報的座標不準,只是最佳估計;不動,每次拿到的也略有不同
- 使用者會移動,座標跟著小幅變化,對多數 App 沒有意義
- 理想:位置小幅變動仍對應同一個 key。geohash/quadtree 剛好做到:同一格的商家都對應同一個 geohash
動手試:手機一直回報不太一樣的座標
白話:cache=手邊的小抄,正本在資料庫(Vol.1 第 1 章第 18 頁);key=查小抄用的標籤;working set=常用的資料整個放得進記憶體;I/O bound=慢在讀硬碟;benchmark=實際量測。
| 回報的座標 | key = lat,lon | key = geohash6 |
|---|
原書 Step 3Types of data to cache · Table 12
兩種 cache:「這格有哪些店」和「這家店長怎樣」
這一步要解決的問題cache 裡要放哪兩種東西?要多少記憶體?
| Key | Value |
|---|---|
| geohash | List of business IDs in the grid |
| business_id | Business object |
📖 原書 商家資料相對穩定,預先算好每個 geohash 的 business ID 清單,放進 Redis 這類 key-value store。先用 SQL 拿清單,cache miss 才寫進 Redis:
SELECT business_id FROM geohash_index WHERE geohash LIKE `{:geohash}%`
public List<String> getNearbyBusinessIds(String geohash) {
String cacheKey = hash(geohash);
List<string> listOfBusinessIds = Redis.get(cacheKey);
if (listOfBusinessIDs == null) {
listOfBusinessIds = Run the select SQL query above;
Cache.set(cacheKey, listOfBusinessIds, "1d");
}
return listOfBusinessIds;
}
📖 原書 商家新增、編輯、刪除時,更新資料庫並讓 cache 失效。這類操作量小,geohash 做法又不用上鎖,所以好處理。
📖 原書 使用者可選 500 m、1 km、2 km、5 km 四種半徑,原書寫「分別對應 geohash 長度 4、5、5、6」,所以在 Redis 快取三種精度:geohash_4、geohash_5、geohash_6。
⚠ 原書前後不一 依 Table 5,500 m → 6、5 km → 4,順序剛好反過來;這裡兩處都照原書列出,以 Table 5 為準。
📖 原書 記憶體
values:8 bytes × 200 million × 3 precisions ≈ 5 GB
keys:可忽略
總共 ≈ 5 GB
一台現代 Redis 就夠,但為了高可用、降低跨洲延遲,把 Redis cluster 部署到全球,每地放同一份 cache。最終架構裡叫它 “Geohash”。
白話:key-value store=用標籤直接拿值的倉庫;TTL=小抄多久過期,"1d" 是一天(Vol.1 第 8 章第 39 頁)。
📖 原書 第二種:key = business_id、value = 商家物件(名稱、地址、圖片 URL 等),很直接,叫 “Business info”。
原書 Step 3Region and availability zones · Figure 20 · Follow-up:篩選
把 LBS 放到離使用者近的地方
這一步要解決的問題全世界的使用者,怎麼讓每個人都連得快、又符合當地法規?
📖 原書 把 LBS 部署到多個 region 和 availability zone,好處:
- 使用者在物理上更近:美西連美西的資料中心,歐洲連歐洲的
- 依人口分散流量:日本、韓國人口密度高,可以獨立成 region,甚至在多個 AZ 部署 LBS 分散負載
- 隱私法規:有些國家要求使用者資料在當地使用與儲存,就在那國設 region,用 DNS routing 把該國請求限制在那個 region
白話:region=一個地區的機房群;AZ(availability zone)=同一地區裡互相獨立的機房;DNS routing=依你在哪裡,把網址指到不同機房;hydrate=拿 ID 換回完整資料。多機房的基礎:Vol.1 第 1 章第 28 頁。
📖 原書 Follow-up:只要「現在有營業」或「只要餐廳」
應徵者:用 geohash 或 quadtree 把世界切成小格後,搜尋結果的商家數相對少。所以可以先拿 business ID,hydrate 成商家物件,再依營業時間或類型過濾。前提是營業時間和類型存在 business table 裡。
原書 Step 3Final design diagram · Figure 21
最終設計:找 500 公尺內的餐廳,一步一步走
這一步要解決的問題把前面全部串起來:一個搜尋從頭到尾怎麼走?
📖 原書 Get nearby businesses
- 在 Yelp 找 500 m 內的餐廳。client 送位置(latitude = 37.776720、longitude = -122.416730)和半徑 500 m 給 load balancer
- Load balancer 把 request 轉給 LBS
- LBS 依位置和半徑找對應的 geohash 長度:查 Table 5,500 m → 長度 6
- LBS 算出鄰格加進清單:
list_of_geohashes = [my_geohash, neighbor1_geohash, …, neighbor8_geohash] - 對清單裡每個 geohash 呼叫 “Geohash” Redis 拿 business IDs,可以並行以降低延遲
- 用 ID 清單到 “Business info” Redis 拿完整商家資料,算距離、排序、回傳給 client
📖 原書 看、改、增、刪商家:這些 API 和 LBS 分開。看詳情時 business service 先查 “Business info” cache,有就回傳;沒有就從資料庫 cluster 拿,再存進 cache。因為「隔天生效」,cache 由夜間 job 更新。
原書 Step 4Wrap up · Chapter summary
原書的收尾:一個典型的 LBS,靠 geospatial index
這一步要解決的問題原書最後怎麼收尾?哪些是這章的骨架?
📖 原書 討論過的索引:二維搜尋、均勻網格、geohash、quadtree、Google S2。geohash、quadtree、S2 都被不同科技公司廣泛使用,原書選 geohash 當例子示範 geospatial index 怎麼運作。
📖 原書 Deep dive 談了:為什麼 cache 能降低延遲、該 cache 什麼、怎麼用 cache 快速拿附近商家;怎麼用 replication 和 sharding 擴展資料庫。
📖 原書 最後把 LBS 部署到不同 region 和 AZ:提高可用性、讓使用者物理上更近、更符合當地隱私法規。
原書最後一句:恭喜你看到這裡,給自己一個讚。
到這裡你已經會了小結 3 / 4
- 經緯度
- index
- read replica
- 2D search
- grid
- geohash
- 鄰格
- quadtree
- Hilbert curve
- N 和 m
到這裡你已經會了:原書的整套設計
- quadtree 讓格子跟著密度變細,適合「最近的 k 家」;但要在每台 LBS 的記憶體裡建樹,啟動要幾分鐘、更新要上鎖。
- Hilbert curve 把格子排成一條線,編號近 ≈ 位置近;Google S2 用它,面試難講清楚。
- 原書的最終設計:geohash 算 9 格 → Redis 拿 business ID → 拿店家資料、算距離。資料庫用 read replica,不急著 shard。
下一階要解決的問題
原書一開始就假設有 2 億家店。如果你的系統只有 1 萬家呢?還需要這整套嗎?
延伸基礎第 10 階 · N 和 m懂的人可以跳過
- 經緯度
- index
- read replica
- 2D search
- grid
- geohash
- 鄰格
- quadtree
- Hilbert curve
- N 和 m
巷口只有 6 家飲料店,你會打開地圖 App 嗎?
① 先想像
巷口 6 家飲料店,走出去一家一家看就好。全台灣 2 萬家,才需要地圖 App。先數有幾家,再決定要不要買地圖。
你猜猜看:1 萬家店、每秒 50 人查詢,每人都把 1 萬家量一遍。每秒要量幾次距離?
1 萬 × 50 = 50 萬。電腦一秒大約做得了 1 億次這種小計算(示意),只用掉 0.5%。
③ 這叫做 N、m、brute force
N:有幾家店(資料多大)。m:每秒查幾次。brute force(暴力解):不用技巧,一家一家量。
④ 跟這章的關係
Triton:先算 N × m,再決定要不要建 geohash、quadtree。N 小,兩層 for-loop 就夠。
② 動手玩:三種規模,暴力解要量幾次?
Triton 怎麼看先知道 N
「Bruteforce algorithm(暴力解法)也是算法的一種啊!」
背景:有人在 Python 版發問「我有 10000 個點,我想找出每一個點的最近鄰居」,一堆人回答 R-tree、Quadtree……
「如果才 10000 個點,單純 2 層 for-loop,O(n^2) solution 吧。現實跑起來應該少於1秒。如果 n > 1M 則肯定不能暴力解」🗣️ Triton 本人說 064-introToAlgorithm.pdf.md · 「我的回應」
「Bruteforce algorithm(暴力解法)也是算法的一種啊!特別在 n 很小的時間。Engineering 是在有限資源(開發時間/server cost/效能)下找出最可行解法」🗣️ Triton 本人說 064 · 「我想說……」
「N 很小時,O(n^2)/O(n^3) 也好,1ms 和 0.1ms 對用戶感覺是沒差別的。越深的 algorithm,很多時其 implementation 就越複雜,這代表:更高的開發時間、更多可以犯錯的細節、更多的 source code,增加維護困難度」🗣️ Triton 本人說 064 · 「我繼續想說……」
你猜猜看:1 萬個點,要找每一點的最近鄰居。網友都推 R-tree、quadtree。如果只用兩層 for-loop 一個一個比,要跑多久?
1 萬 × 1 萬 = 1 億次比對,電腦不到一秒就做完。原書整章沒問「你的 N 多大」,Triton 先問這個。
🗣️ Triton 羅馬不是一天建成的:好的開發者應該
- 先正確地理解問題
- 了解 N(像是 QPS / user count / data size)
- 給 PM 說明不同解法的開發時間和其預測界限,找出平衡的方案
- 開發後,清楚寫下你用了那種解法
- 管理系統中的 tech debt,在 N 變大時換上更好解法
064 · 「羅馬不是一天建成的」(原文「平衝」應為「平衡」)
Triton 怎麼看 · 動手算暴力解 vs 索引:O(m·n) vs O(m·log n)
你的 N 和 m 是多少?算完再決定要不要建索引
你猜猜看:原書 2 億家店、每秒 5,000 次搜尋。如果每次搜尋都把 2 億家量一遍,每秒要量幾次?
2 億 × 5,000 = 1 兆。一顆 CPU 每秒約 1 億次(示意),要上萬顆,所以原書的規模一定要索引。左邊按「原書」驗證。
「反正你只用解一次,暴力解法跑完後把結果存起來就好」🗣️ 064 · 正確地理解問題
「對一個任意點 x,我想知道在 10000 個點中,誰跟 x 最接近。暴力解法:O(m*n),m=你 query 的次數;Quadtree 解法:O(m * log n)。因為 m 可以很大,所以暴力解法不一定能接受」🗣️ 064
🔭 計算假設 用 Triton 自己的數字反推:1 萬點 O(n²) = 1 億次距離計算「少於 1 秒」,所以這裡以一顆 core 每秒約 1 億次當示意。索引的成本只算 log₂ N,忽略常數,真實數字請壓測。判斷門檻用 Triton 說的「n > 1M 則肯定不能暴力解」。
Triton 怎麼看同意:geohash + 8 鄰格
✅ 同意原書 自己這格加 8 個鄰格,找不到就縮短一碼
你猜猜看:原書是「自己這格 + 8 個鄰格,店不夠就把 geohash 縮短一碼」。Triton 會怎麼評?
這是本章少數 Triton 和原書做法一樣的地方,連「縮短一碼重來」都一樣。差別只在資料放哪裡。
「你可以想像:每一個 geohash 都是一個長方形。在一個長方形內的點,其最近鄰居一定是……在同一長方形內,或在鄰近八個長方形內。對於一個 geohash,要找出鄰近8個長方形的所需時間是:O(1),真的是 O(1)」🗣️ Triton 本人說 064 · Geohash(續)
「簡單來說:這是把地球坐標轉成 string 的 encoding。4byte geohash 誤差是 20km、5byte geohash 誤差是 2.4km、6byte geohash 誤差是 610m」🗣️ Triton 本人說 064 · Geohash
Triton 的「誤差」大約是原書 Table 4 格子邊長的一半(39.1 × 19.5 km → 20 km;4.9 km → 2.4 km;1.2 km × 609 m → 610 m),兩邊數字一致。
🗣️ Triton 具體解法(簡化版)
- 「把每一個點,建立從 1byte 到 i byte 的 geohash 的 column,然後把這些資料放進 elastic search」
- 「先建立 i byte 的 geohash(還有其相鄰8格的 geohash)」
- 「把這 9 個 geohash 丟到 ES 搜尋」
- 「如果有結果返回,則一個一個對比,最近的點就是答案」
- 「否則用 i-1 byte 的 geohash 從來~」
064 · 具體解法
和原書對照
第 4 步是原書 Figure 2 之後的「算鄰格、逐格撈、算距離排序」(第 40 頁);第 5 步就是原書的「拿掉最後一碼擴大搜尋」(第 24 頁)。差別只在存哪裡:原書是自建 geo index 表 + Redis,Triton 是每個長度一個欄位,交給 ES 的 index。
Triton 怎麼看情境差異:面試講原理,工作用現成的
原書在 LBS 裡自己建 quadtree;Triton:「以上的都不用自己來寫」
你猜猜看:原書讓每台 LBS 開機時,自己在記憶體裡建一棵 2 億家店的 quadtree。真的上線,最可能遇到什麼麻煩?
原書自己在第 30 頁就列了這些麻煩。Triton 的答案是:別自己寫,用現成的。
📖 原書 自建、自己維運
原書自己也說現實中公司會用 Redis Geohash 或 PostGIS,但面試要你解釋原理。於是 quadtree 版本是:每台 LBS 啟動時花幾分鐘建樹、期間不能接流量;更新要上鎖、重新平衡複雜(第 30 頁);geohash 版本是自建 geo index 表,再加一組 Redis “Geohash”。
🗣️ Triton 本人說 用現成的 index
「這是 quadtree 變種,所以其時間是 O(m log n)。因為其 fanout factor 很高,所以 tree height 很低。Geohash 有現有 library,不用自己來寫。能善用 elastic search/一般 RDBMS 的 indexing,不用自己建立和管理 quadtree」064 · 解法優點
「如果你用 postgresql,使用 postGIS 套件,以上的都不用自己來寫,有人替你寫好了」064 · 附 postgis.net 的 KNN 教學連結
Triton 怎麼看情境差異(續):能不能先在資料庫裡做?
越少模組越好:geo index 能不能就放在原本的資料庫裡?
這一頁要回答不自己建 quadtree,那要用什麼?要不要另外架一套 Elasticsearch?
🗣️ Triton 越少模組越好
「越少模組,便代表你需要監控和管理的模組便越少,代表你的團隊需要掌握的語言/技術便越少」「例子:是否使用 ElasticSearch?你需要 Tokenization 嗎?能不能先在 RDBMS 做 searching?」073 · lesson3
🔭 依 Triton 原則推論 放回這一章
原書已經選了 MySQL/primary-replica。如果改成 Postgres + PostGIS,geo index 就是同一個資料庫裡的一個 index:不用另一張自建表、不用每台 LBS 啟動建樹;「營業中」「只要餐廳」也能寫在同一個 WHERE 裡。064 推 ES,073 又問「能不能先在 RDBMS」,兩句合起來,第一步是 PostGIS。
📅 2026 補充 PostGIS 長什麼樣
CREATE INDEX ON business USING GIST (geog); SELECT business_id FROM business WHERE ST_DWithin(geog, ST_MakePoint(-122.41673, 37.77672)::geography, 500) ORDER BY geog <-> ST_MakePoint(-122.41673, 37.77672)::geography LIMIT 20;
ST_DWithin 用 GiST index 做半徑查詢;<-> 是 index 支援的 KNN 排序。
Triton 怎麼看同意:RDBMS、先 scale up、別急著 shard
✅ 同意原書 1.71 GB 的 index,一台資料庫就放得下
你猜猜看:2 億家店的 geo index 約 1.71 GB。Triton 會建議一開始就 shard 成好幾台嗎?
1.71 GB 一台筆電都放得下。Triton:先 scale up,到盡頭才 shard。
📖 原書 自己就說了
- 讀為主的系統,MySQL 這類關聯式資料庫很合適(第 10 頁)
- geo index 只有約 1.71 GB,放得進 working set,沒有強烈的技術理由 shard,用 read replica(第 36 頁)
- geo index 表一店一列,不要塞 JSON array(第 35 頁)
🔭 依 Triton 原則推論
唯一的差別:原書在 business table 那段說「可能放不進一台,適合 shard」;照 Triton 的順序,先問 2 億筆商家到底多少 GB,scale up 到 20 core、200 GB RAM 還放不下,才輪到 shard。
「不能不見的data,我一定存到RDBMS」「用children table來存你的array data,別為了小事輕易違反3NF」「如果是小型系統,單純scale up便算了」🗣️ Triton 本人說 106-喵 data.md
「正常沒亂來的系統,在20core + 200GB RAM的暴力機器下,絕大部份都沒需要玩clustering」「如果到了scale up盡頭又不想走Hbase那些noSQL……我還不如走傳統的sharding路線」🗣️ Triton 本人說 106
「資料量不夠大 (<100GB) 就乖乖回去用 RDBMS 就好啦」🗣️ Triton 本人說 054-data-analysis.pdf.md · 前言(原文談資料分析)
「Auto-scaling是用來省錢的。一般用在 App. Server層,別用在 DB層。流量上升是慢慢的,不是爆發性的」🗣️ Triton 本人說 051-concurrency.pdf.md · Auto-scaling(對照原書「用餐時間自動加 LBS」:同意,LBS 是 stateless 的 AS 層)
Triton 怎麼看Cache:TTL 對了,夜間 job 要小心
原書設了 1 天 TTL ✅;但「大量 key 同時失效」要先想好
你猜猜看:原書用夜間 job 更新 cache。如果做法是「先全部清掉,等有人查再補」,清掉的那一刻會怎樣?
每個 key 都沒了,每一個查詢都 miss,全部同時打到資料庫。這就是原書點出、但沒給解法的問題;Triton 的處方在右邊。
✅ 同意 一定要設 TTL
原書的程式碼 Cache.set(cacheKey, listOfBusinessIds, "1d")。
「沒設定合理的 TTL:有笨蛋會設 cache TTL = 一年,不設 TTL後果更嚴重,唉~這種瘋狂的 TTL,最終會讓 redis存太多過期資料,觸發 cache eviction」🗣️ Triton 本人說 087-redis-2019.pdf.md · caching 常犯錯誤
「正常人使用 Redis……用作 caching,資料同時存放於主資料庫」087 原書正是這樣用:資料庫是本體,Redis 是 cache。
📖 原書自己點出的問題 夜間 job 讓大量 key 同時失效
原書:用夜間 job 更新 cache,「潛在問題是大量 key 同時失效,cache server 負載很重」,但沒給解法。
「如果資料X的 QPS是 1000……如果主資料庫需要 80ms回傳資料X,那麼便有 80個 request進了主資料庫」🗣️ 087 · 「一般」的 caching 問題
🗣️ Triton 的進階做法 ① 從 Redis 拿 X,有就回傳 ② 拿到 X 的鎖 ③ 再從 Redis 拿一次,有就回傳 ④ 從主資料庫拿 ⑤ 放回 Redis ⑥ 回傳 087
🗣️ 預熱「土法煉鋼但是有效的做法:寫一個 crontab,在 cache miss前到主資料庫拿資料放到 redis」087
🔭 推論 放回這章:夜間 job 不要「先清空再等 miss」,而是直接把新清單寫過去(預熱),TTL 錯開;漏網的 miss 走「上鎖再檢查」。商家資料一天才變一次,也很適合放 LBS 本機的 local cache(051:snapshot 不會被改動,能放在 local cache)。
🗣️ Triton Redis cache 也要當 stateful 看
「如果單純用作caching的,那嚴格定義上算是stateless,不過,實務上當成stateful會比較安全(單純是cache-miss就超級可怕了)」017
Triton 補充Region、AZ 與 High Availability
多 region 是為了近和法規;HA 先用別人做好的
你猜猜看:原書把 Redis cache 部署到全球各地。如果某一區的 cache 突然全空,會怎樣?
cache 雖然不是正本,但它一空,所有查詢都變成 miss,壓力全部回到資料庫。所以 Triton 說 cache 實務上也要當成 stateful 來顧。
「傳統上我們談High Availability,我們是指:1. 系統中沒有single point of failure 2. 如果single component掛掉,是不需要人類即時行動。」「有HA不代表系統完全零秒的Downtime, 有HA只代表有single component掛了後系統能自動短時間內回復。(一般來說「短時間」=數分鐘內)」🗣️ Triton 本人說 017-High Availability stateful component vs stateless component.md
「stateless component算是很簡單的,就單純有N個相同的node就好」「整個過程有數不清的地方可以出錯,請使用像AWS RDS multi-AZ這些別人建好的方案,而不要輕易自己」🗣️ Triton 本人說 017
🔭 依 Triton 原則推論 對照原書
- 原書的 LBS、business service 都 stateless:多開幾台、heartbeat 判斷死活,就是 017 說的簡單那一半
- 麻煩的是 stateful 的 primary DB 和 Redis。原書的圖只畫了 primary + replica,沒說 primary 掛了誰升級;照 017,交給 RDS multi-AZ 這類 managed 方案
- 原書把 Redis cluster 部署到全球,是為了延遲和可用性;照 017,cache 也要當 stateful 看:一個 region 的 cache 全空,流量全打回資料庫
- 原書第三個理由「隱私法規」是 Triton 材料沒談過的,照原書
017 這篇的背景是 Triton 批評 ByteByteGo 一篇談 HA 的貼文(「4 nines」、hot-hot),也就是本書作者那邊的內容;他批評的是那篇貼文,不是這一章。
到這裡你已經會了小結 4 / 4
- 經緯度
- index
- read replica
- 2D search
- grid
- geohash
- 鄰格
- quadtree
- Hilbert curve
- N 和 m
到這裡你已經會了:Triton 的那一個問題
- 先寫下 N(幾家店)和 m(每秒查幾次)。1 萬家暴力解不到一秒;n > 1M 才肯定要索引。
- 同意原書的 geohash + 8 鄰格、縮一碼擴大;但上線別自己寫 quadtree,用 PostGIS、ES 這類現成的 index。
- 資料 1.71 GB 一台放得下:RDBMS、先 scale up、read replica;cache 一定設 TTL,夜間更新要預熱、上鎖再檢查。
10 階全部走完了
下一頁用一句話收尾;再下一頁是名詞小卡,給大家課後複習。
一句話記住
先數有幾家店、每秒查幾次;
小就暴力解,大就用 PostGIS,不要自己種樹。
原書對的地方
- geohash + 8 鄰格解決邊界問題
- 找不到就拿掉一碼擴大搜尋
- geo index 一店一列、不用上鎖
- 資料小,用 read replica 別 shard
- 先問要不要 cache、TTL 設 1 天
情境差異
- 原書假設 N = 2 億,所以一定要索引;你的 N 可能是 1 萬
- 面試要講原理;上線用現成的 PostGIS / ES / Redis GEO
- 自建 quadtree:啟動幾分鐘、更新要上鎖
Triton 的做法
- 先寫下 N 和 m,算 O(m·n)
- N < 1M、m 小:兩層 for-loop,寫進 tech debt
- N 大:geohash 欄位放 ES 或 RDBMS index,或 PostGIS
- 夜間更新 cache:預熱 + 上鎖再檢查
本章名詞小卡課後複習用 · 每個名詞一句白話
今天出現的名詞,一句話講完
給工程師的重點出處與標籤
引述來源(materials/core)
Triton 本人的講義 / 文章
- 064-introToAlgorithm.pdf.md — 本章主來源:1 萬點 O(n²) 少於 1 秒、n > 1M 不能暴力解、「Bruteforce algorithm 也是算法的一種」、了解 N、O(m*n) vs O(m log n)、geohash 長方形 + 8 鄰格 O(1)、1..i byte 欄位放 ES、i-1 重來、不用自建 quadtree、postGIS 套件
- 073-lesson3.pdf.md — 越少模組越好;是否使用 ElasticSearch、能不能先在 RDBMS 做 searching
- 106-喵 data.md — 不能不見的 data 存 RDBMS、children table 不違反 3NF、小型系統 scale up、20core + 200GB RAM、寧走傳統 sharding
- 054-data-analysis.pdf.md — <100GB 用 RDBMS(原文談資料分析)
- 051-concurrency.pdf.md — auto-scaling 用在 AS 層、別用在 DB 層;snapshot 可放 local cache
- 087-redis-2019.pdf.md — 一定要設合理 TTL、cache stampede 上鎖再檢查、crontab 預熱、Redis 用作 cache 資料同時存主資料庫
- 017-High Availability….md — HA = 無 SPOF + 自動數分鐘內恢復、stateless 簡單、用 RDS multi-AZ、Redis cache 當 stateful 看
沒有引用:061(Roy 的專案報告,用了 PostGIS 的 ST_DWithin,但標「僅供面試評估使用,請勿外傳」);187–195 的 AI 生成內容。
循序漸進(文組版)的頁面
學習地圖(第 3 頁);延伸基礎 10 階:經緯度(4)、index(9)、read replica(11)、2D search(14)、grid(16)、geohash(18)、鄰格(21)、quadtree(26)、Hilbert curve(31)、N 和 m(43);小結(13、25、42、52);名詞小卡(54)。Triton 段:44–51(PostGIS / 少模組在 48)。
原書對照
Alex Xu & Sahn Lam, System Design Interview Vol.2 Ch.1。開場與 Figure 1(第 5 頁)、Step 1 需求(6)、估算(7)、API 與 Table 1–2(8)、Data model 與 Table 3(10)、High-level design 與 Figure 2(12)、Option 1 與 Figure 3–4(15)、索引分類、Option 2 與 Figure 5–6(17)、Geohash 與 Figure 7–8(19)、Table 4–5(20)、互動地圖(22)、Boundary issues 與 Figure 9–11(23)、Not enough businesses 與 Figure 12(24)、Quadtree 與 Figure 13–14(27–28)、Table 6–7 與記憶體(29)、Operational 與 Figure 15(30)、S2 與 Figure 16–17(32)、Table 8 與比較(33)、Figure 18–19(34)、Scale the database 與 Table 9–11(35–36)、Caching 與 Table 12(37–38)、Region / AZ、Figure 20 與篩選(39)、Final design 與 Figure 21(40)、Wrap up 與心智圖(41)。21 張圖、Table 3/9/10 的圖片與心智圖都依原書圖說和 alt 重繪,不是原圖。
一個可以直接問自己的問題
你的系統有幾個點要搜?每秒搜幾次?兩個數字乘起來,是一億、還是一兆?