[[409485]]

碼老濕，閱讀了你的巧用數(shù)據(jù)類型實(shí)現(xiàn)億級(jí)數(shù)據(jù)統(tǒng)計(jì)之后，我學(xué)會(huì)了如何游刃有余的使用不同的數(shù)據(jù)類型(String、Hash、List、Set、Sorted Set、HyperLogLog、Bitmap)去解決不同場(chǎng)景的統(tǒng)計(jì)問題。

產(chǎn)品經(jīng)理說(shuō)他有一個(gè) idea，為廣大少男少女提供一個(gè)連接彼此的機(jī)會(huì)。

讓處于這最美的年齡的少男少女能在每一個(gè)十二時(shí)辰里能邂逅到那個(gè) Ta。

所以就想開發(fā)一款 App，用戶登陸后能發(fā)現(xiàn)附近的那個(gè) Ta，連接彼此。

我該如何實(shí)現(xiàn)發(fā)現(xiàn)附近的人?我也希望通過這個(gè) App邂逅女神……

記憶中，一個(gè)下班的夜晚，她從人群中輕盈的移動(dòng)著，那高挑苗條的身材像漂浮在空間中的一個(gè)飄逸的音符。她的眼睛充滿清澈的陽(yáng)光和活力，她的雙眸中印著銀河系的星光。

開篇寄語(yǔ)

• 多鍛煉自己的表達(dá)能力，特別是在工作中。很多人說(shuō)「干活的不如那些做 PPT 的」，實(shí)際上老板都不傻，為何他們會(huì)更認(rèn)可那些做 PPT 的?
• 因?yàn)樗麄儚睦习宓慕嵌瓤紤]問題，對(duì)他而言，需要的是一個(gè)「解決方案」。多從一個(gè)創(chuàng)造者的視角去考慮問題，而不是局限在用程序員的視角考慮問題;
• 多想一下這個(gè)東西到底給人提供什么價(jià)值，而不是「我要怎么實(shí)現(xiàn)它」。當(dāng)然，怎么實(shí)現(xiàn)是必須的，但通常不是最重要的。

什么是面向 LBS 應(yīng)用

經(jīng)緯度是經(jīng)度與緯度的合稱組成一個(gè)坐標(biāo)系統(tǒng)。又稱為地理坐標(biāo)系統(tǒng)，它是一種利用三度空間的球面來(lái)定義地球上的空間的球面坐標(biāo)系統(tǒng)，能夠標(biāo)示地球上的任何一個(gè)位置(小數(shù)點(diǎn)后7位，精度可以到1厘米)。

經(jīng)度的范圍在 (-180, 180]，緯度的范圍 在(-90, 90]，緯度正負(fù)以赤道為界，北正南負(fù)，經(jīng)度正負(fù)以本初子午線 (英國(guó)格林尼治天文臺(tái)) 為界，東正西負(fù)。

附近的人 也就是常說(shuō)的 LBS (Location Based Services，基于位置服務(wù))，它圍繞用戶當(dāng)前地理位置數(shù)據(jù)而展開的服務(wù)，為用戶提供精準(zhǔn)的邂逅服務(wù)。

附近的人核心思想如下：

1. 以 “我” 為中心，搜索附近的 Ta;
2. 以 “我” 當(dāng)前的地理位置為準(zhǔn)，計(jì)算出別人和 “我” 之間的距離;
3. 按 “我” 與別人距離的遠(yuǎn)近排序，篩選出離我最近的用戶。

MySQL 實(shí)現(xiàn)

計(jì)算「附近的人」，通過一個(gè)坐標(biāo)計(jì)算這個(gè)坐標(biāo)附近的其他數(shù)據(jù)，按照距離排序，如何下手呢?

以用戶為中心，給定一個(gè) 1000 米作為半徑畫圓，那么圓形區(qū)域內(nèi)的用戶就是我們想要邂逅的「附近的人」。

將經(jīng)緯度存儲(chǔ)到 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)建時(shí)間', 
  PRIMARY KEY (`id`) 
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4; 

可是總不能遍歷所有的「女神」經(jīng)緯度與自己的經(jīng)緯度數(shù)據(jù)計(jì)算在根據(jù)距離排序，這個(gè)計(jì)算量也太大了。

我們可以通過區(qū)域來(lái)過濾出有限「女神」坐標(biāo)數(shù)據(jù)，再對(duì)矩形區(qū)域內(nèi)的數(shù)據(jù)進(jìn)行全量距離計(jì)算再排序，這樣計(jì)算量明顯降低。

如何劃分矩形區(qū)域呢?

”在圓形外套上一個(gè)正方形，根據(jù)用戶經(jīng)、緯度的最大最小值(經(jīng)、緯度 + 距離)，作為篩選條件過濾數(shù)據(jù)，就很容易將正方形內(nèi)的「女神」信息搜索出來(lái)。

多出來(lái)的一些區(qū)域咋辦?

多出來(lái)的這部分區(qū)域內(nèi)的用戶，到圓點(diǎn)的距離一定比圓的半徑要大，那么我們就計(jì)算用戶中心點(diǎn)與正方形內(nèi)所有用戶的距離，篩選出所有距離小于等于半徑的用戶，圓形區(qū)域內(nèi)的所用戶即符合要求的附近的人。

為了滿足高性能的矩形區(qū)域算法，數(shù)據(jù)表需要在經(jīng)緯度坐標(biāo)加上復(fù)合索引 (longitude, latitude)，這樣可以最大優(yōu)化查詢性能。

實(shí)戰(zhàn)

根據(jù)經(jīng)緯度和距離獲取外接矩形最大、最小經(jīng)緯度以及根據(jù)經(jīng)緯度計(jì)算距離使用了一個(gè)第三方類庫(kù)：

<dependency> 
     <groupId>com.spatial4j</groupId> 
     <artifactId>spatial4j</artifactId> 
     <version>0.5</version> 
</dependency> 

獲取到外接矩形后，以矩形的最大最小經(jīng)、緯度值搜索正方形區(qū)域內(nèi)的用戶，再剔除超過指定距離的用戶，就是最終的附近的人。

/** 
 * 獲取附近 x 米的人 
 * 
 * @param distance 搜索距離范圍 單位km 
 * @param userLng  當(dāng)前用戶的經(jīng)度 
 * @param userLat  當(dāng)前用戶的緯度 
 */ 
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); 
} 
 
     /*** 
     * 球面中，兩點(diǎn)間的距離 
     * @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ù)代碼中實(shí)現(xiàn)的，可以看到SQL語(yǔ)句也非常的簡(jiǎn)單。

SELECT * FROM nearby_user 
WHERE 1=1 
AND (longitude BETWEEN #{minlng} AND #{maxlng}) 
AND (latitude BETWEEN #{minlat} AND #{maxlat}) 

但是數(shù)據(jù)庫(kù)查詢性能畢竟有限，如果「附近的人」查詢請(qǐng)求非常多，在高并發(fā)場(chǎng)合，這可能并不是一個(gè)很好的方案。

嘗試 Redis Hash 未果

我們一起分析下 LBS 數(shù)據(jù)的特點(diǎn)：

1. 每個(gè)「女神」都有一個(gè) ID 編號(hào)，每個(gè)ID 對(duì)應(yīng)著經(jīng)緯度信息。
2. 「宅男」登陸 app獲取「心動(dòng)女生」的時(shí)候，app根據(jù)「宅男」的經(jīng)緯度查找附近的「女神」。
3. 獲取到位置符合的「女神」ID 列表后，再?gòu)臄?shù)據(jù)庫(kù)獲取 ID 對(duì)應(yīng)的「女神」信息返回用戶。

數(shù)據(jù)特點(diǎn)就是一個(gè)女神(用戶)對(duì)應(yīng)著一組經(jīng)緯度，讓我想到了 Redis 的 Hash 結(jié)構(gòu)。也就是一個(gè) key(女神 ID) 對(duì)應(yīng)著 一個(gè) value(經(jīng)緯度)。

Hash看起來(lái)好像可以實(shí)現(xiàn)，但是 LBS 應(yīng)用除了記錄經(jīng)緯度以外，還需要對(duì) Hash 集合中的數(shù)據(jù)進(jìn)行范圍查詢，根據(jù)經(jīng)緯度換算成距離排序。

而 Hash 集合的數(shù)據(jù)是無(wú)序的，顯然不可取。

Sorted Set 初見端倪

Sorted Set 類型是是否合適呢?因?yàn)樗梢耘判颉?/p>

Sorted Set 類型也是一個(gè) key對(duì)應(yīng)一個(gè) value，key元素內(nèi)容，而value `就是該元素的權(quán)重分?jǐn)?shù)。

Sorted Set可以根據(jù)元素的權(quán)重分?jǐn)?shù)對(duì)元素排序，這樣看起來(lái)就滿足我們的需求了。

比如，Sorted Set 的元素是「女神ID」，元素對(duì)應(yīng)的權(quán)重 score 是經(jīng)緯度信息。

問題來(lái)了，Sorted Set 元素的權(quán)重值是一個(gè)浮點(diǎn)數(shù)，經(jīng)緯度是經(jīng)度、緯度兩個(gè)值，咋辦呢?能不能將經(jīng)緯度轉(zhuǎn)換成一個(gè)浮點(diǎn)數(shù)呢?

思路對(duì)了，為了實(shí)現(xiàn)對(duì)經(jīng)緯度比較，Redis 采用業(yè)界廣泛使用的 GeoHash 編碼，分別對(duì)經(jīng)度和緯度編碼，最后再把經(jīng)緯度各自的編碼組合成一個(gè)最終編碼。

這樣就實(shí)現(xiàn)了將經(jīng)緯度轉(zhuǎn)換成一個(gè)值，而 Redis 的 GEO 類型的底層數(shù)據(jù)結(jié)構(gòu)用的就是 Sorted Set來(lái)實(shí)現(xiàn)。

我們來(lái)看下 GeoHash 如何將經(jīng)緯度編碼的。

GEOHash 編碼

關(guān)于 GeoHash 可參考 ：https://en.wikipedia.org/wiki/Geohash

GeoHash算法將二維的經(jīng)緯度數(shù)據(jù)映射到一維的整數(shù)，這樣所有的元素都將在掛載到一條線上，距離靠近的二維坐標(biāo)映射到一維后的點(diǎn)之間距離也會(huì)很接近。

當(dāng)我們想要計(jì)算「附近的人時(shí)」，首先將目標(biāo)位置映射到這條線上，然后在這個(gè)一維的線上獲取附近的點(diǎn)就行了。

GeoHash 編碼會(huì)把一個(gè)經(jīng)度值編碼成一個(gè) N 位的二進(jìn)制值，我們來(lái)對(duì)經(jīng)度范圍[-180,180]做 N 次的二分區(qū)操作，其中 N 可以自定義。

在進(jìn)行第一次二分區(qū)時(shí)，經(jīng)度范圍[-180,180]會(huì)被分成兩個(gè)子區(qū)間：[-180,0) 和[0,180](我稱之為左、右分區(qū))。

此時(shí)，我們可以查看一下要編碼的經(jīng)度值落在了左分區(qū)還是右分區(qū)。如果是落在左分區(qū)，我們就用 0 表示;如果落在右分區(qū)，就用 1 表示。

這樣一來(lái)，每做完一次二分區(qū)，我們就可以得到 1 位編碼值(不是0 就是 1)。

再對(duì)經(jīng)度值所屬的分區(qū)再做一次二分區(qū)，同時(shí)再次查看經(jīng)度值落在了二分區(qū)后的左分區(qū)還是右分區(qū)，按照剛才的規(guī)則再做 1 位編碼。當(dāng)做完 N 次的二分區(qū)后，經(jīng)度值就可以用一個(gè) N bit 的數(shù)來(lái)表示了。

所有的地圖元素坐標(biāo)都將放置于唯一的方格中。方格越小，坐標(biāo)越精確。然后對(duì)這些方格進(jìn)行整數(shù)編碼，越是靠近的方格編碼越是接近。

編碼之后，每個(gè)地圖元素的坐標(biāo)都將變成一個(gè)整數(shù)，通過這個(gè)整數(shù)可以還原出元素的坐標(biāo)，整數(shù)越長(zhǎng)，還原出來(lái)的坐標(biāo)值的損失程度就越小。對(duì)于「附近的人」這個(gè)功能而言，損失的一點(diǎn)精確度可以忽略不計(jì)。

比如對(duì)經(jīng)度值等于 169.99 進(jìn)行 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’。

如此，最后我們就得到一個(gè) 4 位的編碼。

而緯度的編碼思路跟經(jīng)度也是一樣的，不再贅述。

合并經(jīng)緯度編碼

假如計(jì)算的經(jīng)緯度編碼分別是 11011 和00101`，目標(biāo)編碼第 0 位則從經(jīng)度第 0 位的值 1 作為目標(biāo)值，目標(biāo)編碼的第 1 位則從緯度第 0 位值 0 作為目標(biāo)值，以此類推：

就這樣，經(jīng)緯度(35.679，114.020)就可以使用 1010011011 表示，而這個(gè)值就可以作為 SortedSet 的權(quán)重值實(shí)現(xiàn)排序。

Redis GEO 實(shí)現(xiàn)

GEO 類型是將經(jīng)緯度的經(jīng)過 GeoHash 編碼的合并值作為 Sorted Set 元素的 score 權(quán)重，Redis 的 GEO 有哪些指令呢?

我們需要把登陸 app 的女生 ID 和對(duì)應(yīng)的經(jīng)緯度存到 Sorted Set 里面。

更多 GEO 類型指令可參考：https://redis.io/commands#geo

GEOADD

Redis 提供了 GEOADD key longitude latitude member 命令，將一組經(jīng)緯度信息和對(duì)應(yīng)的「女神 ID」記錄到 GEO 類型的集合中，如下：一次記錄多個(gè)用戶(蒼井空、波多野結(jié)衣)的經(jīng)緯度信息。

GEOADD girl:localtion 13.361389 38.115556 "蒼井空" 15.087269 37.502669 "波多野結(jié)衣" 

GEORADIUS

我登陸了 app，獲取自己的經(jīng)緯度信息，如何查找以這個(gè)經(jīng)緯度為中心的一定范圍內(nèi)的其他用用戶呢?

Redis GEO類型提供了 GEORADIUS指令：會(huì)根據(jù)輸入的經(jīng)緯度位置，查找以這個(gè)經(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可以實(shí)現(xiàn)讓「女神」信息按照這個(gè)距離自己的經(jīng)緯度由近到遠(yuǎn)排序。

COUNT選項(xiàng)表示指定返回的「女神」數(shù)量，防止附近太多「女神」，節(jié)省帶寬資源。

如果覺得自己需要更多女神，那么可以無(wú)限制，但是需要注意身體，多吃雞蛋補(bǔ)一補(bǔ)。

用戶下線后，如刪除下線的「女神」經(jīng)緯度呢?

”這個(gè)問題問得好，GEO 類型是基于 Sorted Set 實(shí)現(xiàn)的，所以可以借用 ZREM 命令實(shí)現(xiàn)對(duì)地理位置信息的刪除。

比如刪除「蒼井空」的位置信息：

ZREM girl:localtion "蒼井空" 

小結(jié)

GEO 本身并沒有設(shè)計(jì)新的底層數(shù)據(jù)結(jié)構(gòu)，而是直接使用了 Sorted Set 集合類型。

GEO 類型使用 GeoHash 編碼方法實(shí)現(xiàn)了經(jīng)緯度到 Sorted Set 中元素權(quán)重分?jǐn)?shù)的轉(zhuǎn)換，這其中的兩個(gè)關(guān)鍵機(jī)制就是對(duì)二維地圖做區(qū)間劃分，以及對(duì)區(qū)間進(jìn)行編碼。

一組經(jīng)緯度落在某個(gè)區(qū)間后，就用區(qū)間的編碼值來(lái)表示，并把編碼值作為 Sorted Set 元素的權(quán)重分?jǐn)?shù)。

在一個(gè)地圖應(yīng)用中，車的數(shù)據(jù)、餐館的數(shù)據(jù)、人的數(shù)據(jù)可能會(huì)有百萬(wàn)千萬(wàn)條，如果使用 Redis 的 Geo 數(shù)據(jù)結(jié)構(gòu)，它們將全部放在一個(gè) zset 集合中。

在 Redis 的集群環(huán)境中，集合可能會(huì)從一個(gè)節(jié)點(diǎn)遷移到另一個(gè)節(jié)點(diǎn)，如果單個(gè) key 的數(shù)據(jù)過大，會(huì)對(duì)集群的遷移工作造成較大的影響，在集群環(huán)境中單個(gè) key 對(duì)應(yīng)的數(shù)據(jù)量不宜超過 1M，否則會(huì)導(dǎo)致集群遷移出現(xiàn)卡頓現(xiàn)象，影響線上服務(wù)的正常運(yùn)行。

所以，這里建議 Geo 的數(shù)據(jù)使用單獨(dú)的 Redis 集群實(shí)例部署。

如果數(shù)據(jù)量過億甚至更大，就需要對(duì) Geo 數(shù)據(jù)進(jìn)行拆分，按國(guó)家拆分、按省拆分，按市拆分，在人口特大城市甚至可以按區(qū)拆分。

本文轉(zhuǎn)載自微信公眾號(hào)「 碼哥字節(jié)」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系 碼哥字節(jié)公眾號(hào)。