业务场景
目前很多APP例如饿了么、美团、微信,都会有附近的店、附近的人等功能,这些功能需要基于地理位置算法,根据当前用户的经纬度定位,找到指定范围内的人或店。
GeoHash是业界比较常用的地理位置排序算法,Redis也采用该算法,Geo算法将二维的经纬度数据映射到一维的整数,这样所有的元素都会被挂在到一条线上,距离相近的二维坐标映射到一维后的点之间距离也会很近,
当需要查找附近的人或店的时候,首先将目标位置映射到这条线上,然后在这个一维的线上获取附近的点就可以了。
二刀法
Geo算法将整个地球看成一个二维平面,然后划分成了一系列正方形的方格,就像围棋棋盘,所有地图元素坐标都被放置于唯一的方格中,方格越小,坐标越精确,随后对这些方格进行整数编码,越是靠近的方格编码越接近,
如下图,一个正方形,两刀下去切成四个小正方形,然后分别用00、01、10、11标记着四个小正方形,然后继续对每个小正方形继续进行切割,切出来的小小正方形用4个bit二进制整数表示,随着继续切下去,二进制的整数越来越长,精确度也会越来越高。
编码之后,每个地图元素的坐标都将变成一个整数,通过这个整数就可以还原元素的坐标,整数越长还原出来的坐标值的损失程度就越小,对于附近的事物这个功能而言,损失的一点精确度可以忽略不计。
上面使用的是二刀法,真实算法中还有其他的刀法,不同的算法最终编码出来的整数数字也不一样。
GeoHash会继续对得到的整数做一次base32的编码(0-9、a-z,去掉a、i、l、o四个字母)变成一个字符串,在redis中,经纬度使用52位的整数进行编码,存在zset中,value是元素的key,score是GeoHash的52位整数值,zset的score虽然是浮点数,但是对于52位的整数值,可以无损存储。
在使用redis进行Geo查询时,记住它的内部结构实际只是一个zset(skiplist),通过zset的score排序就可以得到坐标附近的其他元素,通过将score还原成坐标值就可以得到元素的原始坐标。
Geo指令
redis的Geo指令共7个。
增加 / geoadd
geoadd指令携带集合名称以及多个经纬度名称三元组,注意可以是多个三元组,如下指令,我们一共添加了五个公司的经纬度。
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
geodist指令可以用来计算两个元素之间的距离,携带集合名称、两个单位名称和距离单位(距离单位可以是 m、km、ml 和 ft),分别代表米、千米、英里和尺。
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 meituan m
"1387.8166"
获取元素位置 / geopos
geopos指令可以获取集合中任意元素的经纬度坐标,可以一次获取多个。
geoadd进去的经纬度和geopos出来的坐标有少许误差,原因是GeoHash对二维坐标进行的一维映射是有损的,
通过映射再还原回来的值,会有较小的误差,对于附近的事物这种功能来说,这点误差是可以接受的。
127.0.0.1:6379> geopos company juejin
1) 1) "116.48104995489120483"
2) "39.99679348858259686"
127.0.0.1:6379> geopos company meituan
1) 1) "116.48903220891952515"
2) "40.00766997707732031"
127.0.0.1:6379> geopos company meituan juejin
1) 1) "116.48903220891952515"
2) "40.00766997707732031"
2) 1) "116.48104995489120483"
2) "39.99679348858259686"
获取元素hash值 / geohash
GeoHash可以获取元素的经纬度编码字符串,可以通过这个编码去 http://geohash.org/${hash} 上直接进行定位。
127.0.0.1:6379> geohash company juejin
1) "wx4gd94yjn0"
127.0.0.1:6379> geohash company meituan
1) "wx4gdg0tx40"
附近的公司 / georadiusbymember
georadiusbymember用于查询指定元素附近的其他元素。
# 范围20公里以内最多3个元素按距离正排,该命令的结果不会排除自身
127.0.0.1:6379> georadiusbymember company juejin 20 km count 3 asc
1) "juejin"
2) "meituan"
3) "ireader
# 范围20公里以内最多3个元素按距离倒排,该命令的结果排除了自身
127.0.0.1:6379> georadiusbymember company juejin 20 km count 3 desc
1) "xiaomi"
2) "ireader"
3) "meituan"
# 增加了三个可选参数 withcoord (结果包含经纬度)、withdist(返回距离)、withhash(返回hash值)
127.0.0.1:6379> georadiusbymember company juejin 20 km withcoord withdist withhash count 3 desc
1) 1) "xiaomi"
2) "12.9606"
3) (integer) 4069880904286516
4) 1) "116.33425265550613403"
2) "40.02740024658161389"
2) 1) "ireader"
2) "10.5501"
3) (integer) 4069886008361398
4) 1) "116.5142020583152771"
2) "39.90540918662494363"
3) 1) "meituan"
2) "1.3878"
3) (integer) 4069887179083478
4) 1) "116.48903220891952515"
2) "40.00766997707732031"
georadius
georadius 可以根据经纬度获取周围的其它元素,例如附近的车、餐馆、人。
# 根据定位获取周围的公司
127.0.0.1:6379> georadius company 116.514202 39.905409 20 km withdist count 3 desc
1) 1) "jd"
2) "13.7269"
2) 1) "meituan"
2) "11.5748"
3) 1) "juejin"
2) "10.5501
删除
redis中Geo的存储就是使用的ZSet,所以直接通过zrem进行删除就可以了。
注意事项
由于Geo的本质就是ZSet,所以当数据量比较大的时候,百万千万级别的数据量时,在redis的集群环境中,集合可能会从一个节点迁移到另一个节点,
如果单个ZSet的数据过大,会对集群的迁移工作造成很大的影响,在集群环境中,单个key对应的数据量不宜超过1MB,否则会导致集群迁移出现卡顿现象,影响线上服务的运行,
建议Geo的数据使用单独的redis实例部署,不放在集群环境,防止以上现象。
如果数据量过亿,甚至更大,还需要对Geo数据做拆分,按国家、省、市、区拆分,降低单个ZSet集合的大小。