Elasticsearch倒排索引底层数据结构

秒速五厘米 2023-10-03 10:41 1阅读 0赞

### 为什么需要倒排索引 ###

每种数据库都有自己要解决的问题（或者说擅长的领域），对应的就有自己的数据结构，而不同的使用场景和数据结构，需要用不同的索引，才能起到最大化加快查询的目的。

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

### 倒排索引的内部结构 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NTcwNjA3_size_16_color_FFFFFF_t_70_pic_center]  
Lucene 的倒排索，增加了最左边的一层「字典树」term index，它不存储所有的单词，只存储单词前缀，通过字典树找到单词所在的块，也就是单词的大概位置，再在块里二分查找，找到对应的单词，再找到单词对应的文档列表。

当然，内存寸土寸金，能省则省，所以 Lucene 还用了 FST（Finite State Transducers）对它进一步压缩。

FST 是什么？这里就不展开了，这次重点想聊的，是最右边的 Posting List 的，别看它只是存一个文档 ID 数组，但是它在设计时，遇到的问题可不少。

#### Frame Of Reference ####

原生的 Posting List 有两个痛点：

*  如何压缩以节省磁盘空间
 *  如何快速求交并集（intersections and unions）

先来聊聊压缩。

我们来简化下 Lucene 要面对的问题，假设有这样一个数组：

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

如何把它进行尽可能的压缩？

Lucene 里，数据是按 Segment 存储的，每个 Segment 最多存 65536 个文档 ID， 所以文档 ID 的范围，从 0 到 2^16-1，所以如果不进行任何处理，那么每个元素都会占用 2 bytes ，对应上面的数组，就是 6 \* 2 = 12 bytes.

怎么压缩呢？

**压缩，就是尽可能降低每个数据占用的空间，同时又能让信息不失真，能够还原回来。**

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

我们只记录元素与元素之间的增量，于是数组变成了：

\[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 —— 按需分配空间**

对于第一个块，\[73, 227, 2\]，最大元素是227，需要 8 bits，好，那我给你这个块的每个元素，都分配 8 bits的空间。

但是对于第二个块，\[30, 11, 29\]，最大的元素才30，只需要 5 bits，那我就给你每个元素，只分配 5 bits 的空间，足矣。

这一步，可以说是把吝啬发挥到极致，精打细算，按需分配。

以上三个步骤，共同组成了一项编码技术，Frame Of Reference（FOR）：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NTcwNjA3_size_16_color_FFFFFF_t_70_pic_center 1]

#### Roaring bitmaps ####

接着来聊聊 Posting List 的第二个痛点 —— 如何快速求交并集（intersections and unions）。

在 Lucene 中查询，通常不只有一个查询条件，比如我们想搜索：

*  含有“生存”相关词语的文档
 *  文档发布时间在最近一个月
 *  文档发布者是平台的特约作者

这样就需要根据三个字段，去三棵倒排索引里去查，当然，磁盘里的数据，上一节提到过，用了 FOR 进行压缩，所以我们要把数据进行反向处理，即解压，才能还原成原始的文档 ID，然后把这三个文档 ID 数组在内存中做一个交集。

> 即使没有多条件查询， Lucene 也需要频繁求并集，因为 Lucene 是分片存储的。

同样，我们把 Lucene 遇到的问题，简化成一道算法题。

假设有下面三个数组：

\[64, 300, 303, 343\]

\[73, 300, 302, 303, 343, 372\]

\[303, 311, 333, 343\]

求它们的交集。

**Option 1: Integer 数组**

直接用原始的文档 ID ，可能你会说，那就逐个数组遍历一遍吧，遍历完就知道交集是什么了。

其实对于有序的数组，用跳表（skip table）可以更高效，这里就不展开了，因为不管是从性能，还是空间上考虑，Integer 数组都不靠谱，假设有100M 个文档 ID，每个文档 ID 占 2 bytes，那已经是 200 MB，而这些数据是要放到内存中进行处理的，把这么大量的数据，从磁盘解压后丢到内存，内存肯定撑不住。

**Option 2: Bitmap**

假设有这样一个数组：

\[3,6,7,10\]

那么我们可以这样来表示：

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

看出来了么，对，我们用 0 表示角标对应的数字不存在，用 1 表示存在。

这样带来了两个好处：

*  节省空间：既然我们只需要0和1，那每个文档 ID 就只需要 1 bit，还是假设有 100M 个文档，那只需要 100M bits = 100M \* 1/8 bytes = 12.5 MB，比之前用 Integer 数组 的 200 MB，优秀太多。
 *  运算更快：0 和 1，天然就适合进行位运算，求交集，「与」一下，求并集，「或」一下，一切都回归到计算机的起点。

**Option 3: Roaring Bitmaps**

细心的你可能发现了，bitmap 有个硬伤，就是不管你有多少个文档，你占用的空间都是一样的，之前说过，Lucene Posting List 的每个 Segement 最多放 65536 个文档ID，举一个极端的例子，有一个数组，里面只有两个文档 ID：

\[0, 65535\]

用 Bitmap，要怎么表示？

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

你需要 65536 个 bit，也就是 65536/8 = 8192 bytes，而用 Integer 数组，你只需要 2 \* 2 bytes = 4 bytes

呵呵，死板的 bitmap。可见在文档数量不多的时候，使用 Integer 数组更加节省内存。

我们来算一下临界值，很简单，无论文档数量多少，bitmap都需要 8192 bytes，而 Integer 数组则和文档数量成线性相关，每个文档 ID 占 2 bytes，所以：

8192 / 2 = 4096

当文档数量少于 4096 时，用 Integer 数组，否则，用 bitmap。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NTcwNjA3_size_16_color_FFFFFF_t_70_pic_center 2]

### 补充 ###

这里补充一下 Roaring bitmaps 和 之前讲的 Frame Of Reference 的关系。  
Frame Of Reference 是压缩数据，减少磁盘占用空间，所以当我们从磁盘取数据时，也需要一个反向的过程，即解压，解压后才有我们上面看到的这样子的文档ID数组：\[73, 300, 302, 303, 343, 372\] ，接着我们需要对数据进行处理，求交集或者并集，这时候数据是需要放到内存进行处理的，我们有三个这样的数组，这些数组可能很大，而内存空间比磁盘还宝贵，于是需要更强有力的压缩算法，同时还要有利于快速的求交并集，于是有了Roaring Bitmaps 算法。  
另外，Lucene 还会把从磁盘取出来的数据，通过 Roaring bitmaps 处理后，缓存到内存中，Lucene 称之为 filter cache。

### Lucene 为什么不用 b+ 树来搜索数据？ ###

**Mysql 为什么不用 倒排索引来检索数据？**

b+树主要设计目的是减少搜索时访问磁盘的次数，而Lucene等搜索引擎设计的时候，追求的目标是倒排压缩率&倒排解压速度&倒排Bool运算速度。取倒排到内存运算的时候，是连续读取，时间开销和倒排的大小有关系，所以并不适合用b+数。

同理Mysql等数据库使用索引的目的是快速定位某一行数据，若使用倒排这种线性化的数据结构存储数据，其查找的时候访问磁盘的次数会远大于使用b+的数据库。

一句话，现有的pc架构 &业务需求决定了什么时候使用什么数据结构。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NTcwNjA3_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20210711111855766.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NTcwNjA3,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NTcwNjA3_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20210711112114493.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NTcwNjA3,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NTcwNjA3_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/2021071111235643.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NTcwNjA3,size_16,color_FFFFFF,t_70#pic_center