Lucene索引原理

发表于 | 分类于 ， | 评论数：

简单介绍下Lucene

Es 与 Lucene

说道es，我们首先就会想到什么？ 分词? 倒排索引? 搜索？

大部分情况下我们都知道，项目中如果需要分词+倒排索引的场景就使用es就好了，那么倒排索引到底是什么？他有什么作用？它的原理？为什么选择倒排索引？它与传统数据库的区别？

接下来为了更加深入的了解es的索引，简单分析下它的索引引擎-lucene。

为什么使用倒排索引

倒排索引、倒排索引，既然是索引。首先，其首要目的肯定是为了加快查询速度。

对于每种数据库类产品都有自己要解决的问题，对应的就有自己的数据存储结构，而不同的使用场景和数据存储结构，需要用不同的索引，才能起到最大化加快查询的目的。

对 Mysql 来说，是 B+ 树，对 Elasticsearch/Lucene 来说，是倒排索引。

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

简单介绍下Lucene

Lucene 是一个基于 Java 的全文信息检索工具包，elasticsearch就是使用lucene的索引和搜索能力。

其是一个，开源的全文检索引擎工具包，但它不是一个完整的全文检索引擎，而是一个全文检索引擎的架构，提供了完整的查询引擎和索引引擎

Lucene的数据类型

Lucene中包含了四种基本数据类型，分别是：

Index：索引，由很多的Document组成。
Document：由很多的Field组成，是Index和Search的最小单位。
Field：由很多的Term组成，包括Field Name和Field Value。
Term：由很多的字节组成。一般将Text类型的Field Value分词之后的每个最小单元叫做Term。

Lucene 的查询

Lucene查询流程

在查询的过程中，需要一个DirectoryReader和QueryParser，其中:

  • DirectoryReader负责读取写入的文本数据，并进行解析
  • QueryParser主要用来解析你的查询语句，例如你想查 “A and B”，lucene内部会有机制解析出是term A和term B的交集查询。

之后执行具体的Search过程。

Lucene 索引查询过程

倒排链介绍

这里举一个网上的例子

docid name age
1 Alice 18
2 Alice 20
3 Alice 21
4 Alan 21
5 Alan 18

在lucene中为了查询name=XXX的这样一个条件，会建立基于name的倒排链。以上面的数据为例，倒排链如下：

姓名的倒排链数据:

Alice [1,2,3]
Alan [4,5]

年龄的倒排链数据如下:

18 [1,5]
20 [2]
21 [3,4]

这里面建立倒排链的单位，例如 Alice、Alan、18、20 这些就是Lucene中的 term。

所以倒排的本质就是基于term的反向列表，可以方便多维度的各种值的查询

但是虽然我们有了term的倒排链，但是在查询中如何快速的拿到这个倒排链呢？

Lucene获取倒排链的方法

在lucene里面引入了 term dictionary 的概念，也就是term的字典。

在term dictionary中寻找term的方法: -

  1. term字典实现了对term进行排序，那么通过某种算法(例如二分法)就可以定为这个term所在的地址。这样的复杂度是logN
    1. 在term很多，内存放不下的时候，效率还是需要进一步提升。可以用一个hashmap，当有一个term进入，hash继续查找倒排链。这里hashmap的方式可以看做是term dictionary的一个index。
  2. 从lucene4开始，为了方便实现rangequery或者前缀，后缀等复杂的查询语句，lucene使用FST来存储term字典，下面就详细介绍下FST的存储结构。

FST介绍(有穷状态装换器) - term index

我们对“cat”、 “deep”、 “do”、 “dog” 、“dogs”这5个单词进行插入构建FST（注：必须已排序,否则无法生成最小fst）

1）插入“cat”

插入cat，每个字母形成一条边，其中t边指向终点。

image-20211210151435594

2）插入“deep”

与前一个单词“cat”进行最大前缀匹配，发现没有匹配则直接插入，P边指向终点。

image-20211210161502774

3）插入“do”

与前一个单词“deep”进行最大前缀匹配，发现是d，则在d边后增加新边o，o边指向终点。

image-20211210161512093

4）插入“dog”

与前一个单词“do”进行最大前缀匹配，发现是do，则在o边后增加新边g，g边指向终点。

image-20211210161554176

5）插入“dogs”

与前一个单词“dog”进行最大前缀匹配，发现是dog，则在g后增加新边s，s边指向终点。

image-20211210161604461

最终我们得到了如上一个有向无环图。利用该结构可以很方便的进行查询，如给定一个term “dog”，我们可以通过上述结构很方便的查询存不存在。

从FST的结构上可以看出，在单term查询上可能相比hashmap并没有明显的优势，甚至会慢一些。但是在范围、前缀搜索以及压缩率上都有明显的优势。

在通过FST定位到倒排链后，有一件事情需要做，就是倒排链的合并。因为查询条件可能不止一个，例如之前的倒排联我们想找name=”alan” and age=”18”的列表。lucene是如何实现倒排链的合并呢。这里就需要看一下倒排链存储的数据结构

FST详细介绍：

  1. https://blog.csdn.net/zx2011302580235/article/details/88594342
  2. https://www.shenyanchao.cn/blog/2018/12/04/lucene-fst/

FST压缩率一般在3倍~20倍之间，相对于TreeMap/HashMap的膨胀3倍，内存节省就有9倍到60倍！

Skip List

为了在倒排链中，能够快速查找docid，lucene采用了SkipList这一数据结构。SkipList有以下几个特征：

  1. 元素排序的，对应到我们的倒排链，lucene是按照docid进行排序，从小到大。
  2. 跳跃有一个固定的间隔，这个是需要建立SkipList的时候指定好，例如下图以间隔是3
  3. SkipList的层次，这个是指整个SkipList有几层
image-20211210172937297

有了这个SkipList以后比如我们要查找docid=12，原来可能需要一个个扫原始链表，1，2，3，5，7，8，10，12。有了SkipList以后先访问第一层看到是然后大于12，进入第0层走到3，8，发现15大于12，然后进入原链表的8继续向下经过10和12。

Lucene倒排结构

有了FST和SkipList的介绍以后，我们大体上可以画一个下面的图来说明lucene是如何实现整个倒排结构的：

image-20211210173127175

有了这张图，我们可以理解为什么基于lucene可以快速进行倒排链的查找和docid查找，下面就来看一下有了这些后如何进行倒排链合并返回最后的结果。

BKD-TREE(数值类型索引结构)

在lucene中如果想做范围查找，根据上面的FST模型可以看出来，需要遍历FST找到包含这个range的一个点然后进入对应的倒排链，然后进行求并集操作。但是如果是数值类型，比如是浮点数，那么潜在的term可能会非常多，这样查询起来效率会很低。

所以为了支持高效的数值类或者多维度查询，lucene引入类BKDTree。

BKDTree是基于KDTree，对数据进行按照维度划分建立一棵[二叉树]确保树两边节点数目平衡。在一维的场景下，KDTree就会退化成一个二叉搜索树，在二叉搜索树中如果我们想查找一个区间，O(logN)的复杂度就会访问到叶子结点得到对应的倒排链。如下图所示：

image-20211210180532967

如果是[多维]，kdtree的建立流程会发生一些变化。

比如我们以二维为例，建立过程如下：

  1. 对每个维度的数据进行排序；
  2. 确定切分维度，这里以维度数据差值作为依据，进行维度选取(维度数据极差越大，优先选取)。
  3. 选择这个维度最中间的点，进行切分。
  4. 递归进行步骤1，2，我们可以设置一个阈值，点的数目少于多少后就不再切分，直到所有的点都切分好停止。

下图是一个建立例子：

image-20211210180632128

BKD-TREE的建立过程参考： https://www.amazingkoala.com.cn/Lucene/gongjulei/2019/0422/52.html

倒排链合并过程

倒排链合并

假如我们的查询条件是name = “Alice”，那么按照之前的介绍，首先在term字典中定位是否存在这个term，如果存在的话进入这个term的倒排链，并根据参数设定返回分页返回结果即可。

假如我们有多个条件，例如我们需要按名字或者年龄单独查询，也需要进行组合 name = “Alice” and age = “18” / name = “Alice” or age = “18” 的查询，在lucene这多个倒排链是怎么合并呢？

与运算合并 布尔运算的与运算，要求所有的查询关键词（查询条件）共同命中候选文档，即候选文档同时出现了所有查询条件的关键词。

假设有ABCD四个term需要进行与/或合并：

与运算合并

  1. 首先在倒排链中取出最短一条链命名为Lead1（图中C）。
  2. 接着取出次短倒排链的命名Lead2，除此之外称为Others。
  3. 然后遍历Lead1的每个DocId1的过程中，在Lead2中寻找大于等于文档id的一个docId2。假如docId2不等于docId1，继续便利Lead1，否则到others中校验判断是否存在，如果存在返回结果。
image-20211210174448524

整个合并步骤我可以发现，如果某个链很短，会大幅减少比对次数，并且由于SkipList结构的存在，在某个倒排中定位某个docid的速度会比较快不需要一个个遍历。可以很快的返回最终的结果。从倒排的定位，查询，合并整个流程组成了lucene的查询过程，和传统数据库的索引相比，lucene合并过程中的优化减少了读取数据的IO，倒排合并的灵活性也解决了传统索引较难支持多条件查询的问题。

或运算合并

布尔运算的或运算，要求将每个查询条件的结果集进行并集运算。每个查询的结果集倒排链。

  1. 初始化每个Lead的游标cur。
  2. 每一轮获取每个Lead中对应游标位置的数值Leadn[cur]。
  3. 返回最小Leadn[cur]数值，并根据最小值的出现次数计算命中率；
  4. 对获取到最小值的Lead游标进行cur++，重复执行2、3，直到所有Lead遍历完成；
image-20211210175332365

每一轮都会得到一条存在当前DocID的倒排链数组，然后计算查询条件命中率(不是最终的score )，即拥有当前DocID的Postings占所有原子查询条件的比例。

组合条件各种场景下的合并

了解了Lucene的数据结构和基本查询原理，我们知道：

  1. 对单个词条进行查询，Lucene会读取该词条的倒排链，倒排链中是一个有序的docId列表。
  2. 对字符串范围/前缀/通配符查询，Lucene会从FST中获取到符合条件的所有Term，然后就可以根据这些Term再查找倒排链，找到符合条件的doc。
  3. 对数字类型进行范围查找，Lucene会通过BKD-Tree找到符合条件的docId集合，但这个集合中的docId并非有序的。

现在的问题是，如果给一个组合查询条件，Lucene怎么对各个单条件的结果进行组合，得到最终结果。简化的问题就是如何求两个集合的交集和并集。

  1. 对N个倒排链求交集

上面Lucene原理分析的文章中讲过，N个倒排链求交集，可以采用skipList，有效的跳过无效的doc。

  1. 对N个倒排链求并集

处理方式一：仍然保留多个有序列表，多个有序列表的队首构成一个优先队列(最小堆)，这样后续可以对整个并集进行iterator(堆顶的队首出堆，队列里下一个docID入堆)，也可以通过skipList的方式向后跳跃(各个子列表分别通过skipList跳)。这种方式适合倒排链数量比较少(N比较小)的场景。

处理方式二：倒排链如果比较多(N比较大)，采用方式一就不够划算，这时候可以直接把结果合并成一个有序的docID数组。

处理方式三：方式二中，直接保存原始的docID，如果docID非常多，很消耗内存，所以当doc数量超过一定值时(32位docID在BitSet中只需要一个bit，BitSet的大小取决于segments里的doc总数，所以可以根据doc总数和当前doc数估算是否BitSet更加划算)，会采用构造BitSet的方式，非常节约内存，而且BitSet可以非常高效的取交/并集。

  1. BKD-Tree的结果怎么跟其他结果合并

通过BKD-Tree查找到的docID是无序的，所以要么先转成有序的docID数组，或者构造BitSet，然后再与其他结果合并。

如何实现返回结果进行排序聚合

通过之前介绍可以看出lucene通过倒排的存储模型实现term的搜索，那对于有时候我们需要拿到另一个属性的值进行聚合，或者希望返回结果按照另一个属性进行排序。

  • 在lucene4之前需要把结果全部拿到再读取原文进行排序，这样效率较低，还比较占用内存，为了加速lucene实现了fieldcache，把读过的field放进内存中。这样可以减少重复的IO，但是也会带来新的问题，就是占用较多内存。
  • 新版本的lucene中引入了DocValues，DocValues是一个基于docid的列式存储。当我们拿到一系列的docid后，进行排序就可以使用这个列式存储，结合一个堆排序进行。当然额外的列式存储会占用额外的空间，lucene在建索引的时候可以自行选择是否需要DocValue存储和哪些字段需要存储。

默认情况下，Lucene会按照Score排序，即算分后的分数值，如果指定了其他的Sort字段，就会按照指定的字段排序。那么，排序会非常影响性能吗？

首先，排序并不会对所有命中的doc进行排序，而是构造一个堆(n个数取前k大问题)，保证前(Offset+Size)个数的doc是有序的，所以排序的性能取决于(Size+Offset)和命中的文档数，另外就是读取docValues的开销。因为(Size+Offset)并不会太大，而且docValues的读取性能很高，所以排序并不会非常的影响性能。

各种查询结构总结：

  1. FST：保存term字典索引，可以在FST上实现单Term、Term范围、Term前缀和通配符查询等。
  2. Doc-dictionary 的倒排链：保存了每个term对应的docId的列表，采用skipList的结构保存，用于快速跳跃。
  3. BKD-Tree：BKD-Tree是一种保存多维空间点的数据结构，用于数值类型(包括空间点)的快速查找。
  4. DocValues：基于docId的列式存储，由于列式存储的特点，可以有效提升排序聚合的性能。

倒排链的压缩与逻辑运算

原生的倒排链有两个痛点：

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

数据压缩FOR

我们来简化下 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）：

image-20211213164250949

Roaring bitmaps

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

ES会缓存频率比较高的filter查询，其中的原理也比较简单，即生成(fitler, segment)和id列表的映射，但是和倒排索引不同，我们只把常用的filter缓存下来而倒排索引是保存所有的，并且filter缓存应该足够快，不然直接查询不就可以了。ES直接把缓存的filter放到内存里面，映射的posting list放入磁盘中。

ES在filter缓存使用的压缩方式和倒排索引的压缩方式并不相同，filter缓存使用了roaring bitmap的数据结构，在查询的时候相对于上面的Frame of Reference方式CPU消耗要小，查询效率更高，代价就是需要的存储空间（磁盘）更多。

在 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.

image-20211213164629753

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

roaring bitmap 数据结构

image-20211222114227314

每个RoaringBitmap中都包含一个RoaringArray，名字叫highLowContainer。highLowContainer存储了RoaringBitmap中的全部数据。

这个名字意味着，会将32位的整形（int）拆分成高16位和低16位两部分（两个short）来处理。

RoaringArray的数据结构很简单，核心为以下三个成员：

1
2
3
short[] keys;
Container[] values;
int size;

每个32位的整形，高16位会被作为key存储到short[] keys中，低16位则被看做value，存储到Container[] values中的某个Container中。keys和values通过下标一一对应。size则标示了当前包含的key-value pair的数量，即keys和values中有效数据的数量。

keys数组永远保持有序，方便二分查找。

三种Container

下面介绍到的是RoaringBitmap的核心，三种Container。

通过上面的介绍我们知道，每个32位整形的高16位已经作为key存储在RoaringArray中了，那么Container只需要处理低16位的数据。

ArrayContainer

1
2
3
static final int DEFAULT_MAX_SIZE = 4096

short[] content;

结构很简单，只有一个short[] content，将16位value直接存储。

short[] content始终保持有序，方便使用二分查找，且不会存储重复数值。

因为这种Container存储数据没有任何压缩，因此只适合存储少量数据。

ArrayContainer占用的空间大小与存储的数据量为线性关系，每个short为2字节，因此存储了N个数据的ArrayContainer占用空间大致为2N字节。存储一个数据占用2字节，存储4096个数据占用8kb。

根据源码可以看出，常量DEFAULT_MAX_SIZE值为4096，当容量超过这个值的时候会将当前Container替换为BitmapContainer。

BitmapContainer

1
final long[] bitmap;

这种Container使用long[]存储位图数据。我们知道，每个Container处理16位整形的数据，也就是0~65535，因此根据位图的原理，需要65536个比特来存储数据，每个比特位用1来表示有，0来表示无。每个long有64位，因此需要1024个long来提供65536个比特。

因此，每个BitmapContainer在构建时就会初始化长度为1024的long[]。这就意味着，不管一个BitmapContainer中只存储了1个数据还是存储了65536个数据，占用的空间都是同样的8kb。

RunContainer

1
2
3
private short[] valueslength;

int nbrruns = 0;

RunContainer中的Run指的是行程长度压缩算法(Run Length Encoding)，对连续数据有比较好的压缩效果。

它的原理是，对于连续出现的数字，只记录初始数字和后续数量。即：

对于数列11，它会压缩为11,0；
对于数列11,12,13,14,15，它会压缩为11,4；
对于数列11,12,13,14,15,21,22，它会压缩为11,4,21,1；
源码中的 short[] valueslength 中存储的就是压缩后的数据。

这种压缩算法的性能和数据的连续性（紧凑性）关系极为密切，对于连续的100个short，它能从200字节压缩为4字节，但对于完全不连续的100个short，编码完之后反而会从200字节变为400字节。

如果要分析RunContainer的容量，我们可以做下面两种极端的假设：

最好情况，即只存在一个数据或只存在一串连续数字，那么只会存储2个short，占用4字节
最坏情况，0~65535的范围内填充所有的奇数位（或所有偶数位），需要存储65536个short，128kb

RoaringBitmap的优化策略

创建时：

  • 创建包含单个值的Container时，选用ArrayContainer
  • 创建包含一串连续值的Container时，比较ArrayContainer和RunContainer，选取空间占用较少的
    转换：

针对ArrayContainer：

  • 如果插入值后容量超过4096，则自动转换为BitmapContainer。因此正常使用的情况下不会出现容量超过4096的ArrayContainer。
  • 调用runOptimize()方法时，会比较和RunContainer的空间占用大小，选择是否转换为RunContainer。

针对BitmapContainer：

  • 如果删除某值后容量低至4096，则会自动转换为ArrayContainer。因此正常使用的情况下不会出现容量小于4096的BitmapContainer。
  • 调用runOptimize()方法时，会比较和RunContainer的空间占用大小，选择是否转换为RunContainer。

针对RunContainer：

  • 只有在调用runOptimize()方法才会发生转换，会分别和ArrayContainer、BitmapContainer比较空间占用大小，然后选择是否转换
刘小恺(Kyle) wechat
如有疑问可联系博主