自下而上认识 Elasticsearch：第 1 部分

简介

本系列文章的动机是让您更好地了解 Elasticsearch、Lucene 以及搜索引擎在某种程度上的底层工作原理。虽然转动方向盘和踩下油门踏板就能开动汽车，但高水平的驾驶员通常至少了解车辆的一些机械原理。搜索引擎也是如此。Elasticsearch 提供了非常容易使用的 API，可以让您轻松上手，并在日后的使用中为您提供便利。然而，要充分利用 Elasticsearch，了解一些底层算法和数据结构相关知识会有所帮助。掌握这方面的知识后，您就能够充分利用 Elasticsearch 的大量功能，从而改善用户的搜索体验，同时确保系统运作良好、稳定可靠和（近乎）实时更新。

我们先从基础索引结构开始，也就是倒排索引。这是一种非常通用的数据结构。同时，它也很容易使用和理解。可以这样说，Lucene 的实现是一项高度优化、令人印象深刻的工程壮举。我们不会冒险讨论 Lucene 的实现细节，而是继续介绍如何构建和使用倒排索引。这也是影响我们搜索和构建索引方式的因素。

在介绍了倒排索引（即抽象层的“底部”）之后，我们将了解：

• 如何执行简单的搜索。
• 哪些类型的搜索能（不能）高效地完成，以及为什么使用倒排索引将问题转换为字符串前缀问题。
• 为什么文本处理很重要。
• 如何在“段”中构建索引，以及这对搜索和更新有怎样的影响。
• Lucene 索引的构成。
• Elasticsearch 分片和索引。

到那时，我们将了解在搜索和构建索引时单个 Elasticsearch 节点内部会发生什么。本系列的第二篇文章将介绍 Elasticsearch 在分布式方面的知识。

倒排索引和索引项

假设我们有以下三个简单的文档：“Winter is coming.”、“Ours is the fury.”和“The choice is yours.”。经过一些简单的文本处理（改为小写、删除标点符号和拆分成单词）后，我们可以创建如图所示的“倒排索引”。

倒排索引将 term（项）映射到包含相应项的文档（可能还包括文档中的位置）。由于 dictionary（字典）中的项是经过排序的，因此我们可以快速找到某个项，并随后在 postings 结构中找到相应项的出现次数。这与“正排索引”相反，后者会列出与特定文档相关的项。

然后，通过查找所有项及其出现的次数，完成含有多个项的简单搜索，并取得这些出现次数集合的交集（对于 AND 搜索）或并集（对于 OR 搜索），以获得生成的文档列表。更复杂的查询类型显然更为详尽，但方法是一样的：首先，对字典执行操作以查找候选项，然后对相应的出现次数、位置等进行操作。

因此，索引项是搜索的单位。我们生成的项决定了我们能（不能）高效地进行哪些类型的搜索。例如，使用上图中的字典，我们可以高效地找到所有以“c”开头的项。然而，我们无法高效地对包含“ours”的所有内容进行搜索。为此，我们必须遍历所有项，才能发现“yours”也包含这个子字符串。当索引没有那么小时，这样操作是非常昂贵的。就复杂性而言，通过项的前缀查找项是 $\mathcal{O}\left(\mathrm{log}\left(n\right)\right)$，而通过任意子字符串查找项则是 $\mathcal{O}\left(n\right)$。

换句话说，我们可以高效地找到给定了项前缀的内容。如果我们只有倒排索引，我们希望所有内容都像字符串前缀问题一样。以下是此类转换的一些示例。有些例子很简单，最后一个简直就是魔法。

• 为了找到以“tastic”结尾的所有内容，我们可以对反向词构建索引（例如：“fantastic”→“citsatnaf”），然后搜索以“citsat”开头的所有内容。
• 查找子字符串通常需要将项拆分为更小的项，称为“n 元语法”。例如，“yours”可以拆分为“^yo”、“you”、“our”、“urs”和“rs$”，这意味着我们可以通过搜索“our”和“urs”来获得“ours”的出现。
• 对于具有合成词的语言（如挪威语和德语），我们需要将“Donaudampfschiff”这样的单词进行“分解”，例如，分解为 {"donau", "dampf", "schiff"}，以便在搜索“schiff”时找到它。
• 地理坐标点（如 (60.6384, 6.5017)）可以转换为“地理哈希值”，在本例中为“u4u8gyykk”。字符串越长，精度就越高。
• 例如，为了实现对人名非常有用的语音匹配，有一些算法（如 Metaphone）可以将“Smith”转换为 {"SM0", "XMT"}，将“Schmidt”转换为 {"XMT", "SMT"}。
• 在处理数值型数据（和时间戳）时，Lucene 会以类似 trie 的方式自动生成多个精度不同的项，因此可以高效地进行范围搜索¹。简而言之，数字 123 可以存储为 "1"-百位、"12"-十位 和 "123"。因此，搜索 [100, 199] 范围内的所有内容就是与百位为 "1" 的项匹配的所有内容。当然，这与搜索以“1”开头的所有内容不同，因为后者还包括“1234”等数字。
• 要进行“您是不是要找？”类型搜索并找到与输入接近的拼写，可以构建一个“Levenshtein”自动机来高效地遍历字典。这个操作特别复杂，不妨看一下这个精彩的故事，了解它如何在 Lucene 中结束。

在技术层面深层剖析文本处理是未来许多文章的素材，但我们已经强调了为什么在索引项生成方面谨小慎微很重要：旨在获得可以高效执行的搜索。

构建索引

在构建倒排索引时，我们需要优先考虑以下几点：搜索速度、索引紧凑性、索引速度以及新更改变得可见所需的时间。

搜索速度和索引紧凑性息息相关：当利用较小的索引进行搜索时，需要处理的数据较少，而更多的数据将载入内存。正如我们将要看到的，这两者（特别是紧凑性）都是以索引速度为代价的。

为了尽量减少索引大小，我们使用了各种压缩技术。例如，当存储 postings（可能会变得很大）时，Lucene 会使用可变数量的字节（因此可以用单个字节保存较小的数字）等来实现诸如增量编码（例如，将 [42, 100, 666] 存储为 [42, 58, 566]）之类的技巧。

保持数据结构小而紧凑意味着，牺牲了高效更新数据的可能性。事实上，Lucene 根本不更新数据：Lucene 写入的索引文件是不可变的，即这类文件永远不会更新。例如，这与 B 树完全不同，B 树可以更新，并且通常允许您指定填充因子来表明您期望更新的次数。

但删除是个例外。当您从索引中删除一个文档时，该文档会在一个特殊的删除文件中会被标记为删除，这个删除文件实际上只是一个位图，更新起来很便宜。索引结构本身不会更新。

因此，更新先前已编制索引的文档就是执行一个删除操作，然后重新插入该文档。请注意，这意味着更新文档甚至比一开始就添加文档更昂贵。因此，将快速变化的计数器之类的数据存储在 Lucene 索引中通常不是一个好主意，毕竟无法对值进行就地更新。

添加新文档时（可能是通过更新），索引更改首先缓存在内存中。最终，整个索引文件都会被刷新到磁盘上。请注意，这就是 Lucene 中“刷新”的含义。Elasticsearch 中的刷新操作涉及 Lucene 提交等内容，事务日志部分进行了相关介绍。

何时刷新取决于多种因素：更改必须以多快的速度可见、可用于缓存的内存、I/O 饱和度等。通常，对于索引速度而言，缓冲区越大越好。如果缓冲区很小，只要它们足以使 I/O 保持良好状态即可。我们将在下一部分中进行详细介绍。

写入的多个文件构成一个索引段。

索引段

Lucene 索引由一个或多个不可变的索引段组成，索引段本质上是一个“迷你索引”。当您进行搜索时，Lucene 会对每个段进行搜索，过滤掉任何删除内容，并合并所有段的结果。显然，随着段数的增加，这会变得越来越乏味。为了保持段数可控，Lucene 偶尔会在添加新段时根据一些合并策略来合并段。Lucene 黑客 Michael McCandless 有一篇很棒的文章，其中解释并可视化了段合并³。当段被合并时，标记为已删除的文档最终会被丢弃。这也解释了为什么添加更多的文档实际上会导致索引大小更小：它可以触发合并。

Elasticsearch 和 Lucene 通常在何时合并段方面做得很好。Elasticsearch 的策略可以通过配置合并设置进行调整。您还可以使用优化 API 来强制合并。

在将段刷新到磁盘之前，更改会缓存在内存中。在过去 (Lucene <2.3)，每个添加的文档实际上都以自己的小段⁴的形式存在，并且所有段都会在刷新时合并。现在，有了 DocumentsWriter，它可以从一批文档中生成多个较大的内存段。在 Lucene 4 中，现在每个线程都可以有一个这样的选项，通过允许并发刷新来提高索引性能。（以前，必须等待刷新完成才能进行索引。）

在创建新段时（无论是由于刷新还是合并），它们还会导致某些缓存无效，这可能会对搜索性能产生负面影响。缓存（如字段缓存和筛选器缓存）是按段划分的。Elasticsearch 推出了 warmer-API⁵，因此在新段可用于搜索之前，可以“预热”必要的缓存。

使用 Elasticsearch 刷新最常见的原因可能是持续索引刷新，默认情况下每秒刷新一次。当新的段刷新时，它们就可以用于搜索，从而实现（近乎）实时搜索。虽然刷新不像提交那么昂贵（因为刷新不需要等待确认写入），但它确实会导致创建一个新段，使某些缓存无效，并有可能触发合并。

当索引吞吐量很重要时，例如批量（重新）编制索引时，花费大量时间刷新和合并小段的效率没有那么高。因此，在这些情况下，最好暂时增加 refresh_interval 设置，甚至完全禁用自动刷新。用户可以随时手动刷新，并/或在编制完索引时刷新。

Elasticsearch 索引

“计算机科学中的所有问题都可以通过增加一个间接层来解决。”– David J. Wheeler

Elasticsearch 索引由一个或多个分片组成，分片可以有零个或多个副本。这些都是单独的 Lucene 索引。也就是说，Elasticsearch 索引由许多 Lucene 索引组成，而这些 Lucene 索引又由索引段组成。当您搜索一个 Elasticsearch 索引时，会对所有分片执行搜索，进而对所有段进行搜索，然后进行合并。搜索多个 Elasticsearch 索引时也是如此。实际上，用一个分片搜索两个 Elasticsearch 索引与用两个分片搜索一个索引几乎是一样的。在这两种情况下，都会搜索两个底层的 Lucene 索引。

从本文开始，当我们单独提到“索引”时，我们指的是 Elasticsearch 索引。

“分片”是 Elasticsearch 的基本扩展单位。将文档添加到索引中后，它会被路由到一个分片。默认情况下，这个操作是基于文档 id 的哈希值以循环方式完成的。在本系列的第二部分中，我们将进一步介绍分片的移动方式。但是，一定要知道，分片的数量是在创建索引时指定的，而且之后不能更改。Shay 关于 Elasticsearch 的早期演讲中非常全面地介绍了为什么分片实际上是一个完整的 Lucene 索引，以及与其他方法相比分片的各种利弊。

至于向哪些 Elasticsearch 索引以及分片（和副本）发送搜索请求，可以通过多种方式定制。通过结合索引模式、索引别名、文档和搜索路由，可以实现许多不同的分区和数据流策略。我们在此不做深入介绍，但如果您想了解，建议您阅读 Zachary Tong 关于定制文档路由的文章，以及 Shay Banon 关于大数据、搜索和分析的演讲。下面举了几个例子，希望能给您提供一些思路：

• 许多数据都是基于时间的，例如日志、推文等。通过每天（或每周、每月…）创建一个索引，我们可以有效地将搜索限制在特定的时间范围内，并删掉旧数据。请记住，我们无法高效地从现有索引中进行删除，但删除整个索引很便宜。
• 当搜索必须限于某个用户时（例如“搜索您的消息”），将该用户的所有文档路由到同一个分片可能会很有用，这样可以减少必须搜索的索引数量。

事务

虽然 Lucene 有事务的概念，但 Elasticsearch 没有。Elasticsearch 中的所有操作都会添加到相同的时间线，这在节点之间不一定完全一致，因为刷新取决于计时。

在分布式系统中，跨节点跨索引管理不同段、缓存等的隔离性和可见性非常困难。Elasticsearch 没有试图这样做，而是优先考虑速度。

Elasticsearch 有一个“事务日志”，其中附加了要编制索引的文档。附加到日志文件比构建段要便宜得多，因此，Elasticsearch 可以将文档写入到索引（某个持久的位置）中，内存缓冲区除外，因为该缓冲区在崩溃时会丢失。您还可以指定编制索引时所需的一致性级别。例如，您可以要求每个副本在索引操作返回之前为文档编制索引。

总结

总而言之，当涉及到 Lucene 如何在单个节点上构建、更新和搜索索引时，需要注意以下重要属性：

• 如何处理编制索引的文本决定了如何进行搜索。正确的文本分析很重要。
• 索引首先在内存中构建，然后偶尔以段的形式刷新到磁盘。
• 索引段是不可变的。已删除的文档会被标记为已删除。
• 一个索引由多个段组成。对每个段进行搜索，然后合并结果。
• 段偶尔会被合并。
• 字段缓存和筛选器缓存是按段划分的。
• Elasticsearch 没有事务。

在本系列的下一篇文章中，我们将介绍如何在集群中进行搜索和编制索引。