Redis 的 GeoHash詳解

Redis 在 3.2 版本以后增加了地理位置 GEO 模塊，意味著我們可以使用 Redis 來實(shí)現(xiàn)摩拜單車「附近的 Mobike」、美團(tuán)和餓了么「附近的餐館」這樣的功能了。

用數(shù)據(jù)庫來算附近的人

地圖元素的位置數(shù)據(jù)使用二維的經(jīng)緯度表示，經(jīng)度范圍 (-180, 180]，緯度范圍 (-90, 90]，緯度正負(fù)以赤道為界，北正南負(fù)，經(jīng)度正負(fù)以本初子午線 (英國格林尼治天文臺) 為界，東正西負(fù)。比如掘金辦公室在望京 SOHO，它的經(jīng)緯度坐標(biāo)是 (116.48105,39.996794)，都是正數(shù)，因?yàn)橹袊挥跂|北半球。

當(dāng)兩個(gè)元素的距離不是很遠(yuǎn)時(shí)，可以直接使用勾股定理就能算得元素之間的距離。我們平時(shí)使用的「附近的人」的功能，元素距離都不是很大，勾股定理算距離足矣。不過需要注意的是，經(jīng)緯度坐標(biāo)的密度不一樣 (經(jīng)度總共 360 度，緯度總共 180 度)，勾股定律計(jì)算平方差時(shí)之后再求和時(shí)，需要按一定的系數(shù)比加權(quán)求和。

現(xiàn)在，如果要計(jì)算「附近的人」，也就是給定一個(gè)元素的坐標(biāo)，然后計(jì)算這個(gè)坐標(biāo)附近的其它元素，按照距離進(jìn)行排序，該如何下手？

如果現(xiàn)在元素的經(jīng)緯度坐標(biāo)使用關(guān)系數(shù)據(jù)庫 (元素 id, 經(jīng)度 x, 緯度 y) 存儲，你該如何計(jì)算？

首先，你不可能通過遍歷來計(jì)算所有的元素和目標(biāo)元素的距離然后再進(jìn)行排序，這個(gè)計(jì)算量太大了，性能指標(biāo)肯定無法滿足。一般的方法都是通過矩形區(qū)域來限定元素的數(shù)量，然后對區(qū)域內(nèi)的元素進(jìn)行全量距離計(jì)算再排序。這樣可以明顯減少計(jì)算量。如何劃分矩形區(qū)域呢？可以指定一個(gè)半徑 r，使用一條 SQL 就可以圈出來。當(dāng)用戶對篩出來的結(jié)果不滿意，那就擴(kuò)大半徑繼續(xù)篩選。

select id from positions where x0-r  x  x0+r and y0-r  y  y0+r

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

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

GeoHash 算法

業(yè)界比較通用的地理位置距離排序算法是 GeoHash 算法，Redis 也使用 GeoHash 算法。GeoHash 算法將二維的經(jīng)緯度數(shù)據(jù)映射到一維的整數(shù)，這樣所有的元素都將在掛載到一條線上，距離靠近的二維坐標(biāo)映射到一維后的點(diǎn)之間距離也會(huì)很接近。當(dāng)我們想要計(jì)算「附近的人時(shí)」，首先將目標(biāo)位置映射到這條線上，然后在這個(gè)一維的線上獲取附近的點(diǎn)就行了。

那這個(gè)映射算法具體是怎樣的呢？它將整個(gè)地球看成一個(gè)二維平面，然后劃分成了一系列正方形的方格，就好比圍棋棋盤。所有的地圖元素坐標(biāo)都將放置于唯一的方格中。方格越小，坐標(biāo)越精確。然后對這些方格進(jìn)行整數(shù)編碼，越是靠近的方格編碼越是接近。那如何編碼呢？一個(gè)最簡單的方案就是切蛋糕法。設(shè)想一個(gè)正方形的蛋糕擺在你面前，二刀下去均分分成四塊小正方形，這四個(gè)小正方形可以分別標(biāo)記為 00,01,10,11 四個(gè)二進(jìn)制整數(shù)。然后對每一個(gè)小正方形繼續(xù)用二刀法切割一下，這時(shí)每個(gè)小小正方形就可以使用 4bit 的二進(jìn)制整數(shù)予以表示。然后繼續(xù)切下去，正方形就會(huì)越來越小，二進(jìn)制整數(shù)也會(huì)越來越長，精確度就會(huì)越來越高。

上面的例子中使用的是二刀法，真實(shí)算法中還會(huì)有很多其它刀法，最終編碼出來的整數(shù)數(shù)字也都不一樣。

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

GeoHash 算法會(huì)繼續(xù)對這個(gè)整數(shù)做一次 base32 編碼 (0-9,a-z 去掉 a,i,l,o 四個(gè)字母) 變成一個(gè)字符串。在 Redis 里面，經(jīng)緯度使用 52 位的整數(shù)進(jìn)行編碼，放進(jìn)了 zset 里面，zset 的 value 是元素的 key，score 是 GeoHash 的 52 位整數(shù)值。zset 的 score 雖然是浮點(diǎn)數(shù)，但是對于 52 位的整數(shù)值，它可以無損存儲。

在使用 Redis 進(jìn)行 Geo 查詢時(shí)，我們要時(shí)刻想到它的內(nèi)部結(jié)構(gòu)實(shí)際上只是一個(gè)zset(skiplist)。通過 zset 的 score 排序就可以得到坐標(biāo)附近的其它元素 (實(shí)際情況要復(fù)雜一些，不過這樣理解足夠了)，通過將 score 還原成坐標(biāo)值就可以得到元素的原始坐標(biāo)。

Redis 的 Geo 指令基本使用

Redis 提供的 Geo 指令只有 6 個(gè)，讀者們瞬間就可以掌握。使用時(shí)，讀者務(wù)必再次想起，它只是一個(gè)普通的 zset 結(jié)構(gòu)。

增加

geoadd 指令攜帶集合名稱以及多個(gè)經(jīng)緯度名稱三元組，注意這里可以加入多個(gè)三元組

127.0.0.1:6379> geoadd company 116.48105 39.996794 juejin
(integer) 1
127.0.0.1:6379> geoadd company 116.514203 39.905409 ireader
(integer) 1
127.0.0.1:6379> geoadd company 116.489033 40.007669 meituan
(integer) 1
127.0.0.1:6379> geoadd company 116.562108 39.787602 jd 116.334255 40.027400 xiaomi
(integer) 2

距離

geodist 指令可以用來計(jì)算兩個(gè)元素之間的距離，攜帶集合名稱、2 個(gè)名稱和距離單位。

127.0.0.1:6379> geodist company juejin ireader km
"10.5501"
127.0.0.1:6379> geodist company juejin meituan km
"1.3878"
127.0.0.1:6379> geodist company juejin jd km
"24.2739"
127.0.0.1:6379> geodist company juejin xiaomi km
"12.9606"
127.0.0.1:6379> geodist company juejin juejin km
"0.0000"

我們可以看到掘金離美團(tuán)最近，因?yàn)樗鼈兌荚谕?。距離單位可以是 m、km、ml、ft，分別代表米、千米、英里和尺。

獲取元素位置

geopos 指令可以獲取集合中任意元素的經(jīng)緯度坐標(biāo)，可以一次獲取多個(gè)。

127.0.0.1:6379> geopos company juejin
1) 1) "116.48104995489120483"
 2) "39.99679348858259686"
127.0.0.1:6379> geopos company ireader
1) 1) "116.5142020583152771"
 2) "39.90540918662494363"
127.0.0.1:6379> geopos company juejin ireader
1) 1) "116.48104995489120483"
 2) "39.99679348858259686"
2) 1) "116.5142020583152771"
 2) "39.90540918662494363"

我們觀察到獲取的經(jīng)緯度坐標(biāo)和 geoadd 進(jìn)去的坐標(biāo)有輕微的誤差，原因是 geohash 對二維坐標(biāo)進(jìn)行的一維映射是有損的，通過映射再還原回來的值會(huì)出現(xiàn)較小的差別。對于「附近的人」這種功能來說，這點(diǎn)誤差根本不是事。

獲取元素的 hash 值

geohash 可以獲取元素的經(jīng)緯度編碼字符串，上面已經(jīng)提到，它是 base32 編碼。 你可以使用這個(gè)編碼值去 http://geohash.org/${hash}中進(jìn)行直接定位，它是 geohash 的標(biāo)準(zhǔn)編碼值。

127.0.0.1:6379> geohash company ireader
1) "wx4g52e1ce0"
127.0.0.1:6379> geohash company juejin
1) "wx4gd94yjn0"

讓我們打開地址 http://geohash.org/wx4g52e1ce0，觀察地圖指向的位置是否正確。

很好，就是這個(gè)位置，非常準(zhǔn)確。

附近的公司

georadiusbymember 指令是最為關(guān)鍵的指令，它可以用來查詢指定元素附近的其它元
素，它的參數(shù)非常復(fù)雜。

# 范圍 20 公里以內(nèi)最多 3 個(gè)元素按距離正排，它不會(huì)排除自身
127.0.0.1:6379> georadiusbymember company ireader 20 km count 3 asc
1) "ireader"
2) "juejin"
3) "meituan"
# 范圍 20 公里以內(nèi)最多 3 個(gè)元素按距離倒排
127.0.0.1:6379> georadiusbymember company ireader 20 km count 3 desc
1) "jd"
2) "meituan"
3) "juejin"
# 三個(gè)可選參數(shù) withcoord withdist withhash 用來攜帶附加參數(shù)
# withdist 很有用，它可以用來顯示距離
127.0.0.1:6379> georadiusbymember company ireader 20 km withcoord withdist withhash count 3 asc
1) 1) "ireader"
 2) "0.0000"
 3) (integer) 4069886008361398
 4) 1) "116.5142020583152771"
 2) "39.90540918662494363"
2) 1) "juejin"
 2) "10.5501"
 3) (integer) 4069887154388167
 4) 1) "116.48104995489120483"
 2) "39.99679348858259686"
3) 1) "meituan"
 2) "11.5748"
 3) (integer) 4069887179083478
 4) 1) "116.48903220891952515"
 2) "40.00766997707732031"

除了 georadiusbymember 指令根據(jù)元素查詢附近的元素，Redis 還提供了根據(jù)坐標(biāo)值來查詢附近的元素，這個(gè)指令更加有用，它可以根據(jù)用戶的定位來計(jì)算「附近的車」，「附近的餐館」等。它的參數(shù)和 georadiusbymember 基本一致，除了將目標(biāo)元素改成經(jīng)緯度坐標(biāo)值。

127.0.0.1:6379> georadius company 116.514202 39.905409 20 km withdist count 3 asc
1) 1) "ireader"
 2) "0.0000"
2) 1) "juejin"
 2) "10.5501"
3) 1) "meituan"
 2) "11.5748"

小結(jié) 注意事項(xiàng)

在一個(gè)地圖應(yīng)用中，車的數(shù)據(jù)、餐館的數(shù)據(jù)、人的數(shù)據(jù)可能會(huì)有百萬千萬條，如果使用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ì)對集群的遷移工作造成較大的影響，在集群環(huán)境中單個(gè) key 對應(yīng)的數(shù)據(jù)量不宜超過 1M，否則會(huì)導(dǎo)致集群遷移出現(xiàn)卡頓現(xiàn)象，影響線上服務(wù)的正常運(yùn)行。

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

如果數(shù)據(jù)量過億甚至更大，就需要對 Geo 數(shù)據(jù)進(jìn)行拆分，按國家拆分、按省拆分，按市拆分，在人口特大城市甚至可以按區(qū)拆分。這樣就可以顯著降低單個(gè) zset 集合的大小。

到此這篇關(guān)于Redis 的 GeoHash詳解的文章就介紹到這了,更多相關(guān)Redis 的 GeoHash內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！