1. 起因

这一切还得从前段时间接到的一个需求讲起。

业务方需要离线计算一批A附近5公里内的B，并统计聚合B的相关指标，进行展示。

嗯，听起来很合理。🤔

2. 问题

虽然在进行前期评估时，就已经预料到计算量会很大（当时的计算方案十分简陋）。

但在实际运行过程中，还是发现附近5km的逻辑，计算效率过于低下（按照城市编码将数据拆分为3个任务进行并行计算，但平均耗时还是会达到7-10个小时，无法接受）😦

3. 一些尝试

3.1 第一版：

最开始的计算逻辑很粗暴：把每个城市内的A和B进行full join，然后根据经纬度逐个计算距离，排除掉超出距离限制的集合。肉眼可见的低效。。。

3.2 第二版：

由于全量计算十分耗时，并且大部分B的坐标也不会经常变更，因此开始考虑使用增量计算进行优化，减少重复计算。

但在实际任务运行过程中发现，大量耗时用在了历史数据和新增数据的合并写入，并没有有效的效率提升。

3.3 第三版：

这个时候，已经没有什么优化的头绪了。只是一次偶然的搜索，让我发现了一个全新的实现逻辑。（没错，面向google编程）

一个周五的晚上，脑袋里思索着通过经纬度计算距离的逻辑，突然一个想法出现：既然经纬度可以进行距离计算，是否意味着经纬度的数字也是和距离有着一定的转换关系，比如经度小数点后1位，代表距离xx公里？

带着这个疑问，我发现了这两篇文章。

其中 高效的多维空间点索引算法 — Geohash 和 Google S2介绍的案例，与我的需求十分相似。（大神的文章值得好好阅读）

里面提到的geohash算法，则是1966年就有人提出的一种将经纬度坐标点进行一维化编码的解决思路。而后续的google的s2、uber的h3，均是在此设计理念的基础上优化而来的。

这种算法的本质就是对地球的每一块区域都进行编码（精度可调），也就是一个编码代表着一段经纬度范围内的区域。

那么接下来问题就简单了，找到合适的编码方案以及精度参数，测试验证即可。

具体的方案选择就不重复了。可以参考这个帖子：geohash、google s2、uber h3三种格网系统比较

我这边最终选择的是h3(h3-pyspark)。

4. 最终解决

第一步：将A的经纬度按照需要的精度进行编码，再获取该编码附近x公里的区域编码集合。

第二步：将B的经纬度按照同样的精度进行编码。

第三步：将两个数据集inner join，即可获得符合要求的集合。

是的，就是这么简单。（摊手）

5. 总结

通过这次的问题解决，学习到了这类场景的通用解决方案，受益匪浅。

6. 参考文章

高效的多维空间点索引算法 — Geohash 和 Google S2

彩云天气地理查询优化(2): 行政区划查询

geohash算法

geohash、google s2、uber h3三种格网系统比较

h3-pyspark

Uber H3使用