面向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中元素本身的值保存下来,这样相邻经纬度的查询即可通过编码值的大小范围查询实现。