系統設計學習筆記 - 鄰近服務

這次來讀《System Design Interview – An Insider's Guide: Volume 2》第一章——鄰近服務。這個章節中考慮要設計一個類似於 Google Maps 中搜尋附近店家的功能。

需求釐清

作為一個地理基礎的服務，會考慮到是否需要讓使用者自訂搜尋半徑，在這裡的假設是使用者可以在 UI 上選擇搜尋半徑，但當指定的半徑內沒辦法找到需要的結果時可以嘗試擴大搜尋半徑。再來即是當使用者移動時是否需要跟著重新搜尋新的範圍內的店家，這裡的認定為非。

另外，要考慮到資料更新的即時性，例如店家對自身資料的更新是否需要即時反映於搜尋結果上，現行的假設則為非。其實對應到 Google Maps 的行為上來看似乎他們也不會即時更新所有資訊，雖然個人猜測可能是為了防範各種濫用如惡意連結或非法資訊等，而導致會需要跑過各種後端檢查之後才會更新到介面上。

故功能性需求包含：

1. 需要回傳對指定坐標及半徑內所有店家資訊
2. 店家要能增/刪/改店家資訊，但不必即時更新
3. 使用者要能查詢店家的詳細資訊

在非功能性需求上，則要考慮包含 UX、法律及高可用的部分。包含：

1. 要盡量降低延遲，讓使用者快速地得到結果
2. 使用者座標算是個資的一環，要考慮 GDPR 及 CCPA 的法律適用
3. 高可用性

另外就是要估計服務需要負擔多少流量，書上的估算方法是 1 億活躍用戶，而每個使用者每天執行 5 次查詢，故平均的 QPS 為

註：這本書直接用 $10^5$ 代替每天的 86400 秒。

設計

書中 API 設計環節就只是列出 RESTful API 的 spec，這邊就直接跳過拉。

高階概念

首先就是管他三七二十一先上個 Load balancer 來撐場面 （雖然確實是需要用到拉，但這幾乎變成系統設計標準起手式了）

過 LB 之後依據請求類型（直接用請求路徑分類，畢竟已經切 RESTful 了）分兩種狀況：

1. 對搜尋請求交給 Location-based service (LBS) 處理
2. 對於店家資訊的部分就直接進服務處置

搜尋請求

考慮這段可能是最高負載的部分，所以設計上需要帶入 LBS，並且只支援無狀態查詢、只對資料庫進行讀取而不寫入，以這樣的條件來設計服務。且這樣會比較好進行橫向擴容。

資料庫叢集

承前面搜尋請求可能負載很高的問題，設計上會使用資料庫叢集，採用一個讀寫的 primary 及多顆 replica 的設計。處理搜尋請求的服務可以直接對 replica 做查詢，而店家資訊更新則可以直接寫入 primary。

搜尋演算法

書中直接說明在務實上搜尋的需求會直接使用 Geohash 或 PostGIS 這類的工具處理，以下只是探討大方向要怎麼做設計思考。

思路：二維搜尋

算是最直觀但也相對笨的手法，即直接對兩個維度做查找：

SELECT business_id, latitude, longitude
FROM businesses
WHERE 1 = 1
AND (latitide BETWEEN {current_latitide - radius} AND {current_latitide + radius})
AND (longitude BETWEEN {current_longitude - radius} AND {current_longitude + radius})

但這邊認為這樣執行起來效率十分之不好，原因是因為資料庫需要對兩個維度各去取出範圍內的資料再行交集（會發生 full table scan），而即使對這兩個維度都建索引，效果依然不會有太大的提升¹。

書上說資料庫在一維的索引上搜尋效率較好，所以我們的目標應該要是將二維資料映射到一維上來進行搜尋。

思路：均質等分的圖紙

既然想將二維資料映射到一維上，那其中一個方法就是把地圖切分為多個等大的格子，並將店家資訊映射到格子內。那我們在進行搜尋的時候只要把半徑內個格子的資料調出即可。

書上認為不妥的點是城市的一個格子內可能會有過多的店家，而在沙漠、海洋等區域則會浪費大量個格子，即儲存空間，而沒有任何有效的資料在內。故理想上格子的大小要能彈性調整。

解法：Geohash

Geohash 則是一個相對成熟的解決方案，畢竟前幾頁才講說直接拿去用就好，它可以將二維座標以一個字串做表達，方便於直接利用 DB 的索引功能去進行查找。

這個演算法這細節獨立記錄在另一篇文章；就結論而言，Geohash 會將座標編碼所在的區域以一個字串編碼表示，且所有的子分區編碼皆是在母分區編碼上加入後綴（即 beer 一定是在 bee 裡面），故當兩個地點若分享愈長的前綴，即表示兩地點愈接近。但反之並不亦然——可能會有一些地點剛好翻過軸線而使其前綴有很大的差異。

對於這種鄰近地區但前綴不共用的問題，其解決方法並不難，由於 Geohash 的分區有其邏輯，我們可以直接算出所有臨近區域的編碼，然後再來執行搜尋即可。

而對於前面提及的當一地內的商家數量不足，我們需要尋找更大的面積時，只要刪減當前編碼的長度即可擴大搜尋範圍。

解法：四元樹

四元樹（quad tree）是一個樹狀資料結構，它會將空間以均等面積的四份，並將資料儲存在對應的格子中，並在格子內資料數量達到上限時在切分為更細的四等分。細節可閱讀 Beadx6 的這篇文章。

不同於 Geohash 的是四元樹僅在資料數量達到上限時候才會切分，故對於較為空曠的地區並不會有較細的葉節點產生。也因為它不是直接回傳滿足特定半徑內的資料，我們會需要把取得的座標們再做一次比較才能使用，但這個演算法確實可以在極短的時間內幫忙篩選出可能的候選清單的。在閱讀相關資料的過程中也可以注意到這個演算法很常用在遊戲中做碰撞檢測之用，而我們借用了這個演算法要做鄰近服務搜尋。

回到鄰近服務搜尋的問題，書本首先提及到記憶體消耗及運算資源消耗，結論是四元樹的記憶體消耗不嚴重、而建樹可能也只要幾分鐘，在資源消耗上不太構成問題——但會有維護上要注意的小細節。

由於建立四元樹可能不是極短時間可以完成，故在發布新版的時候需要一點時間給他初始化，意味著可能需要有 藍/綠部署 等配套措施。

另一個維護面的考慮的問題是如何對商家資訊進行增刪改。在前面的需求釐清中有說到可以次日再一次更新即可，所以在離峰時段直接清快取、更新服務可以是一個手段。進一步來說，讓線上的服務即時進行增刪改在理論上是可行的，但要注意到例如在單一服務有多執行緒在跑的時候會需要一些互斥鎖之類的機制來預防讀取出錯。

解法：Google S2

書本提及 Google S2 是另一個 in-memory 的解決方案，基本概念上，它利用 Hilbert curve 將二維座標映射進一維空間，且仍會維持兩個接近的點仍可以在該一維空間中接近的特性。但其詳細內容相對複雜，書本只列出了兩個這個方法的優點：

首先，它的演算法更適合於執行 地理圍欄 —— 但書上的說明是當我們要反向對使用者推送通知的時候可以有利於匡出部分不在特定商家半徑內的使用者。似乎不算是現在的題目下的需求而是衍伸服務種類的時候會遇到的需求。

另一個優點就是這個演算法特有的功能：region cover；在一般狀況下，當我們想要確保某個指定範圍都有被涵蓋時，我們需要用較低精度的母節點/母區域直接將所有目標的區域包含進去，而在 region cover 演算法下，它可以用多個大小不同的 cell 去完整包含出我們想要匡列的範圍；這個範圍甚至可以不用是規則的幾何圖形：

如上圖中則用了 100 個 cell 去拼湊出指定的 C 型範圍。Sidewalk labs 也提供了一個快速的 demo 來玩玩。Region cover 這個功能使得包括搜尋及推送訊息等方面都提供了較高的彈性。

演算法比較

S2 直接被略過了，原因依然是它相對複雜。書上只有比較了 geohash 及四元樹的優缺點。

在 geohash 方面，最大的好處就是易於實作及維護，不用去刻樹、也不太需要考慮各種多執行緒或 CRUD 等實作層需求，可以依賴普通的資料庫進行資料維護，並且可以清鬆且快速的搜尋出指定半徑內的所有店家資訊。

但反向來說，如果我們只使用了固定長度的 geohash 則它會相對缺乏彈性，如前面提及的在人口稠密區沒有切更細的區分的問題。而如果我們想依照人口分布去切分，則代表 index 內的長度可能不固定，那就會需要更多、更精細的邏輯來支援這樣的查詢方式。

以實際案例來說，Bing map 及 Lyft 用的就是 geohash，而軟體面 Redis 、 MongoDB 及 Elasticsearch 皆有 geohash 的實作。

而說到四元樹，首要的優點就是它可以進行 KNN 的查詢，另外就是它自身自然會對人口稠密區進行較細的切分。而在缺點方面，第一個是實作上比較複雜，雖然在這個開源的年代要找到一個可以動的實作應該不太困難，另外就是上面提及的維護成本，在發生各種刪改的時候都會變得比較複雜。

實際案例面有 Yext 在用四元樹，而軟體面則是 Elasticsearch 曾經有支援²。

再往後的章節就在討論實作細節，比較瑣碎就跳過拉。