Redis 實戰(zhàn)篇：GEO 助我邂逅附近女神
開篇寄語
多鍛煉自己的表達能力，特別是在工作中。很多人說「干活的不如那些做 PPT 的」，實際上老板都不傻，為何他們會更認可那些做 PPT 的?
因為他們從老板的角度考慮問題，對他而言，需要的是一個「解決方案」。多從一個創(chuàng)造者的視角去考慮問題，而不是局限在用程序員的視角考慮問題;
多想一下這個東西到底給人提供什么價值，而不是「我要怎么實現它」。當然，怎么實現是必須的，但通常不是最重要的。
什么是面向 LBS 應用
經緯度是經度與緯度的合稱組成一個坐標系統。又稱為地理坐標系統，它是一種利用三度空間的球面來定義地球上的空間的球面坐標系統，能夠標示地球上的任何一個位置(小數點后7位，精度可以到1厘米)。
經度的范圍在 (-180, 180]，緯度的范圍 在(-90, 90]，緯度正負以赤道為界，北正南負，經度正負以本初子午線 (英國格林尼治天文臺) 為界，東正西負。
附近的人 也就是常說的 LBS (Location Based Services，基于位置服務)，它圍繞用戶當前地理位置數據而展開的服務，為用戶提供精準的邂逅服務。
附近的人核心思想如下：
以 “我” 為中心，搜索附近的 Ta;
以 “我” 當前的地理位置為準，計算出別人和 “我” 之間的距離;
按 “我” 與別人距離的遠近排序，篩選出離我最近的用戶。
MySQL 實現
計算「附近的人」，通過一個坐標計算這個坐標附近的其他數據，按照距離排序，如何下手呢?
以用戶為中心，給定一個 1000 米作為半徑畫圓，那么圓形區(qū)域內的用戶就是我們想要邂逅的「附近的人」。
將經緯度存儲到 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 '創(chuàng)建時間',
- PRIMARY KEY (`id`)
- ) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;
可是總不能遍歷所有的「女神」經緯度與自己的經緯度數據計算在根據距離排序，這個計算量也太大了。
我們可以通過區(qū)域來過濾出有限「女神」坐標數據，再對矩形區(qū)域內的數據進行全量距離計算再排序，這樣明顯計算量。
如何劃分矩形區(qū)域呢?
在圓形外套上一個正方形，根據用戶經、緯度的最大最小值(經、緯度 + 距離)，作為篩選條件過濾數據，就很容易將正方形內的「女神」信息搜索出來。
多出來的一些區(qū)域咋辦?
多出來的這部分區(qū)域內的用戶，到圓點的距離一定比圓的半徑要大，那么我們就計算用戶中心點與正方形內所有用戶的距離，篩選出所有距離小于等于半徑的用戶，圓形區(qū)域內的所用戶即符合要求的附近的人。
為了滿足高性能的矩形區(qū)域算法，數據表需要在經緯度坐標加上復合索引 (longitude, latitude)，這樣可以最大優(yōu)化查詢性能。
實戰(zhàn)
根據經緯度和距離獲取外接矩形最大、最小經緯度以及根據經緯度計算j距離使用了一個第三方類庫：
- <dependency>
- <groupId>com.spatial4j</groupId>
- <artifactId>spatial4j</artifactId>
- <version>0.5</version>
- </dependency>
獲取到外接矩形后，以矩形的最大最小經、緯度值搜索正方形區(qū)域內的用戶，再剔除超過指定距離的用戶，就是最終的附近的人。
- /**
- * 獲取附近 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;
- }
由于用戶間距離的排序是在業(yè)務代碼中實現的，可以看到SQL語句也非常的簡單。
- SELECT * FROM nearby_user
- WHERE 1=1
- AND (longitude BETWEEN #{minlng} AND #{maxlng})
- AND (latitude BETWEEN #{minlat} AND #{maxlat})
但是數據庫查詢性能畢竟有限，如果「附近的人」查詢請求非常多，在高并發(fā)場合，這可能并不是一個很好的方案。
嘗試 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 采用業(yè)界廣泛使用的 GeoHash 編碼，分別對經度和緯度編碼，最后再把經緯度各自的編碼組合成一個最終編碼。
這樣就實現了將經緯度轉換成一個值，而 Redis 的 GEO 類型的底層數據結構用的就是 Sorted Set來實現。
我們來看下 GeoHash 如何將經緯度編碼的。
GEOHash 編碼
關于 GeoHash 可參考 ：https://en.wikipedia.org/wiki/Geohash
GeoHash算法將二維的經緯度數據映射到一維的整數，這樣所有的元素都將在掛載到一條線上，距離靠近的二維坐標映射到一維后的點之間距離也會很接近。
當我們想要計算「附近的人時」，首先將目標位置映射到這條線上，然后在這個一維的線上獲取附近的點就行了。
GeoHash 編碼會把一個經度值編碼成一個 N 位的二進制值，我們來對經度范圍[-180,180]做 N 次的二分區(qū)操作，其中 N 可以自定義。
在進行第一次二分區(qū)時，經度范圍[-180,180]會被分成兩個子區(qū)間：[-180,0) 和[0,180](我稱之為左、右分區(qū))。
此時，我們可以查看一下要編碼的經度值落在了左分區(qū)還是右分區(qū)。如果是落在左分區(qū)，我們就用 0 表示;如果落在右分區(qū)，就用 1 表示。
這樣一來，每做完一次二分區(qū)，我們就可以得到 1 位編碼值(不是0 就是 1)。
再對經度值所屬的分區(qū)再做一次二分區(qū)，同時再次查看經度值落在了二分區(qū)后的左分區(qū)還是右分區(qū)，按照剛才的規(guī)則再做 1 位編碼。當做完 N 次的二分區(qū)后，經度值就可以用一個 N bit 的數來表示了。
所有的地圖元素坐標都將放置于唯一的方格中。方格越小，坐標越精確。然后對這些方格進行整數編碼，越是靠近的方格編碼越是接近。
編碼之后，每個地圖元素的坐標都將變成一個整數，通過這個整數可以還原出元素的坐標，整數越長，還原出來的坐標值的損失程度就越小。對于「附近的人」這個功能而言，損失的一點精確度可以忽略不計。
比如對經度值等于 169.99 進行 4 位編碼(N = 4，做 4 次分區(qū)),把經度區(qū)間[-180,180]分成了左分區(qū)[-180,0) 和右分區(qū)[0,180]。
169.99 屬于右分區(qū)，使用 1 表示第一次分區(qū)編碼;
再將 169.99 經過第一次劃分所屬的 [0, 180] 區(qū)間繼續(xù)分成 [0, 90) 和 [90, 180]，169.99 依然在右區(qū)間，編碼 ‘1’。
將[90, 180] 分為[90, 135) 和 [135, 180]，這次落在左分區(qū)，編碼 ‘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 girlo:locations 15.087269 37.502669 km ASC COUNT 10
ASC可以實現讓「女神」信息按照這個距離自己的經緯度由近到遠排序。
COUNT選項表示指定返回的「女神」數量，防止附近太多「女神」，節(jié)省帶寬資源。
如果覺得自己需要更多女神，那么可以無限制，但是需要注意身體，多吃雞蛋補一補。
用戶下線后，如刪除下線的「女神」經緯度呢?
這個問題問得好，GEO 類型是基于 Sorted Set 實現的，所以可以借用 ZREM 命令實現對地理位置信息的刪除。
比如刪除「蒼井空」的位置信息：
- ZREM girl:localtion "蒼井空"
小結
GEO 本身并沒有設計新的底層數據結構，而是直接使用了 Sorted Set 集合類型。
GEO 類型使用 GeoHash 編碼方法實現了經緯度到 Sorted Set 中元素權重分數的轉換，這其中的兩個關鍵機制就是對二維地圖做區(qū)間劃分，以及對區(qū)間進行編碼。
一組經緯度落在某個區(qū)間后，就用區(qū)間的編碼值來表示，并把編碼值作為 Sorted Set 元素的權重分數。
在一個地圖應用中，車的數據、餐館的數據、人的數據可能會有百萬千萬條，如果使用 Redis 的 Geo 數據結構，它們將全部放在一個 zset 集合中。
在 Redis 的集群環(huán)境中，集合可能會從一個節(jié)點遷移到另一個節(jié)點，如果單個 key 的數據過大，會對集群的遷移工作造成較大的影響，在集群環(huán)境中單個 key 對應的數據量不宜超過 1M，否則會導致集群遷移出現卡頓現象，影響線上服務的正常運行。
所以，這里建議 Geo 的數據使用單獨的 Redis 集群實例部署。
如果數據量過億甚至更大，就需要對 Geo 數據進行拆分，按國家拆分、按省拆分，按市拆分，在人口特大城市甚至可以按區(qū)拆分。
