自底向上分析Elasticsearch

时间:2022-09-12 23:57:34

原文博客链接
    这个系列文章里,我们将用一个新的视角去剖析Elasticsearch。我们先从一些底部的抽象层开始,逐步上移至用户视角。期间会学习Elasticsearch内部的数据结构和行为。

介绍

    这篇文章的目的为了更好的理解Elasticsearch,Lucene等搜索引擎是如果工作。开车的时候,你只需要把车子启动起来,踩踩踏板就OK,但“老司机”还会对汽车的基本原理有所了解。对于搜索引擎同样如此。Elasticsearch提供了简单易用的API,通过这些API能满足大多数需要。但想最大限度的利用Elasticsearch,了解其底层的算法和数据结构很有必要。

    我们从最基本的倒排索引开始。倒排索引是个非常有用的数据结构,并且简洁易懂。Lucene是一个高度优化的倒排索引实现,但这里不会深入到Lucene的实现细节,先来看倒排索引是如何构建和使用的。这个过程会影响搜索和索引文档

    将倒排索引作为抽象层的底部,我们会讨论:

  • 一个简单的搜索是如何进行的
  • 什么类型的搜索能够(或不能够)有效的执行,以及为什么会这样。使用倒排索引时,我们会将问题转化为字符串前缀匹配问题
  • 为什么文本处理很重要
  • 索引是如何在segment重构建,以及如何影响搜索和更新
  • Lucene索引的组成
  • Elasticsearch中的分片和索引

    从这个点看,我们将学习到在单个Elasticsearch节点中搜索和索引时发生了什么。在这个系列的第二篇文章中会介绍Elasticsearch如何处理分布式管理。

倒排索引和词项

自底向上分析Elasticsearch

    我们有三个简单的文档:”Winter is coming.”, “Ours is the fury.”和 “The choice is yours.”。经过一些简单的文本处理(字母小写化,去除标点符号和切词),我们可以组织一个上图所示的倒排索引。

    倒排索引将词项映射到包含该词项的文档(如果可能的话,还指明词项在文档中出现的位置)。因为词项存储在单词词典中(dictionary),所以我们可以很快的找到该词项,进而找到单词在文档中是否出现的信息(postings)。这些信息存储在一个相反的结构中——正排索引。正排索引记录了和与词项关联的文档。

    一个简单的多词项搜索过程:首先在单词词典查找所有词项,以及词项对应的出现信息,然后对出现文档集合取交集(对于and索索)或者并集(对于or搜索)操作,得到最后的结果文档集合。复杂的搜索也涉及到的过程也基本相同。

    因此一个索引词项是一个搜索单元,我们生成的词项决定哪些搜索能够(或不能够)高效的进行。例如,就上面的词项词典,我们可以很快找到所有”c”开头的词项。但是我们不能很快找到所有包含”ours”的词项。为了找到所有包含”ours”的词项,我们不得不遍历所有词项,并且还会找到”yours”这种词项。除非索引很小,否则这类操作会带来很高的消耗。就复杂度而言,通过前缀查找词项的复杂度 (O(log(n))) ,而从任意位置开始的子串查找复杂度 (O(n))

    换句话说,通过前缀串,我们可以非常有效的找到需要的词项。当我们有倒排索引时,我们希望所有的查找都是前缀串问题。这里有几个例子能做出这种转换,有一些比较简单,最后一个近乎魔法。

  • 为了找到所有以”tastic”结尾的词,我们可以索引词项的反转(例如”fantastic” → “citsatnaf”),然后对每个词项词典中的词作反转后的前缀查找
  • 子串查询通常包含词项切割,例如”yours”被切割成”^yo”,”you”,”our”,”urs”,”rs$”。所以当我们的查找”our”或”urs”的时候,能找到”your”的出现信息
  • 对于有合成词的语言,例如Norwegian和German,我们需要“分解”词项。例如”Donaudampfschiff”分解成{“donau”, “dampf”, “schiff”}。
  • 地理坐标被转化为”地理hash“,例如(60.6384, 6.5017)被转化为”u4u8gyykk”,字符串越长越精确
  • 音标匹配对人名非常有效,像Metaphone的算法将”Smith”转化成{“SM0”, “XMT”}
  • 处理数值型和时间戳数据时,Lucene自动生成几个不同精度的词项,组成前缀存储类型,所以范围搜索非常高效。简单来讲,数字123被存储成”1”个百,”12”个十和”123”。至此,搜索所有[100,199]变成了查找所有”1”个百的词项。这和查询以”1”开头的词项不同,因为这样的搜索会包含例如”1234”
  • 为了做类似”Did you mean”这样的搜索并且找到相似的拼写,在遍历词项字典的时候,编辑距离也需要建立。这个操作非常复杂,好在一切都在Lucene里被完成

    对文本处理的深入理解是后续文章的基础,我们还强调了为什么文本处理对于生成索引词项如此重要:为了更高效的搜索。

创建索引

    创建索引时,有几件事情需要事先考虑:搜索速度,索引密度,索引文档的速度,以及索引文档或更新文档之后到这些变化可以被搜索到的时间。

    搜索速度和索引密度相互关联:搜索的索引越小,需要处理的数据越少,就有更适应于内存操作。而压缩会操作会在索引文档阶段产生消耗一定的时间消耗。

    为了压缩化索引大小,有多种压缩技术可以选择。例如为了存储词项和文档的关系(前文的postings,它可能会非常大),Lucene采取查分编码([42, 100, 666]被存储成[42, 58, 566]),变长字节存储(小数字可以用一个字节存储)等方式。

    缩小&压缩数据存储意味着牺牲快速更新的能力。事实上,Lucene的索引文件都不可变文件,因此并没有更新操作。这与B树这种能够进行更新操作和制定更新量的数据结构不同。

    删除也和通常想的不同。当删除索引中的文档时,只是在bitmap中更新了一下,标志这个文档被删除了。而索引结构本身并没有任何更新。

    相应的更新一个索引文档需要先删除,然后重新插入更新后的文档。因此更新文档比插入文档的性能消耗要高。在Lucene中存储频繁变化的值并不合适,因为这里没有就地更新。

    当新加入文档时(可能是通过更新),索引的变化会先缓存到内存中。最终才被完整的刷到磁盘。需要注意的是,这里的“刷新”是Lucene意义上的刷新,Elasticsearch的刷新操作包括Lucene的提交和其他操作,这些操作会被记录到事务日志中。

    刷新产生的时机取决于几个因素:变化被可见的速度,用于缓存的内存大小,I/O饱和度等。通常来说,对于索引文档的速度而言,只要你的I/O系统能跟得上刷新,缓存越大越好。下一节我们会更加详细的描述。

    这些被写入的文件组成索引段。

索引段(index segment)

    Lucene索引有一个或多个不可变的索引段组成,索引段本身可以看作一个”迷你索引“。搜索时,Lucene在每个索引段上做搜索,过滤掉删除的文档,然后合并所有索引段的结果。当索引段数量变多时,也就存在了更多的冗余。为了把索引段的数量控制在一个方便管理的范围,Lucene会根据合并策略把索引段合并成新索引段。Lucene大咖Michael McCandless对此有索引合并有一个很好的视频解释。在索引段合并的时候,被标记删除的文档才真正被删除。所以有时候新加入文档反而得到一个更小的索引:因为合并而瘦身。

    Elasticsearch和Lucene通常在处理索引段合并时做的很好。Elasticsearch的合并策略可以通过修改合并设置来改变。你也可以使用optimize-API来强制合并。

    索引段被写入到磁盘之前,修改都缓存在内存。以前(Lucene版本小于2.3)每个新增加的文档在内存中都有一个自己的微型索引段,只有在写入磁盘时才合并。现在,通过DocumentsWriter,内存中可以将多篇文档做成一个较大的索引段。在Lucene 4里,每一个线程里都有一个DocumentsWriter,通过兵法写入的方式提高索引文档的性能。(以前索引文档必须等到写入磁盘结束)

    当一个新的索引段产生的时候(不管是新写入还是合并),必定引起某些缓存失效,这影响搜索性能。缓存(例如字段缓存和过滤器缓存)和索引段绑定,一个索引段有几个不同的缓存。Elasticsearch有个warmer-API。必要的缓存可以在新索引段可供查询前准备好。

    最常见的因为Elasticsearch引起的写入磁盘可能由于连续索引文档而产生的刷新。这个操作默认每秒一次。当新的索引段被写入磁盘,他们就能被搜索。尽管flush没有commit如此消耗性能(因为flush不用等待写入确认),但它会创建新的索引段,使某些缓存失效,并且可能触发一次合并。

    如果索引文档的吞吐很重要,例如批量索引文档,花费太多时间flush以及合并小索引段会变得很浪费。这种情况下,暂时把refresh_interval设置得大一点,或者禁止自动refresh会是个好主意。当索引文档结束时,手动refresh总是可行。

Elasticsearch索引

“All problems in computer science can be solved by another level of indirection.” – David J. Wheeler

    Elasticsearch的索引由一个或多个分片组成,每一个分片有零至多个副本。这些分片都是单独的Lucene索引。也就是说,每一个Elasticsearch索引由多个Lucene索引组成,而每一个Lucene索引又由多个索引段组成。当搜索一个Elasticsearch索引时,会在所有的分片上执行,也就是在所有的索引段上执行,最后把结果合并。对于搜索多个Elasticsearch索引也是一样。事实上,搜索两个只有一个分片的Elasticsearch索引和搜索一个有两个分片的索引几乎一样。两者都搜索了两个Lucene索引。

    从这个点开始,后面所有的“索引”都是指Elasticsearch的索引。

    分片是Elasticsearch中最基本的容量缩放单位。当文档被添加到索引里,文档会被路由到一个分片。默认情况下,会根据文档id的hash值做round-robin算法。在这个系列的第二篇文章里,我们会看到更多分片的运作机制。要注意的是,分片数在创建索引时已经确定并且之后不能修改。在一次Shay的Elasticsearch分享中很好的解释了为什么一个分片就是一个完整的Lucene索引,解释了这种方式的优点,并且说明了和别的方式比较时所作的权衡。

    Elasticsearch的搜索非常灵活,能够指定索引和分片。索引名模板,索引别名和搜索路由,很多数据流策略能够使用。这里我们不会展开去讲,在此推荐Zachary Tong的文章《customizing document routing》和Shay Banon的分享《big data, search and analytics》。一下的例子可能会有一点启发:

  • 基于时间的数据,例如日志,每天(或每周,每月)创建一个索引,我们能有效的限制搜索时间范围,并且很容易删除旧数据。虽然从索引里删除文档很麻烦,但是删除整个索引成本却很低。
  • 当必须限定某个用户的搜索时,把那个用户的所有文档路由到同一个分片会非常有用,这样会减少搜索的分片。

事务

    尽管Lucene有事务的概念,但Elasticsearch却没有。所有的Elasticsearch操作被加到同一个时间线,这个时间线不需要贯穿所有节点,因为flush操作依赖各个节点的时机。

    管理分布式系统中不同节点,不同分片中的索引段,缓存非常困难。与其去做这个管理,不如怎么把系统做更快。

    Elasticsearch有事务日志(transaction log),用于追加记录被索引的文档。追加一个文档比建立索引段要简单得多,所以Elasticsearch能将文档持久化,同时还写到内存缓存中。你可以在索引文档时候指定一致性级别。例如可以指定每个副本都索引好文档之后才返回索引文档操作。

总结

    总结起来,Lucene在建立,更新,搜索单个索引时有这么几个重要的属性需要注意

  • 我们如何处理文本决定我们可以怎么搜索。合适的文本分析很重要。
  • 索引现在内存中建立,然后被flush到磁盘中的索引段。
  • 索引段不可变,删除文档只是被标记删除
  • 一个索引由很多索引段组成,搜索操作在每个索引段上执行,然后合并结果
  • 索引段的合并时不时就发生,依赖时机
  • 每个索引段都有字段缓存和过滤器缓存
  • Elasticsearch没有事务

在这个系列的下一篇文章里,我们会看看搜索和索引文档操作如何在集群中执行。

参考链接:
[1]https://www.elastic.co/blog/found-elasticsearch-from-the-bottom-up
[2]http://lucene.apache.org/core/4_4_0/core/overview-summary.html
[3]http://blog.trifork.com/2011/04/01/gimme-all-resources-you-have-i-can-use-them/
[4]http://blog.mikemccandless.com/2011/02/visualizing-lucenes-segment-merges.html
[5]https://www.elastic.co/blog/customizing-your-document-routing