欢迎光临本站!

索引系统-涉及储存规模的一些计算

来源:技术探讨    更新时间:2019-12-12 11:05:55    编辑:老王    浏览:176

  前面提到对于索引目前100亿中文网页进行倒排索引需要TB级的存储空间这么大规模的数据如何生成?在生成后如何存储?存储后如何支持高效的检索?这一连串的问题将在本节解答。

  正排表与倒排表的合并


  下载系统将抓取网页存放在网页库中,分析系统在分析后得到网页对象发送给索引系统,因此索引不停地得到这样的网页对象。由于网页对象在分析系统中进行了分词计算,最终分析的结果发往索引系统。

  在索引系统中,通过计算不难得到如图5-10所示的正排表在实际操作中,正排表不写入文件,而是保存在内存中。可以理解为内存中存储的正排索引,是正排索引的一种具体表现形式,同理,倒排表也是内存中存储的倒排索引,也是倒排索引的一种具体表现形式。

索引系统-涉及储存规模的一些计算

  如图5-12所示,T1是文档Docx的一个词汇。在左边的词典中找到T1的位置,然后通过其 Doclist位置域存放的 DocList位置信息找到记录表。并将文档编号( DocId)在文档命中的次数( HIts),以及命中的位置列表( HitList)作为倒排表中的记录表中的一个记录。可以认为正排表和倒排表合并的过程,就是正排表中的数据追加倒排表的数据过程。追加后,正排表并不保留。

  而倒排表在内存中存储一定的记录后,成批顺序地写入磁盘,成为临时倒排文件(本章约定,在提到正排表时,表示其存放在内存中;而特指倒排文件时,表示其存放在磁盘中),如图5-13所示。

索引系统-涉及储存规模的一些计算

  众所周知,由于磁盘的存储特性,所以很难在较大文件的中间追加数据。追加数据就不得不进行大量的数据移动,这种开销是极大的。回到这个例子中来,如图5-13所示的临时倒排文件中无法再追加有关T1的记录。

  综上所述,生成倒排文件之前,倒排表(图5-12)由于存放在内存中,因此可以任意追加数据。在顺序写入磁盘成为倒排文件后,倒排文件不再变化。但由于不断有新的数据需要进行索引,所以这样的临时倒排文件数量不可避免地还会不断增加。在导入全部需要作索引的数据后,索引系统会有多个这样的临时倒排文件,不妨假设共有64个这样的临时倒排文件。

  出于性能上的考虑,在一次检索时只需要读取一个倒排文件即可得到全部与检索词相关的索引信息。而不是依次读取全部64个临时倒排文件,然后进行结果组合。因此必须将这64个临时倒排文件归并成一个更大的倒排文件,称为“最终倒排文件”,其大小略小于64个临时倒排文件之和。因为在这64个临时倒排文件中分别保留了词典信息,所以这部分冗余的数据在归并成最终倒排文件后只需要保留一份词典即可。

  在具体实现上,还有一种合并方法,简单说来就是将一个正排表(包含多个 DocId的记录)通过对索引词排序的方法,然后次性或者分批次地写入倒排表中在第七节中会提到这个方法,我们这里先通过一个例子理解这个方法。首先正排表的结构需要进行调整,如图5-14所示。

索引系统-涉及储存规模的一些计算

  这里的正排表和前面介绍的稍有不同,可以看到LId被冗余地存放。

  在内存中保留一块这样的区域存放正排表,每增加一个需要索引的文档,就在正排表中追加一条记录。当追加足够多的记录后,正排表足够大,并符合批量做倒排表的条件后,按照关键词编号( WordId)进行一次稳定排序(稳定排序可以参考有关数据结构的书籍,例如归并排序就是一种稳定排序),得到如图5-15所示的排序后的正排表,这里认为T1<T2<T3。

索引系统-涉及储存规模的一些计算

  在图5-15中,全部正排表记录按照 WordId排序。由于采用稳定的排序,所以LId的顺序没有被破坏,图中T2关键词对应的Lld依然是1,2,3。由于在倒排表中 WordId是顺序存放的,因此排序后的正排表可以依序逐个写入倒排表中,如图5-16所示

索引系统-涉及储存规模的一些计算

  通过估计,每个临时倒排文件的大小大约为100MB,因此甚至可以不需要写入倒排表,而直接顺序写入磁盘中的临时倒排文件。这样就形成了内存中存放正排表,磁盘中放临时倒排文件的结果。

  多个临时倒排文件的归并


  首先考虑两个临时倒排文件的归并通过前面数据规模估计,我们知道全部索引大小为TB量级的数据,后面将介绍倒排文件如何进行分布式存储。存储的节点数目控制在百这个数量级上,因此全部索引大小分布在100个索引结点上,平均每个索引结点大约需要存放10GB的倒排文件(降两个数量级)如果每个索引结点存放64个临时倒排文件,这样每个临时倒排文件约10MB(降两个数量级),64个100MB大小的临时倒排文件最终归并成一个10GB大小的最终倒排文件是十分有挑战性的。每个临时倒排文件内部字典中词汇的编号是有序的,每个词汇对应的记录表( posting list)中的 DocId是有序的,每个 HitList中也是有序的,因此归并后依然要保持这种有序性。我们将这种归并过程笼统地称为“归并排序”,很显然这种规模的归并排序在内存中无法完成,下面介绍两种解决这个问题的方法。

  (1)拉链法( Zipper)和二路归并。

  (2)拉链法和多路归并。

  无论是两路归并还是多路归并,拉链法都是必需的。我们首先考察拉链法和二路归并的组合,对于两个较大的文件进行归并排序,不可能将两个文件同时读入到内存中后进行排序。因此可以读取一部分归并,将结果以文件的形式写入磁盘,然后继续读取两个待归并文件的一部分。周而复始,直到读完其一种的某个文件,另一个文件顺序写入结果文件。因此归并的方法如下。

  (1)从头开始读取两个临时倒排文件的一小部分(例如每次读取10MB)

  (2)分别对 Docld进行解压,将压缩后的差分序列还原成原始的差分序列。

  (3)两个按照Docd有序的列表进行归并。

  (4)归并的结果进行压缩。

  (5)写入归并后的临时倒排文件1&2中

  以上方法如图5-17所示。

索引系统-涉及储存规模的一些计算

  这里首先解压临时倒排文件1和临时倒排文件2的两块数据(只解压 DocId,不解压 HitList的部分),分别解压后得到解压后的块1和解压后的块2。因为Docd有序,因此归并可在线性时间内完成(参考有关数据结构的书籍中关于两个有序表归并的内容,这里不再展开)归并后的倒排表中 DocId依然有序,接下来还需要采用 Variable Byte Coding编码方式对 Docld进行压缩最后写入结果倒排文件中(如图5-17的倒排文件1&2)中。

  这种拉链的方法采用的思路是处理大文件( Big File)的一种通用思路,即每次仅取出大文件的一部分在内存中进行计算。计算结束后存储计算结果,并释放内存。继续读取文件的下一部分到内存、计算、存储计算结果并释放内存,周而复始直到处理全部数据。

  64个这样的临时倒排文件进行归并需要多少趟这样的两两归并呢?第1趟,64个100MB的临时倒排文件两两归并得到32个200MB的临时倒排文件;第2趟,32个200MB的倒排文件两两归并,得到16个400MB的临时倒排文件,直到最后剩下两个3200MB大小的临时倒排文件两两归并得到1个64GB大小的最终倒排文件,这样整个归并的过程结束。每一趟归并结束后,归并段的个数少一半。

  一般情况下,m个初始归并段采用k路归并,则归并趟数为图片.png。如果64个初始归并段采用2路归并,则需要6趟图片.png由于每趟都不可避免的将全部文件换入内存和换出磁盘的过程,生成一个最终倒排文件的过程中需要产生大量的临时文件。大量的内存和磁盘数据的换入换出,所以整个索引制作的瓶颈主要在这里。通过下面这个例子来直观地认识归并的趟数对索引的巨大影响,如图5-18所示。

索引系统-涉及储存规模的一些计算

  图中假定有4个临时倒排文件,并且为100MB,在第1块和第2块进行归井时,需要读取的磁盘量为200MB,写入量也为200MB(块1&2的大小为200MB)因此第1趟的归并(第1块与第2块归并,第3块与第4块归并)共计需要的磁盘IO数量(读写量)为800MB。不难计算,第2趟归并的磁盘读写量也必然是800MB。实际上从宏观上看,每次都要读出全部的内容,计算。然后写入全部的内容,因此每趟的读写量是全部归并段的总数的两倍。这样64个100MB大小的临时倒排文件进行6趟归并,需要的读写数量为64×100MBx2×6,约合77GB。

  基于前面的分析,对于m个初始归并段,外排时采用k路归并,则归并趟数为「ogkm。显然,随着归并路数k的增大,归并的趟数将减少。趙数的降低将大大减少磁盘I/O的数量,这样很自然地想到使用多路归并的方法。对于64个临时倒排文件的归并,如果能同时归并64路(k=64),则只需要一趟归并即可。

  多路归并的方法在与数据结构相关书籍中都有介绍,通常采用“败者树”这样的数据结构,当然同时也需要采用拉链的思想。每次读取这64个临时倒排文件的一部分进行多路归并直到处理全部的临时倒排文件,结束归并过程,这里不再展开实现细节。

  二路归并在实际处理中还有很多细节,例如每次解压出来的块中并不是全部都能够被归并写入结果倒排文件中会有一些块尾部分;例如解压后的块1的尾部包含了编号为Tx词汇及其对应的记录表( posting file),而在解压后的块2中没有包含编号为Tx这个词,那么这部分将需要等待下一次归并才能写入磁盘。问题是一次解压多少大小才使最合适,以及如何进行并发的归并操作等。

  针对这些实现的细节,读者可以写一些模拟程序来体验大规模数据归并的全过程。另外可以参考[ Managing Gigabytes]书籍官方主页中的一些及有价值的源代码。

  倒排索引分布式存储


  通过前面的学习,我们知道索引数据的规模为TB级。TB相当于1000GB,一个1000GB的文件是不可想像的。因此将全部索引文件存放在一台主机上,不仅是不合适的,而且是不安全的。这样一旦这个倒排文件损坏,全部服务就会受到很大影响,因此倒排索引的分布式存储技术应运而生了。

  目前倒排索引分布式主要有两种方案,这里假定分布式的方法采用多索引结点(可以理解为多主机)的方法。即把一个巨大的倒排文件通过一些划分方法进行切分,使得每一个索引接点上只保留倒排文件的一部分。这样一方面加快了倒排文件的创建速度,降低了倒排文件损坏带来的损失;另一方面也提高了检索的效果。

  多机分布式索引一般按照文档编号( Docld)或者按照索引词编号( WordId)进行划分。按照 DocId划分的结果称为“局部倒排文件"( Local inverted file);按照 WordId划分的结果称为“全局倒排文件"( Global inverted file),如图5-19和图5-20所示。

索引系统-涉及储存规模的一些计算

索引系统-涉及储存规模的一些计算

  图中毎个索引结点可以理解为一台独立主机。由于索引被分布式地存储到不同的索引结点上,所以全局还是局部是相对于索引词来说的。对于局部倒排文件与索引词相关的一部分, DocId被存放在一个索引结点的倒排文件中。换句话说,在图5-19中索引结点A中的倒排文件只存放了某个关键词的一部分匹配的 DocId;而全局倒排文件则存放了一个关键词全部匹配的 DocId。为了便于表述,以下称这两种方案分别为“局部方案”和“全局方案"。

  对于全局方案,索引结点按索引词ID的不同将倒排文件分布式地存储在不同的索引节点上。每个索引结点负责对一个索引词ID区间的文档进行索引。因此每个索引结点的倒排文件中的索引词ID互不相同,然而每个索引结点的文档可能重复。如果某一个文档的索引词足够多,以至于能够覆盖两个以上的索引词ID区间,则可能会被存放在多个索引结点上,这种重复存储将不可避免。

  全局方案带来的好处是如果只检索一个单词,那么只需要在一个索引结点中检索即可。在图520中,对于一个检索请求,发现这个检索词在索引结点B中索引。因此整个检索只在索引结点B中完成,这就大大节约磁盘I/O。此外,由于查询可能是不同的查询词,因而被分布在不同的索引结点上。这样并发的用户查询不需要在检索代理中排队,可以并发地査询从而提高效率。例如查询“XML时,检索代理检测发现这个词存放在索引结点A上;查询“NJU”,检索代理发现这个词存放在索引结点B上,因此这两个关键词的查询可以做到并发查询。如果把索引看做某种公众服务,则全局方案是64个窗口同时对外服务,而局部方案是单窗口排队服务。

  文献[ Melnik et al.2000]阐明了采用局部倒排文件的方案是相对有利的,主要是以下两点。

  (1)可靠性高。

  (2)降低网络负载,提高查询效率。

  首先,对于全局方案,如果某个索引结点出现故障,可能导致某一些关键词无法查询:而局部方案在这种情况下(某个索引结点出现故障)最多是损失来自于一个 DocId区间内的文档。对于査询效果的影响不大,因此该方案提供了足够的可靠性。

  其次,对于全局方案,由于所有的查询结果来自于一个索引结点,因此检索代理要等待这个索引结点传输全部的查询结果,这是低效的。而局部方案中多个索引结点同时将查询结果并发传送,从而充分利用了网络带宽。有意思的是局部方案有利于并发地获取检索结果;而全局方案有利于查询并发,这一点请读者细细体会这种平衡的奥妙,因此局部方案在获取查询结果方面是有优势的。

  到底哪一种方案最佳呢?在业界,一般认为局部方案的可靠性是必须的,因此主要应用了该方案;而在研究界,有研究表明[B2 S Jeong et al1995],在多处理器多磁盘系统下,如果检索词均匀地被请求或者索引词分布偏差不大的情况下,由于避免了局部方案中检索请求必须排队的弊端,因此全局方案在性能上是最佳的。

  倒排文件缓存


  一般认为一个词被查询的频率与其被使用的频率相当,即频率高的词往往也是查询的热词查询的频率依然符合齐普夫法则。即查询频率排名为i的关键词,其查询的实际频率与1i成比例。大量的实验科学证明,在一段时间内那些有机会被检索到的检索词总是少数的,将这些少数的检索词存放在内存中可以大大降低读取磁盘中倒排文件的机会。关于倒排文件的缓存,可以参考文献[李晓明2004]。这里只给出一个结论,如果一个索引结点需要10GB的倒排文件,那么在这个10GB的倒排文件中,只有不到20%的索引词及其记录表应该进入缓存。然而这20%的索引词占用的空间几乎是80%,即需要8GB的内存,这显然是难以实现的。因此业界采用了很多特有技术来完成这个工作,由于超出本书的范畴,所以不再深入下去。

  倒排文件的缓存及第六章中提到的搜索结果页缓存的基本原理大致相当,读者可以参考第六章中的相关内容,深刻地理解在查询系统和索引系统这种缓存机制的重要性。

  倒排索引词典统计信息的计算


  倒排文件中的词典还需要有关每个索引词的统计信息,主要是词汇出现的文档数。这些信息主要用在査询系统中,在下一章中会详细介绍这些统计数据是如何应用的。

  在索引系统中,这些关于索引词出现的文档数的统计是在查询请求发生之前预先计算好的,是倒排表的词典部分中不可分割的一部分。把做统计工作的这个模块称为“统计员"。关键词的文档频率的统计信息是全局的,因此在整个系统中仅有一个服务模块来完成这项工作。在系统结构图中,统计员的位置如图5-21所示。

  如图所示,统计员把各个索引结点的词典信息综合起来做全局统计。然后将统计结果传回各自的词典中,继而保存这些全局统计信息。在下一节说明倒排索引创建过程时会详细提到关于统计信息的计算过程。

索引系统-涉及储存规模的一些计算

评论区

表情

共0条评论
  • 这篇文章还没有收到评论,赶紧来抢沙发吧~

相关内容

点击排行

随机新闻

评论排行榜