分布式搜索系统的设计

一、介绍

如今，我们几乎在每个网站上都看到一个搜索栏。搜索栏使我们能够快速找到我们需要的内容。

让我们举个例子。想象一下，如果YouTube没有提供搜索栏，我们如何在数百万个视频中找到特定的视频，这些视频多年来都已上传到YouTube？用户仅通过滚动浏览很难找到他们想要的内容。

在每个搜索栏背后，都有一个搜索系统。

二、需求

• 可用性：系统应对用户高度可用。
• 可扩展性：系统应能够随着数据量的增加而扩展。换句话说，它应能够索引大量数据。
• 快速搜索大数据：无论用户搜索多少内容，他们都应该能够快速获取结果。

三、核心概念

倒排索引

• 索引 — 是组织和操作数据的过程，旨在促进快速和准确的信息检索。
• 倒排索引 — 是一种类似于哈希映射的数据结构，它使用文档-词术矩阵。它不是将完整文档存储，而是将文档拆分为单个词语。然后，文档-词术矩阵识别唯一的词语，并丢弃频繁出现的词语，如“to”、“they”、“the”、“is”等等。

图1.0：倒排索引

“映射”列中的每个条目都包括三个列表：

• 词语出现的文档列表。
• 统计词语在每个文档中出现的频率的列表。
• 指出词语在每个文档中的位置的二维列表。一个词语可以在同一文档中出现多次，因此使用二维列表。

对于提取的每个词语，我们要么在倒排索引中添加新行，要么在该词语已经在倒排索引中有条目的情况下更新现有条目。同样，在删除文档时，我们需要处理，找到已删除文档词汇在倒排索引中的条目，然后相应地更新倒排索引。

四、设计

在添加文档或运行搜索查询时，需要将倒排索引加载到主内存中。为了效率，必须将倒排索引的大部分内容适应于机器的RAM中。

这意味着我们必须将大量数据加载到RAM中。不是增加单台机器的资源来索引十亿页，而是要转向分布式系统，利用并行化的力量。

图2.0：分布式搜索系统的高级设计

• 索引器从分布式存储中获取文档，并使用MapReduce进行索引，MapReduce运行在分布式的普通机器集群上。索引器使用分布式数据处理系统（例如MapReduce）进行并行和分布式索引构建。构建的索引表存储在分布式存储中。
• 使用分布式存储来存储文档和索引。
• 用户在搜索栏中输入包含多个词语的搜索字符串。
• 搜索器解析搜索字符串，从存储在分布式存储中的索引中搜索映射，并将最匹配的结果返回给用户。

数据分区

为了实现成本效益，我们在索引中使用了众多小节点。这个过程要求我们对输入数据（文档）进行分区或拆分。

图3.0：在多个普通机器集群中以并行方式进行分布式索引和搜索

索引：

• 集群管理器将输入文档集分成N个分区，其中N等于上图中的2。每个分区的大小由集群管理器决定，考虑到数据的大小、计算、内存限制和集群中的节点数量。由于各种原因，可能不是所有节点都可用。集群管理器通过定期心跳监视每个节点的健康状况。要将文档分配给N个分区之一，可以使用哈希函数。
• 分区后，集群管理器在集群中的N个节点上同时运行所有N个分区的索引算法。每个索引过程都会生成一个小型的倒排索引，存储在节点的本地存储中。这样，我们生成了N个小型倒排索引，而不是一个大的倒排索引。

搜索：

• 在搜索阶段，当用户查询进来时，我们在存储在节点本地存储中的每个小型倒排索引上运行并行搜索，生成N个查询。
• 每个小型倒排索引的搜索结果都是与查询词语匹配的映射列表（我们假设用户查询是单个词语/术语）。合并器聚合这些映射列表。
• 在聚合映射列表后，合并器根据每个文档中词语的频率对文档列表进行排序。
• 排序后的文档列表以升序顺序返回给用户。

复制

我们为生成分配分区的索引节点创建副本。

通常，三个副本足够。三个副本意味着三个节点托管相同的分区并生成索引。三个节点中的一个成为主节点，而其他两个是副本。同一分区将转发到所有三个副本。我们假设每个副本都会独立计算索引，这会导致资源的低效使用。与在副本上重新计算索引不同，我们只在主节点上计算倒排索引。接下来，我们将倒排索引（二进制文件）传输到副本。这种方法的主要好处是避免了在副本上使用重复的CPU和内存来进行索引。

图4.0：由索引节点生成的索引存储在分布式存储中，参与搜索的节点从分布式存储中读取索引以为用户的查询生成结果

索引和搜索之间有很强的分离，而没有索引延迟的负面影响。由于这种分离，索引不会影响搜索可扩展性，反之亦然。此外，与在副本上重新计算索引不同，我们只需复制索引文件。

在硬件故障的情况下，会添加新的搜索器或索引器机器，并从分布式存储中检索数据的副本。

五、评估

可用性

数据在分布式存储中跨多个区域进行复制，使索引和搜索的跨区域部署更加容易。因此，如果一个地方发生故障，我们可以在另一个集群中处理请求。

索引是离线执行的，不在用户的关键路径上。我们不需要同步复制索引操作。无需在将新索引复制到响应搜索查询之前等待。这使得搜索对用户可用。

可扩展性

分区是搜索系统扩展的重要组成部分。当增加分区的数量并向索引和搜索集群添加更多节点时，可以在数据索引和查询方面实现扩展。

索引和搜索过程之间的强分离有助于索引和搜索独立和动态地扩展。

大数据快速搜索

我们利用了多个节点，每个节点在较小的倒排索引上并行执行搜索查询。然后，将每个搜索节点的结果合并并返回给用户。