如何“搖一搖”——Redis實現(xiàn)“附近的人”的方法及其他

1、GEOHash——如何“搖一搖”

1-1、為什么需要GEOHash

現(xiàn)在很多APP都有“搖一搖”橄登、“附近的人”、網(wǎng)約車離我有多遠等類似的功能讥此。

那就不可避免需要進行一系列的地理坐標轉換為距離的計算示绊。

獲取地理坐標不難，只需要用戶授權就能輕松獲取到很精確的經緯度暂论；

計算距離也不難：兩點之間坐標差的平方相加，再開方即可（簡書的markdown太差了拌禾，公式也不支持）取胎。

問題在于，用戶數(shù)量劇增以后（百萬、千萬闻蛀、億……）匪傍，每次進行全量距離計算本身就變成了一個巨大的負擔，大量乘方觉痛、開方這樣的浮點運算役衡，不管多么強壯的算力都會被壓垮。

1-2薪棒、什么是GEOHash

GEOHash是解決這一問題的一種算法手蝎。

GEOHash的核心思想是將二維的經緯度轉換成一維的字符串，這樣無論使用何種方式存儲用戶的位置數(shù)據(jù)俐芯，都可以很方便地建立索引棵介，大大簡化計算。

GEOHash有三個主要特點：

字符串越長吧史，表示的范圍越精確邮辽。編碼長度為8時，精度在19米左右贸营，而當編碼長度為9時吨述，精度在2米左右。
字符串相似的表示距離相近钞脂，利用字符串的前綴匹配揣云，可以查詢附近的地理位置。
GEOHash編碼后的字符串芳肌，可以反向解碼出原來的經緯度灵再。

1-3、GEOHash編碼的簡易原理

GEOHash的編碼過程并不復雜亿笤，首先使用分形的思想對經緯度做處理（二維空間轉換為分形維）翎迁，轉為二進制字符串；然后偶數(shù)位放經度净薛，奇數(shù)位放緯度汪榔，得到一個新的二進制字符串；最后對該二進制字符串做Base32編碼處理即可（或者使用Base64）肃拜。

但是“為什么”要這樣編碼痴腌，就涉及到計算機圖形學的一些思想（GEOHash應用了Peano曲線），本篇側重應用燃领，原理的具體說明此處略去士聪。

1-4、GEOHash的邊緣問題

GEOHash編碼時猛蔽，實際上就是把所有區(qū)域分割成大小相同的矩形塊（分得越細剥悟，字符串就越長灵寺，精度越精確）。

但是不管分割得怎么細区岗，都是一個矩形區(qū)域略板，會出現(xiàn)區(qū)域內靠近邊緣的某個點，與另一片區(qū)域中靠近邊緣的點離得更近慈缔，但是被誤判的情況叮称。

畢竟同一片區(qū)域內的hash碼是相同的，不管離得多遠藐鹤，都會被判定為離得最近瓤檐。

解決方法是在查詢時，除了使用定位點的GeoHash碼進行匹配外教藻，還要使用周圍8個區(qū)域的GeoHash編碼一并匹配距帅。

2、Redis中GEOHash的應用

Redis 從3.2版本開始括堤，追加了GEO數(shù)據(jù)類型用于存儲用戶信息碌秸，并且提供了各種用于地理計算的方法。

（BTW悄窃，對Redis GEO貢獻最大的是其實是國內的開發(fā)者讥电。也是因為我們對這個功能的需求最大）

下面是相關的全部命令列表：

GEOADD：增加地理位置的坐標（支持批量操作）

時間復雜度O(log(N))

GEOADD key longitude latitude member [longitude latitude member ...]

key標識一個地理位置的集合。
longitude是經度轧抗，latitude是緯度恩敌。
member是該地理位置的名稱（自定義）。

應用舉例：

geoadd cities 121.47 31.23 shanghai 

geoadd cities 116.40 39.90 beijing 118.78 32.07 nanjing

GEOPOS：獲取地理位置的坐標（支持批量操作）

時間復雜度O(log(N))

GEOPOS key member [member ...]

GEODIST：獲取兩個地理位置的距離

時間復雜度O(log(N))

GEODIST key member1 member2 [m|km|ft|mi]

單位可以指定為以下四種類型：

m：米横媚，距離單位默認為米纠炮，不傳遞該參數(shù)則單位為米
km：公里
mi：英里
ft：英尺

應用舉例：
geodist cities beijing shanghai

GEORADIUS：根據(jù)給定地理位置坐標獲取指定范圍內的地理位置集合

時間復雜度O(N+log(M))，N為指定半徑范圍內的元素個數(shù)灯蝴，M為要返回的個數(shù)

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

longitude是經度恢口，latitude是緯度。
radius表示范圍距離穷躁。
距離單位可以為m|km|ft|mi
WITHCOORD：傳入WITHCOORD參數(shù)耕肩，則返回結果會帶上匹配位置的經緯度。
WITHDIST：傳入WITHDIST參數(shù)问潭，則返回結果會帶上匹配位置與給定地理位置的距離猿诸。
ASC|DESC：默認結果是未排序的，傳入ASC為從近到遠排序狡忙，傳入DESC為從遠到近排序梳虽。
WITHHASH：傳入WITHHASH參數(shù)，則返回結果會帶上匹配位置的hash值灾茁。
COUNT count：傳入COUNT參數(shù)窜觉，可以返回指定數(shù)量的結果是复。

GEORADIUSBYMEMBER：根據(jù)給定地理位置獲取指定范圍內的地理位置集合

時間復雜度O(N+log(M))，N為指定半徑范圍內的元素個數(shù)竖螃，M為要返回的個數(shù)

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

GEORADIUS 命令的參數(shù)是坐標，而本命令的參數(shù)是地理位置名稱逗余，其他無區(qū)別特咆。

應用舉例：
georadiusbymember cities shanghai 50 km

GEOHASH：獲取地理位置的GEOHash值（支持批量操作）

時間復雜度O(log(N))

GEOHASH key member [member ...]

3、關于Redis中GEO的一些說明

redis使用的GEOHash編碼長度為26位录粱，可以精確到0.59m的精度腻格。

Redis中的GEO核心主要是兩點：

使用GEOHash保存地理位置的坐標
使用有序集合（ZSET）保存地理位置的集合

內部的實際存儲使用的是ZSET，進一步說明如下：

GEO命令中的key就是ZSET的名字
Redis沒有提供地理位置的刪除命令啥繁〔酥埃可以利用ZSET的ZREM命令進行刪除： zrem cities shanghai
執(zhí)行GEOADD命令時，會先按照標準的GEOHash計算方法計算hash值旗闽，然后將地理位置名稱（member）作為集合的member酬核，將GEOHash值作為score，執(zhí)行ZADD命令插入到ZSET中
GEORADIUS和GEORADIUSBYMEMBER适室。內部實現(xiàn)實際上就是先執(zhí)行ZRANGE命令嫡意，然后判斷結果是否符合命令中指定的距離即可。另外就是這兩個命令已經自行解決了GEOHash的“邊緣問題”捣辆，會自動關聯(lián)周圍的八片區(qū)域蔬螟，無需額外處理。

4汽畴、Redis以外的GEOHash實現(xiàn)

4-1旧巾、MySQL

MySQL從 5.7.4 labs 版本開始增加了對于空間索引的支持，通過R樹實現(xiàn)忍些。

如果不具備升級MySQL的條件鲁猩，就需要增加類似 geo_hash 的字段，追加地理位置時手動計算hash碼坐昙，搜索附近的人時手動解決GEOHash的邊緣問題绳匀，從算力和復雜度上來說都不能令人滿意。

4-2炸客、MongoDB + 2d索引

MongoDB主要是通過它的兩種地理空間索引 2dsphere 和 2d來實現(xiàn)地理位置的操作疾棵。

兩種索引的底層依然是基于Geohash，但與通用的Geohash還有一些不同痹仙。

2dsphere 索引僅支持球形表面的幾何形狀查詢是尔。

2d 索引支持平面幾何形狀和一些球形查詢。雖然2d 索引支持某些球形查詢开仰，但 2d 索引對這些球形查詢時拟枚，可能會出錯薪铜。所以球形查詢盡量選擇 2dsphere索引。

盡管兩種索引的方式不同恩溅，但只要坐標跨度不太大隔箍，計算出的距離誤差幾乎可以忽略不計。

對經緯度數(shù)據(jù)創(chuàng)建2d索引（db.coll.createIndex）以后脚乡，只要使用geoNear命令就可以實現(xiàn)附近的人的功能了蜒滩。