图片来自宝途网本文不会重点介绍ES中的分布式技术和相关API的使用，而是着重分享“如何快速检索ES”这个话题。这也是我在学习之前对ES最感兴趣的部分。本文大致包括以下内容：关于搜索：传统关系型数据库与ES的区别搜索引擎原理：倒排索引长啥样（postinglist→termdic→termindex）关于postinglist的一些技巧（FOR,RoaringBitmaps)如何快速进行联合查询？关于搜索，首先想象一个关于搜索的场景。假设我们要搜索一首诗词内容中带有“前”字的古诗。实现传统关系型数据库和ES有什么区别？如果用MySQL这样的RDBMS存储古诗词，我们应该使用这样的SQL查询：selectnamefrompoemswherecontentlike"%before%";这称为顺序扫描法，需要遍历所有记录进行匹配。不仅效率低下，而且在搜索时也不符合我们的预期。例如，我们在搜索“ABCD”等关键词时，通常也希望看到“A”、“AB”、“CD”、“ABC”的搜索结果。于是就有了专业的搜索引擎，比如我们今天的主角ES。搜索引擎的原理搜索引擎的搜索原理简单概括可以分为几个步骤：内容爬取，停用词过滤，比如“的”“了”等一些无用的语气词/连词，内容分词，提取关键词根据关键词创建倒排索引用户输入关键词进行搜索这里我们引入一个概念，这也是我们今天要分析的重点倒排索引。也是ES的核心知识点。了解ES的应该知道，ES可以说是Lucene的一个封装，其中倒排索引的实现是通过lucene的jar包提供的API实现的，所以提到倒排索引的内容下面其实就是lucene里面的所有内容。倒排索引首先，我们不能忘记前面提到的搜索要求。首先我们看看建立倒排索引后我们上面的查询需求会是什么样子。这样，我们一输入“前”，就可以借助倒排索引直接定位到符合查询条件的古诗词。当然，这只是一个大白话，用来描述倒排索引的简单工作原理。在ES中，倒排索引到底是什么，它是如何存储的等等，这些就是倒排索引的本质。①几个概念在进入下面之前，先描述几个前置概念。term：关键字是我自己的说法。在ES中，关键字称为term。贴子列表：还是用上面的例子，{景野寺，望庐山飞瀑}是词条“before”对应的列表。在ES中，这些被描述为包含特定术语的所有id文档的集合。由于整数可以被高效压缩，因此整数最适合作为文档的唯一标识放在postings列表中。ES会处理这些存储的文档，并将它们转换成一个唯一的整数id。再说说这个id的范围。ES在存储数据时，会将数据存储在每个分片中的不同段中。这是一个比分片更小的分片单元，这些分片会周期性地合并。每个segment最多会存储2^31个文档，每个文档都会分配一个唯一的id，范围从0到(2^31)-1。相关名词在ES官方文档中都有描述，出处可参考以下参考资料。②索引的内部结构上面介绍的倒排索引只是一个很粗略的模型。距离真正用于实际生产还差得很远。在实际生产场景中，比如最常用的ES的日志分析，日志内容切分后可以得到多少term？那么如何在海量词条中快速查询出对应的词条呢？遍历一次显然是不现实的。术语词典：所以有一个术语词典。为了快速找到词条，ES将所有词条按顺序排列，采用二分法查找。是不是很眼熟？这不就是MySQL的索引方式吗，直接用B+树建立索引字典指向索引数据。termindex：但是问题又来了，你觉得TermDictionary应该放在哪里呢？它必须放在内存中，对吗？磁盘io太慢了。就像MySQL的索引是存放在内存中一样。但是，如果将整个术语词典放入内存中，会发生什么情况呢？内存爆了……别忘了，ES默认会索引所有的文本字段，这必然会消耗大量的内存。为此，ES对索引进行了索引深度优化。在保证执行效率的同时，尽量减少占用的内存空间。所以有一个术语索引。Termindex：从数据结构上分类，可以看做是“Trie树”，也就是我们常说的字典树。这是一个专门处理字符串匹配的数据结构，用于解决在一组字符串中快速找到某个字符串的问题。这棵树并没有包含所有的词条，它包含了词条的一些前缀（这也是字典树的使用场景，常用前缀）。术语索引可以用来快速定位到术语词典中的某个偏移量，然后从这个位置开始依次查找。就像右图一样。怎么样，像我们查英文字典一样，定位第一个S开头的词，或者定位第一个Sh开头的词，然后依次查询？Lucene这里也做了两个优化，一个termdictionary在磁盘上是分块存储的，一个block用一个commonprefix压缩。例如，如果所有单词都以Ab开头，则可以省略Ab。二是在FST（finitestatetransducer）的数据结构中，termindex存放在内存中。FST有两个优点：占用空间小：通过复用词典中的单词前缀和后缀，压缩了存储空间。查询速度快：O(len(str))查询时间复杂度。FST的理论比较复杂，本文不再赘述，进一步阅读：https://www.shenyanchao.cn/blog/2018/12/04/lucene-fst/OK，现在我们可以搞定什么是lucene了倒排索引看起来就是这样。关于贴子列表的一些技巧在实际使用中，贴子列表还需要解决几个痛点：如果不压缩贴子列表，会占用大量的磁盘空间。联合查询下，如何快速找到交集和并集。关于怎么压缩，可能有人会觉得没必要，“postinglist不是只存documentid吗？还需要压缩吗？”，但是如果postinglist有几百万个docid，压缩就很麻烦了必要的。比如按朝代查询古诗词，至于为什么要交并并，ES是专门用来查的，肯定有很多联合查询的需求（AND，OR）。根据以上思路，我们先来说说如何压缩。①CompressedFrameofReference：在lucene中，postingslists要求是有序的整数数组。这具有能够通过增量编码进行压缩的好处。比如有一个id列表[73,300,302,332,343,372]，转换成每个id相对于前一个id的增量值（第一个id的前一个id默认为0，增量是它自己）列表是[73,227,2,30,11,29]。在这个新列表中，所有的id都小于255，所以每个id只需要一个字节的存储空间。事实上，ES会做的更细：它将所有文档分成很多块，每个块正好包含256个文档，然后对每个文档单独进行增量编码。计算在这个块中存储所有文档需要的最大位数来保存每个id，并将这个位数作为头信息（header）放在每个块的前面。这种技术称为参考框架。上图也是ES官博的例子（假设每个block只有3个文件，而不是256个）。FOR的步骤可以概括为：经过最后的位压缩后，整数数组的类型从固定大小（8、16、32、64位）的4种扩展到[1-64]位的64种全部的。通过以上方法，可以大大节省发布列表的空间消耗，提高查询性能。但是为了提高filter过滤查询的性能，ES做了更多的工作，那就是缓存。RoaringBitmaps(forfiltercache)：在ES中，过滤器可以用来优化查询。过滤查询只处理文档是否匹配，不涉及文档评分操作。可以缓存查询结果。对于过滤器查询，es提供了一个特殊的缓存，叫做filtercache，用来存放过滤器得到的结果集。缓存过滤器不需要太多内存，它只是保留一种信息，即哪些文档与过滤器匹配。同时可以被其他查询复用，大大提高了查询的性能。我们上面提到的FrameOfReference压缩算法对于postings列表效果很好，但它不适用于需要存储在内存中的过滤器缓存。过滤器缓存将存储经常使用的数据。过滤器的缓存是为了加快处理效率，对压缩算法有更高的要求。对于这种类型的帖子列表，ES使用了不同的压缩方法。所以让我们一步一步来。首先我们知道postings列表是一个压缩空间的Integer数组。假设有这样一个数组，我们压缩的第一个想法是什么？它是用位表示的，每个文档对应其中一个，也就是我们常说的位图，位图。它通常用作数据库、查询引擎和搜索引擎中的索引，并且位操作（例如与交集或并集）可以并行化以提高效率。但是，位图有一个明显的缺点。无论业务中实际使用了多少元素，其占用的内存空间都是不变的。那不适合稀疏存储。业界对于稀疏位图也有很多成熟的压缩方案，lucene用的就是roaringbitmap。这里简单介绍一下压缩过程：将docid拆分为高16位和低16位。聚合高位（以高位为key，value为所有高位相同的低位数组），根据低位数据的多少（长度），使用不同的容器（数据结构）存储从不同的高位聚合的低位数组的数量是不同的）。len<4096ArrayContainer直接存储值len>=4096BitmapContainer使用位图存储分割线的来源：最大总值是2^16=65536。假设位图方式存储需要65536bit=8kb，直接存储value的方式，一个value是2个字节，4K总共需要2byte*4K=8kb。因此，当总值小于4k时，使用直接存值的方式更节省空间。空间压缩主要体现在：高位聚合（假设数据中有100w个高位值，原来需要100w2byte，现在只需要12byte）低位压缩的缺点是bit的速度与原始位图相比，操作将受到影响。这是权衡。平衡的艺术。②联合查询说完压缩，再来说说联合查询。让我们从一个简单的开始。如果查询有filtercache，则直接使用filtercache进行计算，即使用位图进行AND或OR计算。如果queryfilter没有被缓存，那么使用skiplist的方法遍历磁盘上的postingslist。以上是三个发帖列表。我们现在需要将它们与AND的关系结合起来，以获得发布列表的交集。先选出最短的postinglist，将另外两个postinglist一一查看是否存在，最后得到交集结果。在遍历过程中可以跳过一些元素。比如我们遍历到绿色13的时候，可以跳过蓝色的3，因为3比13小。使用skiplist也会带来另外一个好处。还记得前面说过的吗，贴子列表是以FOR编码保存在磁盘上的。将所有的文档分成很多块，每个块恰好包含256个文档，然后对每个文档进行增量编码，计算存储这个块中所有文档所需的最大位数来保存每个id，并把该位作为块头信息（header）放在每个块的前面。因为这个FOR的编码是有解压成本的。使用skiplist，除了跳过遍历的开销之外，还跳过了解压这些压缩块的过程，从而节省了cpu。小结下面做一个技术总结：①为了快速定位目标文档，ES使用了倒排索引技术来优化搜索速度。虽然空间消耗比较大，但是搜索性能有明显提升。②为了能够在海量的terms中快速定位到某个term，同时节省内存的使用，减少磁盘io的读取。Lucene采用“termindex→termdictionary→postingslist”的倒排索引结构，通过FST压缩到内存中，进一步提高搜索效率。③为了减少postings列表的磁盘消耗，lucene使用了FOR（FrameofReference）技术进行压缩，压缩效果非常明显。④ES的过滤语句采用RoaringBitmap技术缓存搜索结果，保证高频过滤查询速度，减少存储空间消耗。⑤联合查询时，如果有filtercache，则直接利用位图的原生特性进行快速交并并取联合查询结果，否则使用skiplist对多个postings列表进行交并并，跳过traversalcost并节省解压部分数据的cpu开销。Elasticsearch的索引思想将磁盘的内容尽可能的移动到内存中，减少从磁盘随机读取的次数（同时也利用了磁盘的顺序读取特性），结合各种压缩算法，使用记忆以极其严厉的态度。所以在使用Elasticsearch做索引的时候需要注意：不需要做索引的字段一定要定义清楚，因为默认是自动建索引的。同理，对于String类型的字段，不需要解析的字段也需要明确定义，因为默认也是解析的。选择一个正规的ID很重要。随机性太大的ID（比如Java的UUID）不利于查询。最后，技术选择总是伴随着对业务场景的考虑。每个数据库都有自己需要解决的问题（或擅长领域），对应于自己的数据结构，以及不同的使用场景和数据结构，就需要使用不同的索引来达到最大化和加速查询的目的。这篇文章讲了Lucene如何实现倒排索引，如何仔细计算每一块内存和磁盘空间，以及如何使用奇葩的位运算来加速处理。但是站在更高的层次去想，再和MySQL对比一下，你会发现虽然都是索引，但是在实现上是完全不同的。从广义上讲，B树索引是写优化的索引结构。当我们不需要支持快速更新时，可以使用预排序的方式来换取更小的存储空间、更快的检索速度等好处，代价是更新慢，就像ES一样。作者：Richard_Yi编辑：陶家龙来源：juejin.cn/post/6889020742366920712
