杨志丰-GFS与MapReduce的实现研究及其应用

1GFS与MapReduce的实现研究及其应用杨志丰导师：李晓明教授2008-06-052大纲•引言•TFS分布式文件系统•MapReduce分布式并行计算框架•总结引用次数来自GoogleScholar3本文工作的出发点•TheGoogleFileSystem–ACMSOSP2003–被引用357•MapReduce:SimplifiedDataProcessingonLargeClusters–USENIXOSDI2004–被引用2244动机•开源实现–Hadoop,KFS•支持天网组内工作的需要–大量数据：网页（以InfoMall网页库格式存储），搜索引擎日志，URL数据，CDAL元数据，NLP语料库、词典；网页索引数据，Web链接图；CWT100G,CWT200G,中文网页分类评测测试集,其他机构的数据（如TREC相关数据：terabytetrack）•研究课题–搜索引擎平台–海量数据处理的基础设施–改进系统设计5大纲•引言•TFS分布式文件系统•MapReduce分布式并行计算框架•总结6系统结构•一个master，若干个chunkserver，若干个client•存储大文件（GB-TB）•一个文件由若干个定长块（chunk，64MB）•块是普通linux文件，有若干个复本（replica）7GFS中的记录追加写操作•记录追加写–原子性（atomic）–多写者并发•Lease机制保证一致性•结果数据–成功：至少成功的在一个偏移处写入了一次；块末尾可能产生填充–失败：产生不一致和不完整的数据ClientMasterSecondaryReplicaAPrimaryReplicaSecondaryReplicaB8TFS中的记录追加写操作•记录追加写–原子性–多写者并发•无需lease机制–变长块–写缓存与新块申请•结果–成功：数据被完整的写入一次，且各个复本一致–失败：数据没有被写入ClientReplicaCReplicaAReplicaBMaster9实验设置•一台master，九台chunkserver–Dell2850：2IntelXeon,2GB内存，7200rpmSCSI硬盘6块组成一个软件RAID-0•客户端–2GB内存，其余同上•网络–所有机器通过1Gbps全双工以太网卡与一个1Gbps交换机连接10记录追加写的效率•一台客户机上启动不同个客户线程，网络上限125M•峰值95MB/s，达理论上限的75%（GFS为50%）•另一个实验中，多客户机多进程并发追加，总速率可达380MB/s11读操作的效率•峰值90MB/s，理论上限的72%（GFS为75%）12TFSShell1314大纲•引言•TFS分布式文件系统•MapReduce分布式并行计算框架•总结15例子：词频统计中国人民美国人民中国人民银行美国银行中国，1人民，1美国，1人民，1中国，1人民，1银行，1美国，1银行，1中国，1中国，1银行，1银行，1美国，1美国，1人民，1人民，1人民，1中国，2银行，2美国，2人民，3mapshufflereduce16MapReduce运行流程17系统结构ApplicationMapReduceMasterMapReduceclientCreatejobCompletejobworkerMapTaskReduceTaskMapTaskTransTaskworkerMapTaskReduceTaskMapTaskTransTaskCompletetaskAssigntaskAssigntaskCompletetaskJobListWorkerListTaskList…Legend:DatamessagesControlmessage18系统的优化•忽略失败任务•连接输出结果为一个文件–Google实现中R具有双层含义：Reduce任务数；输出文件个数–TFS提供的concatFiles接口•串行版MapReduce•系统实时监控1920大纲•引言•TFS分布式文件系统•MapReduce分布式并行计算框架•总结21本文贡献•提出了一个与GFS不同的设计方案，使得记录追加写的效率大大提升•设计和实现了一个稳定的分布式文件系统TFS，并已用于实际的研究工作•设计和实现了MapReduce分布式并行计算系统，并评测了它的性能•在我们的MapReduce系统基础上实现了各种搜索引擎系统常见的应用•总结了在分布式系统的设计和实现的实践中得到的一些宝贵的经验22未来工作•继续完善系统，提高系统性能，并根据用户反馈增加必要的新特性•构建一个海量数据处理的基础设施是我们研究小组的一个长期的目标，下一步是bigtable系统•为进一步简化程序员工作，在MapReduce的基础上设计和实现并行STL算法库•总结和研究MapReduce，MapReduceMerge，Dryad等模型的表达能力，探索新的模型23谢谢！24致谢•感谢我的导师李晓明教授三年来对我的教诲和研究工作论文工作的宝贵指导。李老师严谨的治学态度和高瞻远瞩的洞察力是我终身学习的楷模。•感谢闫宏飞老师大三时把我带入网络实验室这个大家庭，在实验室学习期间给予我工作学习的指导和对我各方面的能力的锻炼，以及对我本科毕业设计和毕业论文的关心和指导。•感谢彭波老师研究生期间对我研究工作的指导和各方面的关心和帮助。彭老师谦虚温和的态度总是让人如沐春风，清晰严谨的思路始终是我学习的榜样。•感谢北京大学网络实验室这个温暖的大家庭，从大三进入实验室实习起，我在这里度过了5年的岁月。实验室提供了如此好的环境和宽松的氛围，使我能专心致力于研究工作。感谢天网组的每位老师同学，组会上面红耳赤的学术争论，闲暇时轻松幽默的调侃，4楼小房间热火朝天的``封闭开发''，2007年夏回味无穷的威海之行，等等等等都将成为我生命中美好的回忆。•感谢TFS小组的各位成员：涂其琛，樊楷，陈日闪，朱磊，还有彭波老师，没有诸位的帮助和出色的工作，我的论文很难顺利的完成。•感谢爸爸妈妈对我从小到大的关爱和培养，无论何时何地你们的爱始终如我心灵深处暖暖的泉水，给我温暖和力量。感谢我的女友陈晓艳，可爱倔强的你始终坚定的支持我，才使我能顺利的完成论文工作。25附录TFS补充26相关工作•NFS，AFS•GFS•HadoopHDFS•KFS27记录追加写中变长块带来的问题•每个chunk都增加了一个长度属性–增加了master的内存元数据开销•Client可能产生小chunk–实际中应用产生的数据远远大于一个chunk的大小，所以大部分chunk被填慢–如果n个client并发写一个文件，结束时可能有n个chunk的大小小于chunk最大长度28变长块对读操作设计的影响•GFS–读取offset在client端可以转换为chunkindex–每个chunk的元数据与master通信一次–客户端缓存chunk元数据•TFS–必须获得所有chunk的长度才能把读取offset映射到chunk–文件打开时获得所有chunk的元数据信息–打开之后新增的块不可见29写（覆盖写）操作•GFS–与记录追加操作使用相同的lease机制保证复本一致性–可并发写，但可能导致数据混乱•TFS–不支持并发–文件上写锁（排他锁）30Master操作性能•实验设置–是个客户端并发–1000个RPC请求•结果–每秒上千条•另一个模拟负载实验–每秒3443条RPC响应–GFS200~500Ops/s31读缓冲大小32附录MapReduce补充33相关工作•MapReduce实现–HadoopMapReduce•MapReduce应用–[Chu2006],[Wolfe2007],[Xin-jie2007]•模型改进–[Dyrad2007],[MapReduceMerge]•其他–[DeWitt2008]–[Sawzall]–[bigtable2006],[hypertable]34实验设置•TFS–9台chunkserver•MapReduce–MapReducemaster与TFSmaster位于同一台机器上–18台worker，其中8台与chunkserver共用•排序基准测试程序–100字节记录–前10字节为Key35Reduce数的选择•R越大，reduce任务的并发度越高•由于worker内存有限，R太大导致过多的并发reduce任务会降低reduce效率•R越大，数据传输任务越多（M*R），数据传输开销越大36系统加速比•输入数据：5GB•曲线趋于平缓–随着worker数的增加，R增加，导致通信开销的增大37系统可扩展性•当系统规模（和相应的数据规模）扩大5倍时，程序的运行时间增加了约一倍。系统的等平均速度可扩展度为0.43•影响可扩展性的主要因素是R增加导致的通信开销的增大38压力测试•数据–Cwt200G–副本数2•计算–中文词频统计•资源设置–18台worker•运行时间–10.5小时generatedusingDavidA.Wheeler's'SLOCCount'.39项目代码量•TFS总计约14,000行C++•SLOCDirectorySLOC-by-Language(Sorted)•12849icecpp=7060,java=5789•3812mastercpp=3812•2038chunkservercpp=2038•2016blackboxcpp=1995,sh=21•1654appcpp=1533,ansic=121•1630testcpp=1630•1482clientcpp=1482•912buildcpp=852,tcl=30,sh=30•815datatransfercpp=815•558monitorjava=530,cpp=28•514commonansic=365,cpp=149•193utilcpp=193•133mapredcpp=133•59distribsh=59•10top_dirlisp=7,cpp=3•MapReduce总计约12,000行C++•SLOCDirectorySLOC-by-Language(Sorted)•6963src_icecpp=4569,java=2394•3131src_clientcpp=3131•2940testcpp=2940•2406src_appcpp=2116,perl=290•2172src_mastercpp=2172•1070src_workercpp=1070•913src_monitorjava=692,cpp=221•535src_commonansic=365,cpp=170•273src_sversioncpp=273•56distribsh=56•49buildtcl=30,sh=19•18src_utilcpp=18•13top_dirlisp=13