交友系統設計：哪種地理空間鄰近算法更快？

小熊學Java：https://javaxiaobear.cn

交友與婚戀是人們最基本的需求之一。隨著互聯網時代的不斷發展，移動社交軟件已經成為了人們生活中必不可少的一部分。然而，熟人社交并不能完全滿足年輕人的社交與情感需求，于是陌生人交友平臺悄然興起。

我們決定開發一款基于地理位置服務（LBS）的應用，為用戶匹配鄰近的、互相感興趣的好友，應用名稱為“Liao”。

Liao 面臨的技術挑戰包括：面對海量的用戶，如何為其快速找到鄰近的人，可以選擇的地理空間鄰近算法有哪些？Liao 如何在這些算法中選擇出最合適的那個？

1、需求分析

Liao 的客戶端是一個移動 App，用戶打開 App 后，上傳、編輯自己的基本信息，然后系統（推薦算法）根據其地理位置和個人信息，為其推薦位置鄰近的用戶。用戶在手機上查看對方的照片和資料，如果感興趣，希望進一步聯系，就向右滑動照片；如果不感興趣，就向左滑動照片。

如果兩個人都向右滑動了對方，就表示他們互相感興趣。系統就通知他們配對成功，并為他們開啟聊天功能，可以更進一步了解對方，決定是否建立更深入的關系。Liao 的功能用例圖如下：

用戶規模分析

Liao 的目標用戶是全球范圍內的中青年單身男女，預估目標用戶超過 10 億，系統按 10 億用戶進行設計。

2、概要設計

Liao 的系統架構采用典型的微服務架構設計方案，用戶通過網關服務器訪問具體的微服務，如下圖：

可知，首先，用戶所有請求都通過統一的網關服務器處理。網關服務器負責限流、防攻擊、用戶身份識別及權限驗證、微服務調用及數據聚合封裝等，而真正的業務邏輯則通過訪問微服務來完成。Liao 的關鍵微服務有：用戶微服務、圖片微服務、配對微服務、聊天微服務、推薦微服務、鄰近算法微服務等。Liao 的網關預計將承擔每天百億次規模的訪問壓力。

用戶微服務管理用戶的個人信息、興趣愛好以及交友偏好等，此外也負責用戶登錄服務，只有登錄用戶才能訪問系統。因為需要存儲十億條用戶數據，所以用戶數據庫采用分片的MySQL 數據庫。

圖片微服務用于管理用戶照片，提供用戶照片存儲及展示的功能。Liao 需要存儲的圖片數大約幾百億張。我們使用 Nginx 作為圖片服務器，圖片服務器可以線性擴容，每寫滿一臺服務器（及其 Slave 服務器），就繼續寫入下一臺服務器。服務器 IP、圖片路徑則記錄在用戶數據庫中。同時，購買 CDN 服務，緩存熱門的用戶照片。

配對微服務負責將互相喜歡的用戶配對，通知用戶，并加入彼此的通訊錄中。用戶每次右劃操作都調用該微服務。系統設置一個用戶每天可以喜歡（右劃）的人是有上限的，但是，對于活躍用戶而言，長期積累下來，喜歡的人的數量還是非常大的，因此配對微服務會將數據發送給一個流式大數據引擎進行計算。

推薦微服務負責向用戶展示其可能感興趣的、鄰近的用戶。因此，一方面，推薦微服務需要根據用戶操作、個人興趣、交友偏好調用協同過濾等推薦算法進行推薦，另一方面必須保證推薦的用戶在當前用戶的附近。

3、詳細設計

詳細設計主要關注鄰近位置算法，也就是，如何根據用戶的地理位置尋找距其一定范圍內的其他用戶。

我們可以通過 Liao App 獲取用戶當前經、緯度坐標，然后根據經、緯度，計算兩個用戶之間的距離，距離計算公式采用半正矢公式：

其中 r 代表地球半徑，表示緯度，表示經度。

但是，當我們有 10 億用戶的時候，如果每次進行當前用戶匹配都要和其他所有用戶做一次距離計算，然后再進行排序，那么需要的計算量至少也是千億級別，這樣的計算量是我們不能承受的。通常的空間鄰近算法有以下 4 種，我們一一進行分析，最終選擇出最合適的方案。

1、SQL 鄰近算法

我們可以將用戶經、緯度直接記錄到數據庫中，緯度記錄在 latitude 字段，經度記錄在longitude 字段，用戶當前的緯度和經度為 X，Y，如果我們想要查找和當前用戶經、緯度距離 D 之內的其他用戶，可以通過如下 SQL 實現。

select * from users where latitude between X-D and X+D and longtitude between

這樣的 SQL 實現起來比較簡單，但是如果有十億用戶，數據分片在幾百臺服務器上，SQL執行效率就會很低。而且我們用經、緯度距離進行近似計算，在高緯度地區，這種近似計算的偏差還是非常大的。

同時“between X-D and X+D”以及“between Y-D and Y+D”也會產生大量中間計算數據，這兩個 betwen 會先返回經度和緯度各自區間內的所有用戶，再進行交集 and 處理，如下圖。

我們的用戶量非常大，而計算鄰近好友又是一個非常高頻的訪問，同時，分片數據庫進行集合計算需要在中間代理服務器或應用程序服務器完成計算，因此，這樣的交集計算帶來計算負載壓力是我們的系統完全不能承受的。所以這個方案可以被放棄。

2、地理網格鄰近算法

為了減少上述交集計算使用的中間數據量，我們將整個地球用網格進行劃分，如下圖：

事實上，我們劃分的網格遠比圖中示意的要密集得多，赤道附近，經、緯度方向每 10 公里一個網格。

這樣每個用戶必然會落入到一個網格中，我們在用戶表中記錄用戶所在的網格ID（gridID），然后借助這個字段進行輔助查找，將查找范圍限制在用戶所在的網格（gridIDx0）及其周圍 8 個網格（gridIDx1 ~ gridIDx8）中，可以極大降低中間數據量，SQL 如下：

select * from users where latitude between X-D and X+D and longtitude between

這條 SQL 要比上面 SQL 的計算負載壓力小得多，但是對于高頻訪問的分片數據庫而言，用這樣的 SQL 進行鄰近好友查詢依然是不能承受的，同樣距離精度也不滿足要求。

但是基于這種網格設計思想，我們發現，我們可以不通過數據庫就能實現鄰近好友查詢：我們可以將所有的網格及其包含的用戶都記錄在內存中。當我們進行鄰近查詢時，只需要在內存中計算用戶及其鄰近的 8 個網格內的所有用戶的距離即可。

我們可以估算下所有用戶經、緯度都加載到內存中需要的內存量：1G × 3 × 4B = 12GB（用戶 ID、經度、緯度，都采用 4 個字節編碼，總用戶數 1G）。這個內存量是完全可以接受的。

實際上，通過恰當地選擇網格的大小，我們不停訪問當前用戶位置周邊的網格就可以由近及遠不斷得到鄰近的其他用戶，而不需要再通過 SQL 來得到。那么如何選擇網格大小？如何根據用戶位置得到其所在的網格？又如何得到當前用戶位置周邊的其他網格呢？我們看
下實踐中更常用的動態網格和 GeoHash 算法。

3、動態網格算法

事實上，不管如何選擇網格大小，可能都不合適。因為在陸家嘴即使很小的網格可能就包含近百萬的用戶，而在可可西里，非常大的網格也包含不了幾個用戶。

因此，我們希望能夠動態設定網格的大小，如果一個網格內用戶太多，就把它分裂成幾個小網格，小網格內如果用戶還是太多，繼續分裂更小的網格，如下圖：

這是一個四叉樹網格結構，開始的時候整個地球只有一個網格，當用戶增加，超過閾值（500 個用戶）的時候，就分裂出 4 個子樹，4 個子樹對應父節點網格的 4 個地理子網格。同時，將用戶根據位置信息重新分配到 4 個子樹中。同樣，如圖中所示，如果某個子樹中的用戶增加，超過了閾值，該子樹繼續分裂成 4 個子樹。

因此，我們可以將全球用戶分配在這樣一個 4 叉樹網格結構中，所有的用戶都必然在這個4 叉樹的葉子節點中，而且每個節點內包含的用戶數不超過 500 個。那么，陸家嘴的網格可能就會很小，而可可西里的網格就會很大，太平洋對應的網格可能有幾千公里。

當給定當前用戶的經、緯度，查詢鄰近用戶的時候，首先從根節點開始查找，如果根節點就是葉子節點，那么直接遍歷根節點中的所有用戶，計算距離即可。如果根節點不是葉子節點，那么根據給定的經、緯度判斷其在網格中的位置，左上、右上、右下、左下，4 個位置，順序對應 4 個子樹，根據網格位置訪問對應的子樹。如果子樹是葉子節點，那么在葉子節點中查找，如果不是葉子節點，繼續上面的過程，直到葉子節點。

上面的過程只能找到當前用戶所在網格的好友，如何查找鄰近網格的其他用戶呢？事實上，我們只需要將 4 叉樹所有的葉子節點順序組成一個雙向鏈表，每個節點在鏈表上的若干個前驅和后繼節點正好就是其地理位置鄰近的節點。

動態網格也叫 4 叉樹網格，在空間鄰近算法中較為常用，也能滿足 Liao 的需求。但是編程實現稍稍有點麻煩，而且如果網格大小設計不合適，導致樹的高度太高，每次查找需要遍歷的路徑太長，性能結果也比較差。我們再看下性能和靈活性更好的 GeoHash 算法。

4、GeoHash 算法

除了動態網格算法，GeoHash 事實上是另外一種變形了的網格算法，同時也是 Redis 中Geo 函數使用的算法。GeoHash 是將網格進行編碼，然后根據編碼進行 Hash 存儲的一種算法。

經、緯度數字的不同精度，意味著經、緯度的誤差范圍，比如保留經、緯度到小數點后第1 位，那么誤差范圍最大可能會達到 11 公里（在赤道附近）。也就是說，小數點后 1 位精度的經、緯度，其覆蓋范圍是一個 11km * 11km 的網格。

那么，我們用小數點后 1 位精度的經、緯度做 key，網格內的用戶集合做 value，就可以構建一個 Hash 表的 <key, value> 對。通過查找這個 KV 對及其周圍 8 個網格的 KV 對，計算這些 value 內所有用戶和當前用戶的距離，就可以找到鄰近 11 公里內的所有用戶。

實踐中，redis 的 GeoHash 并不會直接用經、緯度做 key，而是采用一種基于 Z 階曲線的編碼方式，將二維的經、緯度，轉化為一維的二進制數字，再進行 base32 編碼，具體過程如下：

首先，分別針對經度和緯度，求取當前區間（對于緯度而言，開始的區間就是[-90, 90], 對于經度而言，開始區間就是[-180, 180]）的平均值，將當前區間分為兩個區間。然后用用戶的經、緯度和區間平均值進行比較，用戶經、緯度必然落在兩個區間中的一個，如果大于平均值，那么取 1，如果小于平均值，那么取 0。
繼續求取當前區間的平均值，進一步將當前區間分為兩個區間。如此不斷重復，可以在經度和緯度方向上，得到兩個二進制數。這個二進制數越長，其所在的區間越小，精度越高。

下圖表示經、緯度 <43.60411, -5.59041> 的二進制編碼過程，最終得到緯度 12 位編碼，經度 13 位編碼。

得到兩個二進制數后，再將它們合并成一個二進制數。合并規則是，從第一位開始，奇數位為經度，偶數位為緯度，上面例子合并后的結果為 01101 11111 11000 00100 00010，共 25 位二進制數。
將 25 位二進制數劃分成 5 組，每組 5 個二進制數，對應的 10 進制數是 0-31，采用Base32 編碼，可以得到一個 5 位字符串，Base32 編碼表如下：

編碼計算過程如下：
最后得到一個字符串“ezs42”，作為 Hash 表的 key。25 位二進制的 GeoHash 編碼，其誤差范圍大概 2.4 公里，即對應一個2.4km * 2.4km 的網格。網格內的用戶都作為value 放入到 Hash 表中。

一般說來，通過選擇 GeoHash 的編碼長度，實現不同大小的網格，就可以滿足我們鄰近交友的應用場景了。但是在 Redis 中，需要面對更通用的地理位置計算場景，所以 Redis中的 GeoHash 并沒有用 Hash 表存儲，而是用跳表存儲。

Redis 使用 52 位二進制的 GeoHash 編碼，誤差范圍 0.6 米。Redis 將編碼后的二進制數按照 Z 階曲線的布局，進行一維化展開。即將二維的經、緯度上的點，用一條 Z 型曲線連接起來，Z 階曲線布局示例如下圖。

事實上，所謂的 Z 階曲線布局，本質其實就是基于 GeoHash 的二進制排序。將這些經過編碼的 2 進制數據用跳表存儲。查找用戶的時候，可以快速找到該用戶，沿著跳表前后檢索，得到的就是鄰近的用戶。

5、Liao 的最終算法選擇

Liao 的鄰近算法最終選擇使用 Hash 表存儲的 GeoHash 算法，經度采用 13bit 編碼，緯度采用 12bit 編碼，即最后的 GeoHash 編碼 5 個字符，每個網格 2.4km * 2.4km = 5km，將整個地球分為個網格，去掉海洋和幾乎無人生存的荒漠極地，需要存儲的 Hash 鍵不到 500 萬個，采用 Hash 表存儲。Hash 表的 key 是 GeoHash 編碼，value 是一個 List，其中包含了所有相同 GeoHash 編碼的用戶 ID。

查找鄰近好友的時候，Liao 將先計算用戶當前位置的 GeoHash 值（5 個字符），然后從Hash 表中讀取該 Hash 值對應的所有用戶，即在同一個網格內的用戶，進行匹配，將滿足匹配條件的對象返回給用戶。如果一個網格內匹配的對象數量不足，計算周圍 8 個網格的GeoHash 值，讀取這些 Hash 值對應的用戶列表，繼續匹配。