基于Geohash实现根据经纬度的快速定位

59 阅读 0 评论 39 点赞

我是靠谱客的博主直率电话，最近开发中收集的这篇文章主要介绍基于Geohash实现根据经纬度的快速定位，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

背景介绍

在项目中，SDK会上报包含用户经纬度信息的一系列数据，我们需要根据经纬度信息定位出此条数据上报时用户所在的位置（包括国家、省、市、区），并和其他信息写入宽表中。

旧方案

旧方案中，主要使用GeoSpark对数据进行定位，考虑到同一个经纬度下会有多条数据，所以我们先对数据做分组，同一个用户同一个会话下相同经纬度的数据分为一组，从每组数据中抽取第一条生成一张临时表，再在临时表上调用GeoSpark算出district_id，city_id，province_id，country_id，之后将临时表与原表关联，用临时表的四个ID填充相同经纬度的其他数据的ID。
在测试过程中，我们发现有很小一部分数据只有district_id或city_id等细粒度数据，却没有与之相对的province_id、country_id等数据，这是老大所不能接受的（在哪个城市都知道了，国家你给我个null？？？ =。=），所以在计算四个ID之后，会有一个反推的步骤，即：判断是否有下层ID不为空上层ID却为空的情况，如果有，通过下层ID进行反推，得到上层ID，并填充。

中间还有一些其他的过滤排序逻辑不做具体介绍，最后当整个定位逻辑完成后，需要做6~7次的shuffle，我们发现其性能远低于预期，在我们每天将近40亿的数据量下，较大的拖慢了整个流程的运行速度，影响了数据产出，因此需要对这一部分进行优化。经过调研后，本菜鸡决定采用GeoHash的方式进行优化。

什么是Geohash

简单介绍下GeoHash，我们可以用一个经纬度的点（例如点A： 37.788422,-122.391907 ）计算出一个GeoHash字符串（9q8yyzh），这个字符串代表一个矩形面，点A以及点A附近的点B（37.787933,-122.392887）虽然经纬度不同，但通过经纬度计算出的GeoHash字符串相同，也就是说AB两个点都在（9q8yyzh）这个面内。这样就将二维的经纬度坐标转换成了一维的字符串表示。

但A附近的多少点会跟A共享相同的字符串呢？也就是这个面的大小是怎么确定的呢？这就取决于GeoHash字符串的长度了，GeoHash的字符串长度越长，意味着这个面也就越小，会有更少的点跟A共享同样的GeoHash值。

具体GeoHash的计算方式，以及字符串长度对应的面大小。请参考如下这篇文章：
GeoHash算法学习讲解、解析及原理分析

以上就是我们实现基于GeoHash进行定位的基础。

如何用Geohash实现快速定位

既然可以用经纬度代表的一个点得到一个面，那如果我们的历史数据足够多，映射出足够多的的面，这些面就会像拼图一样，慢慢把我们的世界拼出来。

例如我们可以用21个GeoHash字符串将整个北京欢乐谷拼出来：
wx4ffc
有了这个完整的拼图之后，当欢乐谷范围内有一条新数据上报时，我们只需要根据经纬度算出对应的GeoHash值，再用这个值去和这21个字符串匹配，如果和其中任意一个相同，就说明此条数据的位置信息为中国北京的朝阳区（不具体定位到欢乐谷是因为我们最细粒度只划分到行政区）。

采用这个思路，最后我们将世界地图构建好之后，当有新数据需要定位时，我们只需要做一次GeoHash字符串计算，再到数据库中进行匹配即可。速度大大提高。

示例代码

Geohash字符串的计算：

此处采用的方法是写一个UDF，UDF的功能是输入经纬度及想要的GeoHash字符串长度，输出对应的GeoHash字符串。再将其打成jar包，上传之后在hive中创建临时函数，再进行调用。

首先导入依赖

<dependency>
            <groupId>ch.hsr</groupId>
            <artifactId>geohash</artifactId>
            <version>1.3.0</version>
</dependency>

继承UDF并重写evaluate方法

public class getGeoHashString extends UDF {

    private static int precision = 7;

    public String evaluate(double latitude, double longtitude, int precisionParam) {

        GeoHash geoHash = GeoHash.withCharacterPrecision(latitude, longtitude, precisionParam);
        return geoHash.toBase32();
    }

    public String evaluate(double latitude, double longtitude) {

        GeoHash geoHash = GeoHash.withCharacterPrecision(latitude, longtitude, precision);
        return geoHash.toBase32();
    }
}

默认采用7位长度，当然也支持传入参数自定义

Maven打包并上传

略。。

使用UDF

目前是在hive命令行中运行的，具体方法如下：

add jar /data/home/geoHashUDF-1.0-SNAPSHOT-jar-with-dependencies.jar;

先把jar包添加进来，在创建临时函数：

CREATE TEMPORARY FUNCTION get_geohash_string as 'getGeoHashString';

其中get_geohash_string为函数名，getGeoHashString为你的主类。

接下来写SQL就可以了

将每一天的新数据计算后写入分区

INSERT OVERWRITE TABLE geohash_a_d
PARTITION(dt)
SELECT
get_geohash_string(latitude,longitude),

geo_district_id,
geo_district_name_en,
geo_district_name_zh,

geo_city_id,
geo_city_name_en,
geo_city_name_zh,

geo_province_id,
geo_province_name_en,
geo_province_name_zh,

geo_country_id,
geo_country_name_en,
geo_country_name_zh,
dt
from 
report_i_h
WHERE 
dt BETWEEN '2019-11-01' AND '2019-11-30'

对每一天的数据进行去重合并

INSERT OVERWRITE TABLE geohash_summary
SELECT 
geohash,
geo_district_id,
geo_district_name_en,
geo_district_name_zh,
geo_city_id,
geo_city_name_en,
geo_city_name_zh,
geo_province_id,
geo_province_name_en,
geo_province_name_zh,
geo_country_id,
geo_country_name_en,
geo_country_name_zh
from geohash_a_d
WHERE dt='2019-11-01'
UNION DISTINCT
SELECT 
geohash,
geo_district_id,
geo_district_name_en,
geo_district_name_zh,
geo_city_id,
geo_city_name_en,
geo_city_name_zh,
geo_province_id,
geo_province_name_en,
geo_province_name_zh,
geo_country_id,
geo_country_name_en,
geo_country_name_zh
from geohash_a_d
WHERE dt BETWEEN '2019-11-02' AND '2019-11-30'

对hash值进行去重，确保一个hash值只对应一条记录（此处有大坑，之后讲）

with tmp as (
SELECT 
geohash,
geo_district_id,
geo_district_name_en,
geo_district_name_zh,
geo_city_id,
geo_city_name_en,
geo_city_name_zh,
geo_province_id,
geo_province_name_en,
geo_province_name_zh,
geo_country_id,
geo_country_name_en,
geo_country_name_zh,
row_number() OVER(PARTITION BY geohash ORDER BY 
geo_country_id,geo_province_id,geo_city_id,geo_district_id
desc) as rank
from geohash_summary
where geo_country_id is not null
)
insert overwrite table geohash_distinct
select
geohash,
geo_district_id,
geo_district_name_en,
geo_district_name_zh,
geo_city_id,
geo_city_name_en,
geo_city_name_zh,
geo_province_id,
geo_province_name_en,
geo_province_name_zh,
geo_country_id,
geo_country_name_en,
geo_country_name_zh
from tmp
where rank=1

这几个SQL跑完后，我们的GeoHash维度表就初步构建完成了。

效果测试

构建完成后，便可以进行定位的效果测试了，我们采用的测试方案是：
取不在回溯日期内的几天的数据，通过GeoHash的方式获取其位置信息，在和用geoSpark获取的位置信息作对比，校验其准确性。

结果：99.5%的数据可以成功获取定位信息，但是其中千分之七的数据存在distinct级的误差，千分之一的数据存在city级的误差。此外，还意外的实现了千分之一的数据优化。

数据优化：有一些数据可能geoSpark定位不到，或定位的信息不全，通过geoHash可以获取到定位或将定位信息补全。随便举个例子：
geoSpark:

latitude:45.12345
longtitude:110.12345
dim_geohash_distinct.geo_district_id	null
dim_geohash_distinct.geo_city_id	null
dim_geohash_distinct.geo_province_id	3117
dim_geohash_distinct.geo_country_id	3142

geoHash:

latitude:45.12345
longtitude:110.12345
dim_geohash_distinct.geo_district_id	132
dim_geohash_distinct.geo_city_id	3022
dim_geohash_distinct.geo_province_id	3117
dim_geohash_distinct.geo_country_id	3142

通过GeoHash，可以将缺失的district_id及city_id补全。

补充

采用GeoHash实现定位的前提是有足够的数据量支持，为了达到本文实现的效果，我们回溯了三个月的数据，每天的数据量在35亿左右。最后生成的维度表结构如下所示：
在这里插入图片描述
其中district代表行政区（如东城区、朝阳区），geohash为生成的GeoHash字符串。
随便抽取其中一条记录如下：

（话说以前一直以为西藏的英文是Xizang。。orz）