Redis 實戰篇：通過 Geo 類型實現附近的人邂逅女神
碼老濕，閱讀了你的巧用數據類型實現億級數據統計之后，我學會了如何游刃有余的使用不同的數據類型(String、Hash、List、Set、Sorted Set、HyperLogLog、Bitmap)去解決不同場景的統計問題。
產品經理說他有一個 idea，為廣大少男少女提供一個連接彼此的機會。
讓處于這最美的年齡的少男少女能在每一個十二時辰里能邂逅到那個 Ta。
所以就想開發一款 App，用戶登陸后能發現附近的那個 Ta，連接彼此。
我該如何實現發現附近的人?我也希望通過這個 App邂逅女神……
記憶中，一個下班的夜晚，她從人群中輕盈的移動著，那高挑苗條的身材像漂浮在空間中的一個飄逸的音符。她的眼睛充滿清澈的陽光和活力，她的雙眸中印著銀河系的星光。
開篇寄語
- 多鍛煉自己的表達能力，特別是在工作中。很多人說「干活的不如那些做 PPT 的」，實際上老板都不傻，為何他們會更認可那些做 PPT 的?
- 因為他們從老板的角度考慮問題，對他而言，需要的是一個「解決方案」。多從一個創造者的視角去考慮問題，而不是局限在用程序員的視角考慮問題;
- 多想一下這個東西到底給人提供什么價值，而不是「我要怎么實現它」。當然，怎么實現是必須的，但通常不是最重要的。
什么是面向 LBS 應用
經緯度是經度與緯度的合稱組成一個坐標系統。又稱為地理坐標系統，它是一種利用三度空間的球面來定義地球上的空間的球面坐標系統，能夠標示地球上的任何一個位置(小數點后7位，精度可以到1厘米)。
經度的范圍在 (-180, 180]，緯度的范圍 在(-90, 90]，緯度正負以赤道為界，北正南負，經度正負以本初子午線 (英國格林尼治天文臺) 為界，東正西負。
附近的人 也就是常說的 LBS (Location Based Services，基于位置服務)，它圍繞用戶當前地理位置數據而展開的服務，為用戶提供精準的邂逅服務。
附近的人核心思想如下：
- 以 “我” 為中心，搜索附近的 Ta;
- 以 “我” 當前的地理位置為準，計算出別人和 “我” 之間的距離;
- 按 “我” 與別人距離的遠近排序，篩選出離我最近的用戶。
MySQL 實現
計算「附近的人」，通過一個坐標計算這個坐標附近的其他數據，按照距離排序，如何下手呢?
以用戶為中心，給定一個 1000 米作為半徑畫圓，那么圓形區域內的用戶就是我們想要邂逅的「附近的人」。
將經緯度存儲到 MySQL：
- CREATE TABLE `nearby_user` (
- `id` int(11) NOT NULL AUTO_INCREMENT,
- `name` varchar(255) DEFAULT NULL COMMENT '名稱',
- `longitude` double DEFAULT NULL COMMENT '經度',
- `latitude` double DEFAULT NULL COMMENT '緯度',
- `create_time` datetime DEFAULT NULL ON UPDATE CURRENT_TIMESTAMP COMMENT '創建時間',
- PRIMARY KEY (`id`)
- ) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;
可是總不能遍歷所有的「女神」經緯度與自己的經緯度數據計算在根據距離排序，這個計算量也太大了。
我們可以通過區域來過濾出有限「女神」坐標數據，再對矩形區域內的數據進行全量距離計算再排序，這樣計算量明顯降低。
如何劃分矩形區域呢?
”在圓形外套上一個正方形，根據用戶經、緯度的最大最小值(經、緯度 + 距離)，作為篩選條件過濾數據，就很容易將正方形內的「女神」信息搜索出來。
多出來的一些區域咋辦?
多出來的這部分區域內的用戶，到圓點的距離一定比圓的半徑要大，那么我們就計算用戶中心點與正方形內所有用戶的距離，篩選出所有距離小于等于半徑的用戶，圓形區域內的所用戶即符合要求的附近的人。
為了滿足高性能的矩形區域算法，數據表需要在經緯度坐標加上復合索引 (longitude, latitude)，這樣可以最大優化查詢性能。
實戰
根據經緯度和距離獲取外接矩形最大、最小經緯度以及根據經緯度計算距離使用了一個第三方類庫：
- <dependency>
- <groupId>com.spatial4j</groupId>
- <artifactId>spatial4j</artifactId>
- <version>0.5</version>
- </dependency>
獲取到外接矩形后，以矩形的最大最小經、緯度值搜索正方形區域內的用戶，再剔除超過指定距離的用戶，就是最終的附近的人。
- /**
- * 獲取附近 x 米的人
- *
- * @param distance 搜索距離范圍 單位km
- * @param userLng 當前用戶的經度
- * @param userLat 當前用戶的緯度
- */
- public String nearBySearch(double distance, double userLng, double userLat) {
- //1.獲取外接正方形
- Rectangle rectangle = getRectangle(distance, userLng, userLat);
- //2.獲取位置在正方形內的所有用戶
- List<User> users = userMapper.selectUser(rectangle.getMinX(), rectangle.getMaxX(), rectangle.getMinY(), rectangle.getMaxY());
- //3.剔除半徑超過指定距離的多余用戶
- users = users.stream()
- .filter(a -> getDistance(a.getLongitude(), a.getLatitude(), userLng, userLat) <= distance)
- .collect(Collectors.toList());
- return JSON.toJSONString(users);
- }
- // 獲取外接矩形
- private Rectangle getRectangle(double distance, double userLng, double userLat) {
- return spatialContext.getDistCalc()
- .calcBoxByDistFromPt(spatialContext.makePoint(userLng, userLat),
- distance * DistanceUtils.KM_TO_DEG, spatialContext, null);
- }
- /***
- * 球面中，兩點間的距離
- * @param longitude 經度1
- * @param latitude 緯度1
- * @param userLng 經度2
- * @param userLat 緯度2
- * @return 返回距離，單位km
- */
- private double getDistance(Double longitude, Double latitude, double userLng, double userLat) {
- return spatialContext.calcDistance(spatialContext.makePoint(userLng, userLat),
- spatialContext.makePoint(longitude, latitude)) * DistanceUtils.DEG_TO_KM;
- }
由于用戶間距離的排序是在業務代碼中實現的，可以看到SQL語句也非常的簡單。
- SELECT * FROM nearby_user
- WHERE 1=1
- AND (longitude BETWEEN #{minlng} AND #{maxlng})
- AND (latitude BETWEEN #{minlat} AND #{maxlat})
但是數據庫查詢性能畢竟有限，如果「附近的人」查詢請求非常多，在高并發場合，這可能并不是一個很好的方案。
嘗試 Redis Hash 未果
我們一起分析下 LBS 數據的特點：
- 每個「女神」都有一個 ID 編號，每個ID 對應著經緯度信息。
- 「宅男」登陸 app獲取「心動女生」的時候，app根據「宅男」的經緯度查找附近的「女神」。
- 獲取到位置符合的「女神」ID 列表后，再從數據庫獲取 ID 對應的「女神」信息返回用戶。
數據特點就是一個女神(用戶)對應著一組經緯度，讓我想到了 Redis 的 Hash 結構。也就是一個 key(女神 ID) 對應著 一個 value(經緯度)。
Hash看起來好像可以實現，但是 LBS 應用除了記錄經緯度以外，還需要對 Hash 集合中的數據進行范圍查詢，根據經緯度換算成距離排序。
而 Hash 集合的數據是無序的，顯然不可取。
Sorted Set 初見端倪
Sorted Set 類型是是否合適呢?因為它可以排序。
Sorted Set 類型也是一個 key對應一個 value，key元素內容，而value `就是該元素的權重分數。
Sorted Set可以根據元素的權重分數對元素排序，這樣看起來就滿足我們的需求了。
比如，Sorted Set 的元素是「女神ID」，元素對應的權重 score 是經緯度信息。
問題來了，Sorted Set 元素的權重值是一個浮點數，經緯度是經度、緯度兩個值，咋辦呢?能不能將經緯度轉換成一個浮點數呢?
思路對了，為了實現對經緯度比較，Redis 采用業界廣泛使用的 GeoHash 編碼，分別對經度和緯度編碼，最后再把經緯度各自的編碼組合成一個最終編碼。
這樣就實現了將經緯度轉換成一個值，而 Redis 的 GEO 類型的底層數據結構用的就是 Sorted Set來實現。
我們來看下 GeoHash 如何將經緯度編碼的。
GEOHash 編碼
關于 GeoHash 可參考 ：https://en.wikipedia.org/wiki/Geohash
GeoHash算法將二維的經緯度數據映射到一維的整數，這樣所有的元素都將在掛載到一條線上，距離靠近的二維坐標映射到一維后的點之間距離也會很接近。
當我們想要計算「附近的人時」，首先將目標位置映射到這條線上，然后在這個一維的線上獲取附近的點就行了。
GeoHash 編碼會把一個經度值編碼成一個 N 位的二進制值，我們來對經度范圍[-180,180]做 N 次的二分區操作，其中 N 可以自定義。
在進行第一次二分區時，經度范圍[-180,180]會被分成兩個子區間：[-180,0) 和[0,180](我稱之為左、右分區)。
此時，我們可以查看一下要編碼的經度值落在了左分區還是右分區。如果是落在左分區，我們就用 0 表示;如果落在右分區，就用 1 表示。
這樣一來，每做完一次二分區，我們就可以得到 1 位編碼值(不是0 就是 1)。
再對經度值所屬的分區再做一次二分區，同時再次查看經度值落在了二分區后的左分區還是右分區，按照剛才的規則再做 1 位編碼。當做完 N 次的二分區后，經度值就可以用一個 N bit 的數來表示了。
所有的地圖元素坐標都將放置于唯一的方格中。方格越小，坐標越精確。然后對這些方格進行整數編碼，越是靠近的方格編碼越是接近。
編碼之后，每個地圖元素的坐標都將變成一個整數，通過這個整數可以還原出元素的坐標，整數越長，還原出來的坐標值的損失程度就越小。對于「附近的人」這個功能而言，損失的一點精確度可以忽略不計。
比如對經度值等于 169.99 進行 4 位編碼(N = 4，做 4 次分區),把經度區間[-180,180]分成了左分區[-180,0) 和右分區[0,180]。
- 169.99 屬于右分區，使用 1 表示第一次分區編碼;
- 再將 169.99 經過第一次劃分所屬的 [0, 180] 區間繼續分成 [0, 90) 和 [90, 180]，169.99 依然在右區間，編碼 ‘1’。
- 將[90, 180] 分為[90, 135) 和 [135, 180]，這次落在左分區，編碼 ‘0’。
如此，最后我們就得到一個 4 位的編碼。
而緯度的編碼思路跟經度也是一樣的，不再贅述。
合并經緯度編碼
假如計算的經緯度編碼分別是 11011 和00101`，目標編碼第 0 位則從經度第 0 位的值 1 作為目標值，目標編碼的第 1 位則從緯度第 0 位值 0 作為目標值，以此類推：
就這樣，經緯度(35.679，114.020)就可以使用 1010011011 表示，而這個值就可以作為 SortedSet 的權重值實現排序。
Redis GEO 實現
GEO 類型是將經緯度的經過 GeoHash 編碼的合并值作為 Sorted Set 元素的 score 權重，Redis 的 GEO 有哪些指令呢?
我們需要把登陸 app 的女生 ID 和對應的經緯度存到 Sorted Set 里面。
更多 GEO 類型指令可參考：https://redis.io/commands#geo
GEOADD
Redis 提供了 GEOADD key longitude latitude member 命令，將一組經緯度信息和對應的「女神 ID」記錄到 GEO 類型的集合中，如下：一次記錄多個用戶(蒼井空、波多野結衣)的經緯度信息。
- GEOADD girl:localtion 13.361389 38.115556 "蒼井空" 15.087269 37.502669 "波多野結衣"
GEORADIUS
我登陸了 app，獲取自己的經緯度信息，如何查找以這個經緯度為中心的一定范圍內的其他用用戶呢?
Redis GEO類型提供了 GEORADIUS指令：會根據輸入的經緯度位置，查找以這個經緯度為中心的一定范圍內的其他元素。
假設自己的經緯度是(15.087269 37.502669)，需要獲取附近 10 km 的「女神」并返回給 LBS 應用：
- GEORADIUS girl:locations 15.087269 37.502669 km ASC COUNT 10
ASC可以實現讓「女神」信息按照這個距離自己的經緯度由近到遠排序。
COUNT選項表示指定返回的「女神」數量，防止附近太多「女神」，節省帶寬資源。
如果覺得自己需要更多女神，那么可以無限制，但是需要注意身體，多吃雞蛋補一補。
用戶下線后，如刪除下線的「女神」經緯度呢?
”這個問題問得好，GEO 類型是基于 Sorted Set 實現的，所以可以借用 ZREM 命令實現對地理位置信息的刪除。
比如刪除「蒼井空」的位置信息：
- ZREM girl:localtion "蒼井空"
小結
GEO 本身并沒有設計新的底層數據結構，而是直接使用了 Sorted Set 集合類型。
GEO 類型使用 GeoHash 編碼方法實現了經緯度到 Sorted Set 中元素權重分數的轉換，這其中的兩個關鍵機制就是對二維地圖做區間劃分，以及對區間進行編碼。
一組經緯度落在某個區間后，就用區間的編碼值來表示，并把編碼值作為 Sorted Set 元素的權重分數。
在一個地圖應用中，車的數據、餐館的數據、人的數據可能會有百萬千萬條，如果使用 Redis 的 Geo 數據結構，它們將全部放在一個 zset 集合中。
在 Redis 的集群環境中，集合可能會從一個節點遷移到另一個節點，如果單個 key 的數據過大，會對集群的遷移工作造成較大的影響，在集群環境中單個 key 對應的數據量不宜超過 1M，否則會導致集群遷移出現卡頓現象，影響線上服務的正常運行。
所以，這里建議 Geo 的數據使用單獨的 Redis 集群實例部署。
如果數據量過億甚至更大，就需要對 Geo 數據進行拆分，按國家拆分、按省拆分，按市拆分，在人口特大城市甚至可以按區拆分。
本文轉載自微信公眾號「 碼哥字節」，可以通過以下二維碼關注。轉載本文請聯系 碼哥字節公眾號。
