注意:原文发表时间是13年,所以实现有可能与新版不一致.
原文地址:https://www.elastic.co/cn/blog/found-elasticsearch-from-the-bottom-up

Introduction

在本系列文章中,我们从一个新的视角来看ElasticSearch.我们将从下往上,从抽象的底层实现到用户可见层,我们在向上移动的过程中研究各种内部数据结构和行为.

本系列文章的动机是更好地了解Elasticsearch,Lucene以及在某种程度上搜索引擎在引擎盖下是如何工作的.虽然您可以通过转动方向盘和踩下一些踏板来驾驶汽车,但高水平的驾驶员通常至少了解车辆的一些机械原理.搜索引擎也是如此.Elasticsearch提供了非常易于使用的API,它将使您入门并毫不费力地带您走得更远.但是,要充分利用它,对底层算法和数据结构有一些了解会有所帮助.这种理解使您能够充分利用其大量功能,从而改善用户的搜索体验,同时保持系统的性能、可靠性和(近乎)实时更新.

我们将从基本的索引结构开始:倒排索引.它是一种非常通用的数据结构.同时,它也易于使用和理解.也就是说,Lucene的实现是一项高度优化的,令人印象深刻的工程壮举.我们不会冒险讨论Lucene的实现细节,而是坚持如何使用和构建倒排索引.这就是影响我们如何搜索和索引的原因.

引入倒排索引作为抽象级别的”底部”后,我们将研究:

如何执行简单的搜索.
哪些类型的搜索可以(和不能)有效地完成,以及为什么使用倒排索引来转换问题,直到它们看起来像字符串前缀问题.
为什么文本处理很重要.
如何在”段”中构建索引,以及这对搜索和更新有何影响.
什么构成Lucene-index.
*Elasticsearch分片和索引.

到那时,我们将了解单个Elasticsearch节点在搜索和索引时会发生什么.本系列的第二篇文章将介绍Elasticsearch的分布式方面.

Inverted Indexes AND Index Terms

假设我们有这三个简单的文档:”Winter is coming.”,”Ours is the fury.”和”The choice is yours.”.经过一些简单的文本处理(小写、去掉标点、分词),我们就可以构造出如图所示的”倒排索引”.

倒排索引将术语映射到包含该术语的文档(以及可能在文档中的位置).由于字典中的术语是排序的,我们可以快速找到一个术语,然后找到它在帖子结构中的出现.这与列出与特定文档相关的术语的”前向索引”相反.

术语英文为term

然后通过查找所有术语和它们的出现来完成一个包含多个术语的简单搜索,并获取出现集的交集(对于AND搜索)或并集(对于OR搜索)以获得文档的结果列表.更复杂类型的查询显然更精细,但方法是一样的:首先对字典进行操作,找到候选词,然后对相应的出现、位置等进行操作.

因此,索引术语是搜索的单位.我们生成的术语决定了我们可以(和不能)有效地进行哪些类型的搜索.例如,使用上图中的字典,我们可以高效地找到所有以”c”开头的术语.但是,我们无法有效地搜索包含”ours”的所有内容.为此,我们必须遍历所有术语,以发现”yours”也包含子字符串.当索引不是很小时,这是非常昂贵的.

索引术语英文为index term

换句话说,我们可以有效地找到给定术语前缀的东西.当我们只有一个倒排索引时,我们希望一切看起来都像一个字符串前缀问题.以下是此类转换的几个示例.有些很简单,最后一个近乎神奇.

要找到以”tastic”结尾的所有内容,我们可以反向索引(例如”fantastic”→”citsatnaf”)并搜索以”citsat”开头的所有内容.
查找子字符串通常涉及将术语拆分为更小的术语,称为”n-gram”.例如,”yours”可以拆分为”^yo”、”you”、”our”、”urs”、”rs$”,这意味着我们可以通过搜索”our”和”urs”.
对于具有复合词的语言,例如挪威语和德语,我们需要将诸如”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”-hundreds-term 的所有内容.当然,这与搜索以”1”开头的所有内容不同,因为这还包括”1234”等.
“Did you mean?”键入搜索并找到接近输入的拼写,可以构建一个”Levenshtein”自动机来有效地遍历字典.这是异常复杂的,这里有一个关于它如何在Lucene中结束的引人入胜的故事.

对文本处理的技术深入研究是未来许多文章的基础,但我们强调了为什么对索引词生成一丝不苟的重要性:获得可以高效执行的搜索.

Building Indexes

在构建倒排索引时,我们需要优先考虑一些事情:搜索速度、索引紧凑度、索引速度以及新更改变得可见所需的时间.

搜索速度和索引紧凑度是相关的:当搜索较小的索引时,需要处理的数据较少,更适合内存中处理.正如我们将看到的,两者,尤其是紧凑性,都是以索引速度为代价的.

为了最小化索引大小,使用了各种压缩技术.例如,当存储帖子(可能会变得非常大)时,Lucene会使用可变数量的字节(小数字可以用一个字节保存),等等.

保持数据结构小而紧凑意味着牺牲有效更新它们的可能性.事实上,Lucene根本不会更新它们:Lucene写入的索引文档是不可变的,即它们永远不会更新.这与B树完全不同,例如,B树可以更新,并且通常允许您指定一个填充因子来指示您期望的更新量.

例外是删除.当您从索引中删除一个文档时,该文档会在一个特殊的删除文件中被标记为删除文件,该文件实际上只是一个更新成本低的位图.索引结构本身不会更新.

因此,更新先前索引的文档是删除后重新插入文档.请注意,这意味着更新文档比最初添加文档的成本更高.因此,在Lucene索引中存储诸如快速变化的计数器之类的东西通常不是一个好主意——没有值的就地更新.

添加新文档时(可能通过更新),索引更改首先缓冲在内存中.最终,索引文档全部刷新到磁盘.请注意,这是”flush”的Lucene含义.Elasticsearch的刷新操作涉及Lucene提交等,在事务日志部分中介绍.

何时刷新取决于各种因素:必须多快才能看到更改、可用于缓冲的内存、I/O饱和度等.通常,对于索引速度,缓冲区越大越好,只要它们足够小,您的I/O可以跟上².我们将在下一节中更详细地介绍.

写入的文档组成一个索引段.

Index Segments

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

Elasticsearch和Lucene通常可以很好地处理何时合并段.可以通过配置合并设置来调整Elasticsearch的策略.您还可以使用优化API来强制合并.

在段被刷新到磁盘之前,更改被缓冲在内存中.在过去(Lucene<2.3),每个添加的文档实际上都作为自己的小段存在⁴,并且所有这些都在刷新时合并.现在,有一个DocumentsWriter,它可以从一批文档中创建更大的内存段.在Lucene4中,现在每个线程都可以有一个,通过允许并发刷新来提高索引性能.(以前,索引必须等待刷新完成.)

随着新段的创建(由于刷新或合并),它们还会导致某些缓存失效,这会对搜索性能产生负面影响.像字段和过滤器缓存这样的缓存是按段的.Elasticsearch有一个warmer-API⁵,因此可以在新段可用于搜索之前”预热”必要的缓存.

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

当索引吞吐量很重要时,例如批量(re-)索引时,花费大量时间刷新和合并小段的效率不是很高.因此,在这些情况下,临时增加 refresh_interval设置,甚至完全禁用自动刷新通常是个好主意.人们总是可以手动刷新,和/或在索引完成时刷新.

Elasticsearch Indexes

“计算机科学中的所有问题都可以通过另一个间接层次来解决.” – 大卫·J·惠勒

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

从本文的这一点开始,当我们单独提及”索引”时,我们指的是Elasticsearch索引.

“分片”是Elasticsearch的基本伸缩单元.当文档被添加到索引中时,它被路由到一个分片.默认情况下,这是基于文档ID的哈希以循环方式完成的.在本系列的第二部分中,我们将更多地研究碎片是如何移动的.然而,重要的是要知道分片的数量是在创建索引时指定的,以后不能更改.Shay早期关于Elasticsearch的演讲很好地介绍了为什么分片实际上是一个完整的Lucene索引,以及它与其他方法相比的各种好处和权衡.

可以通过多种方式自定义哪些Elasticsearch索引以及将搜索请求发送到哪些分片(和副本).通过结合索引模式、索引别名以及文档和搜索路由,可以实现许多不同的分区和数据流策略.我们不会在这里深入探讨,但我们可以推荐 Zachary Tong 关于自定义文档路由的文章和 Shay Banon 关于大数据、搜索和分析的演讲.只是为了给你一些想法,这里有一些例子:

许多数据是基于时间的,例如日志、推文等.通过每天(或每周、每月……)创建索引,我们可以有效地将搜索限制在特定时间范围内——并删除旧数据.请记住,我们无法有效地从现有索引中删除,但删除整个索引的代价很小.
当搜索必须限于某个用户时(例如”搜索您的消息”),将该用户的所有文档路由到同一个分片可能很有用,以减少必须搜索的索引数量.

Transactions

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

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

Elasticsearch有一个”事务日志”,其中附加了要索引的文档.附加到日志文档比构建段成本低得多,因此Elasticsearch可以将文档写入索引到持久的地方 - 除了内存缓冲区,该缓冲区在崩溃时会丢失.您还可以指定编制索引时所需的一致性级别.例如,您可以要求每个副本在索引操作返回之前为文档建立索引.