【系统设计】本地生活之附近商家 LBS 服务实现

LBS

在本章中我们会设计一个基于位置的附近商家服务系统，用于发现用户附近的一些地方，比如餐厅、酒店、话剧院、博物馆等。

明确需求

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

面试官：这是一个非常好的问题，让我们假设仅需要考虑一个确定范围内的商家，如果之后的时间允许我们再考虑如果没有足够商家时扩大搜索范围的问题。

张三：系统能支持的最大半径是多少？我们可以设定为 20 km？

面试官：这是一个合理的假设。

张三：用户可以通过 UI 自行更改搜索半径吗？

面试官：当然，我们有大概有如下一些选择，如 0.5km、1km、2km、5km、10km、20km。

张三：商家信息的 CRUD 是如何操作的？且是否需要实时展示？

面试官：商家信息是店主添加、删除和修改的，这些信息会在第二天生效？

张三：用户可能在使用期间移动位置，我们是否需要更新搜索结果？

面试官：让我们假设用户的移动速度非常慢，以至于无需持续更新结果。

功能要求

基于上诉的交流，我们注意到三个关键功能：

• 需要基于用户位置（经纬度）和搜索半径返回商家信息。
• 店主可以 CRUD，但信息无需实时更新到前台。
• 用户可以查看商家的详细信息。

非功能要求

从商业角度，我们可以推理出一系列非功能性要求，可以和面试官讨论：

• 低延迟：用户需要快速的获得搜索结果。
• 数据隐私：地理位置信息是一个敏感数据，当我们设计一个基于地理位置服务的系统时，应该将用户的隐私保护考虑进去。
• 高可用和可拓展性：我们需要确保我们的系统可以支持人口密集地区高峰时间段的流量。

粗略评估

让我们做一些简单的评估，以便明确我们的设计方案面临的签字风险和挑战。此处假设我们拥有 100 万的日活用户和 200 万的商家。

方案设计

本小节中我们需要提出以下部分的设计并获得面试官认可：

• API 接口设计
• 高层次设计
• 算法（查询商家）设计
• 数据模型

API 设计

这里作者通过 RESTful 协议设计出几个简单的 API 接口。

GET /v1/search/nearby

以及商家管理 API：

数据模型

这里我们需要再次明确一下读写比例和 schema 设计。同时数据库的可伸缩性也在深层次的讨论中。

• 商家表

• GEO 索引表

一张 GEO 索引表可以支持高效的空间计算操作，但需要对 geohash 有一定了解。

高层次设计

如下面的设计图所示，系统由两部分组成：基于位置服务（location-based service LBS）和业务相关服务（business-related service）。

负载均衡器

负载均衡器可以自动的根据路由将流量分配给不同的后端。

基于位置服务（LBS）

LBS 是系统的核心部分，基于地理位置和半径搜索附近的商家，具备以下特点：

• 只有大量的查询请求，没有写操作。
• QPS 很高，尤其在密集地区的高峰时间。
• 服务是无状态的，方便横向拓展。

业务服务

业务服务主要提供商家的创建、编辑和删除服务，几乎全是写操作，且 QPS 不会很高。

数据库集群

数据库采用主从架构，并且读写分离，提高性能的同时增强可拓展性。

算法实现

在实际情况中，公司也许会采用现有的地理空间数据库，如 Redis 的 Geohash 或者 Postgres 的 PostGIS 插件。虽然面试的时候并不考察这些数据库的内部实现，但是通过这些模块的工作原理你可以更好证明你的解决问题能力和技术储备。

接下来我们就具体讨论几种 LBS 的实现方案。

二维搜索

这种方案最简单有效，以用户位置为中心画一个制定半径的圆圈，然后找出圈内所有的商家信息，如下图所示：

这个过程可以翻译一下 SQL：

select business_id, latitude, longitude
from business
where (latitude between {:my_lat} - radius and {:my_lat} + radius)
and (latitude between {:my_long} - radius and {:my_long} + radius)
1
2
3
4

这种方案虽然满足我们的需求，但是执行效率并不高，因为需要遍历整张表。尽管我们可以在经纬度字段上建立索引以提升查询效率，但还是够，因为我们有两个维度的数据，需要对其取交集，我们拿索引过滤其中一个字段后数据集可能依旧可能很大。

上述问题根因是数据库索引仅支持一个维度的快速检索，而我们有两个维度。难道就没有解决方案吗？当然有，我们可以将地理位置的两个维度转换成一个维度进行计算。

当然这个转换也有很多种方案，接下来我们一一讨论。

均匀分割网格

这是一个简单的方案，就是将这个世界均为分割成一个个小网格，每个小的网格都会有多种多样的商家，每个商家都会映射到其中一个网格中。

这个方案在一定程度上满足需求，但有一个主要的问题：商家的分布不是均匀的，有些网格比如在纽约就会拥有大量的商家，而一些在荒漠或者海洋的网格一个商家也没有，这样会导致数据分布严重不均匀。同时还面临一个潜在的挑战是如何通过一个固定的网格找到相邻的网格。

GeoHash

Geohash 算法更加优于均分网格，它是将二维的经纬度转换成一维的字符串。Geohash 每增加一位就会把世界递归的划分成更小的网格，让我们看看它是如何实现的吧。

1. 首先将地球通过本初子午线和赤道划分为四个部分：

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

1. 然后重复这个过程，再把每个网格划分成四个小网格：

重复上述过程，直到网格大小满足我们的要求，GeoHash 通常使用 base32 表示，举个例子：

Google 总部的 GeoHash 值（长度为 6）

1001 10110 01001 10000 11011 11010 (base32 in binary) -> 9q9hvu (base32)
1

GeoHash 有 12 个精度（也称作级别）用来控制网格的大小，字符串越长，网格越小：

如何确认精度？前面需求中提到用户最小的搜索半径为 0.5km，对应到长度为 6 即可。

边界问题

通过 GeoHash 的方案将地理位置信息查询转换为一维的字符串，很大的提高了查询效率，但就真的没其它问题了吗？

• 边界问题1

答案是否定的，如下图所示，聪明的你可能会发现邻居的网格中都有相同的前缀 9q8zn。

没错，这就是 GeoHash 的特性，两个网格相同前缀越长，则表示他们的位置相邻越近。那么反过来说，两个相邻的网格，它们的 GeoHash 值是否有相同的前缀？

显然这是不成立的，处在边界的两个网格虽然距离很近，但他们的 hash 值从第一位开始就不一样了，当我们使用如下 SQL 查询商家时结果就准确了：

select * from geohash_index where geohash like '9q8zn%';
1

• 边界问题2

还有一个边界问题就是对于红色位置的用户来说，相邻网格绿色位置的商家距离可能比自己所在网格范围内的一些商家的距离还近。

因此，我们在使用 GeoHash 搜索附近的商家时不能仅仅绝限于用户所在的网格，需要扩大到相邻的 4 个或 9 个网格，然后在进行距离计算，找出合适的商家。

没有足够商家问题

当前网格没有足够数量的商家返回时，我们可以移除用户位置 GeoHash 值的后一位进行扩大搜索半径，如果还不够，则再移除一位。

四叉树

四叉树（QuadTree）是另一种比较流行的方案，它是递归的将二维地理空间划分成四个网格，直到每个网格数量都满足要求。

（需要注意的是四叉树是基于内存的数据结构而非数据库解决方案，适用于所有的 LBS。）

上图是四叉图的构建过程，它会从世界的根节点开始，递归的将商家拆分到四个子节点中，直到每个叶子节点中的商家数量不超过指定数量（100）。

需要多少内存？

每个网格最大存储 100 个商家：

• 叶子节点数量为 200 million / 100 ~= 2 million，其中每个节点包含一个父节点和三个兄弟节点的指针（8 bytes * 4 = 32 bytes）以及最大 100 个商家 ID（8 bytes * 100 = 800 bytes）
• 内部节点数量为 2 million * 1/3 ~= 0.67 million，其中每个节点包含一个父节点和三个兄弟节点的指针（8 bytes * 4 = 32 bytes）以及 4 个子节点指针（8 bytes * 4 = 32 bytes）

因此总的内存要求是 2million * 823 bytes + 0.67 million * 64 bytes ~= 1.71 GB。

需要多长时间？

每个叶子节点需要存储接近 100 个商家 ID，因此四叉树的构建时间复杂度为 (N/100)*lg(N/100) 。N 为商家数量，所以初始化 200 million 的数据大概需要持续几分钟。因此我们需要考虑部署时如何启动服务，避免大量机器同时拉去商家信息给数据库带来的压力和用户的访问速度降低问题。

还有个问题值得我们讨论，就是商家信息增加修改带来的脏数据问题，这是使用缓存不可避免的，同时也被需求接受。

Google S2

Google S2 是这个领域的另一个重要参与者，类似 QuadTree，也是一种内存解决方案。其原理是利用希尔伯特曲线将球体映射到一维索引上，而希尔伯特曲线曲线有一个重要的性质就是在球面相近的两个位置映射到一维空间后也会非常接近。

这部分过于复杂，就不过多描述，仅需要了解它的两个优点即可：

• S2 非常适合地理格栅，因为它可以根据不同等级划分任意区域。

• S2 的空间覆盖算法支持更多规格，如最小等级、最大等级或者最多网格等，相比 GeoHash 返回结果更加丰富。

深入设计

经过上述讨论，我们对系统有了一个整体设计，但我们还可以在一些地方做更深层次的设计：

• 数据库设计
• 缓存设计
• 异地多活

数据库设计

对于商家（business）表，我们可以按照 business_id 进行分库分表，这样可以将请求均匀的分配到每台数据库实例上，同时也方便维护。

对于位置索引表，GeoHash 和 QuadTree 都被广泛使用，鉴于 GeoHash 更加简单，这里就以此举例。在我们的例子中，QuadTree 索引大约会占用不到 2G 的存储空间，而 GeoHash 则会更小，因此不能盲目进行分库分表，这样会是得系统逻辑更加复杂。

当然我们可以增加数据库副本以分担读请求的压力。

缓存设计

在使用缓存之前，我们先问一下自己是否真的需要一个缓存层：读数据工作量大，且数据集相对较小。和面试官讨论缓存时千万要小心，因为一般他会要求有详细基准测试和代价分析。

缓存Key

使用 GeoHash 可以很好解决经纬度变化的问题，可以满足用户在一定小范围内移动而搜索结果不会产生差异的问题。

缓存数据

在上面的需求中，我们知道客户端有 4 个搜索半径，分别对应 GeoHash 精度的 4，5，5，6。因为我们可以在 Redis 中缓存这 3 个精度的商家信息（geohash_4，geohash_5，geohash_6）。计算一下大致开销：

• 缓存数据：8 bytes * 200 million * 3 percisions ~= 5 GB
• 缓存值：可忽略不计

多数据中心

我们可以把 LBS 服务部署到世界上的多个地区，这样不同区域的用户就可以访问到最近的服务，以提升访问速度和系统高可用。同时还可以满足不同地区的法律法规，如 GDPR 要求的用户数据本地存储问题。

最终设计图