搜索系统之倒排索引

36 views

在阅读了《这就是搜索引擎》这本书之后,对于倒排索引、在搜索系统中如何建立倒排索引、如何更新倒排索引及如何根据倒排索引进行召回有了基础的认识,写下此篇博客用于总结消化知识。

德彪嘻嘻

1. 什么是倒排索引

倒排索引可以说为检索而设计。在一堆文档中,如何找到包含某个单词的文档集合?最显而易见的办法为建立一个映射,将单词和文档集合之间映射起来,例如<单词,[doc1, doc2, doc3, doc4]>。建立这样的映射关系之后,我们就可直接通过单词找到所有包含该单词的文档。

在现实应用中,倒排索引被拆分成了两个部分,第一个部分为单词词典,第二个部分为倒排列表。单词词典主要保存每个单词和每个单词对应的倒排列表指针,且主要保存在内存当中。倒排列表则主要存储每个文档集合信息信息,不仅有哪些文档文档包含了该单词,还有这个单词在文档中出现的次数(TF)、出现的位置等等。倒排索引主要保存在磁盘等大容量存储设备当中。

倒排索引

单词数量是很多的,如何在词典中迅速找到对应的单词?我们现实生活中的字典通过拼音和偏旁来让我们来快速找到这个字。在倒排索引的字典中,参照拼音和偏旁的方法,我们使用哈希加链表和树形结构来存储我们的字典。

哈希加链表的方式就是将一个单词通过哈希函数哈希到同一个值,然后这个值作为数组的索引。然后对应数组的位置存放的链表中添加一个元素。

哈希加链表存储字典

树形结构的方式就比较多了,比如B+树,但是使用B+树的前提是我们可以对两个单词进行比较,同时这种顺序拥有一定的含义。

如何针对海量的文档,建立倒排索引?

2. 倒排索引如何建立?

倒排索引的建立主要分为这几种方法:两遍文档法、排序法、归并法。

两遍文档法

两遍文档法的思想为:第一次遍历所有文档,建立字典,同时知道每个单词有多少文档包含、整体的文档信息等这些全局信息,利用这些信息初始化指向每个倒排列表的指针,同时也可以初始化倒排列表的存储空间。第二遍扫描,就是解析文档中的信息,然后更新每个单词的倒排索引项。

为啥不直接扫描一次就可以了?原因如下:

  • 文档数量非常非常多,可能你扫描到某个文档,你会发现内存不够了。但是出现了新的单词,这个时候往字典中添加单词就有点麻烦了。
  • 在两遍遍历方法下,字典中单词出现的顺序和文档中单词出现的顺序是存在相似的。在更新每个单词的倒排索引项的时候,cache中通常存储有文档中单词的倒排索引,这样有利于数据的操作。

然而,两遍文档扫描存在如下缺点:

  1. 两遍文档扫描要对所有文档集合进行两次磁盘的IO操作。磁盘操作通常是非常慢的。
  2. 建立索引的过程都在内存中进行。内存通常是有限的。

排序法

排序法作为两遍文档法的升级版本,可以通过一次扫描在固定内存大小下完成索引的建立。排序法主要分为三个过程。

第一步为:在固定大小内存中解析文档获得倒排列表项并构建字典;

在固定大小内存中解析文档获得字典和倒排索引项

第二步:当内存不足时,对倒排列表项根据<单词id、文档id>的顺序进行排序,并写入磁盘中;

排序并写入磁盘

第三步:解析完所有文档之后,合并磁盘中所有存储的数据块,构建成为一个完整的索引。

合并得到完整索引

然而上述方法存在一个缺点:字典在索引构建过程中始终都存在于内存当中。随着文档数量的增多,字典占用空间越来越大,倒排索引项所能拥有的空间就越来越少了。这就会出现一种情况,可能没解析几个倒排索引项,内存就用光了。内存用光了,又要进行一次磁盘操作,效率大大降低。

合并法

合并法在排序法的基础上做了改良,不仅把倒排索引项写入磁盘中,把字典也写入磁盘当中。这样当内存空间使用完之后,就可以一次性清除所有空间了。

不同于排序法需在内存中存储倒排索引项的做法,合并法存储的是一个倒排索引,并且将单词项放在开头。当内存空间满了之后,就将这部分的倒排索引写入磁盘中,合并所有的部分的倒排索引,成为一个全局的倒排索引。

合并法构建索引

3. 如何更新索引?

上面建立索引的过程针对是一个静态的文档集合。如果文档发生了更新和删除?最笨的办法是:针对发生修改的文档中出现的每一个词,找到对应的倒排索引列表进行更新。然而,通常发生了更新的文档通常不止一个,难道每个都要这样操作一遍?

参考考缓存的设计理念,将更新操作进行延后,以保证快速的查询。

我们可以存储一个更新文档的倒排索引集合和删除文档的集合。

当用户需要通过索引召回对应的文档的时候,分别从更新文档的倒排索引集合、删除文档的集合及原来老的索引集合进行召回。

如果更新文档的倒排索引中有,则采用更新文档的倒排索引集合的召回结果。

如果删除文档的集合存在这个文档,则将这个文档在召回结果中删除。然后在一个特定的时机,将更新文档的倒排索引集合更新到老的索引文档中。

上述过程中的合适的时机是什么时候?当更新文档的倒排索引集合和删除文档的集合在内存中放不下的时候,就应该进行更新了。更新一般有四种策略:完全重建策略、再合并策略、原地更新策略及混合策略。

完全重建策略非常粗暴,就是将老文档和新文档进行合并,然后按照建立索引的流程走一遍。注意,此时系统中存在新索引和老索引两套索引?老索引用于在新索引建立期间提供服务,只有新索引全部建立完成之后,才能将老索引删除掉,切到新索引。在实际的系统中,很多的搜索引擎都采用的上述方案。但是在一个分布式系统中,保证各个节点同时切换及新旧两套索引带来的资源利用率问题,是现实系统中需要突破的点。

再合并策略(re-merge)合并的不是文档集合,而是选择合并新增文档的倒排索引(增量索引)和老索引。两者的合并过程有点类似于两个有序链表的合并,一般采用双指针的方式进行合并,最终合并到一个新的索引。

然而,再合并过程中也存在一个缺点。在增量索引和老索引合并到一个新的索引的过程中,一些没有变动的索引也需要从老索引中拷贝到新索引中。因此,会存在一定的性能损耗。

如果在合并过程中我们不需要新索引这个额外的空间,只在老索引上进行操作就好了。原地更新策略可以采用的就是上述思想。

原地更新策略的基本思想为:在索引更新过程中,只更新存在修改的部分。即把增量索引直接追加在老索引对应的位置后面。

然而这里有个问题。在索引存储过程中,两个相邻单词的倒排链表往往是连续存储的,两者紧挨着,不存在任何剩余空间。如果要在一个单词的倒排索引后面追加一些东西,则需要预先保留一些空间才行。这个预留空间为原地更新策略带来了新的问题。

预留空间到底应该多大?固定大小还是动态大小?无论如何,一旦追加的大小超出预留空间,索引迁移必不可少。这个时候,索引迁移带来的磁盘IO损耗也同样不可小觑。

混合策略是上面三种策略的综合,针对不同类型的单词采用不同的策略。我们可以根据倒排列表的长度进行区分,对于长列表单词,由于磁盘IO的损失要比短列表大,我们可以采用原地更新策略(原地更新在老索引追加,磁盘IO损耗小)。对于短列表单词,由于磁盘IO损失一半小,我们可以采用再合并策略。

4. 如何根据倒排索引进行召回?

有了索引,如何根据用户的查询召回对应的文档,下面介绍几种简单的召回方法:一次一单词、一次一文档、跳跃指针。

一次一单词

一个查询一般可以分解成多个单词。一次一单词的策略思想为:每次从索引中拿出一个单词的倒排列表,然后针对倒排列表中的每个文档计算与查询的局部相关性。对所有查询中的单词都按照上述方法处理完之后,将所有文档的局部相关性分值进行合并。整个过程可理解为“矩阵的横向扫描”。

一次一单词

一次一文档

不同于一次一单词,一次一文档的策略思想为:将查询中所有单词的倒排列表取出,然后针对每个文档计算与查询的相关性。整个过程中可理解为“矩阵的纵向扫描”。

一次一文档

跳跃指针

跳跃指针可看作为一次一文档策略的具体实现方法。在现实应用中,用户的查询可以分解为多个单词,这些单词之间逻辑关系通常为“与”的形式。

针对分解单词的倒排列表,我们希望对之进行取交集。我们将倒排列表看作为一个有序的链表(建索引的时候,文档ID是按照升序排序的)。

如何针对多个有序链表取交集?可以利用归并排序的思想,时间复杂度通常为O(m+n)。然而这个实现在现实应用中依然存在很大的性能问题:

  • 倒排项中的文档ID通常是通过差值存储的。因为文档ID通常非常大,我们用文档ID减去第一个文档ID的差值来进行文档ID的存储。使用差值可用一个小的整数存储。而这种差值存储方式为归并排序带来了性能损耗,因为要把倒排列表中所有文档ID的差值转换为真正的ID。
  • 相比于单词的倒排列表,交集部分通常是很小的。但是为了取交集,我们要对一个单词的倒排列表从磁盘中读取,并进行解压缩,有点不划算。其实,我们只需要有交集的那部分数据即可,如果可以进一步缩小范围就好了。

跳跃指针的思想可以参考“跳表”,即针对有序链表建立索引,这个索引可以表示用来描述数据范围。首先将倒排索引进行分块,在每个块的头部插入跳跃指针,这个指针存储块的全局信息,比如<起始文档ID,下一个块的位置>。

跳跃指针

有了跳跃指针,在判断某个文档在不在其他倒排列表中的时候,可以直接精确到块的位置。从而,数据操作的范围大大减少。

不过这里面也有一个tradeoff,块的大小该怎么确定?块越多,数据操作范围越小,磁盘IO损耗及解压缩损耗大大降低,但是跳跃指针跳跃的次数也会大大增加,这是一个额外的控制开销。通常,假定倒排列表的长度为L,块的大小设定为根号L。

5. 总结

本文只是对倒排索引进行了大概的介绍。但是对于文档索引,倒排索引只是基础,还有其他针对不同类型的业务需求的索引。比如多字段索引,短语索引。这些后面的博客再进行总结。

No votes yet.
Please wait...