（计算机软件与理论专业论文）云计算及若干数据挖掘算法的mapreduce化研究.pdf

。v 0 f 。 、 本人声明 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明 确的说明并表示谢意。 签名：硅缝 日期：弘t 。年j 月石日 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：盖雒导师签名： 日期：厶f 。年j 月玎日 l 蟹1j 摘要 摘要 云计算是2 0 0 8 年以来国际i t 业热炒的概念， 根，是业界不可回避和逆转的一大趋势。我们可以 行处理以及网格计算的发展，其中并发、分布是云 海量计算是云计算的重头戏。但是云计算本身只是 的魔力，除了硬件以外，更重要的是还得有软件的 台上高效运行的并行化程序。 海量数据处理和海量计算是数据挖掘领域的一 掘算法往往只能适用小规模输入数据，当输入数据 的增大而速度减慢甚至无法运行，这无疑是许多传统挖掘算法的瓶颈。云计算则 恰好擅长处理大规模数据和大规模计算，如果我们能够将传统数据挖掘算法并行 化，并将之部署到云计算平台上运行，数据挖掘领域中的上述瓶颈问题就能迎刃 而解。而能否有效借助云计算平台解决上述问题，关键在于能否合理地将相应的 数据挖掘算法并行化。 所以本论文首先主要从分布式文件系统和分布式编程模式两大方向分析了 g 0 0 9 l e 、s e c t o r s p h e r e 和h a d o o p 三大云计算平台框架；然后从用户角度出发， 综合考虑文本内容、人类遗忘性和话题流行度等因素，提出了一种基于网络日志 的中文热点话题提取算法，并将其m a p r e d u c e 化后部署到h a d o o p 云计算平台上运 行，取得了良好的加速比效果，成功地提高了算法的运行速度和扩大了算法输入 数据的规模；最后通过分析传统协同过滤算法、局部线性回归算法和朴素贝叶斯 算法的详细流程、瓶颈问题和可并行化点，采取并行和串行相结合的方式，提出 了将这几大算法m a p r e d u c e 化的方法，不但证明了这些算法的可m a p r e d u c e 化， 而且在输入大批量数据的h a d o o p 集群实验中，取得了不错的加速比效果，比较成 功地解决了这些算法计算量过大和计算时间过长的难题。本论文的研究为数据挖 掘领域相关算法提供了可行的m a p r e d u c e 化方案，实验结果证明了上述方案的切 实有效性。 关键词：云计算，m a p r e d u c e ，中文热点话题，协同过滤 1，- 虹1 i n l ( i n gm o d e l ，i fc 1 0 u dc o m p u t i n gt r i e st os h o wi t sm a 百c ，c l o u dc o m p u t i n gp l a t f o m a i l de f f i c i e n tp a r a l l e ls t r a t e 西e sm u s tb ec o n s t n l c t e db e s i d e sh a r d w a r e m a s s i v ec a l c u l a t i o nt a s k sa l w a y ss h o wa sar e g u l a rp r o b l e mi nt h ea r e ao fd a t a m i n i n g m a n y 蛔d i t i o n a ld a t am i n i n ga l g o r i t k n sc a i lo n l yd e a lw i t hs m a l l - s c a l ei n p u t d a t aa 1 1 dw i l lr u ns l o w e ro re v e nc 0 1 l 印s ew h e f lm ei n p u td a t ai n c r e a s e t h ep r o b l 锄 a b o v ei sa l w a y sab o t t l e n e c ko f 舰d i t i o n a ld a t am i n i n ga l g o 矗m m b e t t e rp 幽册a 1 1 c e c a nb ea c h i e v e di fw ec a nt m s p l a n tm e s ea l g o r i t h m so nt h ec l o u dc o m p u t i n g p l a t f o 肌 a n dm a k em 锄m ni np a r a l l e l t h u s ，w h e m e rt h ea l g o 打t h mc a nb en mi np a r a l l e l p r o p e r l yo rn o t b e c o m e sm ek e y t os 0 1 v et h ep r o b l e mm e n t i o n e da b o v e f i l es y s t e m 肌dp r o 黟a m m i n g m e t h o d o l o g yo fg o o g l e ，s e c t o r s p h e r ea n dh a d o o p a r ea i l a l y z e df i r s ti nt h i sp a p 既s e c o n d l y ，ac h i n e s eh o t t o p i ce x t r a c t i o na l g o r i t h mi s p r o p o s e d ，w h i c ht 狄e ss o m ef a c t o r si n t oa c c o u n t ，s u c ha sc o n t e n t so ft e x t ，f o 玛e t t i n go f h u m a l l ，p o p u l 撕t yo ft o p i ca n ds oo n t l l e l lab e t t e rp e r f o n l l a n c ei sa c h i e v e da r e rw e m a p r e d u c ea n dm i lt h ea l g o r i t l l i i lo nh a d o o pp l a t f o n n t h ea l g o r i t h mb e c o m e si n u c h f a s t e ra l l dc a l ld e a lw i t hl a r g e - s c a l ei n p u td a t a f i n a l l y ，a r e ra n a l y z i n gt h ep r o c e s so f c o l l a b o r a t i v ef i l t 嘶n ga l g o r i t h m 、l o c a l1 i n e a rr e g r e s s i o na l g o r i t l u i l 孤dn a i v eb a y e s a l g o r i m m ，t h eb o t t l e n e c ka n dt h ea s p e c tw h i c ：hc a nb ep a r a l l e l i z e di nt h e s ea 】g o 五廿1 m s c o r r e s p o n d i n gm a p r e d u c e da l g o r i t h m sa r ep r o p o s e d ，删c hh a n d l et h ek e yp r o b l e mo f e 街c i e n c ys u c c e s s 血1 1 y t h er e s e a r c ha c h i e v e m e n t sg a i n e di nt h i sp 印e rp r o 、，i d e a s 0 1 u t i o nf o rm a p r e d u c i n ga l g o r i t so fd a t am i n i n g ，a 1 1 dt h ee x p 甜m e n tr e s u l t s d e m o n s t r a t et h ee 丘e c t i v e n e s so fm es o l u t i o n k e y ：c l o u dc o m p u t i n g ，m a p r e d u c e ，c h i n e s eh o t _ t o p i c ，c 0 1 1 a b o r a t i v ef i l t 耐n g i i r 、；h 1 3 国内外研究现状3 1 4 论文研究内容及章节安排4 1 5 本章小结4 第二章云计算平台介绍与浅析5 2 1g o o 西e 云计算平台介绍与分析5 2 1 1g 0 0 西e 文件系统g f s 5 2 1 2g o 0 9 1 e 的b i g t a b l e 7 2 1 3m a p r e d u c e 编程模型7 2 2 开源云计算平台h a d o o p 介绍与分析8 2 2 1h a d o o p 分布式文件系统概述8 2 2 2h a d o o p 分布式文件系统( h d f s ) 详解9 2 2 3m a p r e d u c e 并行编程模型在h a d o o p 中的实现1 4 2 2 4h a d o o pm a p 瓜e d u c e 的容错机制分析17 2 3s e c t o r 架构分析与介绍18 2 3 1s e c t o r 概j 盔18 2 3 2s e c t o r 文件系统管理18 2 4s e c u r i t ) ，s e n ，e r 1 9 2 4 1s p h e f e 计算云l9 2 4 2 调度机制2 1 2 5 平台应用背景的对比2 2 2 5 1g f s 、m a p r e d u c e 和b i 醇a b l e 应用场景2 2 i i i 目录 2 5 2h a d o o 口应用场景2 2 2 5 3s e c t o r s p h e r e 应用场景2 3 2 6g o o 百e 云平台、s e c t o r s p h e r e 及h a d o o p 平台的对比2 4 2 7 本章小结2 4 第三章基于网络日志的中文热点话题提取算法研究2 5 3 1 话题提取算法介绍与分析2 5 3 2 基于网络日志的热点话题提取算法分析2 5 3 3 基于网络日志的热点话题提取方法2 6 3 3 1 网络日志分析2 6 3 3 2 主题提取2 6 3 3 3 热点话题提取2 8 3 3 4 热点话题描述2 9 3 4 单机实验和分析3 0 3 4 1 单机实验结果及分析3 0 3 4 2 中文热点提取算法展望3 3 3 5 中文热点提取算法的m a p r e d u c e 化3 3 3 5 1 网页统计m a p r e d u c e 化3 3 3 5 2 网页爬取、网页解析及主题提取m a p r e d u c e 化3 4 3 5 3 候选话题提取m a p r e d u c e 化一3 6 3 5 4 热点话题描述m a p r e d u c e 化3 7 3 6h a d o o p 云计算集群上实验结果与分析3 7 3 6 1h a d o o p 实验集群的搭建3 7 3 7h a d o o p 集群上的实验结果与分析4 4 3 7 1h a d o o p 集群与单机实验结果与分析4 5 3 7 2h a d o o p 集群线性比测试与分析4 6 3 8 本章小结4 7 第四章基于用户的协同过滤算法在h a d o o p 平台的实现4 8 4 1 协同过滤算法简介4 8 i v 鼍 九 确 目录 4 2 协同过滤系统详解。4 9 4 2 1 假设与目标4 9 4 2 2 协同过滤算法具体过程4 9 4 2 3 传统协同过滤算法面临的问题及应对策略5 0 4 3 传统协同过滤算法的m a p r e d u c e 化5 0 4 3 1 数据划分5 1 4 3 2m 印阶段5 2 4 3 3r e d u c e 阶段5 2 4 4 协同过滤算法实验过程及结果分析5 3 4 4 1 实验总结与展望5 4 4 5 本章小结5 5 第五章局部加权线性回归算法在h a d o o p 平台的实现5 6 5 1 局部加权线性回归算法简介5 6 5 2 局部加权线性回归算法详解5 7 5 2 1 局部加权线性回归算法主要步骤5 7 5 3 局部加权线性回归算法的m a p r e d u c e 化6 2 5 3 1d a t a n o d e 数据量的划分6 2 5 3 2m a p 阶段6 3 5 3 3r e d u c e 阶段6 4 5 4 实验过程及测试结果分析一6 4 5 5 本章小结6 5 第六章朴素贝叶斯分类算法在h a d o o p 平台的实现6 6 6 1 朴素贝叶斯算法简介6 6 6 2 朴素贝叶斯算法详解6 6 6 2 1 贝叶斯定理6 6 6 2 2 算法实现的疑难与解答6 7 6 2 3 朴素贝叶斯算法实现过程6 9 6 3 朴素贝叶斯算法的m a p r e d u c e 化6 9 v 目录 6 3 1 数据预处理m 印r e d u c e 化7 0 6 3 2 模型训练m a p r e d u c e 化7 0 6 3 3 分类m a p r e “c e 化7 2 6 4 实验过程及测试结果分析7 2 6 5 本章小结7 3 第七章总结和展望7 4 致谢7 5 参考文献7 6 攻硕期间取得的研究成果8 0 v i t q 但 代 的 数 便 以g o 0 9 1 e 文件系统为基础搭建起来的g o o g l e 机器集群，为g o o g l e 提供了极快的 搜索速度和强大的处理能力。如何有效利用此类技术，为更多的企业或个人提供 强大的计算能力和服务，就成了g o o g l e 这种拥有丰厚资源和庞大业务的企业所深 深思考的问题。正是由于一方对海量数据处理和海量计算能力的强劲需求，而另 一方能够提供这种能力，所以云计算应运而生。当然以互联网为主要特征的信息 爆炸时代云计算的适应领域不仅仅只限于传统意义上狭隘的互联网，很多符合采 用云计算思维解决问题的场合，都可以运用云计算，只是互联网络催生了云计算 的出现，提高了它的关注度，加速了它的推广和发展。 云计算概念的出现使人们看到了信息爆炸时代解决海量数据处理等诸多问题 的曙光，于是全球诸如：i b m 、g o o g l e 、y a h o o 、a m a z o n 、s u m 和m i c r o s o f t 等知 名i t 厂商们依据各自的优势、定位、核心策略和技术基础，纷纷推出了自己的云 计算计划。但它们大多把自己的云计算计划视作独门秘笈，外人只能闻其名，而 不能知其实，这使得云计算很大程度上看来似乎只是大工t 厂商们的专利，普通用 户只能被服务。幸运的是开源为大家打开了一扇详细了解云计算的窗口，提供了 免费下载云计算平台的来源，这其中犹以a p a c h e 开源组织所开发的h a d o o p 框架 【l 】最为经典，使用最为广泛。仔细研究已有云计算平台有助于我们深入了解云计 算过程和懂得如何有效地利用云计算平台为自己服务。 不仅仅只有互联网会遇到海量数据处理和计算的难题，数据挖掘领域也经常 会遇到同样的问题，这使得许多现有数据挖掘算法面临很大的限制，无法处理输 入数据量或是计算量巨大的情况，云计算擅长处理这类问题，这为在诸多数据挖 电子科技大学硕士学位论文 掘算法中引入云计算概念，利用云计算平台解决数据挖掘领域实际问题带来了希 望，而要在数据挖掘领域中引入云计算思维，关键在于实现相关数据挖掘算法的 并行化，使之能够借助云计算平台高速地处理海量数据和进行海量计算，本论文 以中文热点提取算法、协同过滤算法、局部线性回归算法和朴素贝叶斯算法为基 础，详细讲述了对这四大算法的并行化过程和其并行化后在h a d o o p 云计算平台上 的实际效果，希望能够抛砖引玉深化我们对云计算及m a p r e d u c e 编程模式的理解， 为大家快速、便捷的利用云平台服务提供帮助。 1 2 研究目的和意义 互联网的高速发展为大众提供了丰富的资讯，同时也像滚雪球一样将更多的 人带进了网络圈子，这不仅对大众而言出现了人们常说的“信息爆炸，使他们在 潮水般的信息面前显得无所适从，对网站或者商家而言用户的数量也呈指数增长， 传统的数据处理和服务方式难以招架，于是云计算应运而生。云计算这一新兴的 商业计算模型，利用互联网的高速传输能力，将数据处理过程从个人计算机或服 务器转移到互联网上的计算机集群中。集群机器都是普通的计算机，由某一中心 服务器统一管理，中心服务器按客户的需要分配计算资源，最终能达到与超级计 算机相同的效果，在此模式下海量数据处理和海量计算不再像以前那样让人头痛。 眼下全球各大知名i t 厂商都推出了自己的云计算计划，而且成效显著，以 g o 0 9 1 e 为例，从g o o g l e 在云计算方面所取得的成功，我们就不难看出云计算的 巨大魅力。但是i t 厂商们更趋向于把自己的云计算计划视作独门绝技，不会让外 人窥个究竟，这使得一般用户无法知道云计算的详细原理和过程，更无从谈起借 助已有技术构建自己的云计算平台。幸运的是开源的存在，为大众窥探云计算的 奥妙打开了一扇窗，也为普通用户构建自己的云平台，利用云计算服务自身提供 了机会，开源的云计算项目中犹以a p a c h e 组织开发的h a d o o p 框架最为典型，使 用最为广泛。虽然已经有开源的云计算项目存在，但是由于云计算是新兴的概念， 其详细原理和具体实施流程并不为大家所熟知，详细分析已有云计算平台框架能 帮助大家深刻的理解云计算及其编程模式，也有助于大家快速利用已有资源构建 自己的云平台，享受云计算带来的好处。 光有云计算平台仍不够，还得有适合在云平台上运行的应用程序，才能充分 发挥云计算的威力。如何编写在云平台上运行的并行化程序是很有讲究的，它不 同于以往的单机编程模式，不但要服从一定云计算框架的限制，更重要的是要将 2 k 第一章引言 算法合理地并行化。算法能否有效并行化，成了其能否在云平台上高效运行的关 键所在。以往算法并行化往往只关注多线程并局限于单机内，但云计算思维下的 并行化不同于以往模式，它注重多机间，甚至机器集群间的并行化，因此如何在 云计算平台框架下将算法并行化是一个很值得研究的问题。数据挖掘领域往往受 到海量数据等问题困扰，云计算恰好擅长处理这类问题，本论文以h a d o o p 框架为 基准，研究和探讨了四个数据挖掘算法的并行化工作，不但证实了这些算法的可 m a p r e d u c e 化，而且取得了不错的集群加速比性能，成功地解决了这些算法不能 处理大规模输入数据和计算时间过长的问题。 1 3 国内外研究现状 云计算这一概念，最初由g o o g l e 提出，到目前为止云计算在全球已经形成了 一个很大市场，全球顶级i t 厂商无不根据自身优劣势定制了相应的云计算计划， g o o g l e 于2 0 0 7 年1 0 月推出了“消费云计划口们啼1 ；i b m 于2 0 0 7 年8 月推出了 “蓝云 计划6 埘嘲踟n 阳；a m a z o n 于2 0 0 7 年推出了“弹性云 计划；微软开发 了自身的云计算平台s c o p e ( s t u r c t u r e dc o m p u t a t i o n so p t i m i z e df o rp a r a l l e l e x e c u t i o n ) 署口推出了m i d o r i 计戈0 n 别；s u m 推出了n e t w o r k c o m 计戈0 禾口b l a c kb o x 计划；y a h o o 则以支持开源的方式展开自己的云计算计划；从以上不难看出全球 i t 巨鳄无不想从云计算浪潮中分得一杯羹，其中以g o o g l e 做得最为出色，从其 对全球搜索的强大处理能力不难看出其采用云计算所取得的良好效果。国内，近 两年云计算也是炒得风声水起，许多看到云计算前景的企业和研究机构纷纷在云 计算方面立项，希望赶上这波热潮。除了i b m 、m i c r o s o f t 和g o 0 9 1 e 等国际巨头 已经在中国布局云计算业务外，许多国内企业也在布局云计算，清华大学于2 0 0 4 年前后提出的透明计算平台n n 们；广东电子工业研究所于2 0 0 8 年1 1 月宣布要建 国内第一个云计算平台n 引；2 0 0 8 年初i b m 与无锡市政府合作建立了无锡软件园云 计算中心n 们；2 0 0 8 年7 月份瑞星推了“云安全”计划n7 1 ；另外包括中国移动在内 的电信运营商也都纷纷布局云计算。 虽然国内有关云计算的资料不少，但是真正非常系统详细地介绍云计算平台， 以及深入地分析、改造传统算法使之能够高效地在云平台上运行的资料仍然很少 甚至没有。云计算的引入可以使数据挖掘领域不少问题迎刃而解，但是怎样将相 应算法并行化是个需要解决的关键问题，传统的算法并行化局限于单机内，云计 算环境下的并行化则倾向于多机间，这跟传统编程模式有着根本的不同；而且许 3 电子科技大学硕士学位论文 多数据挖掘算法本身较复杂，将之并行化需要较深入的研究，综观起来，目前较 少有人做这方面的工作。 1 4 论文研究内容及章节安排 本论文采用的研究方法主要是理论研究与实证研究相结合，首先在文献阅读 和项目实践的基础上，详细分析了现有云计算平台框架的理论原理和实现流程， 云计算框架主要包括两个最核心的部分：分布式文件系统和m a p r e d u c e 编程模 式；然后详细分析了四个数据挖掘算法的并行化过程。 数据挖掘算法很多，由于文章篇幅有限，这里只从中选取基于网络日志的中 文热点话题提取算法、协同过滤算法、局部线性回归算法和朴素贝叶斯算法的并 行化进行了分析和阐述。本论文主要创新点如下： ( 1 ) 提出了一种基于网络日志的中文热点话题提取算法； ( 2 ) 提出了一种将上述热点话题提取算法m a p r e d u c e 化的方法； ( 3 ) 提出了一种将传统协同过滤算法m a p r e d u c e 化的方法； ( 4 ) 提出了一种将传统局部线性回归算法m a p r e d u c e 化的方法； ( 5 ) 提出了一种将传统朴素贝叶斯算法m a p r e d u c e 化的方法。 本论文的结构共分六章。 第一章是引言部分。第二章介绍了分布式系统中的一些关键技术并详细讲解 了部分现有云计算平台框架。第三章，创新性地提出了一种基于网络日志的中文 热点提取方法，并且将之并行化后在h a d o o p 平台上运行取得了不错的运行效率和 实验效果。第四章则阐述了协同过滤算法，并详细描述和分析了其m a p r e d u c e 化 的过程和结果。第五章阐述了局部线性回归算法，并详细描述和分析了其 m a p r e d u c e 化的过程和结果。第六章阐述了朴素贝叶斯分类算法，并详细描述和 分析了其m a p r e d u c e 化的过程和结果。第七章是结论和展望。 1 5 本章小结 本章介绍了课题背景、研究目的和意义，并详细介绍了云计算框架及数据挖 掘算法m 印r e d u c e 化的研究和发展状况，为本论文的深入研究打下基础。此外在 本章未还给出了本文的主要研究内容及论文章节安排，便于快速了解本论文研究 的主要内容和结构安排。 4 l i l 、 第二章云计算平台介绍与分析 第二章云计算平台介绍与浅析 云计算虽然是近年才提出来的新概念但却不是突然冒出来的新东西，它是分 布式计算的延伸和拓展，并行和分布是云计算的关键，分布式存储和分布式计算 是分布式系统的两大核心。本论文所讲的分布式系统是指分布式软件系统，或者 说是支持分布式处理的软件系统，分布式系统设计的最根本目的是要将大规模任 务分割成许多小规模任务，再将细分后的小任务分散并行处理，最后将所有小任 务产生的结果归约后作为初始大任务的最终结果。简单地说分布式系统遵循：大 任务任务分割分散并行处理归约分结果输出最终结果这一抽 象流程。分散存储和并行计算是上述过程的重头戏。故本章将主要从分布式文件 系统和分布式并行计算模式两个方向对g o 0 9 1 e 分布式系统、a p a c h e 开源分布式 框架h a d o o p 和n c d m ( n a t i o n a lc e n t e rf o rd a t am i n i n g ) 开源分布式框架 s e c t o r s p h e r e 作详细的介绍与分析。 2 1g o o gle 云计算平台介绍与分析 g o o g l e 有为外人所熟知和大为称道的“g o 0 9 1 e 三宝”：g o o g l e 分布式文件系 统“g f s 【18 1 、g o o 哲e 分布式数据库b i g r a b l e 【1 9 和g o 0 9 1 e 分布式算法模型 “m a p r e d u c e 算法【2 0 】。g 0 0 酉e 三宝是其云计算平台的重要支撑，或者说它们本 身就是g o o g l e 云计算的重要平台。 2 1 1g o o gie 文件系统g f s 2 1 1 1g f s 简介 g f s 是g o o g l ef i l es y s t e m 的简称，它是g o o 西e 针对自身迅速增长的数据处 理需求，设计并实现的。g f s 是一个可扩展的分布式文件系统，主要针对大型的、 分布式的和大量数据进行访问的应用。它运行于廉价的普通硬件上，不但能为大 量的用户提供总体高性能的服务，也有可靠的容错功能。至今只有g o o g l e 在数据 中心维护上开发了文件系统这种十分底层的技术，有了自己的文件系统，g o o 西e 就可以有效的组织庞大的数据、服务器和存储，并用它们工作。 5 电子科技大学硕士学位论文 g f s 之前出现过的分布式文件系统也一样拥有高性能、可扩展性、可靠性和 可用性。但是，g f s 在设计过程中更多地融入了现有应用特性和技术环境的因素， 也包括将来可能出现的，他们仔细地考察过传统文件系统的利弊，并且在设计中 深入研究了各种不同方案，因此g f s 与之前的分布式文件系统设计还是有着显著 的不同。 2 1 1 2g f s 文件系统结构功能 g f s 文件系统采取分布式结构，是一个具有高度容错性的网络文件系统，主 要由一个m a s t e r ( 控制器) 和众多c h u n k s e r v e r ( 从设备或者块服务器) 组成，体 系结构大致如图2 1 ： 说明：- _ _ _ _ 。! 代表数据信息代表控制信息 图2 1g f s 体系结构图 下面简单描述一下g f s 文件系统工作的大致过程： 1 客户端先将应用程序指定的文件名和字节偏移转换成文件的一个固定大小 的块索引，然后向m a s t e r 发送一个包含此块索引和对应文件名的请求。 2 m a s t e r 接收客户端请求，并向相应块服务器发出指示，同时时刻监控众多 c h u n k s e r v e r 的状态。c h u l l l ( s e n ，e r 缓存m a s t e r 传来的文件名和块索引等信息。 3 m a s t e r 通过和c b l m k s e r v e r 的交互，向客户端发送c h u l l l ( - h a i l d l e 和副本位置。 其中文件被分割成若干个块，每个文件块都由一个固定且全局唯一的6 4 位 c h u n k - h a n d l e ( 块句柄) 标识。为保证数据安全，每个文件块都要被复制到多个 c b 硼k s e e r 上，一般默认3 个副本。 6 魁 k 、 句柄 g f s 支持多用户访问，c l i e n t 和m a s t e r 之间采用应答式的命令控制方式， m a s t e r 处于控制中心的地位，它会保存三类元数据( m e t a d a t a ) ：文件名和块的名 字空间、从文件到块的映射、副本位置，它负责向c l i 饥t 发送命令，控制整个集 群系统内任务的分配和数据的流通，协调着整个集群的运行。g f s 对于数据的处 理尽量采取就近或者本地化的原则，这样能够极大地减少数据在应用程序和 c h u n k s e r v e r 之间的移动，有效减少m a s t e r 的负担和对网络资源的消耗。另外，除 了控制数据和元数据，其它数据从来不会流经m a s t e r ，c l i e n t 只向m a s t e r 询问数 据的姿态信息及接受m a s t e r 的指令，它直接通过和c h u n k s e n ，e r 的交互完成读写 操作。再者，g f s 还引入了日志机制、文件备份机制，通过这些机制g f s 可以有 效地容错和实施系统恢复。 2 1 2g o o gie 的big t a bie b i g t a b l e ( b t ) 的是针对分布存储大规模结构化数据设计的，从设计上它可以 扩展到2 5 0 字节，分散存储到上千甚至上万台普通机器上。g o 0 9 1 e 在b t 上存储 海量数据的成功案例很多，这其中广为人知的有：网页查询、g o o 西e 地图和g o 0 9 1 e 金融。应用程序对数据大小、反应速度等方面的要求各不相同，对此b t 都成功 的提供了灵活高效的服务。 b t 采取了很多与数据库类似的实现策略，它的并行数据库和内存数据库具 有扩展性和很高的性能。但是b t 不支持完全的关系数据模型，它只为客户提供 简单的数据模型，客户可以自己动态控制数据的分布和格式，推断底层存储数据 的局部性。 2 1 3m a p r e d u c e 编程模型 m a p r e d u c e 表面上看是g o 0 9 1 e 公司的一项极负盛名技术，其实在实质上来 说它是一种编程模型，亦或者说是一种计算模型，它的设计初衷与处理及产生海 量数据集的实现有关。目前业界对于大规模数据和计算的处理方法，通用的方式 是采取并行计算，g o o g l e 也不例外，它将复杂的运行于大规模集群上的并行计算 过程高度的抽象成两个函数：m a p 和r e d u c e ，抽象过程简单，但却威力巨大。 m a p 瓜e d u c e 编程模式下需要把工作流划到大量的机器上去，它采取的具体的 7 电子科技大学硕士学位论文 方式是将大型分布式计算表达为一个对数据键值对集合进行串行化分布式操作。 m a p 瓜e d u c e 首先将用户定义的m a p 瓜e d u c e 任务分发到计算机集群中的每个块服 务器上，然后每个块服务器并行处理自己的任务，并行处理后得到的结果会被收 集作进一步的计算后得出最终结果。一个m a p 瓜e d u c e 计算包括两个阶段，m 印 阶段和r e d u c e 阶段。所有计算的输入都采取键值对数据集合的形式。 m 印阶段，m 印r e d u c e 模型将输入数据集合拆分为若干数据片段，并将每 一个数据片段对应分配给一个m a p 任务，每一个m a p 任务对应分配给集群中运行 的某一个块服务器。每一个m a p 任务对其分配到的键值对( k ，调用用户自定 义的m a p 函数进行计算后生成相应的中间结果键值对集合m ( k l ，v 1 ) ，( k 2 ，v 2 ) ， ( k 3 ，v 3 ) ( k i ，v i ) 。 然后，m a p 瓜e d u c e 模型会将中间结果键值对集合m ( k l ，v 1 ) ，( k 2 ，v 2 ) ， ( k 3 ，v 3 ) ( k i ，v i ) ) 进行排序产生一个新的二元组( k ，矿水) 集合，新集合中所有对 应键的相同值被归类在一起，同时二元组集合也会被划分出和r e d u c e 任务数量相 同的片段数。 r e d u c e 阶段，二元组，矿木) 集合的片段将作为每一个r e d u c e 任务的输入， 经过一个用户定义的r e d u c e 函数处理后生成一个输出的键值对( k ，v ) 。 m a p r e d u c e 框架最后会再一次将集群中所有节点上的r e d u c e 任务生成结果进行 分发处理形成最终输出结果集合。 2 2 开源云计算平台h a d o o p 介绍与分析 h a d 0 0 p 最早是作为一个开源搜索引擎项目n u t c h 的基础平台而开发的，后来 发展成a p a c h e 的一个单独顶级开源项目，采用j a v a 编写。h a d o o p 平台拥有自己 的分布式文件系统( h d f s ) ，具体实现采用m a p r e d u c e 模式。h a d o o p 采取文件备 份的方式，为每份数据制作若干拷贝拥有较高的安全可靠性。 作为一个开源的分布式系统平台，h a d o o p 除了拥有开源所带来的更新速度 快、应用广泛等优势外，还具有以下一些其它分布式云计算框架所共有的优点： 高度的可扩展性、经济实用性、高速有效性、高可靠性。 2 2 1h a d o o p 分布式文件系统概述 h a d o o p 分布式文件系统d f s ) 是一个设计为用在普通硬件设备上的分布 式文件系统。它与现有的分布式文件系统有很多近似的地方，但又和这些文件系 i 、 k 、 第二章云计算平台介绍与分析 统有很明显的不同：h d f s 被设计为部署在廉价硬件上，拥有较高的容错性；h d f s 对应用程序数据提供高吞吐量，而且适用于大数据集应用程序；h d f s 开放了一 些p o s 的必须接口，容许流式访问文件系统的数据。h d f s 最初是为了a p a c h e 的n u t c h 网络搜索引擎项目的下层构件而设计的，最后发展为h a d o o p 项目的一 部分，该项目的地址是：h t t p ：p r o j e c t s a p a c h e o 嘶r o j e c t s h a d o o p h 缸】 1 l 。 2 2 。2h a d o o p 分布式文件系统( h d f s ) 详解 下面将依据h a d o o p 官方网站上公开的文档和源码，对h d f s 的整体架构和 主要设计思路进行研究和分析，同时也将探讨其在实现上的优缺点。 2 2 2 1 f 段设和目标 ( 一) 硬件错误 硬件错误是正常的，而不是异常。h d f s 集群由成百上千个服务器组成，每 个都存储着文件系统的一部分数据。系统内每个组件出故障的可能性都很大，也 就说h d f s 总有一些组件可能是不能工作的。所以，检测错误并快速自动恢复就 成了h d f s 的核心设计目标。 ( 二) 流式数据主访问 运行在h d f s 上的应用程序需要流式的访问它们的数据集，它们也不是通常 运行在普通文件系统上的普通应用程序。h d f s 针对批量处理而设计，它更强调 数据访问的高吞吐量而非数据访问的低反应时间。所以有些应用程序上不需要的 p o s 语义被牺牲用来提高数据的吞吐率。 ( 三) 海量数据集 运行在h d f s 上的应用程序使用大数据集。h d f s 一个典型的文件可能是几 g b 的或者几t b 的。因此，h d f s 适用于大文件。这将提供高集成带宽，并在一 集群中提供成百上千个结点。一个实例可能支持上千万个文件。 ( 四) 简单一致性模型 h d f s 遵循“一次写，多次读 的原则。文件一旦建立后写入，文件就不需 要再被更改。这样的假定简化了数据一致性问题并使高数据吞吐量成为可能。 m a p r e d u c e 程序或者网络爬虫程序就很适合使用这样的模型。当然未来计划支持 增量写。 ( 五) 移动计算而非移动数据 直接在数据的旁边执行对数据的操作，执行效率会很高效，海量数据尤其如 9 电子科技大学硕士学位论文 此。这可以减少网络的拥塞和提高系统的吞吐量。这也意味着，移动计算比移动 数据更高效。 ( 六) 可移植于异构硬件和软件平台 h d f s 的设计很便于从一个平台移动到另一个平台。这有助于h d f s 被采用 做为一个大程序集合的工作平台。 2 2 2 2 命名节点和数据节点解析 h d f s 是主从结构的。一个集群只有一个命名节点，它是主控制服务器，负责 管理文件系统的名字空间并协调客户对文件的访问；有若干数据节点，一般一个 物理结点上部署一个，负责所在物理结点上的存储管理。h d f s 文件系统内部一个 文件被分割为一个或者多个指定大小的数据块，这些数据块存储在一组数据节点 中。命名节点执行文件系统的名字空间操作，比如打开、关闭、重命名文件或目 录，还决定数据块从数据节点的映射。数据节点负责提供客户的读写请求。数据 节点还依照命名节点的指令执行数据块的创建、删除和复制工作。 7 一，7 机架1 ， 图2 2 h d f s 结构图 命名节点