系统设计：附近人或者地点服务

需求：

让我们设计一个类似Yelp或者大众点评的服务，用户可以搜索附近的地方，比如餐馆、剧院或购物中心等，还可以添加/查看对地方的评论。类似的服务：邻近服务器。

难度等级：难

1.为什么使用Yelp或邻近服务器？

如果你没有使用yelp，邻近服务器可以用来发现附近的景点，如地点、活动等。com之前，请在继续之前尝试一下（你可以搜索附近的餐厅、影院等），并花一些时间了解该网站提供的不同选项。或者使用下大众点评同样类似的功能。

2.系统的要求和目标

我们希望通过类似Yelp的服务实现什么？我们的服务将存储不同地方的信息，以便用户可以对其进行搜索。查询时，我们的服务将返回用户周围的位置列表。服务应满足以下要求：

功能要求：

1.用户应该能够添加/删除/更新位置。

2.考虑到他们的位置（经度/纬度），用户应该能够在一个小时内找到所有附近的地方给定半径。

3.用户应该能够添加关于某个地方的反馈/评论。反馈可以有图片，文本和评级。

非功能性需求：

1.用户应具有最小延迟的实时搜索体验。

2.我们的服务应该支持大量搜索。将有很多搜索请求进行比较添加一个新的位置。

3.规模估算

让我们假设每秒有5亿个位置和10万个查询（QPS），来构建我们的系统。我们还假设每年的学额和QP数量增长20%。

4.数据库模式

每个位置都可以有以下字段：

1.LocationID（8字节）：唯一标识一个位置。2.名称（256字节）

3.纬度（8字节）

4.经度（8字节）

5.说明（512字节）

6.类别（1字节）：例如咖啡馆、餐厅、剧院等。

虽然一个四字节的数字可以唯一标识500万个位置，但考虑到未来的增长，我们将使用8字节作为LocationID。

总大小：8+256+8+8+512+1=>793字节

我们还需要存储一个地方的评论、照片和评级。我们可以有一个单独的表来存储地方评论：

1.LocationID（8字节）

2.ReviewID（4字节）：唯一标识一个审阅，假设任何位置都不会有更多超过2^32条评论。

3.ReviewText（512字节）

4.评分（1字节）：一个地方从十颗星中得到多少颗星。

类似地，我们可以有一个单独的表来存储地点和评论的照片。

5.系统API

我们可以使用SOAP或REST API来公开我们服务的功能。以下可能是用于搜索的API的定义：

search(api_dev_key, search_terms, user_location, radius_filter,
maximum_results_to_return,

    category_filter, sort, page_token)

参数：

api_dev_key（string）：注册帐户的api开发者密钥。除其他外，这将用于根据分配的配额限制用户。

search_terms (string): 包含搜索词的字符串。

user_location (string): 执行搜索的用户的位置。

radius_filter (number):可选的搜索半径，以米为单位。

maximum_results_to_return (number):返回的业务结果数。

category_filter（ string ）：用于过滤搜索结果的可选类别，例如餐厅、购物中心等。

sort (number): ：可选排序模式：最佳匹配（0-默认）、最小距离（1）、最高等级（2）。

page_token（string）：该标记将在结果集中指定应返回的页面。

Returns: (JSON) 包含与搜索查询匹配的企业列表信息的JSON。每个结果条目都有企业名称、地址、类别、评级和缩略图。

6.基本系统设计和算法

在高层次上，我们需要存储和索引上面描述的每个数据集（地点、评论等）。对于查询这个庞大数据库的用户来说，索引应该是高效的，因为在搜索附近的地方时，用户希望实时看到结果。

考虑到一个地方的位置不会经常改变，我们不需要担心数据的频繁更新。相比之下，如果我们打算构建一个服务，其中对象确实会频繁地改变其位置，例如人或出租车，那么我们可能会想出一个非常不同的设计。

让我们看看存储这些数据的不同方法，并找出最适合我们用例的方法：

a、 SQL解决方案

一个简单的解决方案是将所有数据存储在MySQL这样的数据库中。每个位置将存储在单独的一行中，由LocationID唯一标识。每个地方的经度和纬度将分别存储在两个不同的列中，并执行快速搜索；这两个字段都应该有索引。

要查找半径“D”内给定位置（X，Y）的所有附近位置，我们可以这样查询：

Select * from Places where Latitude between X-D and X+D and Longitude between Y-D and Y+D

上面的查询并不是完全准确的，因为我们知道要找到两点之间的距离，我们必须使用距离公式（毕达哥拉斯定理），但为了简单起见，我们采用这个公式。

这个查询的效率有多高？我们估计有5亿个地方需要存储在我们的服务中。由于我们有两个单独的索引，每个索引都可以返回一个巨大的位置列表，在这两个列表上执行交集将不会有效率。另一种看待这个问题的方式是，“X-D”和“X+D”之间可能有太多的位置，同样地，“Y-D”和“Y+D”之间也可能有太多的位置。如果我们能以某种方式缩短这些列表，就可以提高查询的性能。

b、 网格

我们可以把整张地图分成更小的网格，把位置分成更小的集合。每个网格将存储位于特定经度和纬度范围内的所有位置。这个方案将使我们能够只查询几个网格来找到附近的地方。根据给定的位置和半径，我们可以找到所有相邻的网格，然后查询这些网格以找到附近的位置。

让我们假设GridID（一个四字节的数字）将唯一地标识系统中的网格。

合理的网格大小是多少？网格大小可以等于我们想要查询的距离，因为我们还想减少网格的数量。如果网格大小等于我们要查询的距离，那么我们只需要在包含给定位置和相邻八个网格的网格内搜索。由于我们的网格是静态定义的（从固定的网格大小），我们可以很容易地找到任何位置（lat，long）及其相邻网格的网格编号。

在数据库中，我们可以存储每个位置的GridID，并在其上建立索引，以便更快地搜索。现在，我们的查询将如下所示：

Select * from Places where Latitude between X-D and X+D and Longitude between Y-D and Y+D and

GridID in (GridID, GridID1, GridID2, ..., GridID8)

这无疑将改善我们查询的运行时间。

我们应该把索引保存在内存中吗？在内存中维护索引将提高我们服务的性能。我们可以将索引保存在哈希表中，其中“key”是网格编号，“value”是该网格中包含的位置列表。

我们需要多少内存来存储索引？假设我们的搜索半径是10英里；考虑到地球总面积约为2亿平方英里，我们将拥有2000万个网格。我们需要一个4字节的数字来唯一地标识每个网格，因为LocationID是8字节，我们需要4GB的内存（忽略哈希表开销）来存储索引。

(4 * 20M) + (8 * 500M) ~= 4 GB

对于那些有很多位置的网格，这个解决方案仍然运行缓慢，因为我们的位置在网格中分布不均匀。我们可以有一个稠密的区域，有很多地方，另一方面，我们可以有人口稀少的区域。

如果我们可以动态调整网格大小，这样每当我们有一个有很多地方的网格时，我们就可以分解它来创建更小的网格，这个问题就可以解决。这种方法的几个挑战可能是：

• 1）如何将这些网格映射到位置
• 2）如何找到网格的所有相邻网格。

c、 动态尺寸网格

假设我们不想在一个网格中有超过500个位置，这样我们可以进行更快的搜索。所以，每当一个网格达到这个极限，我们就把它分成四个大小相等的网格，并在它们之间分配位置。这意味着人口稠密的地区，如旧金山市中心，将有大量的网格，人口稀少的地区，如太半洋将有较大的网格，只有在海岸线周围的地方。

什么数据结构可以保存这些信息？每个节点有四个子节点的树可以达到我们的目的。每个节点将代表一个网格，并包含该网格中所有位置的信息。如果一个节点达到500个位置的限制，我们将分解它，在其下创建四个子节点，并在它们之间分配位置。这样，所有叶节点将代表无法进一步细分的网格。因此叶节点将保留一个位置列表。这种每个节点可以有四个子节点的树结构称为四叉树。

我们将如何构建四叉树？

我们将从一个节点开始，它将在一个网格中代表整个世界。由于它将有500多个位置，我们将把它分解为四个节点，并在它们之间分配位置。我们将继续对每个子节点重复这个过程，直到没有超过500个位置的节点。

我们如何找到给定位置的网格？

我们将从根节点开始，向下搜索以找到所需的节点/网格。在每一步中，我们都将查看当前访问的节点是否有子节点。如果有，我们将移动到包含所需位置的子节点，并重复此过程。如果节点没有任何子节点，那么这就是我们想要的节点。

如何找到给定网格的相邻网格？

因为只有叶节点包含位置列表，所以我们可以用双链接列表连接所有叶节点。通过这种方式，我们可以在相邻的叶节点之间向前或向后迭代，以找到我们想要的位置。另一种查找相邻网格的方法是通过父节点。我们可以在每个节点中保留一个指针来访问其父节点，而且由于每个父节点都有指向其所有子节点的指针，因此我们可以很容易地找到节点的同级。我们可以通过父指针继续扩大对相邻网格的搜索。

一旦我们有了附近的LocationID，我们就可以查询后端数据库来查找这些地方的详细信息。

搜索工作流程是什么？

我们将首先找到包含用户位置的节点。如果该节点有足够的所需位置，我们可以将它们返回给用户。如果没有，我们将继续扩展到相邻节点（通过父指针或双链接列表），直到找到所需的位置数或根据最大半径耗尽搜索。

存储四叉树需要多少内存？

对于每个位置，如果只缓存LocationID和Lat/Long，则需要12GB来存储所有位置。

24 * 500M => 12 GB

既然每个网格最多可以有500个位置，我们有500米的位置，那么我们总共有多少个网格？

500M / 500 => 1M grids

这意味着我们将有1M个叶节点，它们将保存12GB的位置数据。具有1M叶节点的四叉树将有大约1/3的内部节点，每个内部节点将有4个指针（用于其子节点）。如果每个指针是8字节，那么存储所有内部节点所需的内存将是：

1M * 1/3 * 4 * 8 = 10 MB

因此，保存整个四叉树所需的总内存为12.01GB。这可以很容易地安装到现代服务器中。

我们将如何在我们的系统中插入一个新的位置？

每当用户添加新位置时，我们都需要将其插入数据库以及四叉树中。如果我们的树驻留在一台服务器上，那么添加一个新位置很容易，但是如果四叉树分布在不同的服务器上，那么首先我们需要找到新位置的网格/服务器，然后将其添加到那里（在下一节中讨论）。

7.数据分区

如果我们有大量的位置，以至于我们的索引无法放入一台机器的内存中，该怎么办？随着每年20%的增长，我们将在未来达到服务器的内存限制。此外，如果一台服务器无法提供所需的读取流量，该怎么办？为了解决这些问题，我们必须划分我们的四叉树！

这里我们将探讨两种解决方案（这两种分区方案也可以应用于数据库）：

a、 基于区域的切分：

我们可以将我们的位置划分为区域（如邮政编码），这样属于某个区域的所有位置都将存储在固定节点上。要存储一个位置，我们将通过其所在区域找到服务器，同样，在查询附近位置时，我们将询问包含用户位置的区域服务器。这种方法有几个问题：

1.如果一个地区变热怎么办？

在持有该区域的服务器上会有很多查询，使其执行速度变慢。这将影响我们服务的性能。

2.随着时间的推移，与其他地区相比，一些地区最终可能会储存很多地方。因此，在地区不断增长的同时，保持地方的均匀分布是相当困难的。

为了从这些情况中恢复，我们要么重新划分数据，要么使用一致性哈希。

b、 基于LocationID的分片：

我们的哈希函数将把每个LocationID映射到一个服务器，我们将在那里存储该位置。在构建四叉树时，我们将遍历所有位置，并计算每个LocationID的哈希值，以找到存储它的服务器。要找到靠近某个地点的地方，我们必须查询所有服务器，每个服务器将返回一组附近的位置。集中式服务器将聚合这些结果，并将其返回给用户。

我们会在不同的分区上有不同的四叉树结构吗？

是的，这是可能发生的，因为不能保证在所有分区的任何给定网格中都有相同数量的位置。但是，我们要确保所有服务器的位置数量大致相等。不同服务器上的这种不同的树结构不会引起任何问题，因为我们将在所有分区上搜索给定半径内的所有相邻网格。

本章的剩余部分假设我们已经根据LocationID对数据进行了分区。

8.复制和容错

拥有四叉树服务器的副本可以替代数据分区。为了分配读取流量，我们可以拥有每个四叉树服务器的副本。我们可以有一个主从配置，其中副本（从）将只服务于读取流量；所有写通信量将首先进入主设备，然后应用于从设备。从机可能没有一些最近插入的位置（会有几毫秒的延迟），但这是可以接受的。

当四叉树服务器死亡时会发生什么？

我们可以为每台服务器提供一个辅助副本，如果主副本死亡，它可以在故障切换后接管控制权。主服务器和辅助服务器都将具有相同的四叉树结构。

如果主服务器和辅助服务器同时死亡怎么办？

我们必须分配一个新服务器，并在其上重建相同的四叉树。既然我们不知道这个服务器上保留了哪些位置，我们怎么能做到这一点呢？蛮力解决方案是迭代整个数据库，并使用我们的哈希函数过滤LocationID，以找出将存储在此服务器上的所有必需位置。这将是低效和缓慢的；此外，在重建服务器的过程中，我们将无法提供来自服务器的任何查询，因此会丢失一些用户应该看到的位置。

我们如何有效地检索位置和四叉树服务器之间的映射？

我们必须建立一个反向索引，将所有位置映射到它们的四叉树服务器。我们可以有一个单独的四叉树索引服务器来保存这些信息。我们需要构建一个HashMap，其中“key”是四叉树服务器号，“value”是一个包含该四叉树服务器上保留的所有位置的哈希集。我们需要在每个地方存储LocationID和Lat/Long，因为信息服务器可以通过它构建它们的四叉树。请注意，我们将地点的数据保存在哈希集中，这将使我们能够快速从索引中添加/删除地点。所以现在，每当一个四叉树服务器需要重建自身时，它可以简单地向四叉树索引服务器请求它需要存储的所有位置。这种方法肯定会非常快。我们还应该有一个用于容错的四叉树索引服务器的副本。如果四叉树索引服务器死亡，它总是可以通过在数据库中迭代来重建索引。

9.缓存

为了应对热点，我们可以在数据库前面引入缓存。我们可以使用像Memcache这样的现成解决方案，它可以存储有关热点的所有数据。在访问后端数据库之前，应用服务器可以快速检查缓存是否有该位置。根据客户端的使用模式，我们可以调整需要多少缓存服务器。对于缓存逐出策略，最近最少使用（LRU）似乎适合我们的系统。

10.负载平衡（磅）

我们可以在系统中的两个位置添加LB层1）客户端和应用服务器之间，2）应用服务器和后端服务器之间。最初，可以采用简单的循环方法；这将在后端服务器之间平均分配所有传入请求。该LB易于实现，不会引入任何开销。这种方法的另一个好处是，如果服务器死机，负载平衡器将使其退出循环，并停止向其发送任何流量。

循环LB的一个问题是，它不会考虑服务器负载。如果服务器过载或运行缓慢，负载平衡器将不会停止向该服务器发送新请求。为了解决这个问题，需要一个更智能的LB解决方案，定期查询后端服务器的负载，并根据负载调整流量。

11.排名

如果我们不仅要根据接近程度，还要根据受欢迎程度或相关性对搜索结果进行排名，那该怎么办？

我们怎样才能返回给定半径内最受欢迎的地方？

假设我们跟踪每个地方的整体受欢迎程度。在我们的系统中，一个总的数字可以代表这种受欢迎程度，例如，一个地方十颗星中有多少颗星（这是用户给出的不同排名的平均值）？

我们将把这个数字存储在数据库和四叉树中。在搜索给定半径内的前100个位置时，我们可以要求四叉树的每个分区返回最受欢迎的前100个位置。然后，聚合器服务器可以在不同分区返回的所有位置中确定前100个位置。

请记住，我们构建的系统并不是为了频繁更新place的数据。有了这个设计，我们如何在四叉树中修改一个地方的受欢迎程度？虽然我们可以在四叉树中搜索一个地方并更新它的流行度，但这会占用大量资源，并会影响搜索请求和系统吞吐量。假设一个地方的受欢迎程度预计不会在几个小时内反映在系统中，我们可以决定每天更新一到两次，尤其是在系统负载最小的情况下。

参考资料：

grok_system_design_interview.pdf