Redis 地理散列GeoHash

用数据库来算附近的人

地图元素的位置数据使用二维的经纬度表示，经度范围（-180，180]，纬度范围 （-90，90],纬度正负以赤道为界，北正南负，经度正负已本初子午线（英国格林尼治天文台）为界，东正西负。

当两个元素的距离不是很远时，可以直接使用勾股定理就能算得元素之间的距离。我们平时使用的【附近的人】的功能，元素距离都不是很大，勾股定理算距离就足够。现在，如果要计算【附近的人】，也就是给定一个元素的坐标，然后计算这个坐标附近的其他元素，按照距离进行排序，需要如何着手。

如果现在元素的经纬度坐标使用关系数据库（元素id，经度x，纬度y）存储，首先，不可能遍历来计算所有的元素和目标元素的距离然后再进行排序。这个计算量太大了，性能指标无法满足。一般方法都是通过矩形区域来限定元素的数量，然后对区域内的元素进行全量距离计算再排序。 这样可以明显减少计算量，如何划分矩形区域，可以指定一个半径为r，使用一条SQL就可以圈出来，当用户对筛选出来的结果不满意，就扩大半径继续筛选。

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

为了满足高性能的矩阵区域算法，数据表需要在经纬度坐标加上双向复合索引（x,y）,这样可以最大优化查询性能。
但是数据库查询性能毕竟有限，如果【附近的人】查询请求非常多，在高并发场合下，可能不是一个很好的方案。

GeoHash算法

GeoHash算法将二维的经纬度数据映射到一维的整数，这样所有的元素都将在挂载到一条线上，距离靠近的二维坐标映射到一维后的点之间距离也会很接近。当我们想要计算【附近的人时】，首先将目标位置映射到这条线上，然后在这个一维的线上获取附近的点就可以了。

映射算法将整个地球看成一个二维平面，然后划分成一系列的正方形的方格，就好比围棋棋盘。所有的地图元素坐标都将放置于唯一的方格中。方格越小，坐标越精确。然后对这些方格进行整数编码，越是靠近的方格编码越是接近。如何编码最简单的方案就是切蛋糕法，设想一个正方形的蛋糕摆在面前，二刀下去均匀分成四块小正方形，这四个小正方形分别标记为00，01，10，11四个二进制整数。然后对每个小正方形继续用二刀法切割下去，这时每个小小正方形就可以使用4bit的二进制整数予以表示，然后继续切下去，正方形会越来越小，二进制整数也会越来越长，精确度就会越来越高。

编码之后，每个地图元素的坐标都将变成一个整数，通过这个整数可以还原出元素的坐标，整数越长，还原出来的坐标值的损失程度就越小。对于【附近的人】这个功能而言，损失的一点精确度可以忽略不计。

GeoHash算法会继续对这个整数做一次base32编码（0-9，a-z去掉a,i,l,o四个字母）变成一个字符串。在Redis里面，经纬度使用52位的整数进行编码，放进zset里面，zset的value是元素的key，score是GeoHash的52位整数值。zset的scire虽然是浮点数，但是对于52位的整数值，他可以无损存储。

在使用Redis进行Geo查询时，我们要时刻想到他的内部结构实际上是一个zset。通过zset的score排序就可以得到坐标附近的其他元素，通过将score还原成坐标值就可以得到元素的原始坐标。

Geo指令的基本使用

添加
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

计算距离

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"

我们可以看到掘金离美团最近，因为它们都在望京。距离单位可以是 m、km、ml、ft， 分别代表米、千米、英里和尺。

获取元素位置

geopos指令可以获取集合中任意元素的经纬度坐标，可以一次获取多个。

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

观察到获取的经纬度坐标和getadd进去的坐标有轻微的误差，原因是geohash对二维坐标进行一维映射是有损的，通过映射在还原回来的值会出现较小的差别，对于【附近的人】来说，这种误差是可以接受的。

获取附近的公司
georadiusbymember指令是最为关键的指令，可以用来查询指定元素附近的其他元素

# 范围 20 公里以内最多 3 个元素按距离正排，它不会排除自身
127.0.0.1:6379> georadiusbymember company ireader 20 km count 3 asc 
1) "ireader"
2) "juejin"
3) "meituan"
# 范围 20 公里以内最多 3 个元素按距离倒排
127.0.0.1:6379> georadiusbymember company ireader 20 km count 3 desc 
1) "jd"
2) "meituan"
3) "juejin"
# 三个可选参数 withcoord withdist withhash 用来携带附加参数
# withdist 很有用，它可以用来显示距离
# withcoord 返回结果时包括地理位置的经度和纬度坐标
# withdist：返回结果时包括结果与指定地理位置之间的距离
# withhash：返回结果时包括地理位置的 geohash 值
127.0.0.1:6379> georadiusbymember company ireader 20 km withcoord withdist withhash count 3 asc1) 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指令根据元素查询附近的元素，Redis还提供了根据坐标值来查询附近的元素，这个指令更加有用。他可以根据用户的定位来计算【附近的车】，【附近的餐馆】等。他的参数和georadiusbymember基本一致，除了将目标元素改成经纬度坐标值。

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"

总结

在一个地图应用中，车的数据、餐馆的数据、人的数据可能会有百万千万条，如果使用Redis的Geo数据结构，他们将全部放在一个zset集合中，在Redis的集群环境中，集合可能会从一个节点迁移到另一个节点，如果单个key的数据过大，会对集群的迁移工作造成较大的影响，在集群环境中单个key对应的数据量不宜超过1Mb，否则会导致集群迁移出现卡顿现象，影响线上业务正常运行。

所以，建议Geo的数据使用单独的Redis实例部署，不使用集群环境。

如果数据量过亿甚至更大，就需要对Geo数据进行拆分，按国家拆分、按省拆分、按市拆分，在人口特大城市甚至可以按区拆分。这样就可以显著降低单个zset集合的大小。