惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

云风的 BLOG
云风的 BLOG
IT之家
IT之家
D
Docker
博客园 - 叶小钗
A
About on SuperTechFans
博客园_首页
Apple Machine Learning Research
Apple Machine Learning Research
Recorded Future
Recorded Future
Stack Overflow Blog
Stack Overflow Blog
腾讯CDC
V
V2EX
S
SegmentFault 最新的问题
量子位
P
Proofpoint News Feed
酷 壳 – CoolShell
酷 壳 – CoolShell
Latest news
Latest news
大猫的无限游戏
大猫的无限游戏
月光博客
月光博客
有赞技术团队
有赞技术团队
The GitHub Blog
The GitHub Blog
C
Cyber Attacks, Cyber Crime and Cyber Security
I
InfoQ
奇客Solidot–传递最新科技情报
奇客Solidot–传递最新科技情报
D
DataBreaches.Net
G
GRAHAM CLULEY
P
Proofpoint News Feed
Threat Intelligence Blog | Flashpoint
Threat Intelligence Blog | Flashpoint
Microsoft Security Blog
Microsoft Security Blog
cs.CL updates on arXiv.org
cs.CL updates on arXiv.org
Y
Y Combinator Blog
小众软件
小众软件
NISL@THU
NISL@THU
L
Lohrmann on Cybersecurity
aimingoo的专栏
aimingoo的专栏
让小产品的独立变现更简单 - ezindie.com
让小产品的独立变现更简单 - ezindie.com
I
Intezer
Last Week in AI
Last Week in AI
T
Threatpost
人人都是产品经理
人人都是产品经理
U
Unit 42
Security Latest
Security Latest
AWS News Blog
AWS News Blog
T
The Blog of Author Tim Ferriss
MongoDB | Blog
MongoDB | Blog
罗磊的独立博客
GbyAI
GbyAI
P
Palo Alto Networks Blog
G
Google Developers Blog
MyScale Blog
MyScale Blog
L
LangChain Blog

Java技术经验分享

生产故障处理SOP分享 | Java技术经验分享 系统稳定性建设实践总结【转载】 | Java技术经验分享 valine访问leancloud国际版异常,评论失效修复 | Java技术经验分享 匆匆忙忙的2021 | Java技术经验分享 聊一下换工作 | Java技术经验分享 IoT系列(2):WIFI设备常见配网方案介绍 | Java技术经验分享 IoT系列(1):什么是物联网 | Java技术经验分享 Java8特性2 - StreamApi | Java技术经验分享 Java8特性1 - lambda表达式&函数式接口 | Java技术经验分享 设计模式(5)-适配器模式 | Java技术经验分享 设计模式(4)-建造者模式 | Java技术经验分享 设计模式(3)-原型模式与浅拷贝和深拷贝 | Java技术经验分享 设计模式(2)-工厂模式图文介绍 | Java技术经验分享 设计模式(1)-带你了解3类8种单例模式 | Java技术经验分享 Java时间处理5---Java8中时区相关类库介绍 | Java技术经验分享 Java时间处理4---Java8中LocalDate、LocalTime、LocalDateTime介绍 | Java技术经验分享 Java时间处理3---Java8中Instant、Duration、Period、Clock介绍 | Java技术经验分享 一些有意思的问答 | Java技术经验分享 Nacos系列博客说明 | Java技术经验分享 菜鸡程序员的2019年度总结 | Java技术经验分享 Java时间处理2----时区TimeZone类方法探究(Java8以前) | Java技术经验分享 Java时间处理1----Date和Calendar方法探究(Java8以前) | Java技术经验分享 FastJson中JSONString、JavaBean、JSONObject、JSONArray的转换关系及API示例 | Java技术经验分享 2019.11软考软件设计师归来心得体会及复习备考指南 | Java技术经验分享 你还没用过“约定式提交”吗?那你赶紧来补补知识吧 | Java技术经验分享 教你如何看懂UML中的类图及类图中的关系 | Java技术经验分享 设计模式总览 | Java技术经验分享 萌新入门Github请看这里,学不会远程教 | Java技术经验分享 Hexo的工作原理探究 | Java技术经验分享 Hexo-theme-butterfly修改调整记录教程 | Java技术经验分享 排序8:基数排序 | Java技术经验分享 排序7:归并排序 | Java技术经验分享 排序6:快速排序 | Java技术经验分享 排序5:冒泡排序 | Java技术经验分享 排序4:堆排序 | Java技术经验分享 排序3:选择排序 | Java技术经验分享 排序2:希尔排序 | Java技术经验分享 排序1:直接插入排序 | Java技术经验分享 推荐一款博客一文多发的良心工具OpenWrite | Java技术经验分享 近期学习计划 | Java技术经验分享 Nacos(九):Nacos集群部署和遇到的问题 | Java技术经验分享 Nacos(八):Nacos持久化 | Java技术经验分享 Nacos(七):Nacos共享配置 | Java技术经验分享 Nacos(六):多环境下如何“管理”及“隔离”配置和服务 | Java技术经验分享 Nacos(五):多环境下如何“读取”Nacos中相应的配置 | Java技术经验分享 Nacos(四):SpringCloud项目中接入Nacos作为配置中心 | Java技术经验分享 Nacos(三):Nacos与OpenFeign的对接使用 | Java技术经验分享 Nacos(二):SpringCloud项目中接入Nacos作为注册中心 | Java技术经验分享 Nacos(一):Nacos介绍 | Java技术经验分享 20190719小组分享 | Java技术经验分享 Java中equals和HashCode方法的分析 | Java技术经验分享 Java中==和equals方法的分析 | Java技术经验分享 Java中的自动拆装箱、装箱缓存 | Java技术经验分享 About-blog | Java技术经验分享 Java中的编译、反编译和反编译工具全家桶分享 | Java技术经验分享 finalize()的生命周期(执行过程) | Java技术经验分享 Java关键字之final、finally与finalize方法 | Java技术经验分享 Java中重写、重载 | Java技术经验分享 Java中面向对象的三大特征:继承、封装、多态 | Java技术经验分享 DockerFile介绍 | Java技术经验分享 Docker环境下安装Gitlab | Java技术经验分享 Docker中私有仓库的搭建流程 | Java技术经验分享 Centos7下两种方式安装Docker-CE | Java技术经验分享 Vert.x创建一个Http服务 | Java技术经验分享 Vert.x创建TCP服务端及客户端 | Java技术经验分享 Vert.x Core(二)- Event Bus(事件总线) | Java技术经验分享 Vert.x-Core(一)- 基础篇 | Java技术经验分享 SpringBoot项目中实现国际化 | Java技术经验分享 Vert.x介绍 | Java技术经验分享 毕设选题项目本地运行环境搭建教程 | Java技术经验分享 Jupyter Notebooks的安装和使用介绍 | Java技术经验分享 算法笔试题:1元,5元,10元,20元,50元、100元面值人民币组合给定x元的问题 | Java技术经验分享 Quartz学习总结 | Java技术经验分享 SpringBoot2.x集成Redis | Java技术经验分享 SpringBoot2.x集成MongoDB | Java技术经验分享 [SpringCloud学习] - 浅谈微服务架构 | Java技术经验分享 基于hexo和coding免费搭建个人博客网站 | Java技术经验分享 Hello World | Java技术经验分享
Java中“附近的人”实现方案讨论及代码实现 | Java技术经验分享
文章作者: LarsCheng · 2019-12-18 · via Java技术经验分享

前言

在我们平时使用的许多app中有附近的人这一功能,像微信、qq附近的人,哈罗、街兔附近的车辆。这些功能就在我们日常生活中出现。

像类似于附近的人这一类业务,在Java中是如何实现的呢?

本文就简单介绍下目前的几种解决方案,并提供简单的示例代码

注: 本文仅涉及附近的人这一业务场景的解决方案讨论,并未涉及到相关的技术细节和方案优化,各位看官可以放心阅读。

基本套路和方案

目前业内的解决方案大都依据geoHash展开,考虑到不同的数据量以及不同的业务场景,本文主要讨论以下3种方案

  • Mysql+外接正方形
  • Mysql+geohash
  • Redis+geohash

Mysql+外接正方形

外接矩形的实现方式是相对较为简单的一种方式。

假设给定某用户的位置坐标, 求在该用户指定范围内的其他用户信息

此时可以将位置信息和距离范围简化成平面几何题来求解

实现思路

以当前用户为圆心,以给定距离为半径画圆,那么在这个圆内的所有用户信息就是符合结果的信息,直接检索圆内的用户坐标难以实现,我们可以通过获取这个圆的外接正方形

通过外接正方形,获取经度和纬度的最大最小值,根据最大最小值可以将坐标在正方形内的用户信息搜索出来。

此时在外接正方形中不属于圆形区域的部分就属于多余的部分,这部分用户信息距离当前用户(圆心)的距离必定是大于给定半径的,故可以将其剔除,最终获得指定范围内的附近的人

代码实现

这里只贴出部分核心代码,详细的代码可见源码:NearBySearch

在实现附近的人搜索中,需要根据位置经纬度点,进行一些距离和范围的计算,比如求球面外接正方形的坐标点,球面两坐标点的距离等,可以引入Spatial4j库。

1
2
3
4
5
<dependency>
<groupId>com.spatial4j</groupId>
<artifactId>spatial4j</artifactId>
<version>0.5</version>
</dependency>
  1. 首先创建一张数据表user
1
2
3
4
5
6
7
8
CREATE TABLE `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;
  1. 假设已插入足够的测试数据,只要我们获取到外接正方形的四个关键点,就可以直接直接查询
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
   private SpatialContext spatialContext = SpatialContext.GEO;    









@GetMapping("/nearby")
public String nearBySearch(@RequestParam("distance") double distance,
@RequestParam("userLng") double userLng,
@RequestParam("userLat") double userLat) {

Rectangle rectangle = getRectangle(distance, userLng, userLat);

List<User> users = userMapper.selectUser(rectangle.getMinX(), rectangle.getMaxX(), rectangle.getMinY(), rectangle.getMaxY());

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);
}
  1. 这里给出查询的sql
1
2
3
4
5
6
<select id="selectUser" resultMap="BaseResultMap">
SELECT * FROM user
WHERE 1=1
and (longitude BETWEEN ${minlng} AND ${maxlng})
and (latitude BETWEEN ${minlat} AND ${maxlat})
</select>

Mysql+geohash

前面介绍了通过Mysql存储用户的信息和gps坐标,通过计算外接正方形的坐标点来粗略筛选结果集,最终剔除超过范围的用户。

而现在要提到的Mysql+geohash方案,同样是以Mysql为基础,只不过引入了geohash算法,同时在查询上借助索引。

geohash被广泛应用于位置搜索类的业务中,本文不对它进行展开说明,有兴趣的同学可以看一下这篇博客:[GeoHash核心原理解析],这里简单对它做一个描述:

GeoHash算法将经纬度坐标点编码成一个字符串,距离越近的坐标,转换后的geohash字符串越相似,例如下表数据:

用户 经纬度 Geohash字符串
小明 116.402843,39.999375 wx4g8c9v
小华 116.3967,39.99932 wx4g89tk
小张 116.40382,39.918118 wx4g0ffe

其中根据经纬度计算得到的geohash字符串,不同精度(字符串长度)代表了不同的距离误差。具体的不同精度的距离误差可参考下表:

geohash码长度 宽度 高度
1 5,009.4km 4,992.6km
2 1,252.3km 624.1km
3 156.5km 156km
4 39.1km 19.5km
5 4.9km 4.9km
6 1.2km 609.4m
7 152.9m 152.4m
8 38.2m 19m
9 4.8m 4.8m
10 1.2m 59.5cm
11 14.9cm 14.9cm
12 3.7cm 1.9cm

实现思路

使用Mysql存储用户信息,其中包括用户的经纬度信息和geohash字符串。

  1. 添加新用户时计算该用户的geohash字符串,并存储到用户表中
  2. 当要查询某一gps附近指定距离的用户信息时,通过比对geohash误差表确定需要的geohash字符串精度
  3. 计算获得某一精度的当前坐标的geohash字符串,通过WHERE geohash Like 'geohashcode%'来查询数据集
  4. 如果geohash字符串的精度远大于给定的距离范围时,查询出的结果集中必然存在在范围之外的数据
  5. 计算两点之间距离,对于超出距离的数据进行剔除。

代码实现

这里只贴出部分核心代码,详细的代码可见源码:NearBySearch

同样的要涉及到坐标点的计算和geohash的计算,开始之前先导入spatial4j

  1. 创建数据表user_geohash,给geohash码添加索引
1
2
3
4
5
6
7
8
9
10
CREATE TABLE `user_geohash` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`name` varchar(255) DEFAULT NULL COMMENT '名称',
`longitude` double DEFAULT NULL COMMENT '经度',
`latitude` double DEFAULT NULL COMMENT '纬度',
`geo_code` varchar(64) DEFAULT NULL COMMENT '经纬度所计算的geohash码',
`create_time` datetime DEFAULT NULL ON UPDATE CURRENT_TIMESTAMP COMMENT '创建时间',
PRIMARY KEY (`id`),
KEY `index_geo_hash` (`geo_code`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;
  1. 添加用户信息和范围搜索逻辑
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
private SpatialContext spatialContext = SpatialContext.GEO;





@PostMapping("/addUser")
public boolean add(@RequestBody UserGeohash user) {

String geoHashCode = GeohashUtils.encodeLatLon(user.getLatitude(),user.getLongitude());
return userGeohashService.save(user.setGeoCode(geoHashCode).setCreateTime(LocalDateTime.now()));
}











@GetMapping("/nearby")
public String nearBySearch(@RequestParam("distance") double distance,
@RequestParam("len") int len,
@RequestParam("userLng") double userLng,
@RequestParam("userLat") double userLat) {

String geoHashCode = GeohashUtils.encodeLatLon(userLat, userLng, len);
QueryWrapper<UserGeohash> queryWrapper = new QueryWrapper<UserGeohash>()
.likeRight("geo_code",geoHashCode);

List<UserGeohash> users = userGeohashService.list(queryWrapper);

users = users.stream()
.filter(a ->getDistance(a.getLongitude(),a.getLatitude(),userLng,userLat)<= distance)
.collect(Collectors.toList());
return JSON.toJSONString(users);
}









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;
}

通过上面几步,就可以实现这一业务场景,不仅提高了查询效率,并且保护了用户的隐私,不对外暴露坐标位置。并且对于同一位置的频繁请求,如果是同一个geohash字符串,可以加上缓存,减缓数据库的压力。

边界问题优化

geohash算法将地图分为一个个矩形,对每个矩形进行编码,得到geohash码,但是当前点与待搜索点距离很近但是恰好在两个区域,用上面的方法则就不适用了。

解决这一问题的办法:获取当前点所在区域附近的8个区域的geohash码,一并进行筛选。

如何求解附近的8个区域的geohash码可参考Geohash求当前区域周围8个区域编码的一种思路

了解了思路,这里我们可以使用第三方开源库ch.hsr.geohash来计算,通过maven引入

1
2
3
4
5
<dependency>
<groupId>ch.hsr</groupId>
<artifactId>geohash</artifactId>
<version>1.0.10</version>
</dependency>

对上一章节的nearBySearch方法进行修改如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34










@GetMapping("/nearby")
public String nearBySearch(@RequestParam("distance") double distance,
@RequestParam("len") int len,
@RequestParam("userLng") double userLng,
@RequestParam("userLat") double userLat) {



GeoHash geoHash = GeoHash.withCharacterPrecision(userLat, userLng, len);

GeoHash[] adjacent = geoHash.getAdjacent();

QueryWrapper<UserGeohash> queryWrapper = new QueryWrapper<UserGeohash>()
.likeRight("geo_code",geoHash.toBase32());
Stream.of(adjacent).forEach(a -> queryWrapper.or().likeRight("geo_code",a.toBase32()));


List<UserGeohash> users = userGeohashService.list(queryWrapper);

users = users.stream()
.filter(a ->getDistance(a.getLongitude(),a.getLatitude(),userLng,userLat)<= distance)
.collect(Collectors.toList());
return JSON.toJSONString(users);
}

Redis+GeoHash

基于前两种方案,我们可以发现gps这类数据属于读多写少的情况,如果使用redis来实现附近的人,想必效率会大大提高。

自Redis 3.2开始,Redis基于geohash有序集合Zset提供了地理位置相关功能

Redis提供6条命令,来帮助我们我完成大部分业务的需求,关于Redis提供的geohash操作命令介绍可阅读博客:Redis 到底是怎么实现“附近的人”这个功能的呢?

本文主要介绍下,我们示例代码中用到的两个命令:

  • GEOADD key longitude latitude member:将给定的空间元素(纬度、经度、名字)添加到指定的键里面
    • 例如添加小明的经纬度信息:GEOADD location 119.98866180732716 30.27465803229662 小明
  • GEORADIUS key longitude latitude radius m|km|ft|mi [WITHCOORD] [WITHDIST] [WITHHASH] [ASC|DESC] [COUNT count]: 根据给定地理位置坐标获取指定范围内的地理位置集合(附近的人)
    • 例如查询某gps附近500m的用户坐标:GEORADIUS location 119.98866180732716 30.27465803229662 500 m WITHCOORD

实现思路

  • 添加用户坐标信息到redis(GEOADD),redis会将经纬度参数值转换为52位的geohash码,
  • Redis以geohash码为score,将其他信息以Zset有序集合存入key中
  • 通过调用GEORADIUS命令,获取指定坐标点某一范围内的数据
  • 因geohash存在精度误差,剔除超过指定距离的数据

实现代码

这里只贴出部分核心代码,详细的代码可见源码:NearBySearch

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

@Autowired
private RedisTemplate<String, Object> redisTemplate;


private final static String KEY = "user_info";

public boolean save(User user) {
Long flag = redisTemplate.opsForGeo().add(KEY, new RedisGeoCommands.GeoLocation<>(
user.getName(),
new Point(user.getLongitude(), user.getLatitude()))
);
return flag != null && flag > 0;
}








public String nearBySearch(double distance, double userLng, double userLat) {
List<User> users = new ArrayList<>();

GeoResults<RedisGeoCommands.GeoLocation<Object>> reslut =
redisTemplate.opsForGeo().radius(KEY,
new Circle(new Point(userLng, userLat), new Distance(distance, Metrics.KILOMETERS)),
RedisGeoCommands.GeoRadiusCommandArgs.newGeoRadiusArgs()
.includeDistance()
.includeCoordinates().sortAscending());

List<GeoResult<RedisGeoCommands.GeoLocation<Object>>> content = reslut.getContent();

content.forEach(a-> users.add(
new User().setDistance(a.getDistance().getValue())
.setLatitude(a.getContent().getPoint().getX())
.setLongitude(a.getContent().getPoint().getY())));
return JSON.toJSONString(users);
}

方案总结

方案 优势 缺点
Mysql外接正方形 逻辑清晰,实现简单,支持多条件筛选 效率较低,不适合大数据量,不支持按距离排序
Mysql+Geohash 借助索引有效提高效率,支持多条件筛选 不支持按距离排序,存在数据库瓶颈
Redis+Geohash 效率高,集成便捷,支持距离排序 不适合复杂对象存储,不支持多条件查询

总结以上三种方案,各有优劣,在不同的业务场景下,可选择不同的方案来实现。

当然目前附近的人的解决方案并不仅仅这三种,以上权当是这一功能的入门引子,希望对大家有所帮助。

本文的三种方案均有源码提供,源码地址

参考文章

Redis 到底是怎么实现“附近的人”这个功能的呢?

Geohash求当前区域周围8个区域编码的一种思路

GeoHash核心原理解析