深圳SEO公司
欢迎您光临浏览!

涉及存储规模的多个临时倒排文件的归并

文章前深圳SEO首先带大家来考虑两个临时倒排文件的归并,通过前面数据规模估计,我们知道全部索引大小为TB量级的数据,后面将介绍倒排文件如何进行分布式存储。存储的节点数目控制在百这个数量级上,因此全部索引大小分布在100个索引结点上,平均每个索引结点大约需要存放10 GB的倒排文件(降两个数量级)。如果每个索引结点存放64个临时倒排文件,这样每个临时倒排文件约l00MB(降两个数量级〕,64个100MB大小的临时倒排文件最终归并成一个10GB大小的最终倒排文件是十分有挑战性的。每个临时倒排文件内部字典中词汇的编号是有序的,每个词汇对应的记录表(posting list)中的Docld是有序的,每个HitList中也是有序的,因此归并后依然要保持这种有序性。我们将这种归并过程笼统地称为“归并排序”,很显然这种规模的归并排序在内存中无法完成,下面介绍两种解决这个问题的方法。
1.拉链法(Zipper)和二路归并
2.拉链法和多路归并
无论是两路归并还是多路归并,拉链法都是必需的。我们首先考察拉链法和二路归并的组合,对于两个较大的文件进行归并排序,不可能将两个文件同时读入到内存中后进行排序。因此可以读取一部分归并,将结果以文件的形式写入磁盘,然后继续读取两个待归并文件的一部分。周而复始,直到读完其一种的某个文件,另一个文件顺序写入结果文件。因此归并的方法如下。
1.从头开始读取两个临时倒排文件的一小部分(例如每次读取10MB)
2.分别对Docld进行解压,将压缩后的差分序列还原成原始的差分序列
3.两个按照Docld有序的列表进行归并
4.归并和结果进行压缩
5.写入归并后的临时倒排文件1&2中
以上方法如果图5-17所示。
临时倒排文件
这里首先解压临时倒排文件1和临时倒排文件2的两块数据(只解压Docld.不解压Hit List的部分),分别解压后得到解压后的块1和解压后的块2。因为Docld有序,因此归并可在线性时间内完成(参考有关数据结构的书籍中关于两个有序表归并的内容,这里不再展开)。归并后的倒排表中Docld依然有序,接下来还需要采用Variable Byte Coding编码方式对Docld进行压缩,最后写入结果倒排文件中(如图5-17的侧排文件1&2)中。
这种拉链的方法采用的思路是处理大文件(Big File)的一种通用思路,即每次仅取出大文件的一部分在内存中进行计算。计算结束后存储计算结果,并释放内存。继续读取文件的下一部分到内存、计算、存储计算结果并释放内存,周而复始直到处理全部数据。64个这样的临时倒排文件进行归并需要多少趟这样的两两归并呢?第1真没,64个100 MB的临时倒排文件两两归并得到32个200 MB的临时倒排文件;第2趟,32个200MB的倒排文件两两归并,得到6个400 MB的临时倒排文件,直到最后剩下两个3 200 MB大小的临时倒排文件两两归并得到1个6.4 GB大小的最终倒排文件,这样整个归并的过程结束。每一趟归并结束后,归并段的个数少一半。
倒排文件两两归并
倒排文件归并
针对这些实现的细节,读者可以写一些摸拟程序来体验大规模数据归并的全过程。另外可以参考(Managing Gigabytes)书籍官方主页中的一些及有价值的源代码。
本文出自深圳SEO公司,未经允许不得转载:深圳SEO-微笑SEO服务公司 » 涉及存储规模的多个临时倒排文件的归并
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址