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官网





这一期就到这里。



完成，收工！！





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