題幹與適用場景
設計一個全球附近地點搜尋服務。目錄保存 5,000 萬個餐廳、商店和公共設施；使用者依目前位置、500 公尺到 50 公里的半徑、類別和營業狀態，取得距離最近的 20 個結果。搜尋尖峰為每秒 20 萬次，商家建立、搬遷、關閉等更新尖峰為每秒 100 次，端到端讀取 p99 目標為 150 毫秒。
本題把地點視為低頻更新的靜態實體。司機、外送員或朋友位置的秒級更新、媒合與防止重複指派屬於另一套動態位置系統。距離按地球表面的地理距離計算；路線時間、個人化和廣告競價不在核心範圍。容量和 SLO 都是面試假設。
核心難點是二維半徑搜尋。普通經緯度 B-tree 很難直接跳到查詢圓內的紀錄。推薦路徑是先用空間索引或離散網格找到一定包含正確答案的候選集，再計算精確距離、過濾、排序和截斷。網格命中只是粗篩，不能把同格或鄰格誤當成「半徑內」。
面試官考察點
第一個訊號是先定義正確性。結果必須在半徑內、滿足過濾條件，並按確定性順序回傳最近 20 個。候選集必須覆蓋跨格邊界的地點；粗篩後還要做精確距離複核。只查使用者所在的一個 geohash，會漏掉隔著格邊界但只有幾十公尺的商家。
第二個訊號是依更新模式選索引。靜態商家可從 PostGIS GiST、R-tree 或資料庫內建的距離索引開始；讀量和全球分片壓力上升後，再把地點映射到 H3、S2 或 geohash 單元。直接宣布「用 Redis GEO」沒有解釋查詢圓、精度、熱門點和真實距離。
第三個訊號是辨識空間資料不均勻。海洋和鄉村幾乎為空，市中心一個格可能很熱門。按固定經緯度範圍平均分片會產生熱點；需要按粗粒度空間前綴路由，並讓高密度格拆分或增加讀取副本。大半徑請求還會跨多個分片，不能假設一次查詢永遠命中一個節點。
最後要把分頁、一致性和故障連起來。按距離分頁時，使用者座標、過濾條件、目錄版本、最後距離和地點 ID 都屬於游標契約。更新或分片逾時會改變結果集；強回答會聲明 best-effort 或快照語意，並讓部分結果可辨識。
回答前需要澄清的問題
- 地點是靜態或持續移動？ 本題更新尖峰只有每秒 100 次，適合快取和非同步索引。移動實體需要更短新鮮度、寫入最佳化索引和媒合一致性。
- 「最近」指直線地理距離或路線時間？ 本題先按地理距離。路線時間需要道路圖和獨立 ETA 服務，通常只對粗篩後的少量候選計算。
- 結果必須完整，或允許只回傳前 20 個近似候選？ 本題要求半徑過濾正確，並在已索引目錄中回傳確定性的最近 20 個；空間格只能產生候選。
- 營業狀態要多新？ 地點位置和類別可容忍分鐘級傳播，臨時營業狀態若要求秒級，應獨立儲存和用短 TTL 合併，不能跟低頻目錄共用一個更新承諾。
- 是否需要深分頁？ 附近搜尋通常只需前幾頁。本題允許最多 100 個結果；若要求掃描全部 50 公里結果，應改成非同步匯出或區域瀏覽 API。
- 跨分片失敗時能否回傳部分結果？ 預設回傳帶
partial=true和缺失區域的可辨識部分結果；嚴格場景可失敗重試，不能把部分結果偽裝成完整最近集合。
30 秒回答框架
「我會把寫入路徑和搜尋路徑分開。地點主資料寫入帶版本的目錄庫，並非同步更新空間索引。每個地點保存精確經緯度、粗粒度路由格和搜尋解析度格。查詢先驗證半徑與過濾條件，用 H3、S2、geohash 鄰格集合或 PostGIS 距離索引取得覆蓋查詢圓的候選，再計算精確球面距離、過濾並按 (distance, place_id) 排序取前 20 個。
空間前綴負責路由，高密度格可拆分，跨格查詢平行存取有限分片並做全域 top-k 合併。快取鍵包含格集合、半徑桶、過濾條件和目錄版本，更新透過地點版本讓受影響格失效。游標綁定原查詢與目錄快照，避免換位置後繼續翻頁。最後用邊界、日期變更線、極區、熱門城市、搬遷、分片逾時和快取陳舊測試正確性與 p99。」
分步驟深入解答
第一步：固定 API、資料模型和不變量
API 只接受有界半徑、合法座標、允許的過濾條件和有限頁長。回應回傳計算距離、目錄版本、結果是否完整以及下一頁游標。
GET /v1/places/nearby?lat=&lng=&radius_m=&category=&open_at=&limit=&cursor=
Place {
place_id, lat, lng, search_cell, routing_cell,
category, status, hours_version, location_version, updated_at
}
Cursor {
query_hash, catalog_version, last_distance_m, last_place_id
}維護四個不變量：結果滿足半徑與過濾條件；候選階段不能漏掉圓內地點；最終順序是 (distancem, placeid)；舊位置版本不能覆蓋新位置。經緯度要使用統一座標系並驗證範圍，內部距離單位統一為公尺。
第二步：選擇最簡單能達標的空間索引
第一版可用支援空間索引的關聯式資料庫。半徑查詢先用可索引的包圍盒縮小集合，再用精確距離函式過濾。官方 earthdistance 文件也明確指出，索引框會包含圓外點，因此需要第二次距離檢查。這條「候選超集後精確複核」規則不依賴特定產品。
當單庫無法承受全球 20 萬 QPS 或需要明確空間路由時，將地點編碼到固定解析度的 H3、S2 或 geohash 格。查詢圓轉換為覆蓋它的格集合，讀取每格倒排列表，再去重和精排。H3 層級可快速改變解析度，但父子格的地理包含存在近似邊界；仍需精確點到點檢查。
固定解析度容易兩頭受損：格太大時候選放大，格太小時 50 公里查詢列舉太多格。可按半徑選擇少量預定解析度，並為地點預先計算這些層級，或讓大半徑走更粗的索引。解析度選擇必須由候選放大率、扇出和 p99 壓測決定。
第三步：執行候選查詢與全域 top-k
查詢服務把圓轉換為候選格，確保包含所有相交格，而非只包含中心格。對每個格平行讀取符合粗過濾的地點 ID 和座標，設定總截止時間和每分片預算。重複地點按 place_id 去重，隨後計算精確地理距離，刪除圓外點，再套用權限、狀態和類別過濾。
每個分片可先回傳本地前 k 個，但必須證明截斷安全：若每個分片都按同一最終距離排序並回傳至少全域 k 個候選，任何分片第 k+1 個都不可能進入全域前 k。聚合器用大小為 k 的最大堆合併，時間複雜度與回傳候選數線性相關，記憶體為 O(k)。
大半徑或密集城市可能產生過多候選。服務設定最大候選數，但不能靜默截斷後宣稱結果精確。可以自適應提高格精度、把類別過濾下推、分批擴圈直到已找到 20 個且未搜尋區域的最短可能距離超過目前第 20 名，或回傳明確的資源限制錯誤。
第四步：分片、熱點與容量預算
用粗粒度 routingcell 將格目錄映射到分片，而非按 placeid 隨機分片，否則一次空間查詢會廣播到所有分片。目錄服務維護路由表和 epoch。一個查詢讀取同一 epoch；發現路由變更就重試，避免拆分過程漏讀。
5,000 萬個地點若每條搜尋索引紀錄連同 ID、座標、過濾欄位和開銷按 128 到 256 位元組估算，主搜尋索引約為 6 到 12 GiB，複製、多個解析度和資料庫開銷會繼續放大。這個量級可以分區並駐留在讀取最佳化節點，但不能據此斷言某一種資料庫必然足夠。
20 萬 QPS 若平均扇出 6 個格讀取，會產生約每秒 120 萬次格讀取。快取和批次讀取必須降低後端操作數。熱門格按讀取流量增加副本；超密格細分為子格。稀疏格合併只影響儲存與路由，查詢覆蓋仍由幾何邏輯決定。
第五步：寫入、快取和一致性
地點服務驗證所有權後更新主紀錄，並遞增 location_version。變更事件包含舊格、新格和版本。索引消費者先把新版本寫入新格，再移除舊格；讀取路徑按版本去重，所以重播安全，延遲刪除也不會讓舊紀錄勝出。搬遷跨分片時不依賴分散式交易保證瞬時原子，而是揭露索引延遲並透過版本收斂。
快取分兩層：格到候選 ID 的快取，以及完整地點物件快取。候選快取鍵包含索引版本、格、類別和狀態桶；最終回應快取還必須包含座標桶、半徑桶、過濾條件和目錄版本，命中率通常更低。更新發布舊格和新格的失效事件，並保留短 TTL 作為遺失失效訊息的上界。
open_at 若隨分鐘變化，不應每分鐘清空所有空間快取。快取靜態候選與營業規則，在查詢節點按請求時間求值；只有臨時關閉等高時效狀態使用小型覆蓋層。這樣營業狀態變化不會重建整個地理索引。
第六步：穩定分頁和故障語意
游標對使用者座標、半徑、過濾條件和 catalogversion 求雜湊，並保存最後的 (distancem, place_id)。下一頁拒絕不同查詢參數。若支援短生命週期快照，就從同一目錄版本讀取；若只提供 best-effort，回應必須說明更新可能造成跨頁重複或遺漏，並在用戶端按 ID 去重。
聚合器給每個分片短於 150 毫秒總目標的截止時間。一個分片逾時後，不能稱回傳結果為全域最近 20 個，因為缺失分片可能有更近地點。面向探索的 API 可回傳 partial=true、缺失格和可重試游標；嚴格呼叫端收到明確的不可用錯誤。斷路器只隔離故障分片，不能把整個全球索引一起打開或關閉。
跨區域部署優先在本地讀取完整目錄副本或按地理區域分區。跨國資料邊界影響地點中繼資料和稽核，但公開商家座標仍要經過來源授權。區域故障時只能容錯移轉到已有足夠新鮮索引的區域，並回傳 as_of，不能臨時查詢主目錄全表當備援。
第七步：用幾何反例和故障注入驗證
正確性測試用暴力全表距離計算作為小資料 oracle。隨機產生點和半徑，對比索引結果；專門覆蓋格邊界與角點、經度正負 180 度、極區、半徑恰好相等、重複座標、零結果、20/21 名距離相同和地點跨格搬遷。每次都斷言無漏項、無圓外項和穩定 tie-break。
效能測試分別覆蓋空曠區域、普通城市和超密熱點，測量格扇出、候選放大率、精確距離計算數、快取命中率、分片 p95/p99、聚合時間與端到端 p99。故障注入包括一個格副本變慢、路由 epoch 變更、失效訊息遺失、消費者重播、跨分片搬遷中斷和區域切換。
上線採用影子查詢：新索引與舊的可信實作同時讀取一小部分流量，比較前 20 集合、順序、距離和缺失率。任何效能提升都不能掩蓋 false negative；附近搜尋漏掉正確地點是索引正確性故障。
高品質示範回答
「我先把它限定為靜態地點檢索，不處理移動司機。寫入端由地點目錄保存精確經緯度和單調位置版本，並透過事件更新空間索引。讀取端不對經緯度做全表距離排序，而是把查詢圓轉換成一組完全覆蓋它的候選格。可以先用 PostGIS 的空間索引；到全球讀量需要空間路由時，再使用 H3、S2 或 geohash。格只負責粗篩，候選必須計算精確地理距離，過濾後按距離和地點 ID 穩定排序。
我會用粗格路由到分片，高密度格可拆分，熱門格增加讀取副本。查詢平行讀取有限分片，每個分片回傳本地 top-k，聚合器合併全域 top-k。候選太多時擴大過濾下推或逐圈搜尋；不能靜默截斷。快取格候選和地點物件，鍵帶索引版本，地點搬遷同時讓舊格與新格失效，消費者用位置版本抵抗重播。
游標綁定座標、半徑、過濾條件、目錄版本和最後的距離／地點 ID。分片逾時會讓全域最近結果無法證明，因此探索 API 標記 partial 並列出缺失格，嚴格 API 失敗。驗證時我用暴力距離計算作為 oracle，隨機對比並重點攻擊格邊界、日期變更線、極區、同距離 tie、搬遷和路由變更；再在熱門城市與故障注入下驗證 150 毫秒 p99。」
常見錯誤
- 只查中心 geohash → 查詢圓跨越格邊界時漏掉近鄰 → 讀取所有相交格並做精確距離複核。
- 把鄰格當成半徑內 → 格的外角可能遠超半徑 → 網格產生候選，球面距離決定最終包含。
- 按地點 ID 隨機分片 → 每次附近搜尋廣播全球 → 按粗空間前綴路由，並為熱門格拆分或複製。
- 固定一種最細解析度 → 小半徑候選少但大半徑格扇出爆炸 → 用少量受控層級並依據測量選擇。
- 快取只包含經緯度 → 不同半徑、類別或目錄版本互相污染 → 把完整查詢契約和版本納入鍵。
- 地點搬遷先刪後加 → 處理失敗時地點暫時消失 → 先寫帶新版本的新格，再刪除舊格並按版本去重。
- 分片逾時仍回傳「最近 20 個」 → 缺失分片可能包含更近結果 → 標記部分結果或讓嚴格請求失敗。
- 只測紐約市中心 → 邊界、極區和稀疏區域錯誤被掩蓋 → 用暴力 oracle、隨機屬性測試和專門幾何反例。
追問及應對
追問一：為什麼不直接用 PostGIS 完成全部需求？
可以先這樣做。空間資料庫已經提供正確的索引候選和距離函式，團隊能以更少元件取得可靠版本。只有當 20 萬 QPS、全球路由、熱點隔離或成本測量證明單一資料庫拓撲無法達標時，才引入離散格索引和獨立搜尋層。遷移時用影子查詢比較完整結果，不能只比較延遲。
追問二：如何保證查詢格不會漏掉圓內地點？
使用函式庫提供的圓覆蓋或多邊形覆蓋操作，而非自行猜鄰格數量。覆蓋集合可以包含多餘格，但不能缺少與圓相交的格。讀取後用精確距離刪除 false positive。測試用全表 oracle 對隨機圓、格角、日期變更線和極區做集合差異；任何 false negative 都阻斷發布。
追問三：如果 50 公里查詢覆蓋成千上萬個細格怎麼辦？
切換到預先計算的較粗層級，讓格數保持有界，再依賴類別下推和精確距離複核。也可以逐圈擴展：已取得 20 個結果且未存取區域到中心的最短可能距離大於目前第 20 名時停止。大半徑仍超過資源預算就拒絕或轉非同步，不能悄悄少查。
追問四：如何擴充成附近司機媒合？
先承認問題已經改變。司機位置需要秒級寫入和過期，索引按城市或格分區，更新要涵蓋亂序與幽靈司機；候選檢索後還要按 ETA、司機狀態和公平性排名。最終指派必須透過帶版本的條件更新或單一擁有者防止雙重派單，不能依賴最終一致的空間索引完成占用。
追問五：營業狀態每分鐘變化會不會造成快取失效風暴？
把靜態空間候選與動態狀態分層。格快取保存地點 ID、位置和類別；查詢時從營業規則計算 open_at，臨時關閉由小型即時覆蓋層提供。只有位置或類別變化才讓空間候選失效。監控覆蓋層新鮮度，缺失時回傳狀態未知或採用業務核准的降級規則。