Geohash 與地理索引:附近搜尋的格子邊界、Redis GEO,以及距離如何洩漏位置
System Design 系列 Part 3-8|上一篇:全文搜尋與倒排索引|下一篇:Replication 與 Replication Lag|系列地圖
情境與問題
講座平台開始辦實體講座,全台有 10 萬個合作場地(教室、共享空間、書店)。App 要新增「附近的實體講座」:
- 以使用者目前的位置為圓心,列出 3 公里內的場地,由近到遠排序
- 尖峰每秒 2,000 次查詢
- 下一階段要做「附近的同好」,讓願意公開位置的學員找到彼此
最簡單的做法與它的極限
經緯度存成兩個 DOUBLE 欄位,查詢時對每個場地算一次距離,留下 3 公里內的。每次查詢要算 10 萬次距離,尖峰每秒 2 億次。
加索引也幫不上太多忙。B+Tree 是一維的:在 (latitude, longitude) 的複合索引上,緯度用了範圍條件,經度就不能再縮小掃描範圍(Index 篇的最左前綴原則)。索引只能把範圍縮小到一條橫跨東西的「緯度帶」,下面的實測中,緯度帶裡有 1,500 多筆,真正在圓內的只有 43 筆。
問題的本質是:要把二維的位置,變成一維的索引能處理的形式。
核心機制
Geohash:把座標變成一個字串
- 把經度的範圍 [-180, 180] 對半切,座標落在右半就記 1、左半記 0,再對落進去的那一半繼續切
- 緯度的範圍 [-90, 90] 用同樣的方式切
- 把經度與緯度的 bit 交錯排列(第 1、3、5… 個 bit 是經度,第 2、4、6… 個是緯度)
- 每 5 個 bit 換成一個 base32 字元
每多一個字元,格子就再切成 32 份。最重要的性質是:前綴相同,就落在同一個格子裡。台北 101 的 geohash 是 wsqqqm29d,它在 wsqqq 這個格子裡,也在更大的 wsqq 格子裡。所以「找出 wsqqq 格子裡的場地」就是 geohash LIKE 'wsqqq%',一般的 B+Tree 索引就能做。
wsqqq 和它周圍的 8 個格子:
| 西 | 中 | 東 | |
|---|---|---|---|
| 北 | wsqqt | wsqqw | wsqqx |
| 中 | wsqqm | wsqqq | wsqqr |
| 南 | wsqqj | wsqqn | wsqqp |
實測:格子大小、邊界與附近搜尋
在台灣附近的經緯度範圍內隨機放 10 萬個場地,依 geohash 排序存放(等同於資料庫裡 geohash 欄位上的 B+Tree 索引),比較幾種查詢方式:
Geohash 實作(Geohash.java)
| |
實測程式(GeohashDemo.java)
| |
| |
格子大小:長度 5 大約 5 公里見方,長度 6 約 1 公里 × 600 公尺,長度 7 約 150 公尺見方。格子的高度到哪裡都一樣,寬度則隨緯度變窄:經線在兩極匯聚,同樣的經度差,在北緯 25 度只有赤道的 90%,到北緯 60 度只剩一半。
相鄰不代表前綴相同:兩個相距約 100 公尺的點,geohash 卻從第 3 個字元就不同了。Geohash 的編號順序是一條 Z 字形的曲線(Z-order curve),在大格子的邊界上會跳很遠,所以「前綴越長越接近」只在一個方向成立:前綴相同代表很近,很近卻不代表前綴相同。
只查中心格會漏掉一半:使用者站在台北 101,3 公里內的 43 個場地只找到 22 個;站在格子的角落,33 個只找到 9 個。
查 9 格:只要格子的寬與高都不小於搜尋半徑,以使用者為圓心的圓就一定落在「自己的格子加周圍 8 格」裡面。9 格掃描 254 筆,再逐筆算精確距離,結果和全表掃描完全相同;緯度索引則要掃描 1,500 多筆。
格子大小是取捨:格子越小,掃描的筆數越少,但格子比半徑小時,9 格就蓋不住整個圓,要查更多格。實作中的 precisionFor 選擇「格子不小於半徑」的最長精度,並且考慮緯度對寬度的影響。
其他空間索引
Geohash 是最容易理解、也最容易用一般資料庫實作的做法,但不是唯一的做法:
- Quadtree:區域內的點太多就切成四塊,密集的市區切得細,鄉下保持大格子。資料分布不均時比固定大小的格子有效率,常用在記憶體內的索引
- R-Tree:把鄰近的物件用最小外接矩形(MBR)分組,組成一棵樹。除了點,也能存線與多邊形。MySQL 的
SPATIAL索引、PostGIS 的 GiST 索引都屬於這一類 - S2(Google):把地球投影到立方體的六個面上,用 Hilbert curve 編號。Hilbert curve 不會像 Z-order 那樣大跳,覆蓋任意形狀需要的格子比較少
- H3(Uber):六角形的格子,共 16 種解析度。六角形的六個鄰居與中心等距,適合做區域統計,例如各區的需求熱度
Redis 的 GEO 指令也是 geohash:經緯度交錯成 52 bits 的整數,存成 sorted set 的 score。查詢時同樣檢查中心加周圍 8 個區域對應的 score 範圍,再濾掉圓外的成員,原理和上面的實測相同。
方案比較
| Geohash 欄位 + B+Tree | MySQL SPATIAL(R-Tree) | Redis GEO | PostGIS | |
|---|---|---|---|---|
| 原理 | 9 個前綴範圍查詢,再算距離 | R-Tree | sorted set + 52 bits geohash | R-Tree(GiST) |
| 形狀 | 點 | 點、線、多邊形 | 點 | 點、線、多邊形,函式最完整 |
| 和業務資料的一致性 | 同一個交易 | 同一個交易 | 衍生資料,需要同步 | 同一個交易 |
| 適合 | 任何資料庫都能做 | 已經在用 MySQL | 高頻查詢、會移動的物件 | 行政區、外送範圍、路線等地理運算 |
Java 落地
1. 附近的場地:Redis GEO
場地資料很少變動,查詢量卻很大,適合放在 Redis。資料庫仍是唯一的資料來源,場地新增或搬家時,透過 outbox 事件更新 Redis(同 全文搜尋篇的索引同步):
| |
geo.search對應 Redis 6.2 起的GEOSEARCH- 半徑與筆數都有上限,不讓一個請求掃過大片區域
- Spring 的
Point與 Redis 的參數順序都是經度在前
查到附近的場地 ID 後,再到資料庫查這些場地本週的講座。要注意「先找最近的 50 個,再篩本週有講座的」可能篩到一個不剩;如果業務條件會篩掉大部分場地,就把條件反映在 key 上,例如只把本週有講座的場地放進 geo:venues:active。
2. 不想多維運 Redis:geohash 欄位
資料量與查詢量沒那麼大時,在資料表多存一個 geohash 欄位就夠了。寫入時由應用程式計算 Geohash.encode(lat, lng, 9),查詢時用 9 個格子的前綴:
| |
開頭不是萬用字元的 LIKE 可以用索引,9 個條件就是 9 段範圍掃描,和實測中的 subMap 相同。查回來的資料再用 Geohash.distanceKm 算精確距離、排序。
3. MySQL SPATIAL 的座標順序
要用 MySQL 的 R-Tree 索引時,欄位必須是 NOT NULL 並指定 SRID,否則最佳化器不會使用這個索引:
| |
SRID 4326(WGS 84,GPS 使用的座標系統)在 MySQL 裡預設的座標順序是緯度在前。少了 'axis-order=long-lat',121.5645 會被當成緯度,因為超出 ±90 度而報錯。
踩坑與 Gotchas
- 經緯度的順序:Redis、Spring 的
Point、GeoJSON 都是經度在前;在地圖 App 上複製的座標、MySQL 的 SRID 4326 則是緯度在前。台灣的經度超過 90,寫反會直接報錯;歐洲、非洲這類經緯度都在 90 以內的地區,就會悄悄存到錯的位置 - 只查中心格:實測中漏掉一半以上
- 格子比半徑小:9 格蓋不住整個圓。精度要依半徑與緯度選擇
- 跨越 180 度經線與極區:自己寫的鄰居計算要處理經度繞回,正式環境用成熟的函式庫
- 直線距離不是路程:3 公里內的場地可能隔著一條河。Redis 的距離也是把地球當成球體計算,最多有 0.5% 的誤差,計費或運費要用其他方式計算
- GEO 成員不會過期:GEO 是 sorted set,成員不能個別設定 TTL。外送員、司機這類會移動的物件,下線後會一直留在 key 裡,需要另一個以最後回報時間為 score 的 sorted set,定期找出太久沒回報的成員一起移除
- 單一 key 的熱點:Redis Cluster 中一個 key 只在一個節點上。會移動的物件更新頻繁時(10 萬名外送員每 4 秒回報一次,就是每秒 2.5 萬次寫入),可以依 geohash 前綴分成多個 key,代價是靠近邊界的查詢要查多個 key 再合併
資安相關
距離會洩漏位置(三角定位):「附近的同好」顯示「距離 1 公里」看似無害,但攻擊者可以偽造自己的位置,從不同地點反覆查詢,用三個距離畫圓求交點。下面的模擬中,攻擊者只看得到伺服器回傳的距離:
三角定位模擬(
TrilaterationDemo.java)1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117package geo; import java.util.Random; /** 攻擊者可以任意偽造自己的位置,伺服器只回傳「你和對方相距多遠」。光靠這個回答,能把對方定位到多準? */ public class TrilaterationDemo { static final double TARGET_LAT = 25.0418; static final double TARGET_LNG = 121.5503; // 被搜尋者的真實位置,攻擊者不知道 static final double START_LAT = 25.0340; static final double START_LNG = 121.5645; // 攻擊者只知道對方大概在台北 101 附近 interface DistanceApi { double distanceKm(double lat, double lng); // 攻擊者唯一看得到的東西 } static int queries; public static void main(String[] args) { Random random = new Random(7); double[] cell = Geohash.bounds(Geohash.encode(TARGET_LAT, TARGET_LNG, 6)); double snappedLat = (cell[0] + cell[1]) / 2; double snappedLng = (cell[2] + cell[3]) / 2; DistanceApi exact = (lat, lng) -> Math.round(distance(lat, lng, TARGET_LAT, TARGET_LNG) * 1000) / 1000.0; DistanceApi rounded = (lat, lng) -> Math.round(distance(lat, lng, TARGET_LAT, TARGET_LNG)); DistanceApi noisy = (lat, lng) -> distance(lat, lng, TARGET_LAT, TARGET_LNG) + (random.nextDouble() - 0.5); DistanceApi snapped = (lat, lng) -> Math.round(distance(lat, lng, snappedLat, snappedLng)); report("回傳精確距離(到公尺)", averagingAttack(exact, 1)); report("距離四捨五入到整數公里", boundaryAttack(rounded)); report("每次查詢加上 ±500 公尺的隨機誤差", averagingAttack(noisy, 500)); report("先把位置對齊到格子中心,再四捨五入", boundaryAttack(snapped)); System.out.printf("(真實位置與所在 geohash 長度 6 格子中心的距離:%.0f 公尺)%n", distance(TARGET_LAT, TARGET_LNG, snappedLat, snappedLng) * 1000); } static void report(String label, double[] guess) { System.out.printf("查詢 %,5d 次|定位誤差 %,4.0f 公尺|%s%n", queries, distance(guess[0], guess[1], TARGET_LAT, TARGET_LNG) * 1000, label); queries = 0; } /** 從三個位置各查 n 次取平均,再用三個圓求交點。 */ static double[] averagingAttack(DistanceApi api, int n) { double[][] anchors = {{START_LAT, START_LNG}, {START_LAT + 0.02, START_LNG}, {START_LAT, START_LNG - 0.02}}; double[] radii = new double[3]; for (int i = 0; i < 3; i++) { double sum = 0; for (int k = 0; k < n; k++) { sum += query(api, anchors[i]); } radii[i] = sum / n; } return trilaterate(anchors, radii); } /** 沿三個方向移動自己的位置,用二分搜尋找出回答剛好改變的點:那一點和對方的距離正好是 k + 0.5 公里。 */ static double[] boundaryAttack(DistanceApi api) { double[][] centers = new double[3][]; double[] radii = new double[3]; for (int i = 0; i < 3; i++) { double angle = Math.toRadians(90 + 120 * i); double dLat = Math.sin(angle) / 110.574; // 每走 1 公里,緯度與經度各變多少 double dLng = Math.cos(angle) / (111.320 * Math.cos(Math.toRadians(START_LAT))); double first = query(api, new double[] {START_LAT, START_LNG}); double low = 0; double high = 0.25; while (query(api, new double[] {START_LAT + high * dLat, START_LNG + high * dLng}) == first) { low = high; high += 0.25; } double changed = query(api, new double[] {START_LAT + high * dLat, START_LNG + high * dLng}); for (int k = 0; k < 40; k++) { double mid = (low + high) / 2; if (query(api, new double[] {START_LAT + mid * dLat, START_LNG + mid * dLng}) == first) { low = mid; } else { high = mid; } } centers[i] = new double[] {START_LAT + low * dLat, START_LNG + low * dLng}; radii[i] = Math.min(first, changed) + 0.5; } return trilaterate(centers, radii); } static double query(DistanceApi api, double[] position) { queries++; return api.distanceKm(position[0], position[1]); } /** 在幾公里的範圍內把經緯度當成平面座標(公里),三個圓的方程式兩兩相減得到線性方程組。 */ static double[] trilaterate(double[][] centers, double[] r) { double kmPerLng = 111.320 * Math.cos(Math.toRadians(START_LAT)); double[] x = new double[3]; double[] y = new double[3]; for (int i = 0; i < 3; i++) { x[i] = (centers[i][1] - START_LNG) * kmPerLng; y[i] = (centers[i][0] - START_LAT) * 110.574; } double a1 = 2 * (x[1] - x[0]); double b1 = 2 * (y[1] - y[0]); double c1 = r[0] * r[0] - r[1] * r[1] + x[1] * x[1] - x[0] * x[0] + y[1] * y[1] - y[0] * y[0]; double a2 = 2 * (x[2] - x[0]); double b2 = 2 * (y[2] - y[0]); double c2 = r[0] * r[0] - r[2] * r[2] + x[2] * x[2] - x[0] * x[0] + y[2] * y[2] - y[0] * y[0]; double det = a1 * b2 - a2 * b1; double px = (c1 * b2 - c2 * b1) / det; double py = (a1 * c2 - a2 * c1) / det; return new double[] {START_LAT + py / 110.574, START_LNG + px / kmPerLng}; } static double distance(double lat1, double lng1, double lat2, double lng2) { return Geohash.distanceKm(lat1, lng1, lat2, lng2); } }1 2 3 4 5查詢 3 次|定位誤差 3 公尺|回傳精確距離(到公尺) 查詢 134 次|定位誤差 9 公尺|距離四捨五入到整數公里 查詢 1,500 次|定位誤差 8 公尺|每次查詢加上 ±500 公尺的隨機誤差 查詢 153 次|定位誤差 329 公尺|先把位置對齊到格子中心,再四捨五入 (真實位置與所在 geohash 長度 6 格子中心的距離:336 公尺)- 回傳精確距離:3 次查詢就定位到 3 公尺
- 只把輸出四捨五入沒有用:攻擊者移動自己的位置,找出回答從「1 公里」變成「2 公里」的那一點,那一點和對方的距離正好是 1.5 公里。134 次查詢就定位到 9 公尺
- 每次加隨機誤差也沒有用:同一個位置查 500 次取平均,誤差就互相抵銷了
- 有效的做法是在計算之前就降低精度:把被搜尋者的位置對齊到固定格子的中心,而且同一格內保持不變。攻擊者最多只能找到格子中心,誤差就是對齊造成的 300 多公尺。再搭配查詢頻率限制與「不可能的移動速度」檢查,提高邊界搜尋的成本
只能找到願意被找到的人:只把開啟分享的學員放進專用的 key,關閉分享時立刻移除(GEO 成員不會自己過期)。可見性條件要在查詢本身成立,和 全文搜尋篇的道理相同,這是 BOLA 的另一種形態(Part 8)
位置是個資:位置的歷史紀錄可以推出住家與上班地點。只存需要的精度、設定保存期限,log 不要記錄原始座標
用戶端回報的位置可以偽造:模擬定位的 App 隨手可得,GPS 不能當作「人在現場」的證明。實體講座的現場簽到,改用場地螢幕上定時更換的 QR code
何時用/何時別用
- geohash 欄位:資料已經在關聯式資料庫、只需要點的附近搜尋、不想多維運一套系統
- Redis GEO:查詢頻率高、物件會移動、可以接受衍生資料的同步延遲
SPATIAL/PostGIS:需要多邊形(行政區、外送範圍)、路線或其他地理運算- H3:區域統計與熱度分析
- 別用:只有幾百個點(全部載入記憶體直接算距離就好);需要路程距離或到達時間(要用路網與路徑規劃服務)
參考資料
- G. M. Morton, “A Computer Oriented Geodetic Data Base and a New Technique in File Sequencing”, IBM, 1966
- Antonin Guttman, “R-Trees: A Dynamic Index Structure for Spatial Searching”, SIGMOD, 1984
- Redis — GEOADD:https://redis.io/docs/latest/commands/geoadd/
- Redis — GEOSEARCH:https://redis.io/docs/latest/commands/geosearch/
- MySQL 8.4 Reference Manual — SPATIAL Index Optimization:https://dev.mysql.com/doc/refman/8.4/en/spatial-index-optimization.html
- MySQL 8.4 Reference Manual — Functions That Create Geometry Values from WKT Values:https://dev.mysql.com/doc/refman/8.4/en/gis-wkt-functions.html
- S2 Geometry:https://s2geometry.io/
- H3:https://h3geo.org/
- 互動圖解延伸:Dilum Sanjaya,System Design — an interactive course:https://designed-to-scale.vercel.app/
留言討論