近水楼台 — GeoHash

近水楼台 — GeoHash

用数据库来计算附近的人

地球上的任一位置都可以用经纬度(经度:东西方向,以本初子午线为起始点;纬度:南北方向,以赤道为起始点)来表示,如果将坐标位置存在数据库中,它的数据模型应该是:

坐标表(元素id,经度值x,纬度值y)

那么计算 “附近的人” 时,给定一个坐标点A(x,y),取出坐标表中所有的记录,利用 勾股定理 分别与 A 点计算距离,然后按照距离进行排序。

勾股定理:c² = a² + b²

问题是当坐标越来越多,计算量会变得越来越大,性能会随之下降。所以一般的做法是 划分一个矩形区域,对这个区域中的坐标进行计算再排序,这样可以明显的减少计算量。如何计算这个区域呢,可以指定一个半径 r,用一条 sql 就能圈出来。如果用户对筛选出来的结果不满意,就扩大这个半径继续计算。

当前位置 (a,b)
select id, x, y from 坐标表 where a-r < a < a+r and b-r < b < b+r

当请求量小的时候,这种数据库存储方式足以应对了。但是在并发量很高的情况下,数据库的查询性能将会十分有限,这时候就需要更好的方案了。

GeoHash 算法

GeoHash 算法是业界比较通用的地址位置距离排序算法,它将二维的经纬度数据映射到一维的整数,这样所有的元素都将挂载到一条线上,距离靠近的二维坐标映射到一维的点之间的距离也会很近。当要计算附近的人时,首先将目标位置映射到这条线上,然后在这个一维的线上获取附近的点就行。

该映射算法将地球看作一个二维平面,在平面中划分了一系列正方形的方格,所有的位置坐标都放在唯一的方格中。
每一个方格都会计算一个编码,方格越小,编码越长,位置越精确。如何进行编码?以二刀法为例:首先对一个大正方形二切为四份,每一份都用 2bit 的二进制数表示 00、01、10、11。然后继续对每个小方格切分,此时每个小方格需要用 4bit 的二进制数表示。以此往复,正方形会越来越小,二进制数越来越长,位置越来越精确。

编码之后,每个坐标都变成了一个整数,通过该整数可以还原出坐标,整数越长,还原出来的坐标值损失程度就越小。对于附近的人这个功能而言,一点点的精度损失可以忽略不计。然后,Geo 算法会进一步将整数做 base32 编码最终变成一个字符串。

在 redis 中,经纬度使用 52 位整数进行编码,存储到 zset 结果中,value 是元素的 key,score 是 GeoHash 的 52 位整数值。zset 的 score 虽然是浮点数,但是对于 52 整数可以无损存储。

在 redis 进行 Geo 查询时,通过 zset 的 score 排序可以得到该坐标附近的其他元素,通过将 score 还原成坐标值就能得到原始坐标了。

Geo 指令的使用

redis 提供的 Geo 指令有 6 个,由于它是一个 zset 结构,所以也能够使用 zset 的指令。

增加坐标 geoadd

geoadd key longitude latitude member [longitude latitude member …]

  • key:zset 的 key
  • longitude:经度
  • latitude:纬度
  • member:zset 的 member,即元素值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
127.0.0.1:6379> geoadd company 116.48105 39.996794 juejin
(integer) 1
127.0.0.1:6379> geoadd company 116.514203 39.905409 ireader
(integer) 1
127.0.0.1:6379> geoadd company 116.489033 40.007669 meituan
(integer) 1
127.0.0.1:6379> geoadd company 116.562108 39.787602 jd
(integer) 1
127.0.0.1:6379> geoadd company 116.334225 40.027400 xiaomi
(integer) 1
127.0.0.1:6379> zrange company 0 -1 withscores # zset 命令也能使用
1) "jd"
2) "4069154033428715"
3) "xiaomi"
4) "4069880898694078"
5) "ireader"
6) "4069886008361398"
7) "juejin"
8) "4069887154388167"
9) "meituan"
10) "4069887179083478"

计算距离 geodist

geodist key member1 member2 [unit]

  • key:元素 key
  • member1:第一个成员
  • member2:第二个成员
  • unit:单位,可选值:m、km、ml、ft 分别代表:米、千米、英里、尺。
1
2
3
4
5
6
7
8
9
10
127.0.0.1:6379> geodist company juejin ireader km
"10.5501"
127.0.0.1:6379> geodist company juejin meituan km
"1.3878"
127.0.0.1:6379> geodist company juejin meituan m
"1387.8166"
127.0.0.1:6379> geodist company juejin jd km
"24.2739"
127.0.0.1:6379> geodist company juejin xiaomi km
"12.9628"

获取元素原始坐标 geopos

geopos key member [member …]

1
2
3
4
5
6
7
8
9
10
11
127.0.0.1:6379> geopos company juejin
1) 1) "116.48104995489120483"
2) "39.99679348858259686"
127.0.0.1:6379> geopos company ireader
1) 1) "116.5142020583152771"
2) "39.90540918662494363"
127.0.0.1:6379> geopos company juejin ireader
1) 1) "116.48104995489120483"
2) "39.99679348858259686"
2) 1) "116.5142020583152771"
2) "39.90540918662494363"

由于 GeoHash 对二维坐标的计算是有损的,通过映射回来的坐标值有一些差别,但这点误差是能够接受的。

获取元素 Hash 值

geohash key member [member …]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
127.0.0.1:6379> geohash company juejin # 最终 hash 值
1) "wx4gd94yjn0"
127.0.0.1:6379> geohash company ireader # 最终 hash 值
1) "wx4g52e1ce0"
127.0.0.1:6379> zrange company 0 -1 withscores # 坐标编码的 52 位整数值
1) "jd"
2) "4069154033428715"
3) "xiaomi"
4) "4069880898694078"
5) "ireader"
6) "4069886008361398"
7) "juejin"
8) "4069887154388167"
9) "meituan"
10) "4069887179083478"

这个编码字符串就是上面说的 base64 编码,通过这个编码去 http://geohash.org/{hash} 上能够直接定位。

查找附近的人 georadiusbymemer

根据目标元素查找

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

  • member:目标成员
  • radius m|km|ft|mi:半径
  • WITHCOORD:显示经纬度
  • WITHDIST:显示距离
  • WITHHASH:显示编码值
  • COUNT c:最近的多少个单位

根据指定坐标查找

georadius key longitude latitude radius m|km|ft|mi [WITHCOORD] [WITHDIST] [WITHHASH] [COUNT c

  • 参数和 georadiusbymember 基本一致,只不过将 member 替换成了 longitude latitude

1)查找半径 20 千米以内离 ireader 最近的三个公司,它不会排除自身。

1
2
3
4
5
6
7
8
127.0.0.1:6379> georadiusbymember company ireader 20 km count 3 desc # 降序
1) "jd"
2) "meituan"
3) "juejin"
127.0.0.1:6379> georadiusbymember company ireader 20 km count 3 asc # 升序
1) "ireader"
2) "juejin"
3) "meituan"

2)查找半径 20 千米以内离 ireader 最近的三个公司,分别显示距离、编码值、经纬度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
127.0.0.1:6379> georadiusbymember company ireader 20 km count 3 asc WITHDIST WITHHASH WITHCOORD
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"
127.0.0.1:6379>

注意事项

在一个重度使用 “附近的人” 应用中,数据量可能会有几百万甚至几千万条,如果使用 redis 的 Geo 数据结构,他们会被全部放入一个 zset 集合中。在 redis 集群环境中,集合可能从一个节点迁移到另一个节点,如果单个 key 数据过大,会对迁移工作造成很大影响。集群环境中单个 key 的大小不宜超过 1M。

所以一般建议对 Geo 的数据使用单独的 redis 实例部署,不使用集群环境。如果数量量特别大,需要对 Geo 数据进行拆分,按国家拆分、按市拆分、这样可以显著降低单个 key 的大小。

# redis

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×