写点什么

redis 系列之——数据类型 geospatial:你隔壁有没有老王?

用户头像
诸葛小猿
关注
发布于: 2020 年 07 月 22 日
redis系列之——数据类型geospatial:你隔壁有没有老王?

Redis系列目录



redis系列之——分布式锁



redis系列之——缓存穿透、缓存击穿、缓存雪崩



redis系列之——Redis为什么这么快?



redis系列之——数据持久化(RDB和AOF)



redis系列之——一致性hash算法



redis系列之——高可用(主从、哨兵、集群)



redis系列之——事物及乐观锁



redis系列之——数据类型geospatial:你隔壁有没有老王?



redis系列之——数据类型bitmaps:今天你签到了吗?



布隆过滤器是个啥!



一个稍稍可人的头像,或者一个吸睛的名字,亦或一条有趣的个性签名,再打开微信“附近的人”功能,只需不多时,便会有几个、十几个陌生人主动打招呼,这些打招呼的人里面,除去一些营销推广、利益交换外,剩下的大多是“约P”、“约聊”等,其中,不乏一些发展为劈腿、婚外情、一夜情、精神出gui等各种扭曲的情感纠纷。





今天,我们不聊社交App的产品经理们为什么都做”附近的人“,我们聊一聊如何实现“附近的人”这个功能。





经纬度



正式开始之前,我们先来回顾一下多年以前学习过的经纬度是什么。正在看文章的你来回答一下,别看了,说的就是你!





对,你说的差不多了,还没有完全忘记,不错。我来补充一下:



将一张世界地图铺开,以赤道为界将地球分成南北,以本初子午线将地球分成东西。赤道和本初子午线都是0度;



以赤道0度开始,向上和向下分别分出90度,南极和北极分别为南纬90度和北纬90度,南极到北极的跨度是(-90,90),其中赤道到南极称为南纬,赤道到北极称为北纬;



从本初子午线0度开始,向左和向右分别分出180度,跨度是(-180,180),其中本初子午线向左称为西经,本初子午线向右称为东经。



要想算出正确的geohash,经纬度一定不能超出这两个范围,同时注意,地球是圆的,这两个数字的单位不是距离,而是角度。





如何实现



说到定位,很多人第一反应应该是,实时上报经纬度,数据库中提前存储好所有的经纬度,然后用上报的经纬度和数据库中的经纬度进行比较,计算出附近的人或共享单车。这种做法需要循环遍历,数据库中的数据量大,查询慢,效率低。



那么,这些app是如何做到既能够精确定位,又能够实时查询的呢?答案就是使用geohash。redis的"数据类型"geospatial就能计算出geohash。redis使用geohash技术将实时上报的精度和纬度,通过一定的算法转化成最长12个字符的字符串,两个位置的经纬度计算的字符串的前缀越相同,则两个位置离得越近。这样一来就可以通过数据库的like加上geohash的前几位模糊查询数据库的数据了。比如ofo共享单车,数据库中用一张表t_bike专门存储ofo的每一辆车的编号no、经度longitude 、纬度latitude、geohash等字段,当每一辆车上报自己的经纬度时,同时计算一个geohash存到表中;当用户要用车时,上报用户的实时位置的经纬度,并计算一个hash值,比如hash=efgrtv98fjng,那么可以使用:



select * from t_bike where geohash like 'efgrtv98%'



就可以找到附近有多少车了。like后面使用的hash位数越多,查找的范围越准确。



查询的前提是开启实时定位功能。



Geohash技术



geohash技术就是将经纬度转换成最长12个字符的字符串,同时两个位置越近,生成的字符串的前缀越一致。这是如何实现的呢?



例如,东方明珠的经纬度,东经121.506377,北纬31.245105。



下面就以东方明珠为例,简单说一下如何将这两个经纬度计算成一个hash字符串的。



geohash的计算



1.使用二分法生成二进制



将纬度(-90,90)分成两个区间,(-90,0)和(0,90),如果目标纬度落在左边区间则记为0,否则记为1;再将目标纬度所在的那个区间在通过二分法分成两个相等的区间,如果目标纬度落在左边区间则记为0,否则记为1,以此类推。



同样的,将经度(-180,180)也通过这种方式计算。



最终,经度和纬度计算后,分别得到一个由0和1组成的二进制。



假如,东方明珠的经纬度计算后,得到两个二进制位:



经度:110101100101001110111100011010
纬度:101011000101010000110101100101



2.合并二进制



将上面的两个二进制按照“偶数位放经度,奇数位放纬度”的原则,从0位开始数起,合并成一个二进制。



可以理解成将纬度向后移动一位,然后将两行压成一行。





结果: 111001100111100000110011000110101000111110110001011010011001



3.二进制转换成十进制



把上面合并后的60位二进制,按照从左往右,每5位划分成1个组,如果最后一组如果不足5位就用0补齐到5位。分组后所示:



分组结果: 11100 11001 11100 00011 00110 00110 10100 01111 10110 00101 10100 11001



将上面的每组二进制分别转成十进制:



十进制结果: 28 25 28 3 6 6 20 15 22 5 20 25



4.十进制转base32字符串



使用base32编码表,将每个十进制数替换成编码表中的字符,获得一个字符串。



base32编码表如下:





转化后的字符串:



base32字符串:4Z4CGGUPWFUZ



这就是模拟东方明珠的经纬度生产的geohash的值(不是真实值)。



geohash的精度



geohash这个字符串在地图上表示一个矩形的块。





hash的字符串长1位-12位,对应精度的级别1-12级。字符串越长,位置越精确。



上面模拟的东方明珠的hash有12位字符串,精度在37mm以内。上面可以看出,6位hash的精度在1.2km以内。所以当两个hash的前6位相同时,就可以将范围缩小到1.2km以内了。在实际的应用中,我们就可以通过调整精度级别控制搜索的范围。





geohash的边界问题



geohash的区块中,同一个区块内部的点被认为是最近的。如下图,如果你在东方明珠圆圈的中心,搜索最近的便利店,你会搜索到A点,而搜索不到B点,虽然B点是最近的。这就是geohash的边界问题。这个该如何解决呢?



其实,就是将该区块上下左右以及四个对角的8个区块的hash都计算一遍,分别计算这些便利店和自己之间的距离,找到最近的一家。因为这是的数据量已经非常小了,计算周边的8个块也很快。





Redis对地理位置的支持



可以通过编程的方式实现上面的计算过程,当然也可以直接使用redis计算geohash。



redis中的geospatial本质是使用sorted set存储的。使用的也是geohash技术。经度二进制和纬度二进制,通过上面介绍的“偶数位放经度,奇数位放纬度”的原则,形成一个独特的52位二进制。sorted set存储每一个成员时,会给每一个成员一个分数用于排序,分数值是一个双精度的64位浮点型数字字符串,它能包括的整数范围是-(2^53)+(2^53)。所以使用sorted set存储52位的二进制不会丢失精度。同时,这种格式的数据通过半径查询时,支持查询中间的1个区块和周边的8个区块,并丢弃半径意外的元素,可以解决geohash的边界问题。



实际使用时,可以提前将一份各地区的经纬度表格,通过redis命令导入到redis内存中,然后可以通过相关的redis命令计算每个地区的geohash,并且可以搜索指定范围内,redis中存在的地区有哪些,同时也可以计算两个经纬度之间的距离。



redis> GEOADD china:city 121.47 31.23 shanghai #添加上海的经纬度
(integer) 1
redis> GEOADD china:city 116.40 39.90 beijing #添加北京的经纬度
(integer) 1
redis> GEODIST china:city shanghai beijing km #计算上海和北京之间的直线距离
"1067.3788"
redis> GEORADIUS china:city 116 39 1500 km #找到离经纬度为116,39的位置1500km以内的地方有哪些 ,因为redis中只有两个城市,所以只能显示两个
1) "beijing"
2) "shanghai"
redis> GEOHASH china:city beijing #获得北京的geohash
1) "wx4fbxxfke0"



参考资料



redis中geospatial相关的命令有6个,具体学习可以参考官网。redis官网





这一期就到这里。



完成,收工!!





传播知识,共享价值】,感谢小伙伴们的关注和支持,我是【诸葛小猿】,一个彷徨中奋斗的互联网民工。





发布于: 2020 年 07 月 22 日阅读数: 297
用户头像

诸葛小猿

关注

我是诸葛小猿,一个彷徨中奋斗的互联网民工 2020.07.08 加入

公众号:foolish_man_xl

评论

发布
暂无评论
redis系列之——数据类型geospatial:你隔壁有没有老王?