分布式搜索系统的设计
一、介绍
如今，我们几乎在每个网站上都看到一个搜索栏。搜索栏使我们能够快速找到我们需要的内容。
让我们举个例子。想象一下，如果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：由索引节点生成的索引存储在分布式存储中，参与搜索的节点从分布式存储中读取索引以为用户的查询生成结果
索引和搜索之间有很强的分离，而没有索引延迟的负面影响。由于这种分离，索引不会影响搜索可扩展性，反之亦然。此外，与在副本上重新计算索引不同，我们只需复制索引文件。
在硬件故障的情况下，会添加新的搜索器或索引器机器，并从分布式存储中检索数据的副本。
五、评估
可用性
数据在分布式存储中跨多个区域进行复制，使索引和搜索的跨区域部署更加容易。因此，如果一个地方发生故障，我们可以在另一个集群中处理请求。
索引是离线执行的，不在用户的关键路径上。我们不需要同步复制索引操作。无需在将新索引复制到响应搜索查询之前等待。这使得搜索对用户可用。
可扩展性
分区是搜索系统扩展的重要组成部分。当增加分区的数量并向索引和搜索集群添加更多节点时，可以在数据索引和查询方面实现扩展。
索引和搜索过程之间的强分离有助于索引和搜索独立和动态地扩展。
大数据快速搜索
我们利用了多个节点，每个节点在较小的倒排索引上并行执行搜索查询。然后，将每个搜索节点的结果合并并返回给用户。
