【系统设计】邻近服务

在本文中，我们将设计一个邻近服务，用来发现用户附近的地方，比如餐馆，酒店，商场等。

设计要求

从一个小明去面试的故事开始。

面试官：你好，我想考察一下你的设计能力，如果让你设计一个邻近服务，用来搜索用户附近的商家，你会怎么做？

小明：好的，用户可以指定搜索半径吗？如果搜索范围内没有足够的商家，系统是否支持扩大搜索范围？

面试官：对，用户可以根据需要修改，大概有以下几个选项，0.5km，1km，2km，5km，10km，20km。

小明：嗯，还有其他的系统要求吗？

面试官：另外还需要考虑的是，系统的低延迟，高可用，和可扩展性，以及数据隐私。

小明：好的，了解了。

总结一下，需要做一个邻近服务，可以根据用户的位置（经度和纬度）以及搜索半径返回附近的商家，半径可以修改。因为用户的位置信息是敏感数据，我们可能需要遵守数据隐私保护法。

高层次设计

高层次设计图如下所示，系统包括两部分：基于位置的服务（location-based service）LBS 和业务（bussiness）相关的服务。

让我们来看看系统的每个组件。

负载均衡器

负载均衡器可以根据路由把流量分配给多个后端服务。

基于位置的服务 (LBS)

LBS 服务是系统的核心部分，通过位置和半径寻找附近的商家。LBS 具有以下特点：

• 没有写请求，但是有大量的查询
• QPS 很高，尤其是在密集地区的高峰时段。
• 服务是无状态的，支持水平扩展。

Business 服务

商户创建，更新，删除商家信息，以及用户查看商家信息。

数据库集群

数据库集群可以使用主从配置，提升可用性和性能。数据首先保存到主数据库，然后复制到从库，主数据库处理所有的写入操作，多个从数据库用于读取操作。

接下来，我们具体讨论位置服务 LBS 的实现。

1. 二维搜索

这种方法简单，有效，根据用户的位置和搜索半径画一个圆，然后找到圆圈内的所有商家，如下所示。

商家的纬度用 latitude 表示，经度用 longitude 表示。同样的用户的纬度和经度可以用 user_latitude 和 user_longitude 表示，半径用 radius 表示。

上面的搜索过程可以翻译成下面的伪 SQL 。

代码语言：javascript复制

SELECT business_id, latitude, longitude,
FROM business
WHERE 
latitude >= (@user_latitude - radius) AND latitude < (@user_latitude   radius)
AND
longitude >= (@user_longitude - radius) AND longitude < (@user_longitude   radius)

这种方式可以实现我们的需求，但是实际上效率不高，因为我们需要扫描整个表。虽然我们可以对经纬度创建索引，效率有提升，但是并不够，我们还需要对索引的结果计算取并集。

2. Geohash

我们上面说了，二维的经度和纬度做索引的效果并不明显。而 Geohash 可以把二维的经度和纬度转换为一维的字符串，通过算法，每增加一位就递归地把世界划分为越来越小的网格，让我们来看看它是如何实现的。

首先，把地球通过本初子午线和赤道分成四个象限，如下

• 纬度范围 [-90, 0] 用 0 表示
• 纬度范围 [0, 90] 用 1 表示
• 经度范围 [-180, 0] 用 0 表示
• 经度范围 [0, 180] 用 1 表示

然后，再把每个网格分成四个小网格。

重复这个过程，直到网格的大小符合我们的需求，Geohash 通常使用 base32 表示。让我们看两个例子。

• Google 总部的 Geohash（长度为 6）：
- 1001 10110 01001 10000 11011 11010 (base32 convert) → 9q9hvu (base32)
• Facebook 总部的 Geohash（长度为 6）：1001 10110 01001 10001 10000 10111 (base32 convert) → 9q9jhr (base32)

Geohash 有 12 个精度（也称为级别）, 它可以控制每个网格的大小，字符串越长，拆分的网格就越小，如下