Elasticsearch 倒排索引

目录

一、简介

二、为什么叫倒排索引

三、倒排索引内部结构

倒排列表（Postings List）

增量编码压缩（Frame Of Reference）

位图压缩算法（Roaring Bitmap）

---

一、简介

Elasticsearch 是建立在全文搜索引擎库 Lucene 基础上的搜索引擎，它隐藏了 Lucene 的复杂性，取而代之的提供一套简单一致的 RESTful API，不过掩盖不了它底层也是 Lucene 的事实。Elasticsearch 的倒排索引，其实就是 Lucene 的倒排索引。 

二、为什么叫倒排索引

在没有搜索引擎时，我们是直接输入一个网址，然后获取网站内容，这时我们的行为是：

document -> to -> words

通过文章，获取里面的单词，这便是正向索引，即 forward index

后来，我们希望能够输入一个单词，找到含有这个单词，或者和这个单词有关系的文章：

word -> to -> documents

于是我们把这种索引，称为倒排索引，即 inverted index

三、倒排索引内部结构

Lucene 的倒排索引主要是由以下三部分组成：

先来看一个实际例子来大概认识下倒排索引的这三个概念，假设在 es 里有如下的数据：

                                                                     

es 中每一行就是一个document，每个document es都会生成一个docid，建立倒排索引后的样子就是：

                                                                     

文档中的每个字段都会建立自己的倒排索引，18，20这些叫做 term，而 [1,3] 就是 posting list，posting list 是一个 int 数组，存储了所有符合某个 term 的文档 id，那么什么是 term dictionary 和 term index 呢？

我们回到需要倒排索引的场景上来，首先，我们肯定需要先生成数据，比如爬虫爬到一篇文章，这时我们需要对这篇文章进行分析，将文本拆分成一个个单词。这个过程很复杂，比如“四月是你的谎言”，好一点的中文分词器应该能自动将它分解为“四月”、“是”、“你的”、“谎言”，然后还把 “是”、“你的” 这两个无意义的词语去掉，这应该是个神奇的步骤，逻辑应该都在分析器中，之后有兴趣再看吧...

好了，将单词分解完之后，这时把这两个词语及它对应的文档id存下来：

接着爬虫继续爬，又爬到一个含有“谎言”的文档，于是索引变成：

下次搜索“谎言”，就会返回文档id是1和2的两份文档。然而这种实现需要进行全局遍历才能找到对应的 term，但是这世界上有那么多单词，全局遍历肯定不现实。于是有了排序，这样我们就可以用二分查找的方式，比全局遍历更快地找出目标 term，这就是  term dictionary （term dictionary 在磁盘上是以分 block 的方式保存的，一个block内部利用公共前缀压缩，比如都是Ab开头的单词就可以把Ab省去，这样term dictionary可以比b+tree更节约磁盘空间）。

光排序还不行，单词都是在磁盘的，而磁盘的随机读操作仍然是非常昂贵的（一次random access大概需要10ms的时间），所以尽量少的读磁盘，就有必要把一些数据缓存到内存（就像 mysql 的B+树），要是 es 也学 mysql，那么多单词放进去内存立马就炸了，于是就有了 term index（字典树），term index 有点像一本字典的大的章节表，比如：

A开头的term ……………. Xxx页
 
C开头的term ……………. Xxx页
 
S开头的term ……………. Xxx页

当然 term 未必都是英文字符，可以是任意的byte数组，因此实际的 term index 是一颗 trie 树，也叫字典树或前缀树，即这颗树不会包含所有的 term，它包含的是term的一些前缀。通过 term index 可以快速地定位到term dictionary 的某个 offset，然后从这个位置再往后顺序查找。再加上一些压缩技术（term index在内存中是以FST<Finite State Transducers>形式保存的，其特点是非常节省内存） term index 的尺寸可以只有所有 term 的尺寸的几十分之一，使得用内存缓存整个term index变成可能。下图例子是一颗包含 "A", "to", "tea", "ted", "ten", "i", "in", 和 "inn" 的 trie 树：

 

三者整体效果图大概如下：

 

现在我们可以回答“为什么Elasticsearch/Lucene检索可以比mysql快了"，mysql只有term dictionary这一层，是以b+tree排序的方式存储在磁盘上的，检索一个term需要若干次的random access的磁盘操作，而Lucene在term dictionary的基础上添加了term index来加速检索，term index以树的形式缓存在内存中，从term index查到对应的term dictionary的block位置之后，再去磁盘上找term，大大减少了磁盘的random access次数。

倒排列表（Postings List）

搜索引擎一项很重要的工作就是高效的压缩和快速的解压缩一系列有序的整数列表。我们都知道，Elasticsearch 基于 Lucene，一个 Lucene 索引 我们在 Elasticsearch 称作 分片，并且引入了 按段搜索 的概念。

新的文档首先被添加到内存索引缓存中，然后写入到一个基于磁盘的段。在每个 segment 内文档都会有一个 0 到文档个数之间的标识符（最高值 2^31 -1），称之为 doc ID。这在概念上类似于数组中的索引：它本身不做存储，但足以识别每个 item 数据。

Segments 按顺序存储有关文档的数据，在一个 Segments 中 doc ID 是 文档的索引。因此，segment 中的第一个文档的 doc ID 为 0，第二个为 1，等等。直到最后一个文档，其 doc ID 等于 segment 中文档的总数减 1。

倒排索引需要将 terms 映射到包含该单词 （term） 的doc ID列表，这样的映射列表就称之为 倒排列表 （Postings List），一般很多文档都会包含该单词，每个文档都会记录文档编码（doc ID），单词在这个文档中出现的次数（TF）及单词在文档中哪些位置出现过等信息，这样一个与文档相关的信息被称作 倒排索引项（Posting）

虽然倒排列表只是一个用来存文档id的数组，但是在设计时遇到的问题可不少：

• 如何压缩以节省磁盘空间
• 如何快速求交并集

增量编码压缩（Frame Of Reference）

针对倒排列表，Lucene 采用一种增量编码的方式将一系列 ID 进行压缩存储，自 Lucene 4.1 以来一直在使用。

假设有这样一个数组：

[73, 300, 302, 332, 343, 372]

如何尽可能的压缩？

在 Lucene 中，由于数据是按segment存储的，且最大值为 2^31 -1 ，所以如果不进行任何处理，每个元素占用四个字节（byte），对应上面数组即占用24 byte。

压缩，就是尽可能降低每个数据占用的空间，同时又能让信息不失真，能够还原回来。在实际的搜索引擎系统中，并不存储倒排索引项中的实际文档编号（Doc ID），而是代之以文档编号差值（D-Gap）。文档编号差值是倒排列表中相邻的两个倒排索引项文档编号的差值，一般在索引构建过程中，可以保证倒排列表中后面出现的文档编号大于之前出现的文档编号，所以文档编号差值总是大于 0 的整数。

Step 1：Delta-encode —— 增量编码

增量编码就是从第二个数开始每个数存储与前一个 id 的差值，即只记录元素与元素之间的增量，于是数组变成了：

[73, 227, 2, 30, 11, 29]

之所以要对文档编号进行差值计算，主要原因是为了更好地对数据进行压缩，原始文档编号一般都是大数值，通过差值计算，就有效地将大数值转换为了小数值，而这有助于增加数据的压缩率。

Step 2：Split into blocks —— 分割成块

Lucene里每个块是 256 个文档 ID，这样可以保证每个块，增量编码后，每个元素都不会超过 256（1 byte），为了方便演示，我们假设每个块是 3 个文档 ID：

[73, 227, 2], [30, 11, 29]

Step 3：Bit packing —— 位压缩

计算每组 3 个数中最大的那个数需要占用 bit 位数，比如  [30, 11, 29]  中最大数 30 最小需要 5 个 bit 位存储，这样 11、29 也用 5 个 bit 位存储，这样才占用 15 个 bit，不到 2 个字节，压缩效果很好。

以上三个步骤，共同组成了一项编码技术，Frame Of Reference（FOR），如下面原理图所示，这是一个区块大小为 3 的示例（实际上是 256）：

 

位图压缩算法（Roaring Bitmap）

在实际查询时，如果给定查询过滤条件 age=18 ，其过程就是先从term index找到18在term dictionary的大概位置，然后再从term dictionary里精确地找到18这个term，然后得到一个posting list或者一个指向posting list位置的指针，然后再查询 gender=女 的过程也是类似的，最后得出 age=18 AND gender=女 就是把两个 posting list 在内存中做一个交集（由于posting list在磁盘中是压缩过的，因此需要先解压回原始 id 数组）。

而这个求交集的过程可不容易，也就是 Posting List 的第二个痛点 —— 如何快速求交并集

我们把 Lucene 遇到的问题，简化成一道算法题。假设有下面三个数组：

[64, 300, 303, 343]
 
[73, 300, 302, 303, 343, 372]
 
[303, 311, 333, 343]

求他们的交集。

这里有四种方式可以进行计算：

• Integer 数组
• Skip List 
• Bitmap
• Roaring Bitmaps

而 Lucene 就是采用了第四种方式，但是我们需要先了解 Bitmap 的方式，假设有这样的一个 Posting list：

[3,1,4,7,8]

如果使用 Integer 数组遍历求交集的方式，大概需要 20 byte存储，在文档id一多的时候，要把这么多数据从磁盘解压后丢到内存，内存肯定撑不住。

因此旧版本(5.0 之前)的 Lucene 采用 Bitmap 方式来解决，对应上面 Posting list ，对应的 Bitmap 就是：

[0,1,0,1,1,0,0,1,1]

非常直观，用 0/1 表示某个值是否存在，比如 8 这个值就对应第 8 位，对应的 bit 值是 1，这样用一个字节就可以代表 8 个文档 id。但这样的压缩方式仍然不够高效，Bitmap 自身就有压缩的特点，其用一个 byte 就可以代表 8 个文档，所以 100 万个文档只需要 12.5 万个 byte。而 Bitmap 的缺点是存储空间随着文档个数线性增长，例如下面数组：

[0, 65535]

如果用 Bitmap 表示：

[1,0,0,0,….(超级多个0),…,0,0,1]

你需要 65536 个 bit，也就是 65536/8 = 8192 bytes，而用 Integer 数组，你只需要 2 * 4 bytes = 8 bytes，可以看出在文档个数少的时候使用 Integer 数组是更加节省内存的。

而 Lucene 使用的这个数据结构叫做 Roaring Bitmap ，简称 RBM

RBM 的主要思想并不复杂，简单来讲，有如下三条：

1. 我们将 32-bit 的范围 ([0, n)) 划分为 2^16 个桶，每一个桶有一个 Container 来存放一个数值的低16位；
2. 在存储和查询数值的时候，我们将一个数值 k 划分为高 16 位(k % 2^16)和低 16 位(k mod 2^16)，取高 16 位找到对应的桶，然后在低 16 位存放在相应的 Container 中；
3. 容器的话， RBM 使用两种容器结构： Array Container 和 Bitmap Container。Array Container 存放稀疏的数据，Bitmap Container 存放稠密的数据。即，若一个 Container 里面的 Integer 数量小于 4096，就用 Short 类型的有序数组来存储值。若大于 4096，就用 Bitmap 来存储值。

为什么这里用的 4096 这个阈值？因为一个 Integer 的低 16 位是 2Byte，因此对应到 Arrary Container 中的话就是 2Byte * 4096 = 8KB；同样，对于 Bitmap Container 来讲，2^16 个 bit 也相当于是 8KB。

然后，基于前面提到的两种 Container，在两个 Container 之间的 Union (bitwise OR) 或者 Intersection (bitwise AND) 操作又会出现下面三种场景：

• Bitmap vs Bitmap
• Bitmap vs Array
• Array vs Array

RBM 提供了相应的算法来高效地实现这些操作。