Redis GEO & 实现原理深度分析

移动互联网已融入到我们生活中的方方面面。

我们平时找商家、找房子、找车都可以通过各种App来完成。作为:man:‍:computer:‍的笔者职业习惯性地思考这些功能是如何实现的呢？

例如寻找附近3公里范围内的出租车的需求，最直观的想法就是去数据库里面查表筛选出距离用户小于3公里的车辆，将数据返回给客户端。

这种方法有一个很严重的问题，需要对整张表里面的每一项都计算一次相对距离太耗时了。既然整张表数据量比较大那么我们能不能缩小扫描的范围呢？那么就会想到是否可以按业务特点缩小扫描范围比如只扫描用户当前位置所在城市的车辆，按照这个思路扩展开来发现数据量还是很大而且不能解决当用户处于两个城市的边界时的问题。

如何快速地索引数据是解决这个问题的关键，在浏览Redis API的时候发现其可以直接实现附近的XXX功能，下文中将介绍如何以 Redis 实现此类功能并深入分析其背后的实现原理。

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]
复制代码

以给定的经纬度为中心， 返回键包含的位置元素当中， 与中心的距离不超过给定最大距离的所有位置元素。

eg:

以经度120.375821纬度31.556381为中心查找5公里范围内的车辆

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"
复制代码

以给定的经纬度为中心， 返回键包含的位置元素当中， 与中心的距离不超过给定最大距离的所有位置元素。

范围可以使用以下其中一个单位：

• m 表示单位为米。
• km 表示单位为千米。
• mi 表示单位为英里。
• ft 表示单位为英尺。

在给定以下可选项时， 命令会返回额外的信息：

• WITHDIST ： 在返回位置元素的同时， 将位置元素与中心之间的距离也一并返回。 距离的单位和用户给定的范围单位保持一致。

• WITHCOORD ： 将位置元素的经度和维度也一并返回。

• WITHHASH ： 以 52 位有符号整数的形式， 返回位置元素经过原始 geohash 编码的有序集合分值。 这个选项主要用于底层应用或者调试， 实际中的作用并不大。 命令默认返回未 排序 的位置元素。 通过以下两个参数， 用户可以指定被返回位置元素的排序方式：

• ASC ： 根据中心的位置， 按照从近到远的方式返回位置元素。DESC ： 根据中心的位置， 按照从远到近的方式返回位置元素。

• 在默认情况下， GEORADIUS 命令会返回所有匹配的位置元素。 虽然用户可以使用 COUNT 选项去获取前 N 个匹配元素， 但是因为命令在内部可能会需要对所有被匹配的元素进行处理， 所以在对一个非常大的区域进行搜索时， 即使只使用 COUNT 选项去获取少量元素， 命令的执行速度也可能会非常慢。 但是从另一方面来说， 使用 COUNT 选项去减少需要返回的元素数量， 对于减少带宽来说仍然是非常有用的。

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

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

eg:

以编号为1的车辆为中心查找5公里范围内的车辆 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"
复制代码

相关可选参数同2.4中一致。

3 Redis GEO实现附近XXX功能

研究完Redis GEO API后可以发现只要在Redis客户端调用

2.4 获取指定位置范围的地理信息位置集合

API 即可实现相关需求。so easy！！！

4 Redis GEO背后的原理

4.1 存储结构

Redis 在存储数据不同数据类型的数据时都有对应的编码方式。 Redis GEO是采用哪种编码方式进行存储的呢？

在翻阅Redis GEO API时发现其并没有删除指令，因为其底层是使用 zset 进行实现的。 我们可以使用zrem 进行数据的删除。

再尝试用zset的查询指令，查询上文中添加的GEO信息

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

发现车辆编号为1的位置信息为4054421060663027；车辆编号为2的位置信息为4054421167795118。 再回顾一下zset增加成员的指令

ZADD key score member [[score member] [score member] ...]
复制代码

至此可以推断出Redis GEO 添加经、纬度位置信息的指令的过程是

ZADD cars:locations 4054421060663027 1
复制代码

4054421060663027为对经纬度进行编码后的值。使用4054421060663027作为score 可以快速实现对经纬度的索引。

查看相关文档发现Redis使用了geohash对经纬度信息进行的编码。

4.2 geohash原理分析

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

总结下来就是

• 如何唯一表示地球上的一块空间？
• 如何将地球切分成大小近似的区块，并支持不同粒度的表示？

为了解决上述两个问题，我们需要三个步骤。

1. 第一步，将三维地球变成二维；
2. 第二步，将二维再转成一维；
3. 最后一步，将一维表示成二进制码存储。

4.2.1 如何将三维变二维？

地球纬度区间是[-90,90],经度区间是[-180,180]。 将它展开想象长一个矩形为

4.2.2 如何将二维变一维？

通过刚才的方法，我们能够将地球的表面转换成二维空间的平面。那接下来要将二维转变成一维。如果切割二维空间，可以切割出很多正方形。如何表示这个正方形呢？最简单的方法是在平面上进行遍历。每遍历到一个点，就给它标注一个值，比如00、01、10、11，随着二进制数字增加，相当于遍历面上不同的位置。

当将空间划分为四块时候，编码的顺序分别是左下角00，左上角01，右下脚10，右上角11，也就是类似于Z的曲线。

如何表示不同的粒度？

当我们递归的将各个块分解成更小的子块时可以标识更小的空间范围（如上图二中所示），如从0000开始到1111结束编码的顺序是自相似的（分形），每一个子快也形成Z曲线，这种类型的曲线被称为Peano空间填充曲线。

4.2.3 如何将一维表示成二进制码存储

Geohash 也有几种编码形式，常见的有2种，base 32 和 base 36。 会将落到网格中的二进制数据编码成字符串

尾巴

分析完Redis GEO的实现原理后不然发现其背后核心是geohash，使用geohash将二维的经纬度数据编码成一维数据，再使用B树索引快速查找出需要的数据。

上述使用Redis GEO 实现附近的人，附近的车辆，附近的商家此类功能时只能通过半径进行查找。

Q：如果需求是我要查找附近5公里内所有商家中有卖咖啡的呢？

A：当然我们可以在应用层对Reids 查询出的所有数据进行过滤。

Q：当Redis返回数据量、用户请求量比较大时是非常吃内存资源的，是否有更优解？业内的数据库实现中是否已经有了更好的解决方案？

A：带着这样的疑问我查找了相关资料发现geohash其实是空间索引的一种实现，我们经常使用的 MySql 、 MongoDB 都有空间索引的实现。

1. MongoDB

mongo中的GeoJSON对象有点、线、多边形、多条线段、多点、多个多边形。支持 包含、相交、临近的查询，同时支持多条件查询。( 感觉非常强大的样子真是换一个解决方案可能会有质的收益 )

2. MySql

MySql InnoDB 在5.7.4 labs版本中才添加对空间索引的支持，它们都是通过 R 树来实现空间索引。

MySql的升级成本是很高的，理解了geohash原理后我们可以在MySql表中新增geohash字段，通过B数的二分查找法快速定位数据。

下一篇blog将进行手动计算geohash + MySql B树索引实现的相关实践总结，并对比MySql自带的空间索引在存储空间和查询效率上的区别。