搜索引擎架构的演变——Algolia 搜索架构第 1 部分

一个全新的搜索引擎架构会是什么样子？谁能比 Algolia 的联合创始人兼首席技术官 Julien Lemoine 更能描述搜索的未来。这是该系列的第一篇文章。搜索引擎，更普遍的信息检索系统，在当今几乎所有的技术栈中都发挥着核心作用。信息检索始于计算机科学之初。随着文本检索会议 (TREC) 的推出，研究在 90 年代初加速。自TREC以来，经过30多年的演变，搜索引擎不断发展壮大，带来了新的挑战。在本文中，我们将介绍搜索引擎架构发展过程中的一些关键里程碑。我们还描述了这些架构今天面临的挑战。如您所见，我们将引擎分为四个架构类别。这是一种简化，因为实际上有许多不同的引擎具有不同的架构组合。我们这样做是为了将注意力集中在这些架构的最重要特征上。在搜索引擎的早期，第一次大革命是使用倒排索引。 “索引”一词来自您在书末找到的索引，它将一个词与包含该词信息的不同页面相关联。本质上，搜索引擎为每个单词构建了一个字典，其中对于每个单词，它存储和排序包含该单词的文档列表。因此，当最终用户使用多个单词执行查询时，搜索引擎可以扫描所有单词，计算交集（包含所有单词的文档），并对它们进行排名。所有搜索引擎都遵循索引的一般概念。索引开辟了一个新的研究领域，即如何以有效的方式表示倒排索引（由几个倒排列表组成）。这项研究导致了多组压缩算法来有效地压缩和扫描那些包含越来越多信息的倒排列表。如果您对倒排列表的表示方式以及可以使用的不同算法感兴趣，我建议您阅读 Christopher D. Manning 所著的 Introduction to Information Retrieval 一书。

在软件架构方面，早期的搜索引擎可以概括为： 一个“索引过程”，将记录列表计算并生成一个表示倒排索引的二进制文件 一个“查询处理”搜索过程，将二进制文件解释为计算特定查询的倒排列表的交集 在这个阶段没有缩放的概念。这种架构适用于少量数据。上世纪 90 年代初期的网络扩张，数据量迅速增加，需要对这种架构进行扩展。在互联网的早期，网站是在目录中手动列出的。几年后很明显，手动列表无法继续处理越来越多的网站（根据互联网实时统计，网站数量从1993年的130个网站发展到1995年的23,500个）。于是开始了最流行的搜索引擎用例：网络搜索引擎。 1993 年，第一个网络搜索引擎问世。在 90 年代初，它们都不得不处理大量增加的数据量。 1995 年，当数字设备公司 (DEC) 推出 Alta Vista 时，它是为了说明他们的多处理器 64 位 Alpha 服务器的强大功能。它是第一个（如果不是第一个）完全并行化的搜索引擎，能够索引当时列出的 1000 万个网站。您可以将文档拆分为 N 个较小的文档集，而不是对所有文档使用一个倒排索引。每个集合称为一个分片，包含初始文档集的一个子集。

现在您可以并行运行所有这些分片的索引，生成 N 个较小的倒排索引而不是一个大的倒排索引。最后，您可以在每个分片中并行搜索，生成 N 个查询并聚合结果以生成统一的结果集。分片的引入使搜索引擎能够处理大量数据。在分片的早期，分片的数量以及服务器的数量是预先确定的。许多实现使用数学散列函数将一个文档分配给 N 个分片之一。一个文档总是被分配到同一个分片，因此永远不会导致分片之间的记录重复。跨不同分片（搜索，每个分片一个线程）的搜索结果的分布式计算，通过 N 个结果的快速合并最终确定 索引和搜索需要在同一台机器上进行给定分片（倒排索引在本地存储上） ）。没有像分布式提交这样的机制允许索引操作同时在所有分片上可见。例如，如果要更改索引的属性列表，或者如果要更改记录结构，则需要创建另一个索引，因为您无法以原子方式执行这些操作。当合并函数必须处理非代数聚合时，新类型的问题就会出现。一个示例是基于字段值折叠结果（例如，您想要折叠每个公司名称的职位，然后显示每个类别的前 10 个职位的职位板）。

这种类型的架构在 90 年代甚至 2000 年代初期使用过。当然，对这些架构进行了大量改进和改进，以确保它们能够支持负载。例如，批量索引很快被数据结构的增量构建取代，以避免在每次通过时重建整个倒排列表（类似于数据库）。分片是搜索引擎扩大规模的关键组成部分。今天，除了达到高可用性的其他原则外，它是所有搜索引擎架构的一部分，我们将在下一节中介绍。搜索引擎需要扩展，以管理大量数据和查询数量。根据 Internet World Stats 的数据，1995 年互联网用户只有 1600 万，但在 2020 年迅速增长到超过 5B。 上一节讨论了如何通过分片来管理大量数据。接下来的问题是如何管理大量的查询，以及相关的搜索的高可用性（即支持硬件故障）。解决这个问题需要引入倒置分片的副本，以便能够回答来自多台机器的查询。一般原则很简单：我们使用与以前相同的架构，但我们有 N 组机器能够回答任何查询，而不是只有一组机器。每组机器包含回答任何查询的所有分片，副本的数量可以根据查询量增加或减少。这种架构的复杂性主要在于复制逻辑，与之前的架构具有相同的属性和缺点。倒排索引复制的复杂性取决于磁盘上数据结构的格式。分代数据结构通常经过优化以最小化传输的数据量。如果您有兴趣了解有关磁盘上不同类型数据结构的更多信息，我建议您阅读 LevelDB 键值存储内部结构的说明；同样的概念也经常应用于搜索引擎。当架构托管在公共云环境中时，不同的机器组必须托管在不同的可用区上，以实现更好的服务水平目标 (SLO)。需要负载平衡器组件将查询分发到不同的机器组，并在出错时重试。这种基于副本的搜索引擎架构与前一个具有完全相同的特征，但增加了：

通过数据复制处理无限量查询的能力（增加容量需要时间，通常需要数小时，因为它需要从现有机器复制倒排索引。只有当可以预期流量增加时，这是一个很好的解决方案。）。在多供应商部署中，磁盘上数据结构的副本通常被转移索引操作的主/副本设置所取代。主分片接收索引操作，将它们存储在 LOG 中。 LOG 由索引过程在本地使用，并且 LOG 被复制到一个或多个位置。这种设置的原因是复制索引操作而不是二进制文件通常更快，因为在传输大型二进制文件时，提供商间带宽可能是瓶颈。鉴于搜索的高可用性对所有在线业务的重要性，在不影响业务的情况下容忍硬件故障至关重要。架构必须管理硬件故障，使其对最终用户保持透明。前面讨论的架构引入了在不影响搜索能力的情况下接受硬件故障的可能性。像 Snapshat 这样的新用例使索引成为系统的关键部分：Snapshot 的信息是短暂的，需要快速搜索，因此索引也需要高可用性。索引的高可用性通过不同的体系结构引入搜索引擎，这些体系结构的共同点是至少两台机器可以构建一个分片。最著名的架构是 Elasticsearch，它于 2010 年推出，具有搜索和索引的高可用性。 Elasticsearch 引入的最重要的创新不是索引的高可用性；这是弹性。弹性是将机器添加到现有实例并在机器之间移动分片的能力。这是搜索引擎架构的重大演变！索引高可用性的引入是上一节中描述的主/副本架构的演变。每个分片都有一个主分片，从而确保索引作业和 N 个副本的唯一排序。确保每个副本都以相同的顺序处理作业以收敛到完全相同的状态，这一点很重要。假设托管主分片的机器停机。在这种情况下，通过领导选举算法将一个副本选为新的主副本，以确保全局一致状态。当索引操作进入系统时，路由阶段会将操作路由到正确的主分片。此路由过程可由三台机器中的任何一台执行（因此您可以针对任何机器执行索引操作）。主分片的索引过程然后将在每个分片上复制索引操作，从而导致在三台机器上并行应用索引操作（模式 3）

模式 3：在一个索引有四个分片、复制因子为 3 的情况下，分片 1 的索引操作示例。负载均衡器选择每个分片的三个副本之一来执行查询。三个副本允许每秒比单个分片副本多三倍的查询。在此设置中，机器分布在两个可用区 (AZ) 上。每个可用区都在云提供商区域内尽可能多的不同物理基础设施上运行。这三个副本的存储方式是，第一个副本 100% 托管在第一个可用区上，第二个副本 100% 托管在第二个可用区上，第三个副本在两个可用区之间拆分。模式 4 说明了发送到 100% 托管在第一个可用区上的副本的一个查询。模式 4：由副本处理的查询示例，完全托管在第一个可用区上 在每台机器上，索引和搜索过程可以访问本地存储的所有分片。弹性来自在现有设置中添加和删除机器。例如，可以在前面的示例中添加一台新机器。然后碎片会自动移动到新机器上，以确保您在每台机器上均匀加载。根据您的搜索引擎的分配算法，您最终可能会得到类似于模式 5 的结果。在此架构中，分片的数量是静态的。定义分片数量是配置的关键要素，因为它定义了扩展能力和基础性能。在这个例子中，分片的数量不足以使用所有机器上的所有 CPU 资源。不过，您可以增加副本数量以支持每秒更多查询并使用所有资源，这是扩展的标准方式。不要有太多碎片也很重要。目标是并行处理所有这些。如果您没有足够的 CPU 线程同时用于所有分片，则会对您的响应时间产生负面影响。 Schema 5：在第二个可用区添加新机器后的示例

在保持所有分片可用的同时，此架构可以支持两种类型的故障： 一台机器停机。这不会影响索引和搜索的能力。有足够的副本来确保我们仍然可以执行搜索查询。领导选举将选举两个副本之一作为主。唯一的影响是减少搜索容量，因为可用于搜索的 CPU 线程较少。 1 个 AZ 已关闭。在这种情况下，搜索仍然可用，但可扩展容量较小。两个分片的索引将不可用，因为只有三个副本中的一个仍然存在，这会阻止领导者选举。这种类型的架构是当今搜索架构中最先进的技术，具有以下特点： 能够根据您配置的分片数量扩展数据 最新一代架构现在已有十多年的历史了！从那时起，快速增长的市场和 SaaS 应用程序对这些架构施加了许多限制。现在是为未来十年设计下一代架构的时候了，解决以下挑战： 以亚分钟的速度添加/删除机器。我们已经知道如何从现有实例中添加/删除机器。但是，我们需要更进一步支持动态可扩展性：能够在一分钟内添加或删除机器，并且能够在新机器可用之前临时处理增加的流量！今天的搜索引擎比以往任何时候都更需要预测增长，并扩展其基础设施以应对流量高峰。全面的动态可扩展性将使每个人都更加经济高效，同时释放搜索引擎的新创意用法。例如，一个大型市场提出了利用搜索引擎在其商店进行限时抢购的想法：客户必须找到隐藏在其庞大目录中的廉价产品。您可以想象他们的搜索引擎在向数百万用户发送电子邮件后立即收到大量查询，他们上次活动产生的流量是平均每日流量的 160 倍。但每次搜索事件传播开来时都会发生同样的情况，这通常是不可能提前计划的。

一个动态数量的分片。分片的数量是性能和扩展能力的关键因素。为了达到最佳效果，这个数字需要经常改变。下一代搜索引擎架构将允许您动态更改此数字。它还需要更进一步，引擎会自动调整此数字以确保您始终拥有最佳性能和扩展能力。分离搜索和索引。在查询量和数据量方面进行扩展是搜索引擎最苛刻的情况。对于市场等许多用例来说，这是一个问题。在这种情况下，如果您为每个副本执行索引，基础设施的成本很快就会变得过高。增加搜索或索引容量会影响现有机器的资源消耗。例如，当系统已经加载时，扩展其中一个子系统会使整个系统崩溃。下一代将具有搜索和索引的高可用性，同时对每个分片仅执行一次索引工作。它将分别缩放索引和搜索，避免索引对搜索的任何负面影响。利用网络带宽的演进。十年前，机器之间拥有 1Gbps 的链路是常态。今天，您可以访问公共云提供商中高达 100 Gbps 的网络链接，这将越来越成为常态。与带宽上的 100 倍因素相比，CPU 和存储的改进在同一时期受到的限制要大得多！利用这种网络架构需要具有更多并行化的非常不同的数据传输使用。这是一个重要因素，需要成为搜索引擎架构的核心才能有效扩展。本机多租户优化。 SaaS 应用程序在单个索引中托管多个用户的情况很普遍。为每个客户设置专用索引的成本太高了。虽然这是一个很好的策略，但今天几乎不可能为最大的用户提供有保证的性能。新的搜索架构需要不断发展，以确保从逻辑角度来看，它仍然可以显示为一个索引。尽管如此，最重要的客户仍然拥有专用的分片和资源，以确保有保证的性能并避免来自其他客户的任何影响。我们在 2019 年开始开发下一代架构时确定了这五个独特的挑战。我们开发了一个独特的架构来解决这五个挑战，我们的第一批客户正在测试它。以下文章将详细介绍该架构的工作原理以及我们如何解决这五个独特的搜索挑战。