[系统设计总结] - Proximity Service算法介绍

问题描述

Proximity Service广泛应用于各种地图相关的服务中比如外卖，大众点评，Uber打车，Google地图中，其中比较关键的是我们根据用户的位置来快速找到附近的餐厅，司机，外卖员也就是就近查询算法。

主流的就近算法

基本的主流就近算法大致就是下图粉色高光的几种,根据实现方式分为两个部分Hash类以及Tree类，基本思路都是将地图按照分割成足够小范围的小格来进行就近查询。

1. Even Grid等距分割

顾名思义，就是将世界地图按照一个固定的密度分割成固定大小的格子，每一个格子代表一小块经纬度范围[lat, long]，我们给每一个格子定义一个ID, 这样再查找目标附近满足条件的餐厅时(下面算法讲解都以餐厅为例)，我们找到目标所在格子相邻格子内满足条件的餐厅(不断扩大搜索范围直到找到所有满足条件)

优缺点：

索引相对比较简单，等距分割即可；但是缺点就是数据库中范围搜索相对较慢，很不高效。而且等距分割，对于餐厅高度不平衡的位置 (市中心和农村)，进行等距比较浪费资源。

2. Geohash

Geohash算法就可以解决上面even grid的局限性，Geohash是将二维地理坐标压缩成base32一维字符作为ID来保存一个区域信息，这个Geohash是通过01决策树编码生成，根据经纬度范围进行决策编码。geohash长度越长，精度越高，通常来说geohash长度达到6位格子的范围就差不多在1km直径范围内，基本满足精度要求。而且这种geohash编码的优点在于向邻近的区域前缀相同可以通过前缀查找的方式来进行

1001 10110 01001 10000 11011 11010 (base32 in binary) → 9q9hvu (base32)

算法流程

目标位置经纬度 -> 进入决策树进行编码 -> 根据一个搜索半径对满足条件的格子的相邻格子进行搜索 -> 根据前缀搜索相邻的格子 ->如果相邻各自餐厅数量不够则继续扩大范围查找直到数量达标为止

优缺点

优点：可以处理区域数据不平衡，密集的位置就细分更多的层数，查找的速度也更快，因为先定位到目标grid后，根据ID前缀可以快速找到附近的相邻grid. (可以通过ElasticSearch, 也可以直接使用Redis GeoHash API进行查询)

缺点：1. 边界问题，两个相邻较近的节点可能不在一个同一个前缀中，这时如果查询可能就需要对整个数据库进行遍历找到临近的位置。或者把这种corner case缓存起来，在下一次查询时可以直接查询。2. Geohash如果hash做更新成本较高，如果你的geohash grid需要根据区域内密度进行一定动态合并或者拆分，那么geohash存储的话你需要对grid对应的所有数据进行逐一更新。

3. QuadTree 四叉树

四叉树的存储思路类似于二维的线段树，每一个节点保存的就是二维区间范围，并且在每一个节点中保存对应的餐厅信息。如果某个节点范围内密度超过阈值，那么就继续细分，这种数据结构存储大大增加了范围设置的灵活性。而且QuadTree本身对于存储大小需求不大，根据下面估计这个QuadTree存储大小大约在5GB以内，完全可以实现在单机内存中维护这个数据结构而无需使用数据库。并且范围搜索也比较快 O(LogN) 

 

优缺点：

优点：1. 便于动态分割，很好的解决区域密度不平衡问题。2.查询，更新操作速度相对较快，资源存储相对较小 3. 可以快速合并，拆分Quad Tree结构，并且范围查询时区间合并不会有GeoHash边界问题。

缺点：1. 数据结构实现较为复杂。2. 如果建立在单机来实现快速响应，对于分布式系统来说，你需要去实现data backup, sharding/partition以及node crash之后数据恢复的问题。

图文引用

• Bytebytego: https://bytebytego.com/courses/system-design-interview/proximity-service