关于后端:Redis-实战篇GEO助我邂逅附近女神

6次阅读

共计 6204 个字符，预计需要花费 16 分钟才能阅读完成。

码老湿，浏览了你的巧用数据类型实现亿级数据统计之后，我学会了如何熟能生巧的应用不同的数据类型（String、Hash、List、Set、Sorted Set、HyperLogLog、Bitmap）去解决不同场景的统计问题。

产品经理说他有一个 idea，为宽广少男少女提供一个连贯彼此的机会

让处于这最美的年龄的少男少女能在每一个十二时刻里能邂逅到那个 Ta。

所以就想开发一款 App，用户登陆后能发现左近的那个 Ta，连贯彼此。

我该如何实现发现 左近的人 ？我也心愿通过这个 App 邂逅女神……

记忆中，一个上班的夜晚，她从人群中轻捷的挪动着，那高挑苗条的身材像沉没在空间中的一个飘逸的音符。她的眼睛充斥明澈的阳光和生机，她的双眸中印着银河系的星光。

多锤炼本人的表达能力，特地是在工作中。很多人说「干活的不如那些做 PPT 的」，实际上老板都不傻，为何他们会更认可那些做 PPT 的？

因为他们从老板的角度思考问题，对他而言，须要的是一个「解决方案」。多从一个创造者的视角去思考问题，而不是局限在用程序员的视角思考问题；

多想一下这个货色到底给人提供什么价值，而不是「我要怎么实现它」。当然，怎么实现是必须的，但通常不是最重要的。

经纬度是经度与纬度的合称组成一个 坐标零碎 。又称为地理坐标零碎，它是一种利用三度空间的球面来定义地球上的空间的球面坐标零碎，可能标示地球上的 任何一个地位（小数点后 7 位，精度能够到 1 厘米）。

经度的范畴在 (-180, 180]，纬度的范畴在(-90, 90]，纬度正负以赤道为界，北正南负，经度正负以本初子午线 (英国格林尼治天文台) 为界，东正西负。

左近的人 也就是常说的 LBS (Location Based Services，基于位置服务)，它围绕用户以后地理位置数据而开展的服务，为用户提供精准的邂逅服务。

左近的人 核心思想如下：

以“我”为核心，搜寻左近的 Ta；
以“我”以后的地理位置为准，计算出他人和“我”之间的间隔；
按“我”与他人间隔的远近排序，筛选出离我最近的用户。

计算「左近的人」，通过一个坐标计算这个坐标左近的其余数据，依照间隔排序，如何下手呢？

以用户为核心，给定一个 1000 米作为半径画圆，那么圆形区域内的用户就是咱们想要邂逅的「左近的人」。

将经纬度存储到 MySQL ：

CREATE TABLE `nearby_user` (`id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(255) DEFAULT NULL COMMENT '名称',
  `longitude` double DEFAULT NULL COMMENT '经度',
  `latitude` double DEFAULT NULL COMMENT '纬度',
  `create_time` datetime DEFAULT NULL ON UPDATE CURRENT_TIMESTAMP COMMENT '创立工夫',
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

可是总不能遍历所有的「女神」经纬度与本人的经纬度数据计算在依据间隔排序，这个计算量也太大了。

咱们能够通过区域来过滤出无限「女神」坐标数据，再对矩形区域内的数据进行全量间隔计算再排序，这样计算量明显降低。

如何划分矩形区域呢？

在圆形外套上一个正方形，依据用户经、纬度的最大最小值（经、纬度 + 间隔），作为筛选条件过滤数据，就很容易将正方形内的「女神」信息搜寻进去。

多进去的一些区域咋办？

多进去的这部分区域内的用户，到圆点的间隔肯定比圆的半径要大，那么咱们就计算用户中心点与正方形内所有用户的间隔，筛选出所有间隔小于等于半径的用户 ，圆形区域内的所用户即符合要求的 左近的人。

为了满足高性能的矩形区域算法，数据表须要在经纬度坐标加上复合索引 (longitude, latitude)，这样能够最大优化查问性能。

依据经纬度和间隔获取外接矩形最大、最小经纬度以及依据经纬度计算间隔应用了一个第三方类库：

<dependency>
     <groupId>com.spatial4j</groupId>
     <artifactId>spatial4j</artifactId>
     <version>0.5</version>
</dependency>

获取到外接矩形后，以矩形的 最大最小经、纬度值 搜寻正方形区域内的用户，再剔除超过指定间隔的用户，就是最终的 左近的人。

/**
 * 获取左近 x 米的人
 *
 * @param distance 搜寻间隔范畴 单位 km
 * @param userLng  以后用户的经度
 * @param userLat  以后用户的纬度
 */
public String nearBySearch(double distance, double userLng, double userLat) {
  //1. 获取外接正方形
  Rectangle rectangle = getRectangle(distance, userLng, userLat);
  //2. 获取地位在正方形内的所有用户
  List<User> users = userMapper.selectUser(rectangle.getMinX(), rectangle.getMaxX(), rectangle.getMinY(), rectangle.getMaxY());
  //3. 剔除半径超过指定间隔的多余用户
  users = users.stream()
    .filter(a -> getDistance(a.getLongitude(), a.getLatitude(), userLng, userLat) <= distance)
    .collect(Collectors.toList());
  return JSON.toJSONString(users);
}

// 获取外接矩形
private Rectangle getRectangle(double distance, double userLng, double userLat) {return spatialContext.getDistCalc()
    .calcBoxByDistFromPt(spatialContext.makePoint(userLng, userLat), 
                         distance * DistanceUtils.KM_TO_DEG, spatialContext, null);
}

     /***
     * 球面中，两点间的间隔
     * @param longitude 经度 1
     * @param latitude  纬度 1
     * @param userLng   经度 2
     * @param userLat   纬度 2
     * @return 返回间隔，单位 km
     */
    private double getDistance(Double longitude, Double latitude, double userLng, double userLat) {return spatialContext.calcDistance(spatialContext.makePoint(userLng, userLat),
                spatialContext.makePoint(longitude, latitude)) * DistanceUtils.DEG_TO_KM;
    }

因为用户间间隔的排序是在业务代码中实现的，能够看到 SQL 语句也十分的简略。

SELECT * FROM nearby_user
WHERE 1=1
AND (longitude BETWEEN #{minlng} AND #{maxlng})
AND (latitude BETWEEN #{minlat} AND #{maxlat})

然而数据库查问性能毕竟无限，如果「左近的人」查问申请十分多，在高并发场合，这可能并不是一个很好的计划。

咱们一起剖析下 LBS 数据的特点：

每个「女神」都有一个 ID 编号，每个 ID 对应着经纬度信息。
「宅男」登陆 app 获取「心动女生」的时候，app 依据「宅男」的经纬度查找左近的「女神」。
获取到地位合乎的「女神」ID 列表后，再从数据库获取 ID 对应的「女神」信息返回用户。

数据特点就是一个女神（用户）对应着一组经纬度，让我想到了 Redis 的 Hash 构造。也就是一个 key（女神 ID）对应着一个 value（经纬度）。

Hash 看起来如同能够实现，然而 LBS 利用除了记录经纬度以外，还须要对 Hash 汇合中的数据进行范畴查问，依据经纬度换算成间隔排序。

而 Hash 汇合的数据是无序的，显然不可取。

Sorted Set 类型是是否适合呢？因为它能够排序。

Sorted Set 类型也是一个 key 对应一个 value，key 元素内容，而 value ` 就是该元素的权重分数。

Sorted Set 能够依据元素的权重分数对元素排序，这样看起来就满足咱们的需要了。

比方，Sorted Set 的元素是「女神 ID」，元素对应的权重 score 是经纬度信息。

问题来了，Sorted Set 元素的权重值是一个浮点数，经纬度是经度、纬度两个值，咋办呢？能不能将经纬度转换成一个浮点数呢？

思路对了，为了实现对经纬度比拟，Redis 采纳业界宽泛应用的 GeoHash 编码，别离对经度和纬度编码，最初再把经纬度各自的编码组合成一个最终编码。

这样就实现了将经纬度转换成一个值，而 Redis 的 GEO 类型的底层数据结构用的就是 Sorted Set来实现。

咱们来看下 GeoHash 如何将经纬度编码的。

对于 GeoHash 可参考：https://en.wikipedia.org/wiki…

GeoHash 算法将二维的经纬度数据映射到一维的整数，这样所有的元素都将在挂载到一条线上，间隔凑近的二维坐标映射到一维后的点之间间隔也会很靠近。

当咱们想要计算「左近的人时」，首先将指标地位映射到这条线上，而后在这个一维的线上获取左近的点就行了。

GeoHash 编码会把一个经度值编码成一个 N 位的二进制值，咱们来对经度范畴 [-180,180] 做 N 次的二分区操作，其中 N 能够自定义。

在进行第一次二分区时，经度范畴 [-180,180] 会被分成两个子区间：[-180,0) 和[0,180]（我称之为左、右分区）。

此时，咱们能够查看一下要编码的经度值落在了左分区还是右分区。如 果是落在左分区，咱们就用 0 示意；如果落在右分区，就用 1 示意。

这样一来，每做完一次二分区，咱们就能够失去 1 位编码值（不是 0 就是 1）。

再对经度值所属的分区再做一次二分区，同时再次查看经度值落在了二分区后的左分区还是右分区，依照方才的规定再做 1 位编码。当做完 N 次的二分区后，经度值就能够用一个 N bit 的数来示意了。

所有的地图元素坐标都将搁置于惟一的方格中。方格越小，坐标越准确。而后对这些方格进行整数编码，越是凑近的方格编码越是靠近。

编码之后，每个地图元素的坐标都将变成一个整数，通过这个整数能够还原出元素的坐标，整数越长，还原进去的坐标值的损失水平就越小。对于「左近的人」这个性能而言，损失的一点精确度能够忽略不计。

比方对经度值等于 169.99 进行 4 位编码（N = 4，做 4 次分区）, 把经度区间 [-180,180] 分成了左分区[-180,0) 和右分区[0,180]。

169.99 属于右分区，应用 1 示意第一次分区编码；
再将 169.99 通过第一次划分所属的 [0, 180] 区间持续分成 [0, 90) 和 [90, 180]，169.99 仍然在右区间，编码‘1’。
将[90, 180] 分为[90, 135) 和 [135, 180]，这次落在左分区，编码‘0’。

如此，最初咱们就失去一个 4 位的编码。

而纬度的编码思路跟经度也是一样的，不再赘述。

如果计算的经纬度编码别离是 11011 和 00101`，指标编码第 0 位则从经度第 0 位的值 1 作为目标值，指标编码的第 1 位则从纬度第 0 位值 0 作为目标值，以此类推：

就这样，经纬度（35.679，114.020）就能够应用 1010011011 示意，而这个值就能够作为 SortedSet 的权重值实现排序。

GEO 类型是将经纬度的通过 GeoHash 编码的合并值作为 Sorted Set 元素的 score 权重，Redis 的 GEO 有哪些指令呢？

咱们须要把登陆 app 的女生 ID 和对应的经纬度存到 Sorted Set 外面。

更多 GEO 类型指令可参考：https://redis.io/commands#geo

GEOADD

Redis 提供了 GEOADD key longitude latitude member 命令，将一组经纬度信息和对应的「女神 ID」记录到 GEO 类型的汇合中，如下：一次记录多个用户（苍井空、波多野结衣）的经纬度信息。

GEOADD girl:localtion 13.361389 38.115556 "苍井空" 15.087269 37.502669 "波多野结衣"

GEORADIUS

我登陆了 app，获取本人的经纬度信息，如何查找以这个经纬度为核心的肯定范畴内的其余用用户呢？

Redis GEO 类型提供了 GEORADIUS 指令：会依据输出的经纬度地位，查找以这个经纬度为核心的肯定范畴内的其余元素。

假如本人的经纬度是（15.087269 37.502669），须要获取左近 10 km 的「女神」并返回给 LBS 利用：

GEORADIUS girl:locations 15.087269 37.502669 km ASC COUNT 10

ASC 能够实现让「女神」信息依照这个间隔本人的经纬度由近到远排序。

COUNT 选项示意指定返回的「女神」数量，避免左近太多「女神」，节俭带宽资源。

如果感觉本人须要更多女神，那么能够无限度，然而须要留神身材，多吃鸡蛋补一补。

用户下线后，如删除下线的「女神」经纬度呢？

这个问题问得好，GEO 类型是基于 Sorted Set 实现的，所以能够借用 ZREM 命令实现对地理位置信息的删除。

比方删除「苍井空」的地位信息：

ZREM girl:localtion "苍井空"

GEO 自身并没有设计新的底层数据结构，而是间接应用了 Sorted Set 汇合类型。

GEO 类型应用 GeoHash 编码方法实现了经纬度到 Sorted Set 中元素权重分数的转换，这其中的两个要害机制就是对二维地图做区间划分，以及对区间进行编码。

一组经纬度落在某个区间后，就用区间的编码值来示意，并把编码值作为 Sorted Set 元素的权重分数。

在一个地图利用中，车的数据、餐馆的数据、人的数据可能会有百万千万条，如果应用 Redis 的 Geo 数据结构，它们将全副放在一个 zset 汇合中。

在 Redis 的集群环境中，汇合可能会从一个节点迁徙到另一个节点，如果单个 key 的数据过大，会对集群的迁徙工作造成较大的影响，在集群环境中单个 key 对应的数据量不宜超过 1M，否则会导致集群迁徙呈现卡顿景象，影响线上服务的失常运行。

所以，这里倡议 Geo 的数据应用独自的 Redis 集群实例部署。

如果数据量过亿甚至更大，就须要对 Geo 数据进行拆分，按国家拆分、按省拆分，按市拆分，在人口特大城市甚至能够按区拆分。

这样就能够显著升高单个 zset 汇合的大小。

伟人肩膀

https://segmentfault.com/a/11…
https://juejin.cn/book/684473…
https://cloud.tencent.com/dev…
Redis 核心技术与实战

正文完

后端

发表至：后端

2021-07-09

0

关于后端:EECS-4313感想体会

关于后端:ES系列一简介与安装

关于后端:体验IntelliJ-IDEA的远程开发Remote-Development

关于后端:吊炸天的-JDhotkey-京东开源单机-QPS-高达-370000

关于php:PHP中DirectIO直操作文件扩展的使用

关于后端:Redis-实战篇GEO助我邂逅附近女神

开篇寄语

什么是面向 LBS 利用

MySQL 实现

实战

尝试 Redis Hash 未果

Sorted Set 初见端倪

GEOHash 编码

合并经纬度编码

Redis GEO 实现

小结

站内搜索