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

涉及存储规模的倒排索引分布式存储

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

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

多机分布式索引一般按照文档编号(Docld )或者按照索引词编号(Wordld)进行划分。按照Docld划分的结果称为“局部倒排文件”(Local inverted file );按照Wordld划分的结果称为“全局倒排文件”(Global inverted file),如图5-19,和图5-20所示。(图片首发于深圳SEO,别盗图)
全局倒排文件
图中每个索引结点可以理解为一台独立主机。由于索引被分布式地存储到不同的索引结点上,所以全局还是局部是相对于索引词来说的。对于局部倒排文件与索引词相关的一部分,Docid被存放在一个索引结点的倒排文件中。换句话说,在图5-19中索引结点A中的倒排文件只存放了某个关键词的一部分匹配的Docid;而全局倒排文件则存放了一个关键词全部匹配的Docid。为了便于表述,以下称这两种方案分别为“局部方案”和“全局方案”。

对于局部方案,索引结点按Docid的不同将倒排文件分布式地存储在不同的索引节点上。每个索引结点负责对一个Docid区间的文档进行索引,因此每个索引结点的倒排文件中的Docid互不相同。在检索时,将检索请求广播到每个结点。每个结点分别查询,最后由检索代理合并查询结果。

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

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

文献(Melnik et al. 2000)阐明了采用局部倒排文件的方案是相对有利的,主要是以下两点。
1.可靠性高
2.降低网络负载,提高查询效率

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

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

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

本文出自深圳SEO公司,未经允许不得转载:深圳SEO-微笑SEO服务公司 » 涉及存储规模的倒排索引分布式存储
分享到: 更多 (0)

评论 抢沙发

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