1.1.1. 08.GeoHash 算法


如今移动互联网时代 LBS(Location Based Service 基于位置服务) 应用越来越多,如交友 app 查找附近的人,外卖 app 查找附近的餐馆,地图 app 查找附近的地点等等。那么这些究竟是如何实现的呢?

我们都知道,地球的位置是使用二维经纬度来表示的,经度 [-180, 180], 维度 [-90, 90]。只要给出一个地点的经纬度,我们就知道它在地球上的那个位置。

通过 sql 来计算 “附近的人”

通过 sql 来计算附近的人

比如我们要找“附近的人”,我们的坐标是 (x0,y0),搜索半径为 r。那么使用如下 SQL 即可:

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

但是会有什么问题呢:

  • 当并发量大的时候,会搞垮数据库。
  • 计算的是一个矩形的位置,而不是以我为中心 r 公里为半径的圆形方位。
  • 精准度比较低。我们知道地球不是平面坐标系,而是一个圆球,这种矩形计算在长距离计算时会有很大误差

使用 Redis 的 GeoHash

GeoHash 算法是将二维经纬度数据映射到一维的整数上,把所有的元素都挂载到了一条数轴上。在数轴上找到我们的点,然后就可以获取附近的点了。

  • 将地球看成一个二维平面
  • 然后划分为一系列的正方形方格,好比围棋棋盘。
  • 将地图坐标都表如所在方格中。方格越小,精度越高。
  • 然后进行编码 编码原理:设想一个正方形的蛋糕摆在你面前,二刀下去均分分成四块小正方形,这四个小正方形可以分别标记为 00,01,10,11 四个二进制整数。然后对每一个小正方形继续用二刀法切割一下,这时每个小小正方形就可以使用 4bit 的二进制整数予以表示。然后继续切下去,正方形就会越来越小,二进制整数也会越来越长,精确度就会越来越高。

    GeoHash原理

原理

GeoHash 原理

主要分为三步

  • 将三维的地球变为二维的坐标
  • 在将二维的坐标转换为一维的点块
  • 最后将一维的点块转换为二进制在通过 base32 编码

Redis 的 Geohash 基于 zset。

指令

添加一个或多个,geoadd [key] [lon1] [lat1] [member1] [lon2] [lat2] [member2] ... (lon:经度,lat:维度)

127.0.0.1:6379> geoadd city 120.20000 30.26667 hangzhou  116.41667 39.91667 beijing 121.47 31.23 shanghai
(integer) 3

geohash 没有删除,但是 geohash 基于 zset 数据结构,所以直接使用 zrem 就行了

127.0.0.1:6379> zrem city hangzhou
(integer) 1

计算两个元素之间的距离,geogist [key] [member1] [member2] [unit]

127.0.0.1:6379> geodist city beijing shanghai km
"1068.3890"

获取一个或多个元素位置,geopos [key] [member1] [member2]...

127.0.0.1:6379> geopos city beijing shanghai
1) 1) "116.41667157411575317"
   2) "39.91667095273589183"
2) 1) "121.47000163793563843"
   2) "31.22999903975783553"

获取一个或多个元素 hash 值,geohash [key] [member1]....

127.0.0.1:6379> geohash city beijing shanghai
1) "wx4g14s53n0"
2) "wtw3sj5zbj0"

获取附近的元素,georadiusbymember [key] [member1] [num] [unit] [withcoord|withdist|withhash] [count] [num] [asc|desc]

不会排除自己。

127.0.0.1:6379> geoadd company 116.48105 39.996794 juejin 116.514203 39.905409 ireader 116.489033 40.007669 meituan 116.562108 39.787602 jd 116.334255 40.027400 xiaomi
(integer) 5

# 查找 ireader 附近 20KM 以内,最多 3 个公司,按顺序排列,它不会排除自己
127.0.0.1:6379> georadiusbymember company ireader 20 km count 3 asc
1) "ireader"
2) "juejin"
3) "meituan"

# 查找 ireader 附近 20KM 以内,最多 3 个公司,按逆序排列,它不会排除自己
127.0.0.1:6379> georadiusbymember company ireader 20 km count 3 desc
1) "jd"
2) "meituan"
3) "juejin"

# 三个可选参数 withcoord(坐标)、 withdist(距离)、 withhash(hash 值)。
127.0.0.1:6379> georadiusbymember company ireader 20 km withcoord withdist withhash  count 3 asc
1) 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"

根据坐标查找附近元素,georadius [key] [lon] [lat] [num] [unit] [withcoord|withdist|withhash] [count] [num] [asc|desc]

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 集合大小。

Copyright © Kagami丶 2019 all right reserved,powered by Gitbook该文件修订时间: 2019-12-10 21:47:13

results matching ""

    No results matching ""