使用Redis实现附近的人及打车服务

面向LBS应用的GEO数据类型

各种社交软件里面都有附件的人的需求，在该应用中，我们查询附近 1 公里的食客，同时只需查询出 20 个即可。 这都依赖基于位置信息服务（Location-Based Service，LBS）的应用。LBS应用访问的数据是和人或物关联的一组经纬度信息，而要能查询相邻的经纬度范围，GEO就非常适合应用在LBS服务的场景。

解决基于地理位置的搜索，很多数据库品牌都支持：MySQL、MongoDB、Redis 等都能支持地理位置的存储。

• 当用户登录应用时，或者保持用户登录后用户在使用应用时，客户端是可以时刻获取用户位置信息的（前提是用户要开启位置获取的权限），客户端获取到最新的地理位置后，上传到后端服务器进行更新。
• 当用户点击 Near Me 功能时，那么通过后台就可以以当前用户的位置为圆点，距离为半径查询相关的用户展示即可完成

GEO底层结构

设计一个数据类型的底层结构时，首先要知道，待处理的数据的访问特点。

那位置信息到底是怎么被存取的呢？如打车服务：

• 每辆网约车都有个编号（如666），网约车需将自己的经度、纬度发给叫车应用
• 打车时，打车应用会根据用户的经纬度位置，查找用户的附近车辆，并匹配
• 等把位置相近的用户和车辆匹配后，打车应用就会根据车辆编号，获取车辆信息，并返回给用户

可见，一辆车（或用户）对应一组经纬度，并随车（或用户）的位置移动，相应经纬度也会变化。

这种数据记录模式属于一个K（例如车ID）对应一个V（一组经纬度）。当有很多车辆信息要保存时，就需要有个集合保存一系列KV。Hash正合适：

Hash类型的HSET会根据K设置相应V，所以可用其快速更新车辆变化的经纬度信息。

这就完事了吗？

对于一个LBS应用，除记录经纬度，还需根据用户经纬度信息在车辆的Hash集合中进行范围查询。 而涉及到范围查询，就要求集合中的元素有序，Hash显然不满足需求。

那有序的Sorted Set能胜任吗？

Sorted Set也支持一个K对应一个V:

• K就是Sorted Set中的元素
• V则是元素的权重分数

Sorted Set可根据元素的权重分数排序，支持范围查询。这就能满足LBS查找相邻位置的需求。 GEO底层数据结构其实就是Sorted Set，保存车辆经纬度信息时：

• Sorted Set的元素是车辆ID
• 元素的权重分数是经纬度信息

但Sorted Set元素的权重分数是一个浮点数（float类型），而一组经纬度包含的是经度和纬度两个值，没法直接保存为一个浮点数，到底怎么保存？

这就要用到GEO类型中的GeoHash编码。

工作原理

sorted set 使用一种称为 Geohash 的技术进行填充。经度和纬度的位是交错的，以形成一个独特的 52 位整数. 我们知道，一个 sorted set 的 double score 可以代表一个 52 位的整数，而不会失去精度。 这种格式允许半径查询检查的 1 + 8 个领域需要覆盖整个半径，并丢弃元素以外的半径。通过计算该区域的范围，通过计算所涵盖的范围，从不太重要的部分的排序集的得分，并计算得分范围为每个区域的 sorted set 中的查询。

GeoHash编码

为高效对比经纬度，Redis使用GeoHash编码：二分区间，区间编码。

对一组经纬度进行GeoHash编码时：

• 先分别编码经度、纬度
• 再把经、纬度各自编码组合成一个最终编码

一个地理位置信息，其经度范围[-180,180]。GeoHash编码会把一个经度值编码成一个N位的二进制值，对经度范围[-180,180]做N次的二分区操作，其中N可以自定义。

第一次二分区：[-180,0)和[0,180]。可查看要编码的经度值落在哪个分区：

• 左分区，用0表示
• 右分区，用1表示

这样，每做完一次二分区，即可得到1位编码值。

再对经度值所属分区再做一次二分区，同时再次查看经度值落在了二分区后的左分区还是右分区，按照刚才的规则再做1位编码。当做完N次的二分区后，经度值就可以用一个N bit数表示了。 如要编码经度=116.37，用5位编码值（即N=5，做5次分区）：

• 第一次二分区操作，把经度区间[-180,180]分成了左分区[-180,0)和右分区[0,180] 116.37是属右分区，所以，用1表示
• 第二次二分区：把经度值116.37所属的[0,180]区间，分成[0,90)和[90, 180] 116.37属于右分区[90,180]，所以，第二次分区后的编码值为1

以此类推 ，做完5次分区后，把经度值116.37定位在[112.5, 123.75]这个区间，得到经度值的5位编码值：11010

对纬度的编码方式，和对经度的一样，只是纬度范围[-90，90]，如对纬度值39.86的编码过程：

当一组经纬度值都编完码后，我们再把它们的各自编码值组合在一起，组合的规则是：最终编码值的偶数位上依次是经度的编码值，奇数位上依次是纬度的编码值，其中，偶数位从0开始，奇数位从1开始。

刚计算的经纬度（116.37，39.86）各自编码值11010、10111，组合后，第0位是经度的第0位1，第1位是纬度的第0位1，第2位是经度的第1位1，第3位是纬度的第1位0，以此类推，就能得到最终编码值1110011101：

GeoHash编码后，原来无法用一个权重分数表示的一组经纬度（116.37，39.86）即可用1110011101一个值表示，就能保存为Sorted Set的权重分数了。

这也相当于把整个地理空间划分成了一个个方格，每个方格对应GeoHash中的一个分区。 如把经度区间[-180,180]二分区，把纬度区间[-90,90]二分区，就会得到4个分区：

• 分区一：[-180,0)和[-90,0)，编码00
• 分区二：[-180,0)和[0,90]，编码01
• 分区三：[0,180]和[-90,0)，编码10
• 分区四：[0,180]和[0,90]，编码11

这4个分区对应了4个方格，每个方格覆盖了一定范围内的经纬度值，分区越多，每个方格能覆盖到的地理空间越小，越精准。 将所有方格的编码值映射到一维空间，相邻方格GeoHash编码值也接近：

所以，使用Sorted Set范围查询得到的相近编码值，在实际地理空间也是相邻方格，即可实现LBS应用“附近的人”。

有的编码值虽然数值接近，但实际对应方格却距离较远。 如用4位GeoHash编码，将经度区间[-180,180]和纬度区间[-90,90]各分成4个分区，共16分区，对应16方格。编码值0111、1000两方格就相距较远：

所以，为避免查询不准确，可同时查询给定经纬度所在的方格周围的4或8个方格。

GEO类型是把经纬度所在区间编码作为Sorted Set中元素的权重分数，把和经纬度相关的车辆ID作为Sorted Set中元素本身的值保存下来，这样相邻经纬度的查询即可通过编码值的大小范围查询实现。

工作原理

sorted set 使用一种称为 Geohash 的技术进行填充。经度和纬度的位是交错的，以形成一个独特的 52 位整数. 我们知道，一个 sorted set 的 double score 可以代表一个 52 位的整数，而不会失去精度。 这种格式允许半径查询检查的 1 + 8 个领域需要覆盖整个半径，并丢弃元素以外的半径。通过计算该区域的范围，通过计算所涵盖的范围，从不太重要的部分的排序集的得分，并计算得分范围为每个区域的 sorted set 中的查询。

地球模型（Earth model）

这只是假设地球是一个球体，因为使用的距离公式是 Haversine 公式。这个公式仅适用于地球，而不是一个完美的球体。当在社交网站和其他大多数需要查询半径的应用中使用时，这些偏差都不算问题。 但最坏的情况下的偏差可能是 0.5%，所以一些地理位置很关键的应用还是需要谨慎考虑。

命令

GEOADD

把一组经纬度信息和对应一个ID，记录到GEO集合。

# 添加单个位置
GEOADD diner:location 121.446617 31.205593 'zhangsan'
"1"

# 添加多个位置信息
GEOADD diner:location 121.4465774 31.20485103  'lisi' 121.44534  31.2031 'wangwu'  121.4510648 31.2090667 'zhangliu'
"3"

底层使用的 sortedSet 存储。

GEODIST

计算距离。

key member1 member2 [unit] 

其中 unit 为单位 m|km|ft（英尺）|mi（英里）

# 计算两点间的距离，返回距离的单位是米（m）
127.0.0.1:0>GEODIST diner:location zhangsan lisi m
"82.4241"
# 计算两点间的距离，返回距离的单位是千米（km）
127.0.0.1:0>GEODIST diner:location zhangsan lisi km
"0.0824"

GEOHASH

key member [member …]

返回一个或多个位置元素的 Geohash。保存到 Redis 中是用 Geohash 位置 52 点整数编码。

GeoHash 将二维经纬度转换成字符串。比如下图展示了北京 9 个区域的 GeoHash 字符串，分别是 WX4ER，WX4G2、WX4G3 等，每一个字符串代表了某一矩形区域。 即这个矩形区域内所有的点（经纬度坐标）都共享相同的 GeoHash 字符串，这样既可保护隐私（只表示大概区域位置而非具体点），又容易做缓存。 比如左上角区域内的用户不断发送位置信息请求餐馆数据，由于这些用户的 GeoHash 字符串都是 WX4ER，所以可把 WX4ER 当作 key，把该区域的餐馆信息当作 value 来进行缓存，而若不使用 GeoHash，由于区域内的用户传来的经纬度各不相同的，很难做缓存。字符串越长，表示的范围越精确。

GEOPOS

从key里返回所有给定位置元素的位置（经度和纬度）。

key member [member …] 

# 返回zhangsan和lisi的位置信息
127.0.0.1:0>GEOPOS diner:location zhangsan lisi
 1)    1)   "121.44661813974380493"
  2)   "31.20559220971455971"
 2)    1)   "121.44657522439956665"
  2)   "31.20485207113603821"

GEORADIUS

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

范围可使用如下单位：

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

• WITHDIST: 在返回位置元素的同时， 将位置元素与中心之间的距离也一并返回。 距离的单位和用户给定的范围单位保持一致
• WITHCOORD: 将位置元素的经度和维度也一并返回
• WITHHASH: 以 52 位有符号整数的形式， 返回位置元素经过原始 geohash 编码的有序集合分值。 这个选项主要用于底层应用或者调试， 实际中的作用并不大。 命令默认返回未排序的位置元素。 通过以下两个参数， 用户可以指定被返回位置元素的排序方式：
• ASC 根据中心的位置， 按照从近到远的方式返回位置元素。
• DESC 根据中心的位置， 按照从远到近的方式返回位置元素。

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

# 以121.446617 31.205593(张三位置)为圆心，3000m为半径，查询返回用户及其位置
127.0.0.1:0>GEORADIUS diner:location 121.446617 31.205593 3000 m WITHCOORD 
 1)    1)   "wangwu"
  2)      1)    "121.44534140825271606"
   2)    "31.20310057881493293"


 2)    1)   "lisi"
  2)      1)    "121.44657522439956665"
   2)    "31.20485207113603821"


 3)    1)   "zhangsan"
  2)      1)    "121.44661813974380493"
   2)    "31.20559220971455971"


 4)    1)   "zhangliu"
  2)      1)    "121.45106524229049683"
   2)    "31.20906731242401833"


# 以121.446617 31.205593(张三位置)为圆心，3000m为半径，查询返回用户及其距离(单位是米)
127.0.0.1:0>GEORADIUS diner:location 121.446617 31.205593 3000 m WITHDIST
 1)    1)   "wangwu"
  2)   "302.6202"

 2)    1)   "lisi"
  2)   "82.5066"

 3)    1)   "zhangsan"
  2)   "0.1396"

 4)    1)   "zhangliu"
  2)   "573.0651"
  
# 以121.446617 31.205593(张三位置)为圆心，3000m为半径，查询返回用户及其距离(单位是米) 由近及远
47.110.246.98:15>GEORADIUS diner:location 121.446617 31.205593 3000 m WITHDIST ASC
 1)    1)   "zhangsan"
  2)   "0.1396"

 2)    1)   "lisi"
  2)   "82.5066"

 3)    1)   "wangwu"
  2)   "302.6202"

 4)    1)   "zhangliu"
  2)   "573.0651"
  

# 以121.446617 31.205593(张三位置)为圆心，3000m为半径，查询返回用户及其GeoHash值
127.0.0.1:0>GEORADIUS diner:location 121.446617 31.205593 3000 m WITHHASH
 1)    1)   "wangwu"
  2)   "4054756135204337"

 2)    1)   "lisi"
  2)   "4054756138536712"

 3)    1)   "zhangsan"
  2)   "4054756138736536"

 4)    1)   "zhangliu"
  2)   "4054756186304127"

# 以121.446617 31.205593(张三位置)为圆心，3000m为半径，查询返回用户及其GeoHash值去2个
127.0.0.1:0>GEORADIUS diner:location 121.446617 31.205593 3000 m WITHHASH COUNT 2
 1)    1)   "zhangsan"
  2)   "4054756138736536"

 2)    1)   "lisi"
  2)   "4054756138536712"

GEORADIUSBYMEMBER

找出位于指定范围内的元素

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

• GEORADIUSBYMEMBER 的中心点是由给定的位置元素决定
• GEORADIUS 使用输入的经度和纬度来决定中心点
• 指定成员的位置被用作查询的中心

使用GEOADD添加地理位置信息时，用标准格式的参数 x,y, 所以经度必须在纬度之前。这些坐标的限制是可以被编入索引的，区域面积可以很接近极点但是不能索引。具体的限制，由 EPSG:900913 / EPSG:3785 / OSGEO:41001 规定如下： • 有效的经度从 - 180 度到 180 度。 • 有效的纬度从 - 85.05112878 度到 85.05112878 度。 当坐标位置超出上述指定范围时，该命令将会返回一个错误。

代码实战

打车

假设车辆：

• ID=33
• 经纬度=（116.034579，39.030452）

可用一个GEO集合保存所有车辆的经纬度，集合key：cars:locations。 如下命令即可将ID=33车辆的当前经纬度存入GEO集合：

GEOADD cars:locations 116.034579 39.030452 33

当用户想寻找自己附近的网约车，LBS应用就能使用GEORADIUS。 如LBS应用执行下面命令：

# 根据输入的用户经纬度信息，查找以该经纬度为中心的5公里内车辆信息，返回给LBS应用
GEORADIUS cars:locations 116.054579 39.030452 5 km ASC COUNT 10

进一步限定返回的车辆信息：

• ASC，让返回的车辆信息按距离中心位置从近到远排序，以方便选择最近车辆
• COUNT，指定返回的车辆信息的数量 可能5公里范围内车辆很多，返回全部会占用较多数据带宽

可以看到，使用GEO数据类型可以非常轻松地操作经纬度这种信息。

• 更新坐标

• 查找附近的人