目录

使用 Redis-GEO HASH 实现实时查看附近的人

https://en.wikipedia.org/wiki/Geohash

GeoHash算法将二维的经纬度数据映射到一维的整数,这样所有的元素都将在挂载到一条线上,距离靠近的二维坐标映射到一维后的点之间距离也会很接近。

当我们想要计算「附近的人时」,首先将目标位置映射到这条线上,然后在这个一维的线上获取附近的点就行了。

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

在进行第一次二分区时,经度范围[-180,180]会被分成两个子区间:[-180,0) 和[0,180](我称之为左、右分区)。

此时,我们可以查看一下要编码的经度值落在了左分区还是右分区。如果是落在左分区,我们就用 0 表示;如果落在右分区,就用 1 表示。

这样一来,每做完一次二分区,我们就可以得到 1 位编码值(不是0 就是 1)

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

所有的地图元素坐标都将放置于唯一的方格中。方格越小,坐标越精确。然后对这些方格进行整数编码,越是靠近的方格编码越是接近。

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

比如对经度值等于 169.99 进行 4 位编码(N = 4,做 4 次分区),把经度区间[-180,180]分成了左分区[-180,0) 和右分区[0,180]。

  1. 169.99 属于右分区,使用 1 表示第一次分区编码;
  2. 再将 169.99 经过第一次划分所属的 [0, 180] 区间继续分成 [0, 90) 和 [90, 180],169.99 依然在右区间,编码 ‘1’。
  3. 将[90, 180] 分为[90, 135) 和 [135, 180],这次落在左分区,编码 ‘0’。

如此,最后我们就得到一个 4 位的编码。

而纬度的编码思路跟经度也是一样的,不再赘述。

合并经纬度编码

假如计算的经纬度编码分别是 1101100101,目标编码第 0 位则从经度第 0 位的值 1 作为目标值,目标编码的第 1 位则从纬度第 0 位值 0 作为目标值,以此类推:

https://cdn.jsdelivr.net/gh/cexll/cexll.github.io/images/2021/09/640-84baa7b2f9d4499f80e812717d20bf8e.webp

就这样,经纬度(35.679,114.020)就可以使用 1010011011 表示,而这个值就可以作为 SortedSet 的权重值实现排序。

Redis GEO 实现

GEO 类型是将经纬度的经过 GeoHash 编码的合并值作为 Sorted Set 元素的 score 权重,Redis 的 GEO 有哪些指令呢?

我们需要把登陆 app 的女生 ID 和对应的经纬度存到 Sorted Set 里面。

更多 GEO 类型指令可参考:https://redis.io/commands#geo

GEOADD

Redis 提供了 GEOADD key longitude latitude member 命令,将一组经纬度信息和对应的「女神 ID」记录到 GEO 类型的集合中,如下:一次记录多个用户(苍井空、波多野结衣)的经纬度信息。

GEOADD girl:localtion 13.361389 38.115556 "三上悠亚" 15.087269 37.502669 "樱空桃"

GEORADIUS

我登陆了 app,获取自己的经纬度信息,如何查找以这个经纬度为中心的一定范围内的其他用用户呢?

Redis GEO类型提供了 GEORADIUS 指令:会根据输入的经纬度位置,查找以这个经纬度为中心的一定范围内的其他元素。

假设自己的经纬度是(15.087269 37.502669),需要获取附近 10 km 的「女神」并返回给 LBS 应用:

GEORADIUS girl:locations 15.087269 37.502669 km ASC COUNT 10

ASC可以实现让「女神」信息按照这个距离自己的经纬度由近到远排序。

COUNT选项表示指定返回的「女神」数量,防止附近太多「女神」,节省带宽资源。

如果觉得自己需要更多女神,那么可以无限制,但是需要注意身体,多吃鸡蛋补一补

用户下线后,如删除下线的「女神」经纬度呢?

GEO 类型是基于 Sorted Set 实现的,所以可以借用 ZREM 命令实现对地理位置信息的删除。

ZREM girl:localtion "樱空桃"

结尾

GEO 本身并没有设计新的底层数据结构,而是直接使用了 Sorted Set 集合类型。

GEO 类型使用 GeoHash 编码方法实现了经纬度到 Sorted Set 中元素权重分数的转换,这其中的两个关键机制就是对二维地图做区间划分,以及对区间进行编码。

一组经纬度落在某个区间后,就用区间的编码值来表示,并把编码值作为 Sorted Set 元素的权重分数。

在一个地图应用中,车的数据、餐馆的数据、人的数据可能会有百万千万条,如果使用 Redis 的 Geo 数据结构,它们将全部放在一个 zset 集合中。

在 Redis 的集群环境中,集合可能会从一个节点迁移到另一个节点,如果单个 key 的数据过大,会对集群的迁移工作造成较大的影响,在集群环境中单个 key 对应的数据量不宜超过 1M,否则会导致集群迁移出现卡顿现象,影响线上服务的正常运行。

所以,这里建议 Geo 的数据使用单独的 Redis 集群实例部署。

如果数据量过亿甚至更大,就需要对 Geo 数据进行拆分,按国家拆分、按省拆分,按市拆分,在人口特大城市甚至可以按区拆分。

这样就可以显著降低单个 zset 集合的大小。