现在的位置: 首页 > 算法 > 正文

Elasticsearch 的倒排索引是什么

2020年02月21日 算法 ⁄ 共 3749字 ⁄ 字号 评论关闭

  为什么需要倒排索引

  倒排索引,也是索引。

  索引,初衷都是为了快速检索到你要的数据。

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

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

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

  Elasticsearch 的倒排索引,其实就是 Lucene 的倒排索引。

  为什么叫倒排索引

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

  document -> to -> words

  通过文章,获取里面的单词,此谓「正向索引」,forward index.

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

  word -> to -> documents

  于是我们把这种索引,成为inverted index,直译过来,应该叫「反向索引」,国内翻译成「倒排索引」,有点委婉了。

  现在思考一下,如果让你来设计这个可以通过单词,反向找到文章的索引,你会怎么实现?

  倒排索引的内部结构

  首先,在数据生成的时候,比如爬虫爬到一篇文章,这时我们需要对这篇文章进行分析,将文本拆解成一个个单词。

  这个过程很复杂,比如“生存还是死亡”,你要如何让分词器自动将它分解为“生存”、“还是”、“死亡”三个词语,然后把“还是”这个无意义的词语干掉。这里不展开,感兴趣的同学可以查看文末关于「分析器」的链接。

  下次搜索“生存”,就会返回文档ID是 1、2两份文档。

  然而上面这套索引的实现,给小孩子当玩具玩还行,要上生产环境,那还远着。

  想想看,这个世界上那么多单词,中文、英文、日文、韩文 … 你每次搜索一个单词,我都要全局遍历一遍,很明显不行。

  于是有了排序,我们需要对单词进行排序,像 B+ 树一样,可以在页里实现二分查找。

  光排序还不行,你单词都放在磁盘呢,磁盘 IO 慢的不得了,所以 Mysql 特意把索引缓存到了内存。

  你说好,我也学 Mysql 的,放内存,3,2,1,放,哐当,内存爆了。

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

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

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

  Frame Of Reference

  我们来简化下 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):

  Roaring bitmaps

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

  这样就需要根据三个字段,去三棵倒排索引里去查,当然,磁盘里的数据,上一节提到过,用了 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。

  这里补充一下 Roaring bitmaps 和 之前讲的 Frame Of Reference 的关系。

  Frame Of Reference 是压缩数据,减少磁盘占用空间,所以当我们从磁盘取数据时,也需要一个反向的过程,即解压,解压后才有我们上面看到的这样子的文档ID数组:[73, 300, 302, 303, 343, 372] ,接着我们需要对数据进行处理,求交集或者并集,这时候数据是需要放到内存进行处理的,我们有三个这样的数组,这些数组可能很大,而内存空间比磁盘还宝贵,于是需要更强有力的压缩算法,同时还要有利于快速的求交并集,于是有了Roaring Bitmaps 算法。

  另外,Lucene 还会把从磁盘取出来的数据,通过 Roaring bitmaps 处理后,缓存到内存中,Lucene 称之为 filter cache。

  总结

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

  这篇文章讲的虽是 Lucene 如何实现倒排索引,如何精打细算每一块内存、磁盘空间、如何用诡谲的位运算加快处理速度,但往高处思考,再类比一下 Mysql,你就会发现,虽然都是索引,但是实现起来,截然不同。

抱歉!评论已关闭.