（教育技术学专业论文）基于mapreduce的网络书写纹识别关键技术研究.pdf

硕士学位论文 m a s t e r st h e s i s 摘要 网络书写纹是指用户在网络文字中留下的具有独特写作风格( 如用词习惯、语 法结构等) 的特征集合。网络书写纹就像人的指纹一样，是可以标记作者写作特征 的独一无二的标识符。随着研究的深入，作者数量增加，需要处理的总体数据规模 也相应增加，另外，研究中还发现，在程序运行过程中，计算机的内存、c p u 等资 源并没有得到充分的利用。本文尝试对网络书写纹识别研究中的数据处理关键算法 并行化，以期能够充分利用计算机资源，提高数据处理的效率。 n 蹦l m 是指给定一个序列的文本，根据n 值选择等长或变长的连续子序列。研 究证明，基于n 蓼锄特征的抽取是构建网络书写纹个体特征集的重要技术，提高数 据处理效率是n 肝锄特征抽取过程需要解决的重要内容。本文设计h a d o o 洲鲜衄 算法，并在h a d 0 0 p 集群上实现，实验结果表明，相对未并行化的n 龋啪特征抽取， h a d o o p n 醇u n 在文本数据的处理效率上有所提升，同时，c p u 、内存等资源的利 用率也有所提高，计算机资源得到较充分的使用。在实验中，还通过配置h a d o o p 通用参数选项来比较数据的处理效率，实验证明，根据处理任务的规模和特点灵活 的配置h a d o o p 通用参数，可以使算法的运行效率进一步提高。 基于特征选择的集成学习( 简称集成特征选择) ，是构建网络书写纹分类模型 的重要技术，它首先对特征集合进行选择，去除冗余和无效特征，然后按照一定的 划分算法对特征集进行划分，将划分好的特征子集分配到个体分类器，由个体分类 器处理特征子集，最后将各个体分类器的结果汇总得到分类模型或分类结果。在利 用集成特征选择构建分类模型的过程中也面临数据量增加，数据处理效率不理想的 问题。基于此，本文设计基于m 印r e d u c e 的集成特征选择算法h a d 0 0 pfe n s e m b l e 。 实验结果表明，h a d o o pfe n s e m b l e 执行时分类模型的构建效率也有所提高，系统 资源也能得到较充分的利用，通过h a d o o p 通用参数选项的调整，实现的效果会更 加良好。这说明，将m 印r e d u c e 应用于网络书写纹识别研究是有意义的。 关键词：网络书写纹；n g r a m ；m a p r e d u c e ；集成学习 硕士学位论文 m a s t e r st h e s l s a b s t r a c t n e 晰o d ( 州t e p r i n tr e f i e 娼t 0f e a t u r es e to ft i l eu s e r s 岫i q u ew r i t i n gs t ) ，l el e f ti n 廿l e n e t 、) i ，o r kt e x t ( s u c h 嬲aw o r du s a g eh a b i t 萨a m m a rs 劬j c t u r e ) n e t w o r kw r i t 叩r i n t 啪b e l a b e l o d 觞a n 砒o r su n i q u ei d e n t i 6 e ro fo n e sw r i t i n gd l 赳a c t e r i s t i c s ，j u s tl i k e e s f i n g e 巾r i n t s w i t l l 廿l ed e 印e n i n go ft 1 1 er e s e 鲫c h ，t l l en u m b e ro ft l l ea u t l l o ri l lr e s 髓r c h i n c r e 嬲e s ，t h et o t a ld a 舾s i z en e e dt 0b ed 既l e dw i ma l s 0 协c r e 舔e s ，廿l et i m es p to nd a t a p r o c e s s i n gb e g i i lt oh i n d e rt h ep r o g r e s so ft l l es t u d y h la d d i t i o 玛w ea l f o 蛐dt l l 鸸i 1 1 t i l ec o u r s eo f 姗n i n gt h ep r o g 舳，t 1 1 er e s o u r c e ss u c h 私m e m o 巧a i l dc p uh a v en o tb e 伽 向l l y u t i i i z e d t h i sp a p e ra t t e m p t st o s t u d ym ek e y 咖p l c e s s i i l ga 1 9 0 r i t l l m s p a r a l l e l i z a t i o n ，i no r d e ：r t om a l ( e 如l li 塔eo f 廿l ec o m p m e rr e s o u r c e st 0i n l p r 0 v et h e e m c i e n c yo f 纰p 帕c e s s i n g n 铲锄r e f e r st l l a tg i v 朗as e q u 钮c eo f 锄鸡t 0g e tt l l ec o t i i l u o 邺s e q u e n c ci i l i s o m 嘶co ro fv 撕a b l el e n g t l l a st l l er c s e a r c hs h o w s ，n g r a mf e a _ t u r ee x n 佻t i i s 锄 i m p o r 咖tt e c h n o l o g yc o n t s 仃u c t i n g m ei n d i v i d u a lc 1 1 a r a c t e r i s t i c ss e to f n e t w o f k 、砸t e p n n t i i i l p r o v i n gt h ee 伍c i e n c yo fd a t ap r 0 c e s s i n gi s a ni m p o r t 锄t 伽i n t e n ti l lm e n g m mf e a n 鹏e x 仃a “o np r o c e s s i l l l i sp a p w ed e s i 髓h a d o o p - n g 瑚na l g 耐t l i m ，锄d r e a l i z ei to n 协eh a d o o pp l a t f o m 1 h ee x p r i m 朗t sr e s u l t ss h o w s l 砖c o m p 玳d 谢m n g m m 危a t i l r ee x 仃a c t i o nt h a th a sn o tb e p a r a l l i z c d ，h a d o 删g r a mh 硒ab e t t e rd a 协 p r o c e s s i n ge 币c i e i l c y a t 廿l e 观m et i m e ，t h eu t i l i z a t i 谢t eo fc o m p u t e rr c s o u r c e ss u c h 嬲 c p ua n dm e m o 巧i sa i s oi m p r 0 v e 也t l l ec o m o 咖r e s o u r c eg e tam o r es u m c i e n tu s e i i l n l ee x p 两m e 峨w ec o m p a r et h e 咖p r o c e s s i n ge 衔c i 即c yb yc o n f i g 嘶n gt 1 1 eh a d o o p g e n e r a jp a m m e t e 瑙t h ee x p 嘶m e n t s sr e s u l ts h o w st h a tt l l ea l g o r i t l l mm 彻i n ge 衔c i 朗c y c a nb ef 吣e ri m p r o v e db yc o n f i 2 ：u r i n gt l l eh a d o 叩g 朗e r i cp a m m e t e rf l e x i b l ea c c o r d i n g t ot l l es i z e 觚dt l l ec h a r a c t e r i s t i c so f 廿l ep r o c e s s i n gt a s k e n s e m b l ei e 锄i n gb a s e do nf e a 眦l e c t i o ni sak e yt e c l l i l o l o g yc o n 咖c t i n g 廿l e c l a s s i f i c a t i o nm o d e lo fn e t 、0 r kw r i t e p r i n t i t1 f i r s ts e l e c tf e a t u r e st 0r e m o v e 廿1 er e d u n d a n t 锄di n e 氐“v ec h a m c ：t 舐s t i c s ，n l e nd i v i d e n l ef i e 孤聪s e tt 0f e 撕心s u b s e t sb y 锄 a l g o r i m m ，m ef - e a t u r es u b s e t 、o u l db ea s s i g n e dt 0i l l d i v i d u a lc l a s s i f i e rf 0 rp r o c e s s i n g ， e a c hi n d i v i d u a lc l 觞s i f i e r sr c s u l tw o u l db eo b t a i n e dt 0g e tm ef i n a lc i a s s i f i c a t i o nm o d e l o r l er e s u l t so fc l a s s i f i c a t i o n 1 1 1t h ep r o c c s sc 0 璐t 1 1 j c t i n gt i l ec l a l s s i f i c a t i o nm o d e lu s i n g ： ： 硕士学位论文 m a s t e r st h e s i s 锄m b l ef e a t u 他l e t i o i l l ei n c r e a s i n g 讹锄。眦t 锄dm el o wd a t ap r o c e s s i n g e m c i 朗c y a r ea l s o p r o b l e 眦 i tf a c e s b a u s e d m i s ， t h i s p a p 盱d e s i 趴 h a d 0 0 pfe n s e m b l e b 勰e d0 n m a p r e d u c e t h e r e s u l t ss h o wm a t u s i n g h a d o o pfe n s e m b l e ，l ec l 弱s i 6 c a t i m o d e le 衔c i e n c yi si n c r e 私e d ，s y s t e mr e s o u r c 髓 a l s ob eu t i l i z e dm o r cm l l 弘ab e t t e rp e 墒m 柚c ew o u l db es h o w nt l l l o u 曲廿1 eh a d o 叩 g e n e r i cp a r 锄舒璐a 由u s t m e n t t h i ss h 0 、sm a tn l ea p p l i c a t i o no fm 印r e d u c ci i l n e t 、釉r kw r i t 印r i n tr e c o n g n i t i o nr e s e a r c hi sm e a i l i n g m l k e y w o r d s ：n e t 、o r kw h t 印r i n t ；n g r a m ；m 印r e d u c e ；e n m b l el e 锄i i l gb 私e do n f e a t u f es e l e c t i o n 硕士学位论文 m a s t e r st h e s i s 1 1 研究背景 第1 章绪论 随着信息技术的迅猛发展和网络的普及，全球网民数量日益增加，人们可以随 时随地使用网络获取和发布信息，在网络上自由发表观点。“科学技术是一把双刃 剑，在网络技术给大家带来便利的同时，一些不法人士也利用网络平台传播不法 信息，进行非法活动。 随着“农夫果园砒霜门一、“霸王致癌门 等热门事件的陆续爆发，“网络打黑 被提出。2 0 0 9 年1 2 月，中央电视台经济半小时栏目曾专门报道“网络黑社会 【i j 的灰色产业链，揭示令人触目惊心的种种黑幕。2 0 l o 年1 0 月，网络盛传蒙牛 高管涉嫌策划诋毁伊利产品，后证明属实。该事件是当前市场恶性竞争的缩影，也 让大家看到了以“网络公关公司 为代表的“网络黑社会 的庐山真面目。 。网络黑社会”的出现在很大程度上源于互联网的开放性和隐匿性。许多网络 信息是人们匿名或变换不同的身份发布的，这使一些不法分子隐藏在网络的汪洋大 海中，在互联网上发表不法言论信息却难以得到有效的追踪。这些舆论不仅破坏网 络和谐，还会引发“网络信任危机【2 j 。 网络信任危机产生的根本原因在于用户在网络空间的责任感较弱。互联网信息 传播迅速，传播范围广泛，网络用户可以通过各种简单的手段不着痕迹的发布和转 发信息，影响社会舆论。只有提高用户使用网络空间的责任感，才能构建良好的网 络舆论环境。研究互联网反匿名技术有利于提高用户在网络空间的责任感，对创建 和谐网络环境、维护网络文化安全意义重大，基于网络信息的作者身份识别技术的 研究应运而生并逐步展开。 口地址是确定信息来源的主要技术，然而随着网络技术的发展和成熟，地址欺 骗等技术使基于i p 地址的追踪变得无效。加拿大康卡迪亚大学研究人员研究出一种 新的作者身份识别技术，这项技术可以更准确地确定匿名信息的作者，该技术被称 为“书写纹 。研究【1 2 】认为，人们在进行文字创作时会无意识的形成自己独特的写 作风格( 如用词习惯、语法结构等) ，网络书写纹i l3 j 是指网络用户在网络文字中留 下的具有自己独特的写作风格并能有效识别其身份的特征集合，即作者的个人写作 风格所构成的“书写纹 ，就像人的指纹一样，是独一无二的标识符。 硕士学位论文 m a s t e r st h e s i s 1 2 国内外研究现状 网络书写纹识别研究与语种相关，国外以英语为主，并已开展了大量的研究， 其中最具代表性的是2 0 0 7 年美国亚利桑那大学人工智能实验室启动的“黑网计划 ( d a r kw 曲p 喇e c t ) 。该计划通过收集互联网上恐怖组织、极端组织的论坛留言或网 站文字，分析其书写风格特征，来锁定与识别互联网匿名仇恨言论的作者，以达到 互联网反恐的目的【l ”5 ，1 6 】。网络书写纹识别研究设计数据收集、特征抽取、分类模 型构建和识别实验几个阶段。下面主要针对网络书写纹识别研究中的特征抽取和分 类模型构建两个方面进行现状分析： ( 1 ) 网络书写纹特征抽取阶段 特征集的抽取是网络书写纹识别研究的重要内容，特征集的质量直接影响网络 书写纹识别的效果。关于网络书写纹特征集，当前研究主要围绕语言、结构和格式 等方面。特征集的研究以语言类特征研究较多，包括字母、数字、标点等多种字符 类特征，另外还有n 舻釉字符特征以及n 目锄词汇特征等。在所有风格特征中， 字符n 料锄特征类型被证明是在作者身份识别研究中最有效的可代表文本的风格 特征。k e s e l j 等人【l7 l 在英语，希腊语以及中文语言中使用n g r a m 特征取得了超过以 往研究的很好的识别效果。为了研究和抽取具有鉴别性的多样性风格特征， h o u v 鲫d 弱，j 与e s t 锄a t a t o s1 1 8 j 结合变长的n g 豫i n s ( n - 2 ，3 ，4 ) 字符特征集，在r c v l ( r e u t e r sc o r p i i s l 啪e1 ) 数据集的子集识别实验，取得了比词汇更好的效果。 n 辩衄数据集维数高、数据量大，在数据集较少的情况下，n g r a m 特征抽取的效率 可以满足需求，但是，随着作者数量和文本数量的提高，n j 驰m 特征抽取开始变的 耗时。 ( 2 ) 网络书写纹分类模型构建阶段 从机器学习的角度，网络书写纹的模型构建是一个多类别单标签的文本分类问 题，基于分类技术的网络书写纹识别技术一直是该领域的研究热点。根据是否基于 i l e f ( i n d i v i d 岫ll e v e lf e a t u r es e t ) 类型特征集结构，可分为单分类器和以集成学 习为代表的多分类器技术。神经网络【聊、决策树卿、线性判别分类器f 1 8 】和支持向 量机( s v m ) 【3 雕1 2 2 1 等主流单分类器技术都曾被用于网络书写纹识别研究，多个实 验研究表明1 2 0 2 1 2 3 1 ，s 订是该领域具有最佳识别性能的单分类器。但当待识别作者 数增加时，以s v m 为代表的单分类器的识别性能下降幅度较大，分类模型的可伸 缩性有待进一步提高。文献【2 4 】提出了一种通过随机划分特征空间构建集成学习的方 法e d s ( e x h a u s t i v ed i 硒o i n ts u b s p a c i n g ) ，在划分粒度较小的情况下取得了比支持 2 硕士学位论文 m a s t e r lst h e s i s 向量机( s v m ) 更好的识别效果，多分类器应用于网络书写纹的研究由此展开。经 过前期特征抽取得到的数据，其数据量比数据集大很多，相应的，模型构建阶段需 要处理的数据量也增大。目前网络书写纹识别研究中，作者类别的数量还比较少， 每个作者类别的文本数据集也比较少，识别模型的可伸缩性有待增强。数据处理效 率在很大程度上影响网络书写纹识别研究的进展。 针对网络书写纹的特征抽取、分类模型构建环节中数据处理效率的问题，主要 的解决方法是通过将问题进行并行化设计和实现，并在集群上运行，以实现数据处 理效率的提高。 1 3 研究意义 通过对网络书写纹的研究现状进行分析，发现网络书写纹的研究主要集中在提 高识别系统的效果和性能上，然而随着研究的深入，需要处理的数据规模增大，数 据处理效率不理想，间接影响了研究的进度；另外，还发现，在数据处理过程中， 计算机c p u 、内存等资源的使用效率却不高，系统资源没有得到充分的利用。 并行化技术是提高数据处理效率的重要技术。随着并行处理技术的发展，越来 越多的研究使用并行处理的方法来提高数据的处理效率。典型的处理方法是将数据 集划分成多份子集，将数据子集发送到单机，在各个单机处理器上对数据进行分别 处理，最终的结果通过将单机上的各运算结果进行汇总得到，采用并行模式处理数 据，数据运算和算法效率的提高是其最明显的特征。在对任务并行设计化之前要对 算法和程序本身进行并行化分析，考虑任务的特性，另外还要对并行体系结构的特 点加以考虑，以选择合适的硬件和软件平台平台，使设计既能满足实际的需求，又 能体现并行结构的高效性。 m p i ( m e s s a g ep 勰s i n gi n t e r f a c e ) 消息传递编程模型是一种传统的并行方法，具 有简单易用的特点；并行虚拟计算机( p ，p 锄l l e lv j n l l a lm a c h i n e ) 也是一种并 行方法，在负载均衡和容错性上均具有优势。然而，这两种并行思想的抽象度比较 低，用户需要了解并行细节才能够有效的使用。 m a p r e d u c e 编程模型是由g o o g l e 实验室提出的，底层对数据分割、任务分配、 并行处理、容错等细节问题进行了封装，用户不必了解内部细节，只需将精力集中 在需要解决的并行计算任务上，使用方便，大规模数据集的处理可以用m a p r e d u c e 在集群上来处理。2 0 0 9 年，n s f ( n a t i o n a ls c i e n c ef o u n d a t i o n ) 在h a d o o p 上实现了 包括图像挖掘、基因组序列、机器翻译、网格数据分析、文本挖掘、图像分析和天 文学【2 0 j 的多个m a p r e d u c e 应用。 3 硕士学位论文 m a s t e r st h e s l s g o o g l e 的m a p r e d u c e 软件应用没有对外开源，h a d 0 0 p 提供了开源的m a p r e d u c e 并行计算框架，同时也研发了h d f s ( h a d o o pd i s t r i b u ：t i e df i l es y s t 锄) ，与g 0 0 9 l e 的g f s ( g 0 0 9 l ef i l es y 啦m ) 对应，m a p r e d u c e 已经成为最受关注的技术之一。 目前，m a p r e d u c e 并行编程模型应用到包括数据挖掘和文本分类的各个领域， 并取得了不错的成效。论文1 2 5 】实现了包括朴素贝叶斯、主成分分析在内的数据挖掘 算法，并提出了使数据集交互大大加快的方法，使数据流挖掘的可伸缩性大大提高。 论文1 1 9 j 实现了包括局部加权线性回归，逻辑回归，朴素贝叶斯，支持向量机，独立 分量分析，主成分分析，高斯判别分析等在内的多个算法。研究【4 5 l 利用m a p r e d u c e 实现了并行化的朴素贝叶斯算法，并且实验结果证明，并行化的朴素贝叶斯在大规 模数据集的处理上具有良好的加速比，研究1 5 】还对文本统一格式预处理、训练以及 测试分类过程进行了详细的并行化。 通过对m a p r e d u c c 的应用现状分析，发现通过将算法m 印r e d u c c 化来实现算 法执行效率的提高是有效的，可以考虑将m a p r e d u c e 应用于网络书写纹的研究，以 提高研究中的数据处理效率。另外还发现，目前m a p r e d u c e 的应用研究都是在比较 大的集群上实现的。本文在单机上用v i w a r e 虚拟出三台l i n u 】【系统来搭建h a d o o p 集群，实现n 蓼a m 特征抽取和集成特征选择的并行化，并对并行化和费并行化两种 情况下的实验数据进行分析，考察在同等资源的情况下，并行化能否提高系统资源 的使用效率以充分利用有限资源。 1 4 研究内容与组织结构 本文的主要任务是在h a d o o p 集群上实现n 鲫特征抽取和集成特征选择算法 的并行化，另外还对并行化和非并行化两种情况下的资源使用情况进行考察和分 析。基于此，本论文的主要研究内容有： ( 1 ) 研究m a p r c d u c e 并行编程模型，并对已有的m a p r c d u c e 程序进行分析， 为并行化n g 姗特征抽取和并行化集成特征选择的实现提供参考。 ( 2 ) 研究n 鲫n 特征抽取算法和集成特征选择算法，并对其进行并行化设计 和实现。 ( 3 ) 另外研究h a d o o p 集群上资源使用的特点并对h a d 0 0 p 通用参数选项进行 分析，并通过灵活配置h a d 0 0 p 通用参数选项来优化算法效率。 本文分为五章，章节内容安排如下： 第l 章绪论。主要介绍网络书写纹识别的研究背景，网络书写纹的研究现状 以及m 印r e d u c e 应用现状，然后详细描述了本文的研究内容和主要工作，最后对论 4 硕士学位论文 m a s t e r st h e s i s 文的组织结构进行说明。 第2 章m 印r e d u c e 及相关技术介绍。首先对m 印r c x l u c e 这一高性能并行计算 模型的编程模式和实现框架进行了介绍，然后详细描述了h a d o o p 分布式文件系统 中，最后分别对影响h a d 0 0 p 实验结果的h 蜘和通用参数选项进行了相关分析。 第3 章基于m 印r e d u c e 的n 鲈l m 并行化研究。本章主要针对n 掣锄特征抽取 技术进行并行化设计和实现，提出h a d 0 0 p n 舻衄算法，并进行实验，对并行化和 非并行化两种方式下的效率和资源使用情况进行分析和比较。 第4 章基于m a p r e d u c e 的集成特征选择。本章首先对模型构建中的集成特征 选择技术进行分析，然后对其进行并行化设计，提出h a d 0 0 pfe n s e m b l e 算法，最 后进行实验，比较同一算法在不同平台上的实验数据，分析算法性能。 第5 章总结与展望。本章属于结论部分，主要对文章中提出的两种并行化算 法思想进行总结，并提出进一步需要研究的内容。 5 硕士学位论文 m a s t e r st h e s i s 第2 章m a p r e d u c e 及相关技术介绍 2 1m a p r e d u c e 相关技术介绍 m a p r e d u c e 的历史要追溯到1 9 5 6 年，图灵奖获得者著名的人工智能专家j o h n m c c a n l l y 首次提出了“s t 语言的构想，“s t 语言是一种用于人工智能领域的语言， 而在l i s t 语言中就包含了现在我们所采用的m a p r e d u c e 功能。5 0 年后g o o g l e 借用 m a p 胝d u c e 这一思路，将m a p 依e d u c e 作为进行大规模数据集并行运算的一个软件 框架，并取得了巨大的成功。 2 1 1m a p r e d u 编程模型 m a p r e d u c e 通过将任务划分为多个子任务，并调度集群中的闲置节点来使数据 得到高速处理，然后再通过一定的规则将各节点结果进行合并得到最终的处理结 果。 从名称上看，m a p 瓜e d u c e 可以分为“m a p 和“r e ：d u c e 两个过程。m a p r e d u c e 编程模型6 】的基本思想是：将要执行的问题拆解成m a p ( 映射) 和r e d u c e ( 规约) 两种操作，即先通过m a p 程序将数据切割成不相关的区块，分配( 调度) 给大量计 算机处理达到分布运算的效果，再通过r e d u c e 程序将结果汇总，输出开发者需要 的结果。 曰 图2 1m a p r e d u c e 中单一r e d u c e 任务的数据流图 6 竺 母母母 一 团团固 硕士学位论文 m a s t e r st h e s l s 图2 2 多个r e d u c e 任务的m a p r e d u c e 数据流图 以m a p r e d u c e 作业在h a d 0 0 p 平台中为例：客户端执行的单位是m a p r e d u c e j 0 b ，即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 任务， h a d o o p 通过将作业划分成若干此类小任务( t a s k ) 来完成作业的执行。输入数据会 被划分成等长的小数据，我们称这些小数据为分片( s p l i t ) ，然后h a d 0 0 p 会把这些 数据分片发送到m a p r e d u c e ，对应每一个分片( s p l i t ) 都会相应的有一个m a p 任务 被创建，分片中的每一个记录都由用户自定义的m a p 函数来分析，r e d u c e 接收m a p 任务的中间结果会作为输入，然后将结果进行汇总，产生最后的结果【2 6 1 。 2 1 2m a p r e d u c e 数据类型与控制节点数据结构 ( 1 ) m a p r e d u c e 数据类型 m a p r c d u c e 的数据模型很简单：m a p 和r c d u c e 函数使用键值对( k e y v a l u e ) 进 行输入和输出。h a d o o pm 印r e d u c e 中的m a p 和r e d u c e 函数遵循以下格式： m a p ：( k 1 ，v 1 ) 专l i s t ( k 2 ，v 2 ) r e d u c e ：( 1 ( 2 ，l i s t ( v 2 ) )专l i s t ( 1 【3 ，v 3 ) 一般来说，m a p 函数的输入键值对( k l 和v 1 ) 类型与输出的( k 2 和v 2 ) 的类 型不同，m a p 函数的中间结果作为r e d u c e 函数的输入，故而两者的类型应该想匹配 同时，r e d u c e 函数的输入类型与输出类型有可能与上述两者都不同。 ( 2 ) 控制节点的数据结构 控制节点是一个管道，将一个m a p 任务产生的中间结果传送到r e d u c e 任务节点， 每个m a p 任务和r e d u c e 任务都需要保存其当时的状态( 闲置、处理中、已处理) ， 对于已处理的m a p 任务，控制节点保存其生成的中间结果文件的位置以及大小等信 息；当m a p 任务完成时，控制节点会自动将其生成的中间结果信息保存并传送到处 于运行状态的r e d u c e 节点上。 7 回 回 - 日日 芝， 母母母 - 一 一 一 回目曰 硕士学住论文 m a s t e r st h e s i s 2 1 3 容错机制 m a p r e d u c c 程序运行在大规模集群上，集群一般是由多个普通计算机搭建而成 的，m a p r e d u c e 函数要在集群上处理大规模数据，集群中各结点失效导致的容错性 必须考虑在内。在分布式集群中，节点失效被认为是一种正常的状态，结点分为控 制节点和工作节点，控制节点定时p i n g 集群中其他的工作机器，控制工作节点的状 态和信息。节点失效有一下几种情况： ( 1 ) 控制节点失效 控制节点失效，造成的问题是很严重的，控制节点会定期检查工作节点。处理 控制节点失效的一般方法是同时终止m 印r e d u c e 运行，客户可根据需要重新启动所 需操作。一般情况下会设置一个备用的控制节点，当主控制节点失效时，会启动备 用控制节点。 ( 2 ) 工作节点失效 控制节点在一定时间内没有得到某工作节点的响应，则该工作节点会标记为失 效，m a p r e d u c e 可以容忍一定限度的节点失效，其控制模式会把失效的工作节点上 的任务重新执行，继续调度至任务完成。当工作节点失效时，若这台机器上的m a p 任务完成，则会由于m 印产生的中间结果保存在该机器上无法被其他节点获得而使 任务在其他机器上重新执行；若咖任务已经完成，则任务不需要重新执行，因 为r e d u c e 产生的中间结果以全局数据类型保存在系统中。 2 2h a d o 叩分布式并行计算平台 2 2 1h a d o o p 分布式文件系统 h a d o o p 最初是搜索引擎项目n u t c h 的一部分，目前已经成为a p a c h e 的顶级项 目，是m 印r 舭和g f s 的开源j a v a 实现。h a d o o p 目前由h d f s 、m a p r e d u c e 、 h b a s e 、h i v e 和z o o k e 印e r 等成员组成，其中，h a d 0 0 p 分布式文件系统( h d f s ， h a d o o pd i s 仃i b m e df i l es y s t 锄) 和m a p r e d u c e 是两个最基础最重要的成员。 8 硕士学位论文 m a s t e r st h e s i s 图2 3h d f s 架构示意图 h d f s ( h a d o o pd i s t r i b u t e df i l es y s t e m ) 是以流式数据访问模式存储超大文件 而设计的文件系统，在商用硬件的集群上运行。其中“超大文件”是指几百m b 及 以上大小的文件；“商用硬件”是指普通硬件，这里的普通硬件并不是指是次品或 质量差得硬件，只是说明h a d o o p 不需要运行在昂贵并且可靠性高的硬件上。 图2 - 3 为h d f s 架构图，从图2 3 中我们可以看到h d f s 集群有名称节点 ( n a m e n o d e ) 和数据节点( d a t a n o d e ) 两种节点，以管理者一工作者( m a s t e r s l a v e ) 的模式运行，即一个名称节点( 管理者m a s t e r ) 和多个数据节点( 工作者s l a v e ) 。 ( 1 ) 块：一个磁盘有它的块大小，代表着它能够读写的最小数据量，文件系 统块一般为几千字节，而磁盘块一般为5 1 2 字节，h d f s 的块是更大的单元，默认 为6 4 m b 。在h a d o o p 分布式文件系统中块的单元比磁盘的要大，其主要原因是为 了减少寻址开销。在分布式文件系统中使用抽象块的优势在于两个方面：一方面系 统可以储存比集群中任意磁盘容量大得多的文件，文件的所有分块的副本不需要存 储在一个磁盘中；另一方面使用块抽象单元而不是文件会简化存储子系统，存储子 系统控制的是块，简化了存储管理。 ( 2 ) 副本：为了应对损坏的块以及磁盘或者机器的故障，每个块都在少数其 他分散的机器( 一般为3 个) 进行复制，这些被复制的块被称为副本。如果一个块损 9 硕士学位论文 m a s t e r st h e s i s 坏了，系统会在其他地方读取另一个副本，而这个块也会从其它候选地点复制到正 常运行的机器上以保证副本的数量回到正常水平。 ( 3 ) 名称节点：其主要任务是管理集群文件系统的命名空间，集群文件系统 树以及所有书内的文件和索引目录也由名称节点来维护，名称节点以命名空间镜像 和编辑日志两种形式来储存信息，并在本地磁盘上将信息文件保存。名称节点还记 录着所有文件的每个块和副本的数据节点，但是块的位置并没有被保存，这是因为 在系统启动时，数据节点会重建该信息。 ( 4 ) 数据节点：d a t 卸o d e 是文件系统的工作者，它们存储并提供定位块的服 务，并且定时向名称节点发送它们存储的块列表。 2 2 2h a d o o p 调度器 在h a d o o p 平台下，可同时运行多个作业，甚至不同类型的作业，且作业之间 还存在着某种依赖关系，为了使平台中的计算资源充分利用，就需要有一个作业调 度器去保证作业的调度与执行过程。h a d o o p 平台下的调度器角色是由协k t r a c k c r 充当的，在具体实现上，h a d o o p 调度器采取了插件机制，即调度器是可以动态加 载或者可插拔的，甚至第三方还可以开发自己的调度器去替换掉h a d 0 0 p 平台下默 认的调度器。目前，h a d o o p 平台主要支持以下几种作业调度器【2 7 j ： ( 1 ) f l f o 在早期的h a d o o p 平台架构中，j o b t r a c k e r 在进行作业调度时使用的是f i f o 【7 】 算法，即所有的作业被提交到一个作业队列中，然后按照作业的优先级以及提交作 业的先后顺序选择被执行的作业。这种调度算法的优点是简单，j o b l h c k e r 的负载 较轻，缺点是忽略了作业之间的差异，计算资源的利用率低。 ( 2 ) 计算能力调度器 与f i f o 的单队列相比，计算能力调度器支持多个队列，并且每个队列采用f i f o 调度策略。在具体调度时，每个队列分配一定的系统资源，空闲资源可以动态分配 给负担较重的队列，它的优点是支持多个作业并发执行以及动态调整资源分配，在 资源的利用率和作业的执行效率方面有优势；缺点是用户需要了解大量的系统信息 ( 如内存使用率，c p u 利用率等) ，才能设置和选择队列。 ( 3 ) 公平调度器 公平调剧7 j 是一种使所有作业获取等量资源份额的算法。该算法旨在保证集群 资源不被一个作业独占，当系统有新的作业提交时，亿l ( t h c k e r 会释放并分配给该 作业，以使集群中的所有作业都获得大体相等的资源。公平调度器并未考虑节点的 实际负载情况，易导致节点负载实际并不均衡。 硕士学位论文 m a s t e r st h e s i s 以上是h a d o o p 平台中使用最广泛的三种调度策略，当然用户也可以根据实际 应用所需去设计自己的调度算法，但是要想使得自己的调度策略在h a d o o p 平台下 能正常运行，还需要完成下面几个步骤的设置：首先需要将i a r 包拷贝到 h a d o o ph o m e l i b 中( 或者修改h a d o o pc o n fd i 壬0 h a d o o p 锄v s h 中的 h a d o o p c l a s s 姗参数，并将j a r 包的路径加入其中) ；然后需要在 h a d o o pc o n fd i m a p 佗d s i t e x m l 中设置m a p 川j o b 概k 既t a s k s c h e d u l e r 的值为 。娼印a c h e h a d 0 0 p m 印r e d ) o ( x ( 其中x x x 为用户自定义调度器名) ，另外，在该文 件中还可以定义一些其它的参数值。 2 2 3h a d o 叩通用参数选项 h a d o o p 平台中存在1 9 0 多个可以手动设置的通用参数，针对运行在h 撕平 台上的作业特性，并灵活地配置这些参数可以达到提高h a d 0 0 p 数据处理效率的目 的。下面主要介绍几个常见的通用参数以及在设置时的注意事项： d f s n a m e n o d e h 卸d 1 既c o u n t ( 1 l d f s s i t e x m l ) ：用来配置n a m e n o d e 节点处理r p c ( 远 程过程调用) 的进程数，默认值是l o ，若是针对较大的集群，可以进行适当增加。 m 印r 甜j o b 仃a c k 既h 觚d l e r c o u n t ( m a p 化d _ s i t e x m l ) ：用来配置j o 矶r a c k c r ，参数其 它性质同上。 d f s b l o c k s i z e ( h d s f s i t e x m l ) ：用来配置h a d 0 0 p 平台中的数据块的大小，默认大 小是6 4 m ，对于较大的集群，可以适当增加，如1 2 8 m 或2 5 6 m 。值得注意的是， 依照h d f s 规定，它的值但必须是5 1 2 字节的整数倍。 m a p r e d u c e t 嬲k i o s o n m b ( c o r e 。s i t e x m l ) ：用来配置m a p 任务的输出结果以及其 它元数据在内存中所能占的b u 仃e r 总和，系统默认值是l o o m ，对于大型集群，可 以增大为2 0 0 m 。当增大到b u 脏r 总和的阈值时，系统会启动后台进程将b u 行e r 数 据写入到本地磁盘( 一个s p i l l 文件) ，这个阈值则是在i o s o n s p i l l p e 袱m t 中设定， 默认值是0 。8 。 m a p 他d u c e t 弱k i o s o r t 最l c t o r ( c o r e s i t e x m l ) ：当m 印p e r 执行完任务后，本地磁盘 中可能存在着多个s p i l l 文件，m 印p e r 需要做的最后一件事情是执行m e r g e s o r t ，并 把这些s p i l l 文件合成一个文件，而在执行m e r g e s o r t 时同时可以打开多少s p i l l 文件 则是由这个参数配置。 m a p r e d c o m p r e s s m 印o u t p u t ( c o r e s i t e x m l ) ：用来配置是否对中间结果和最终结 果进行压缩，若是进行压缩，则需要指定压缩方式，目前比较常用的是l z o 【7 】压缩。 i n t e l 内部测试证明，相比未压缩，使用l z o 压缩使得作业运行时间缩减了6 0 。 m 印r e d u c e r e d u c e s h u 用e p a r a l l e l c o p i e s ( m a p r e d s i t e x m l ) ：一般来讲，h a d o o p 中 硕士学位论文 m a s t e r st h e s l s 的r e d u c e 阶段由以下三个阶段组成：c o p y s o r t 和r e d u c e ，其中c o p y 也称为s h u 用e 阶段，即当m a p 瓜e d u c e 工作已完成了5 的m a p 任务之后就会启动r o d u c e ，从其它 已经完成的m 印p e r 上去下载属于自己的r e