基于MapReduce的HITS算法的实现

余 辉，王笑梅

(上海师范大学信息与机电工程学院，上海200030)

0 引言

HITS算法是一种基于“导航页”和“权威页”的迭代算法［1］，用于计算每个网页的重要性．由于处理的网页数量巨大，普通的串行实现效率太低，在这种情况下，考虑使用MapReduce编程模型来实现HITS算法成为必然．MapReduce编程模型最早由Google公司提出［2］，用于并行处理大规模数据集，并逐渐成为云计算的核心技术之一．MapReduce的开源实现框架Hadoop［3－4］是一个优秀的并行编程平台，它克服了传统并行计算框架MPI的不足，实现了计算向存储迁移［5］，在处理密集型的大规模数据集时有很大的优势．

1 HITS算法与Hadoop框架

1．1 HITS 算法

HITS算法对网页重要性的计算有两个度量准则，第一个是网页作为导航页的重要性，即它的导航度;第二个是网页作为权威页的重要性，即它的权威度．网页的导航度和权威度分别用n维向量h和a表示，第i个网页的导航度为向量h的第i个分量，权威度为向量a的第i个分量．为了计算出向量h和a，还需要一个n×n维的连接矩阵L和它的转置矩阵LT，如果Lij=1，则表示第i个网页到第j个网页存在链接，如果Lij=0，则表示两个网页之间没有关联．

一个网页的导航度依赖于这个网页所链出网页的权威度，权威度依赖于这个网页所链入网页的导航度，所以有以下公式:

由权威度a计算出导航度h，再由导航度h计算出权威度a．显然，这是一个迭代过程，第一次迭代时取a为n维全1向量．由于迭代过程中h和a的分量可能会急剧增大，所以需要做归一化处理:

其中ξ和δ是归一化因子，它们将每次迭代计算出的h和a的最大分量变为1．以上公式(3)和(4)作为1次完整的迭代，当h和a分别达到一定精度要求时即停止迭代．

1．2 Hadoop 框架

基于MapReduce编程模型的云计算框架Hadoop是一种分布式并行计算框架，在其底层支撑MapReduce数据处理功能的是分布式文件系统HDFS［6，7］，MapReduce编程模型和HDFS构成了Hadoop最基本、最核心的组件．HDFS的结构如图1所示．

图1 HDFS结构

在分布式环境中，存在着一个主节点NameNode和多个从节点DataNode．主节点存储着文件系统的元数据，比如文件系统的名字空间等，用于向用户映射文件．但实际的数据并非存储于主节点，而是分布存储在多个从节点上．Hadoop在MapReduce编程模型上的主程序被称为Jobtracker，子程序被称为Tasktracker．主程序负责整个MapReduce执行流程的控制工作，由于需要读取文件系统的相关信息，所以它通常位于主节点．主程序启动之后，会创建位于从节点的子程序．子程序Tasktracker每隔一段时间向主程序Jobtracker发送心跳，返回自己的执行状态．子程序会在从节点创建两种类型的子任务，分别是map任务和reduce任务．在Hadoop中由于有HDFS文件系统的支持，数据是分布式存储在各个节点的，map任务在并行运行时，各节点读取存储在自己节点的数据进行处理，从而避免了大量数据在网络上的传递，实现了计算向存储的迁移．map任务生成中间的＜key，value＞对集合，将其存储在本地，并将具有相同key的中间值合并发送给reduce任务;reduce任务将合并的值进行相关的计算后产生最后的＜key，value＞对集合．MapReduce编程模型如图2所示．

图2 MapReduce编程模型

2 算法设计

2．1 基本思想

从公式(3)和(4)可以看出，HITS算法可以简化为矩阵和向量的乘法．若有n×n维矩阵A和n维向量 b，则

基于MapReduce的矩阵和向量乘法的算法思想如下:

map阶段:对于矩阵A的每个元素 Aij，生成键值对 ＜ ＜i，1＞，＜A，j，Aij＞ ＞;对于向量 b的每个元素 bj，生成键值对 ＜ ＜i，1 ＞ ，＜b，j，bj＞ ＞ ，其中 i=1，2，…，n．

reduce阶段:根据MapReduce编程模型的原理，具有相同key的键值对合并后发送给reduce任务，此时即可计算出(Ab)i，并输出键值对 ＜ ＜i，1＞，(Ab)i＞．

2．2 算法实现

为了实现基于MapReduce的HITS算法，需要编写3个函数，即map函数，reduce函数和main函数．map和reduce函数分别实现上述算法思想中的map阶段和reduce阶段，main函数则负责向量的精度控制．当同时满足两个条件时，就停止迭代．基于 MapReduce的HITS算法的伪代码描述如下:

3 实验

3．1 实验平台

采用一台Intel(R)Xeon(R)cpu E5－16070@3．0GHZ，8G内存pc作为主机，在 pc上安装5台VMware虚拟机，其中1台作为NameNode(Jobtracker)节点，另外4台作为DataNode(Tasktracker)节点．每台虚拟机安装linux Red Hat 9．0操作系统，分配1G内存;Hadoop和java的版本分别为hadoop－0．20．2，jdk1．6．实验数据采用来自斯坦福大学的StanfordBerkeleyWeb数据集，其中包含685230个网页，页面之间存在7636535条链接，数据集大小为143M．

3．2 实验分析

3．2．1 分块大小对算法运行时间的影响

在Hadoop框架中，分块大小(blocksize)会直接影响算法执行的效率．在集群中，map任务的数量和对输入文件进行分块后的块数是相等的，所以输入文件的大小和blocksize决定了集群中map任务的数量．如果blocksize太小，则启动的map任务过多，就会导致集群负载剧增，过多地损耗资源，降低算法性能;反之，如果blocksize太大，map任务太少，算法就不能充分利用集群资源，不能充分发挥出并行的特性．因此，在执行算法时，需要合理的配置集群中blocksize的大小，在不增加集群负载的情况下充分发挥出并行处理的优势．实验中采用数据集StanfordBerkeleyWeb，将blocksize分别设置为16、32、64、128、256M，在不同的blocksize下分别执行算法，结果如表1所示．

表1 不同blocksize下算法执行时间

由于集群有5台虚拟机，其中4个是DataNode节点，所以blocksize为16、32、64、128、256M时，平均每个DataNode节点分配到的map任务为2～3个，1～2个，0～1个，0～1个，0～1个．从表1可以看出，当blocksize为16M，即每个DataNode节点分配2～3个map任务时，算法运行的效率最高;当blocksize增大时，由于没有充分利用集群的并行特性，算法效率逐渐降低．

3．2．2 集群规模对算法运行时间的影响

将blocksize设置为64M，分别在3机集群、4机集群、5机集群的环境中执行算法，结果如表2所示．

表2 不同集群下算法执行时间

从表2可以看出，适当扩大集群规模，算法运行效率逐渐提高．这是因为随着集群规模的扩大，集群中可利用的处理器和内存也会随之增加，从而集群也获得了更强大的并行处理能力．

4 结语

提出了一种基于Hadoop框架下的HITS算法的设计与实现．算法的设计主要涉及map阶段和reduce阶段，其中map阶段是算法并行化的关键．在试验中深入分析了集群配置参数blocksize和集群规模对算法执行效率的影响，探索了执行map任务期间的集群负载和集群的可伸缩性．在后续工作中，将继续探索云计算环境下的搜索引擎相关算法的设计与实现，并就如何提高算法的性能展开研究．

［1］RAJARMAN A，ULLMAN J D．Mining of Massive Datasets［M］．Cambridge:Cambridge University Press，2011．

［2］DEAN J，GHEMAWAT S．Mapreduce:simplified data processing on large clusters［J］．Communications of the ACM，2008，51(1):1－13．

［3］WHITE T．Hadoop:The Definitive Guide［M］．Newton:O’Reilly Media，2010．

［4］WIKIPEDIA．Hadoop［EB/OL］．［2011 －10 －15］(2013 －04 －15)．http://en．wikipedia．org/wiki/Hadoop．

［5］王鹏．云计算的关键技术与应用实例［M］．北京:人民邮电出版社，2010．

［6］SHVACHKO K，KUANG H．The Hadoop Distributed File System［C］//Proceedings of the 26thIEEE Symposium on Massive Storage Systems and Technologies，Piscataway:IEEE Press，2010．

［7］GHEMAWAT S，GOBIOFF H，LENNG S．The google file system［J］．ACM Sigops Operating Systems Review，2003，37(5):29－43．