聊聊 Elasticsearch 的倒排索引
以下文章来源于柳树的絮叨叨 ,作者靠发型吃饭的柳树
为什么需要倒排索引
倒排索引,也是索引。
索引,初衷都是为了快速检索到你要的数据。
每种数据库都有自己要解决的问题(或者说擅长的领域),对应的就有自己的数据结构,而不同的使用场景和数据结构,需要用不同的索引,才能起到最大化加快查询的目的。
对 Mysql 来说,是 B+ 树,对 Elasticsearch/Lucene 来说,是倒排索引。
Elasticsearch 是建立在全文搜索引擎库 Lucene 基础上的搜索引擎,它隐藏了 Lucene 的复杂性,取而代之的提供一套简单一致的 RESTful API,不过掩盖不了它底层也是 Lucene 的事实。
Elasticsearch 的倒排索引,其实就是 Lucene 的倒排索引。
为什么叫倒排索引
在没有搜索引擎时,我们是直接输入一个网址,然后获取网站内容,这时我们的行为是:
document -> to -> words
通过文章,获取里面的单词,此谓「正向索引」,forward index.
后来,我们希望能够输入一个单词,找到含有这个单词,或者和这个单词有关系的文章:
word -> to -> documents
于是我们把这种索引,成为inverted index,直译过来,应该叫「反向索引」,国内翻译成「倒排索引」,有点委婉了。
现在思考一下,如果让你来设计这个可以通过单词,反向找到文章的索引,你会怎么实现?
关于 Elasticsearch 这类「搜索引擎」要解决的问题、它和传统关系型数据库的区别等等,可以看我之前写的文章:为什么需要 Elasticsearch(文末有链接)
倒排索引的内部结构
首先,在数据生成的时候,比如爬虫爬到一篇文章,这时我们需要对这篇文章进行分析,将文本拆解成一个个单词。
这个过程很复杂,比如“生存还是死亡”,你要如何让分词器自动将它分解为“生存”、“还是”、“死亡”三个词语,然后把“还是”这个无意义的词语干掉。这里不展开,感兴趣的同学可以查看文末关于「分析器」的链接。
接着,把这两个词语以及它对应的文档id存下来:
word documentId
生存 1
死亡 1
接着爬虫继续爬,又爬到一个含有“生存”的文档,于是索引变成:
word documentId
生存 1,2
死亡 1
下次搜索“生存”,就会返回文档ID是 1、2两份文档。
然而上面这套索引的实现,给小孩子当玩具玩还行,要上生产环境,那还远着。
想想看,这个世界上那么多单词,中文、英文、日文、韩文 … 你每次搜索一个单词,我都要全局遍历一遍,很明显不行。
于是有了排序,我们需要对单词进行排序,像 B+ 树一样,可以在页里实现二分查找。
光排序还不行,你单词都放在磁盘呢,磁盘 IO 慢的不得了,所以 Mysql 特意把索引缓存到了内存。
你说好,我也学 Mysql 的,放内存,3,2,1,放,哐当,内存爆了。
哪本字典,会把所有单词都贴在目录里的?
所以,上图:
imageLucene 的倒排索,增加了最左边的一层「字典树」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^32-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):
imageRoaring 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.
image这里补充一下 Roaring bitmaps 和 之前讲的 Frame Of Reference 的关系。
Frame Of Reference 是压缩数据,减少磁盘占用空间,所以当我们从磁盘取数据时,也需要一个反向的过程,即解压,解压后才有我们上面看到的这样子的文档ID数组:[73, 300, 302, 303, 343, 372] ,接着我们需要对数据进行处理,求交集或者并集,这时候数据是需要放到内存进行处理的,我们有三个这样的数组,这些数组可能很大,而内存空间比磁盘还宝贵,于是需要更强有力的压缩算法,同时还要有利于快速的求交并集,于是有了Roaring Bitmaps 算法。
另外,Lucene 还会把从磁盘取出来的数据,通过 Roaring bitmaps 处理后,缓存到内存中,Lucene 称之为 filter cache.
升华与总结
文章的最后,如果来一段话总结(zhuang)升华(bi)一下,这篇文章就会得高分。
有什么总结,可以拔高这篇文章的高度呢?
首先,你会发现,很多业务上、技术上要解决的问题,最后都可以抽象为一道算法题,复杂问题简单化。
呃,这个“华”,升的还不够。
另一个具有高度的“华”,其实在开头已经讲出来了:
每种数据库都有自己要解决的问题(或者说擅长的领域),对应的就有自己的数据结构,而不同的使用场景和数据结构,需要用不同的索引,才能起到最大化加快查询的目的。
这篇文章讲的虽是 Lucene 如何实现倒排索引,如何精打细算每一块内存、磁盘空间、如何用诡谲的位运算加快处理速度,但往高处思考,再类比一下 Mysql,你就会发现,虽然都是索引,但是实现起来,截然不同。
这个往细讲,又是一篇文章:如此不同,如此成功 —— B+ 树索引 vs 倒排索引
留个作业吧
知识要融合起来看才有意思。
来,放大招了,两个问题:
-
Lucene 为什么不用 b+ 树来搜索数据?
-
Mysql 为什么不用 倒排索引来检索数据?
附上两张图:
imageMysql 的 B+树索引
image