1 前言

找吃的泡嘴、找住的、找車

移動互聯(lián)網(wǎng)已融入到我們生活中的方方面面柑土。

我們平時找商家蜀肘、找房子、找車都可以通過各種App來完成稽屏。作為??????的筆者職業(yè)習慣性地思考這些功能是如何實現(xiàn)的呢扮宠？

例如尋找附近3公里范圍內(nèi)的出租車的需求，最直觀的想法就是去數(shù)據(jù)庫里面查表篩選出距離用戶小于3公里的車輛狐榔，將數(shù)據(jù)返回給客戶端坛增。

這種方法有一個很嚴重的問題，需要對整張表里面的每一項都計算一次相對距離太耗時了荒叼。既然整張表數(shù)據(jù)量比較大那么我們能不能縮小掃描的范圍呢轿偎？那么就會想到是否可以按業(yè)務特點縮小掃描范圍比如只掃描用戶當前位置所在城市的車輛，按照這個思路擴展開來發(fā)現(xiàn)數(shù)據(jù)量還是很大而且不能解決當用戶處于兩個城市的邊界時的問題被廓。

如何快速地索引數(shù)據(jù)是解決這個問題的關鍵坏晦，在瀏覽Redis API的時候發(fā)現(xiàn)其可以直接實現(xiàn)附近的XXX功能，下文中將介紹如何以Redis 實現(xiàn)此類功能并深入分析其背后的實現(xiàn)原理。

2 Redis GEO API

2.1 增加地理位置信息

geo add key longitude latitude member [longitude latitude member ...]

eg:

向cars:locations中增加車輛編號為1以及車輛編號為2的位置信息昆婿。

127.0.0.1:6379> geoadd cars:locations 120.346111 31.556381 1 120.375821 31.560368 2 

2.2 獲取地理位置信息

eg:

獲取車輛編號為1的車輛位置信息

127.0.0.1:6379> geopos cars:locations 1
1) 1) "120.34611314535140991"
   2) "31.55637987511895659"

2.3 獲取兩個地理位置的距離

eg:

獲取編號為1的車輛與編號為2的車輛之間的距離

127.0.0.1:6379> geodist cars:locations 1 2 km
"2.8504"

2.4 獲取指定位置范圍的地理信息位置集合

GEORADIUS key longitude latitude radius m|km|ft|mi [WITHCOORD] [WITHDIST] [WITHHASH] [ASC|DESC] [COUNT count]

以給定的經(jīng)緯度為中心球碉， 返回鍵包含的位置元素當中， 與中心的距離不超過給定最大距離的所有位置元素仓蛆。

eg:

以經(jīng)度120.375821緯度31.556381為中心查找5公里范圍內(nèi)的車輛

127.0.0.1:6379> GEORADIUS cars:locations 120.375821 31.556381 5 km WITHCOORD WITHDIST WITHHASH  ASC COUNT 100
1) 1) "2"
   2) "0.4433"
   3) (integer) 4054421167795118
   4) 1) "120.37582129240036011"
      2) "31.5603669915025975"
2) 1) "1"
   2) "2.8157"
   3) (integer) 4054421060663027
   4) 1) "120.34611314535140991"
      2) "31.55637987511895659"

以給定的經(jīng)緯度為中心睁冬， 返回鍵包含的位置元素當中， 與中心的距離不超過給定最大距離的所有位置元素看疙。

范圍可以使用以下其中一個單位：

• m 表示單位為米豆拨。
• km 表示單位為千米。
• mi 表示單位為英里能庆。
• ft 表示單位為英尺施禾。

在給定以下可選項時， 命令會返回額外的信息：

• WITHDIST ： 在返回位置元素的同時搁胆， 將位置元素與中心之間的距離也一并返回弥搞。 距離的單位和用戶給定的范圍單位保持一致。

• WITHCOORD ： 將位置元素的經(jīng)度和維度也一并返回渠旁。

• WITHHASH ： 以 52 位有符號整數(shù)的形式攀例， 返回位置元素經(jīng)過原始 geohash 編碼的有序集合分值。 這個選項主要用于底層應用或者調試顾腊， 實際中的作用并不大粤铭。
  命令默認返回未排序的位置元素。 通過以下兩個參數(shù)投慈， 用戶可以指定被返回位置元素的排序方式：

• ASC ： 根據(jù)中心的位置承耿， 按照從近到遠的方式返回位置元素。DESC ： 根據(jù)中心的位置伪煤， 按照從遠到近的方式返回位置元素加袋。

• 在默認情況下， GEORADIUS 命令會返回所有匹配的位置元素抱既。 雖然用戶可以使用 COUNT <count> 選項去獲取前 N 個匹配元素职烧， 但是因為命令在內(nèi)部可能會需要對所有被匹配的元素進行處理， 所以在對一個非常大的區(qū)域進行搜索時防泵， 即使只使用 COUNT 選項去獲取少量元素蚀之， 命令的執(zhí)行速度也可能會非常慢。 但是從另一方面來說捷泞， 使用 COUNT 選項去減少需要返回的元素數(shù)量足删， 對于減少帶寬來說仍然是非常有用的。

2.5 獲取指定元素范圍的地理信息位置集合

GEORADIUSBYMEMBER key member radius m|km|ft|mi [WITHCOORD] [WITHDIST] [WITHHASH] [ASC|DESC] [COUNT count]

eg:

以編號為1的車輛為中心查找5公里范圍內(nèi)的車輛
GEORA

127.0.0.1:6379> GEORADIUSBYMEMBER cars:locations 2 5 km WITHCOORD WITHDIST WITHHASH  ASC COUNT 100
1) 1) "2"
   2) "0.0000"
   3) (integer) 4054421167795118
   4) 1) "120.37582129240036011"
      2) "31.5603669915025975"
2) 1) "1"
   2) "2.8157"
   3) (integer) 4054421060663027
   4) 1) "120.34611314535140991"
      2) "31.55637987511895659"

相關可選參數(shù)同2.4中一致锁右。

3 Redis GEO實現(xiàn)附近XXX功能

研究完Redis GEO API后可以發(fā)現(xiàn)只要在Redis客戶端調用

2.4 獲取指定位置范圍的地理信息位置集合

API 即可實現(xiàn)相關需求失受。so easyＱ忍！拂到！

4 Redis GEO背后的原理

4.1 存儲結構

Redis 在存儲數(shù)據(jù)不同數(shù)據(jù)類型的數(shù)據(jù)時都有對應的編碼方式痪署。
Redis GEO是采用哪種編碼方式進行存儲的呢？

在翻閱Redis GEO API時發(fā)現(xiàn)其并沒有刪除指令兄旬，因為其底層是使用zset進行實現(xiàn)的狼犯。 我們可以使用zrem 進行數(shù)據(jù)的刪除。

再嘗試用zset的查詢指令领铐，查詢上文中添加的GEO信息

127.0.0.1:6379> ZRANGE cars:locations  0 -1 WITHSCORES
1) "1"
2) "4054421060663027"
3) "2"
4) "4054421167795118"

發(fā)現(xiàn)車輛編號為1的位置信息為4054421060663027悯森；車輛編號為2的位置信息為4054421167795118。
再回顧一下zset增加成員的指令

ZADD key score member [[score member] [score member] ...]

至此可以推斷出Redis GEO 添加經(jīng)绪撵、緯度位置信息的指令的過程是

ZADD cars:locations 4054421060663027 1

4054421060663027為對經(jīng)緯度進行編碼后的值呐馆。使用4054421060663027作為score 可以快速實現(xiàn)對經(jīng)緯度的索引。

查看相關文檔發(fā)現(xiàn)Redis使用了geohash對經(jīng)緯度信息進行的編碼莲兢。

4.2 geohash原理分析

關于geohash的核心原理，這篇文章分析的很好 GeoHash核心原理解析

總結下來就是

• 如何唯一表示地球上的一塊空間续膳？
• 如何將地球切分成大小近似的區(qū)塊改艇，并支持不同粒度的表示？

為了解決上述兩個問題坟岔，我們需要三個步驟谒兄。

1. 第一步，將三維地球變成二維社付；
2. 第二步承疲，將二維再轉成一維；
3. 最后一步鸥咖，將一維表示成二進制碼存儲燕鸽。

4.2.1 如何將三維變二維？

地球緯度區(qū)間是[-90,90],經(jīng)度區(qū)間是[-180,180]啼辣。 將它展開想象長一個矩形為

三維變二維

4.2.2 如何將二維變一維啊研？

通過剛才的方法，我們能夠將地球的表面轉換成二維空間的平面鸥拧。那接下來要將二維轉變成一維党远。如果切割二維空間，可以切割出很多正方形富弦。如何表示這個正方形呢沟娱？最簡單的方法是在平面上進行遍歷。每遍歷到一個點腕柜，就給它標注一個值济似，比如00矫废、01、10碱屁、11磷脯，隨著二進制數(shù)字增加，相當于遍歷面上不同的位置娩脾。

二維變一維

當將空間劃分為四塊時候赵誓，編碼的順序分別是左下角00，左上角01柿赊，右下腳10俩功，右上角11，也就是類似于Z的曲線碰声。

如何表示不同的粒度诡蜓？

當我們遞歸的將各個塊分解成更小的子塊時可以標識更小的空間范圍（如上圖二中所示），如從0000開始到1111結束編碼的順序是自相似的（分形）胰挑，每一個子快也形成Z曲線蔓罚，這種類型的曲線被稱為Peano空間填充曲線。

4.2.3 如何將一維表示成二進制碼存儲

Geohash 也有幾種編碼形式瞻颂，常見的有2種豺谈，base 32 和 base 36。
會將落到網(wǎng)格中的二進制數(shù)據(jù)編碼成字符串

尾巴

分析完Redis GEO的實現(xiàn)原理后不然發(fā)現(xiàn)其背后核心是geohash贡这，使用geohash將二維的經(jīng)緯度數(shù)據(jù)編碼成一維數(shù)據(jù)茬末，再使用B樹索引快速查找出需要的數(shù)據(jù)。

上述使用Redis GEO 實現(xiàn)附近的人盖矫，附近的車輛丽惭，附近的商家此類功能時只能通過半徑進行查找。

Q：如果需求是我要查找附近5公里內(nèi)所有商家中有賣咖啡的呢辈双？

A：當然我們可以在應用層對Reids 查詢出的所有數(shù)據(jù)進行過濾责掏。

Q：當Redis返回數(shù)據(jù)量、用戶請求量比較大時是非常吃內(nèi)存資源的湃望，是否有更優(yōu)解拷橘？業(yè)內(nèi)的數(shù)據(jù)庫實現(xiàn)中是否已經(jīng)有了更好的解決方案？

A：帶著這樣的疑問我查找了相關資料發(fā)現(xiàn)geohash其實是空間索引的一種實現(xiàn)喜爷，我們經(jīng)常使用的MySql冗疮、MongoDB都有空間索引的實現(xiàn)。

1. MongoDB

mongo中的GeoJSON對象有點檩帐、線术幔、多邊形、多條線段湃密、多點诅挑、多個多邊形四敞。支持 包含、相交拔妥、臨近的查詢忿危，同時支持多條件查詢。(感覺非常強大的樣子真是換一個解決方案可能會有質的收益)

2. MySql

MySql InnoDB 在5.7.4 labs版本中才添加對空間索引的支持没龙，它們都是通過 R 樹來實現(xiàn)空間索引铺厨。

MySql的升級成本是很高的，理解了geohash原理后我們可以在MySql表中新增geohash字段硬纤，通過B數(shù)的二分查找法快速定位數(shù)據(jù)解滓。

下一篇blog將進行手動計算geohash + MySql B樹索引實現(xiàn)的相關實踐總結，并對比MySql自帶的空間索引在存儲空間和查詢效率上的區(qū)別筝家。