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