01-Redis 特殊数据类型之 GeoHash

一、使用数据库实现查找附近的人

众所周知，地球上的任何一个位置都可以使用二维的 经纬度 来表示，经度范围 [-180, 180]，纬度范围 [-90, 90]，纬度正负以赤道为界，北正南负，经度正负以本初子午线 (英国格林尼治天文台) 为界，东正西负。

比如说，北京人民英雄纪念碑的经纬度坐标就是(39.904610, 116.397724)，都是正数，因为中国位于东北半球。

所以，当我们使用数据库存储了所有人的 经纬度 信息之后，我们就可以基于当前的坐标节点，来划分出一个矩形的范围，来得知附近的人，如下图：

所以，我们很容易写出下列的伪 SQL 语句：

1
SELECT id FROM positions WHERE x0 - r < x < x0 + r AND y0 - r < y < y0 + r

如果想进一步知道与每个坐标元素的距离并排序的话，就需要一定的计算。

当两个坐标元素的距离不是很远的时候，我们就可以简单利用 勾股定理 就能够得出他们之间的 距离。不过需要注意的是，地球不是一个标准的球体，经纬度的密度 是 不一样 的，所以我们使用勾股定理计算平方之后再求和时，需要按照一定的系数 加权 再进行求和。当然，如果不准求精确的话，加权也不必了。我们能够差不多能写出如下优化之后的 SQL 语句：

1
2
3
4
5
6
7
8
9
10
11
12
13
SELECT
    * 
FROM
    users_location 
WHERE
    latitude > '.$lat.' - 1 
    AND latitude < '.$lat.' + 1 AND longitude > '.$lon.' - 1 
    AND longitude < '.$lon.' + 1 
ORDER BY
    ACOS(
        SIN( ( '.$lat.' * 3.1415 ) / 180 ) * SIN( ( latitude * 3.1415 ) / 180 ) + COS( ( '.$lat.' * 3.1415 ) / 180 ) * COS( ( latitude * 3.1415 ) / 180 ) * COS( ( '.$lon.' * 3.1415 ) / 180 - ( longitude * 3.1415 ) / 180 ) 
    ) * 6380 ASC 
    LIMIT 10 ';

为了满足高性能的矩形区域算法，数据表也需要把经纬度坐标加上 **双向复合索引(x, y)**，这样可以满足最大优化查询性能。

二、GeoHash 算法简述

这是业界比较通用的，用于 地理位置距离排序 的一个算法，Redis 也采用了这样的算法。

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

它的核心思想就是把整个地球看成是一个 二维的平面，然后把这个平面不断地等分成一个一个小的方格，每一个 坐标元素都位于其中的 唯一一个方格 中，等分之后的 方格越小，那么坐标也就 越精确，类似下图：

经过划分的地球，我们需要对其进行编码：

经过这样顺序的编码之后，如果你仔细观察一会儿，你就会发现一些规律：

  • 横着的所有编码中，第 2 位和第 4 位都是一样的，例如第一排第一个 0101 和第二个 0111，他们的第 2 位和第 4 位都是 1；
  • 竖着的所有编码中，第 1 位和第 3 位都是递增的，例如第一排第一个 0101，如果单独把第 1 位和第 3 位拎出来的话，那就是 00，同理看第一排第二个 0111，同样的方法第 1 位和第 3 位拎出来是 01，刚好是 00 递增一个；

通过这样的规律我们就把每一个小方块儿进行了一定顺序的编码，这样做的 好处 是：每一个元素坐标既能够被 唯一标识 在这张被编码的地图上，也不至于 暴露特别的具体的位置，因为区域是共享的，我可以告诉你我就在公园附近，但是在具体的哪个地方你就无从得知了。

总之，我们通过上面的思想，能够把任意坐标变成一串二进制的编码了，类似于 11010010110001000100 这样 _(注意经度和维度是交替出现的哦…)_，通过这个整数我们就可以还原出元素的坐标，整数越长，还原出来的坐标值的损失程序就越小。对于 附近的人 这个功能来说，损失的一点经度可以忽略不计。

最后就是一个 Base32 (09, az, 去掉 a/i/l/o 四个字母) 的编码操作，让它变成一个字符串，例如上面那一串儿就变成了 wx4g0ec1。

在 Redis 中，经纬度使用 52 位的整数进行编码，放进了 zset 里面，zset 的 value 是元素的 key，score 是 GeoHash 的 52 位整数值。zset 的 score 虽然是浮点数，但是对于 52 位的整数值来说，它可以无损存储。

三、在 Redis 中的 Geo

简介

Redis 的 GEO 特性在 Redis 3.2 版本中推出，这个功能可以将用户给定的地理位置信息储存起来，并对这些信息进行操作。来实现诸如附近位置、摇一摇这类依赖于地理位置信息的功能。geo的数据类型为 zset。

GEO 的数据结构总共有六个常用命令：geoadd、geopos、geodist、georadius、 georadiusbymember、gethash

官方文档：https://www.redis.net.cn/order/3685.html

常用指令

1、geoadd 增加

语法：geoadd key longitude latitude member ...

  • 将给定的空间元素(经度、纬度、名字)添加到指定的键里面。
  • 这些数据会以有序集的形式被储存在键里面，从而使得georadius和georadiusbymember这样的命令可以在之后通过位置查询取得这些元素。
  • geoadd命令以标准的x,y格式接受参数，所以用户必须先输入经度，然后再输入纬度。
  • geoadd能够记录的坐标是有限的：非常接近两极的区域无法被索引。有效的经度介于-180-180度之间，有效的纬度介于-85.05112878 度至 85.05112878 度之间
  • 当用户尝试输入一个超出范围的经度或者纬度时,geoadd命令将返回一个错误。

测试：百度搜索经纬度查询，模拟真实数据

1
2
3
4
5
6
127.0.0.1:6379> geoadd china:city 116.23 40.22 北京
(integer) 1
127.0.0.1:6379> geoadd china:city 121.48 31.40 上海 113.88 22.55 深圳 120.21 30.20 杭州
(integer) 3
127.0.0.1:6379> geoadd china:city 106.54 29.40 重庆 108.93 34.23 西安 114.02 30.58 武汉
(integer) 3

2、geopos 获取集合中任意元素的经纬度坐标

语法：geopos key member [member...]

  • 从key里返回所有给定位置元素的位置（经度和纬度）
  • geopos 获取的经纬度坐标和 geoadd 进去的坐标有轻微的误差，原因是 Geohash 对二维坐标进行的一维映射是有损的，通过映射再还原回来的值会出现较小的差别。对于 「附近的人」 这种功能来说，这点误差根本不是事。
1
2
3
4
5
6
7
8
9
10
127.0.0.1:6379> geopos china:city 北京
1) 1) "116.23000055551528931"
2) "40.2200010338739844"
127.0.0.1:6379> geopos china:city 上海 重庆
1) 1) "121.48000091314315796"
2) "31.40000025319353938"
2) 1) "106.54000014066696167"
2) "29.39999880018641676"
127.0.0.1:6379> geopos china:city 新疆
1) (nil)

3、geodist 计算两个元素之间的距离

语法：geodist key member1 member2 [unit]

  • 返回两个给定位置之间的距离，如果两个位置之间的其中一个不存在，那么命令返回空值

  • 指定单位的参数unit必须是以下单位的其中一个：

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

  • 如果用户没有显式地指定单位参数，那么geodist默认使用 米 作为单位。

  • geodist命令在计算距离时会假设地球为完美的球形，在极限情况下，这一假设最大会造成0.5%的误差。

1
2
3
4
5
6
127.0.0.1:6379> geodist china:city 北京 上海
"1088785.4302"
127.0.0.1:6379> geodist china:city 北京 上海 km
"1088.7854"
127.0.0.1:6379> geodist china:city 重庆 北京 km
"1491.6716"

4、georadius 以给定的经纬度为中心， 找出某一半径内的元素

语法：georadius key longitude latitude radius m|km|ft|mi [withcoord][withdist] [withhash][asc|desc][count count]

  • 以给定的经纬度为中心， 找出某一半径内的元素
  • 重新连接 redis-cli，增加参数 –raw ，可以强制输出中文，不然会乱码
1
2
3
4
5
6
7
8
9
127.0.0.1:6379> georadius china:city 100 30 1000 km #乱码
1) "\xe9\x87\x8d\xe5\xba\x86"
2) "\xe8\xa5\xbf\xe5\xae\x89"
127.0.0.1:6379> exit
[root@localhost bin]#  redis-cli --raw -p 6379
# 在 china:city 中寻找坐标 100 30 半径为 1000km 的城市
127.0.0.1:6379> georadius china:city 100 30 1000 km
重庆
西安

withdist 返回位置名称和中心距离

1
2
3
4
5
127.0.0.1:6379> georadius china:city 100 30 1000 km withdist
重庆
635.2850
西安
963.3171

withcoord 返回位置名称、经纬度

1
2
3
4
5
6
7
127.0.0.1:6379> georadius china:city 100 30 1000 km withcoord
重庆
106.54000014066696167
29.39999880018641676
西安
108.92999857664108276
34.23000121926852302

withdist withcoord 返回位置名称、距离、经纬度，count 限定寻找个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
127.0.0.1:6379> georadius china:city 100 30 1000 km withcoord withdist count 1
重庆
635.2850
106.54000014066696167
29.39999880018641676
127.0.0.1:6379> georadius china:city 100 30 1000 km withcoord withdist count 2
重庆
635.2850
106.54000014066696167
29.39999880018641676
西安
963.3171
108.92999857664108276
34.23000121926852302

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

语法：georadiusbymember key member radius m|km|ft|mi [withcoord][withdist] [withhash][asc|desc][count count]

  • 找出位于指定范围内的元素，中心点是由给定的位置元素决定
1
2
3
4
5
6
127.0.0.1:6379> GEORADIUSBYMEMBER china:city 北京 1000 km
北京
西安
127.0.0.1:6379> GEORADIUSBYMEMBER china:city 上海 400 km
杭州
上海

6、geohash 将二维经纬度转换为一维字符串

语法：geohash key member [member...]

  • Redis使用geohash将二维经纬度转换为一维字符串，字符串越长表示位置更精确，两个字符串越相似表示距离越近。
  • 它是 base32 编码。 你可以使用这个编码值去 http://geohash.org/${hash} 中进行直接定位，它是 Geohash 的标准编码值。
1
2
3
4
5
6
127.0.0.1:6379> geohash china:city 北京 重庆
wx4sucu47r0
wm5z22h53v0
127.0.0.1:6379> geohash china:city 北京 上海
wx4sucu47r0
wtw6sk5n300

zrem:GEO没有提供删除成员的命令，但是因为GEO的底层实现是zset，所以可以借用zrem命令实现对地理位置信息的删除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
127.0.0.1:6379> geoadd china:city 116.23 40.22 beijing
1
127.0.0.1:6379> zrange china:city 0 -1 # 查看全部的元素
重庆
西安
深圳
武汉
杭州
上海
beijing
北京
127.0.0.1:6379> zrem china:city beijing # 移除元素
1
127.0.0.1:6379> zrem china:city 北京 # 移除元素
1
127.0.0.1:6379> zrange china:city 0 -1
重庆
西安
深圳
武汉
杭州
上海

注意事项

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

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

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

Reference

  1. https://www.cnblogs.com/wmyskxz/p/12466945.html
Redis
#Redis
01-Redis 特殊数据类型之 GeoHash
https://flepeng.github.io/041-Redis-41-核心概念-01-Redis-特殊数据类型之-GeoHash/
作者
Lepeng
发布于
2021年1月1日
许可协议