基于hadoop的大规模数据排序算法-----韩旭红组

                           -------2011.10.26

  小组成员：

            组长：韩旭红 1091000161

            组员：李巍 1091000167   李越 1091000169  闫悦 1091000178

 

近几周内容：

最近一段时间我们首先把操作平台配置好了，然后大致了解了一下java的内容。把一些源代码看了看，看了一些有关大规模数据排序算法的内容。今天我们组介绍一下nutch的内容。

Nutch的内容谨此让大家了解,有兴趣可以看一下,估计我们也没有时间做这部分的内容了。。。

一．概述

图 1

 

 

Nutch是一个由Java实现的，刚刚诞生开放源代码(open-source)的web搜索引擎。

随着互联网技术的不断发展,搜索引擎已经成为人们获取网络信息的主要工具。研究搜索引擎网页排序的目的是从众多搜索结果中将内容相关和权威的网页排在前面,帮助用户迅速定位需要的网络资源。网页排序算法直接影响到搜索引擎信息检索的准确率和用户使用满意度。Nutch是基于Java实现的开源搜索引擎。通过对Nutch进行深入研究,指出其目前存在的两大问题,其一是没有实现PageRank算法,影响了最终排序效果;其二是对中文进行单字切分,影响了查询结果准确率。
　　 首先,针对目前Nutch搜索引擎中没有实现网页PageRank计算的问题,利用MapReduce并行计算模型处理大数据集的优势,在Nutch机群系统上设计和实现了基于MapReduce的PageRank分布式并行算法。实验结果表明:处理的数据量越大,机群中的节点越多,计算PageRank的效率越高;另外,该分布式并行算法具有较好的可扩展性。然后,针对目前Nutch对中文进行单字切分的问题,加入了JE中文分词器对Nutch的中文分词进行改进。在分析和研究经典PageRank算法原理的基础上,通过设置控制站外与站内链接的比重因子对该算法进行了改进。为了改善Nutch基于Lucene的网页综合排序模型,将改进后的PageRank算法因子融入到Nutch网页评分计算公式当中。实验表明,改进后Nutch明显提高了查询结果的准确率,改善了中文网页的排序效果。

二．    Nutch 致力于做到：

  Nutch 致力于做到：

　　* 每个月取几十亿网页

　　* 为这些网页维护一个索引

　　* 对索引文件进行每秒上千次的搜索

　　* 提供高质量的搜索结果

　　* 以最小的成本运作

三． 组成

Nutch主要分为两个部分

　　爬虫crawler和查询searcher。Crawler主要用于从网络上抓取网页并为这些网页建立索引。Searcher主要利用这些索引检索用户的查找关键词来产生查找结果。两者之间的接口是索引，所以除去索引部分，两者之间的耦合度很低。

Crawler和Searcher两部分尽量分开的目的主要是为了使两部分可以分布式配置在硬件平台上，例如将Crawler和Searcher分别放在两个主机上，这样可以提升性能。

爬虫，Crawler

　　Crawler的重点在两个方面，Crawler的工作流程和涉及的数据文件的格式和含义。数据文件主要包括三类，分别是web database，一系列的segment加上index，三者的物理文件分别存储在爬行结果目录下的db目录下webdb子文件夹内，segments文件夹和index文件夹。

　　Web database，也叫WebDB，其中存储的是爬虫所抓取网页之间的链接结构信息，它只在爬虫Crawler工作中使用而和Searcher的工作没有任何关系。WebDB内存储了两种实体的信息：page和link。Page实体通过描述网络上一个网页的特征信息来表征一个实际的网页，因为网页有很多个需要描述，WebDB中通过网页的URL和网页内容的MD5两种索引方法对这些网页实体进行了索引。Page实体描述的网页特征主要包括网页内的link数目，抓取此网页的时间等相关抓取信息，对此网页的重要度评分等。同样的，Link实体描述的是两个page实体之间的链接关系。WebDB构成了一个所抓取网页的链接结构图，这个图中Page实体是图的结点，而Link实体则代表图的边。

　　一次爬行会产生很多个segment，每个segment内存储的是爬虫Crawler在单独一次抓取循环中抓到的网页以及这些网页的索引。Crawler爬行时会根据WebDB中的link关系按照一定的爬行策略生成每次抓取循环所需的fetchlist，然后Fetcher通过fetchlist中的URLs抓取这些网页并索引，然后将其存入segment。Segment是有时限的，当这些网页被Crawler重新抓取后，先前抓取产生的segment就作废了。在存储中。Segment文件夹是以产生时间命名的，方便我们删除作废的segments以节省存储空间。

　　Index是Crawler抓取的所有网页的索引，它是通过对所有单个segment中的索引进行合并处理所得的。Nutch利用Lucene技术进行索引，所以Lucene中对索引进行操作的接口对Nutch中的index同样有效。但是需要注意的是，Lucene中的segment和Nutch中的不同，Lucene中的segment是索引index的一部分，但是Nutch中的segment只是WebDB中各个部分网页的内容和索引，最后通过其生成的index跟这些segment已经毫无关系了。

Crawler工作流程

　　在分析了Crawler工作中设计的文件之后，接下来我们研究Crawler的抓取流程以及这些文件在抓取中扮演的角色。Crawler的工作原理：首先Crawler根据WebDB生成一个待抓取网页的URL集合叫做Fetchlist，接着下载线程Fetcher根据Fetchlist将网页抓取回来，如果下载线程有很多个，那么就生成很多个Fetchlist，也就是一个Fetcher对应一个Fetchlist。然后Crawler用抓取回来的网页更新WebDB，根据更新后的WebDB生成新的Fetchlist，里面是未抓取的或者新发现的URLs，然后下一轮抓取循环重新开始。这个循环过程可以叫做“产生/抓取/更新”循环。

　　指向同一个主机上Web资源的URLs通常被分配到同一个Fetchlist中，这可防止过多的Fetchers对一个主机同时进行抓取造成主机负担过重。另外Nutch遵守Robots Exclusion Protocol，网站可以通过自定义Robots.txt控制Crawler的抓取。

　　在Nutch中，Crawler操作的实现是通过一系列子操作的实现来完成的。这些子操作Nutch都提供了子命令行可以单独进行调用。下面就是这些子操作的功能描述以及命令行，命令行在括号中。

　　1. 创建一个新的WebDb (admin db -create).

　　2. 将抓取起始URLs写入WebDB中 (inject).

　　3. 根据WebDB生成fetchlist并写入相应的segment(generate).

　　4. 根据fetchlist中的URL抓取网页 (fetch).

　　5. 根据抓取网页更新WebDb (updatedb).

　　6. 循环进行3－5步直至预先设定的抓取深度。

　　7. 根据WebDB得到的网页评分和links更新segments (updatesegs).

　　8. 对所抓取的网页进行索引(index).

　　9. 在索引中丢弃有重复内容的网页和重复的URLs (dedup).

　　10. 将segments中的索引进行合并生成用于检索的最终index(merge).

Crawler详细工作流程是

　　在创建一个WebDB之后(步骤1), “产生/抓取/更新”循环(步骤3－6)根据一些种子URLs开始启动。当这个循环彻底结束，Crawler根据抓取中生成的segments创建索引（步骤7－10）。在进行重复URLs清除（步骤9）之前，每个segment的索引都是独立的（步骤8）。最终，各个独立的segment索引被合并为一个最终的索引index（步骤10）。

　　其中有一个细节问题，Dedup操作主要用于清除segment索引中的重复URLs，但是我们知道，在WebDB中是不允许重复的URL存在的，那么为什么这里还要进行清除呢？原因在于抓取的更新。比方说一个月之前你抓取过这些网页，一个月后为了更新进行了重新抓取，那么旧的segment在没有删除之前仍然起作用，这个时候就需要在新旧segment之间进行除重。

四、Nutch和Lucene

　　Nutch是基于Lucene的。Lucene为Nutch提供了文本索引和搜索的API。

　　一个常见的问题是：我应该使用Lucene还是Nutch？

　　最简单的回答是：如果你不需要抓取数据的话，应该使用Lucene。

　　常见的应用场合是：你有数据源，需要为这些数据提供一个搜索页面。在这种情况下，最好的方式是直接从数据库中取出数据并用Lucene API 建立索引。

　　在你没有本地数据源，或者数据源非常分散的情况下，应该使用Nutch。