GFS与MapReduce实现研究及其应用.ppt

1,GFS与MapReduce的实现研究及其应用,杨志丰导师：李晓明 教授2008-06-05,2,大纲,引言TFS分布式文件系统MapReduce分布式并行计算框架总结,引用次数来自Google Scholar,3,本文工作的出发点,The Google File SystemACM SOSP 2003被引用357MapReduce: Simplified Data Processing on Large ClustersUSENIX OSDI 2004被引用224,4,动机,开源实现Hadoop, KFS支持天网组内工作的需要大量数据：网页（以InfoMall网页库格式存储），搜索引擎日志，URL数据，CDAL元数据，NLP语料库、词典；网页索引数据，Web链接图；CWT100G, CWT200G, 中文网页分类评测测试集, 其他机构的数据（如TREC相关数据：terabyte track）研究课题搜索引擎平台海量数据处理的基础设施改进系统设计,5,大纲,引言TFS分布式文件系统MapReduce分布式并行计算框架总结,6,系统结构,一个master，若干个chunkserver，若干个client存储大文件（GB-TB）一个文件由若干个定长块（chunk，64MB）块是普通linux文件，有若干个复本（replica）,7,GFS中的记录追加写操作,记录追加写原子性（atomic）多写者并发Lease机制保证一致性结果数据成功：至少成功的在一个偏移处写入了一次；块末尾可能产生填充失败：产生不一致和不完整的数据,Client,Master,SecondaryReplica A,PrimaryReplica,SecondaryReplica B,8,TFS中的记录追加写操作,记录追加写原子性多写者并发无需lease机制变长块写缓存与新块申请结果成功：数据被完整的写入一次，且各个复本一致失败：数据没有被写入,Client,Replica C,Replica A,Replica B,Master,9,实验设置,一台master，九台chunkserverDell2850：2 Intel Xeon, 2GB内存，7200rpm SCSI硬盘6块组成一个软件RAID-0客户端2GB内存，其余同上网络所有机器通过1Gbps全双工以太网卡与一个1Gbps交换机连接,10,记录追加写的效率,一台客户机上启动不同个客户线程，网络上限125M峰值95MB/s，达理论上限的75%（GFS为50%）另一个实验中，多客户机多进程并发追加，总速率可达380MB/s,11,读操作的效率,峰值90MB/s，理论上限的72%（GFS为75%）,12,TFS Shell,13,14,大纲,引言TFS分布式文件系统MapReduce分布式并行计算框架总结,15,例子：词频统计,中国人民,美国人民,中国人民银行,美国银行,中国，1人民，1,美国，1人民，1,中国，1人民，1银行，1,美国，1银行，1,中国，1中国，1银行，1银行，1,美国，1美国，1人民，1人民，1人民，1,中国，2银行，2,美国，2人民，3,map,shuffle,reduce,16,MapReduce运行流程,17,系统结构,18,系统的优化,忽略失败任务连接输出结果为一个文件Google实现中R具有双层含义：Reduce任务数；输出文件个数TFS提供的concatFiles接口串行版MapReduce系统实时监控,19,20,大纲,引言TFS分布式文件系统MapReduce分布式并行计算框架总结,21,本文贡献,提出了一个与GFS不同的设计方案，使得记录追加写的效率大大提升设计和实现了一个稳定的分布式文件系统TFS，并已用于实际的研究工作设计和实现了MapReduce分布式并行计算系统，并评测了它的性能在我们的MapReduce系统基础上实现了各种搜索引擎系统常见的应用总结了在分布式系统的设计和实现的实践中得到的一些宝贵的经验,22,未来工作,继续完善系统，提高系统性能，并根据用户反馈增加必要的新特性构建一个海量数据处理的基础设施是我们研究小组的一个长期的目标，下一步是bigtable系统为进一步简化程序员工作，在MapReduce的基础上设计和实现并行STL算法库总结和研究MapReduce，MapReduceMerge，Dryad等模型的表达能力，探索新的模型,23,谢谢！,24,致谢,感谢我的导师李晓明教授三年来对我的教诲和研究工作论文工作的宝贵指导。李老师严谨的治学态度和高瞻远瞩的洞察力是我终身学习的楷模。感谢闫宏飞老师大三时把我带入网络实验室这个大家庭，在实验室学习期间给予我工作学习的指导和对我各方面的能力的锻炼，以及对我本科毕业设计和毕业论文的关心和指导。感谢彭波老师研究生期间对我研究工作的指导和各方面的关心和帮助。彭老师谦虚温和的态度总是让人如沐春风，清晰严谨的思路始终是我学习的榜样。感谢北京大学网络实验室这个温暖的大家庭，从大三进入实验室实习起，我在这里度过了5年的岁月。实验室提供了如此好的环境和宽松的氛围，使我能专心致力于研究工作。感谢天网组的每位老师同学，组会上面红耳赤的学术争论，闲暇时轻松幽默的调侃，4楼小房间热火朝天的封闭开发''，2007年夏回味无穷的威海之行，等等等等都将成为我生命中美好的回忆。感谢TFS小组的各位成员：涂其琛，樊楷，陈日闪，朱磊，还有彭波老师，没有诸位的帮助和出色的工作，我的论文很难顺利的完成。感谢爸爸妈妈对我从小到大的关爱和培养，无论何时何地你们的爱始终如我心灵深处暖暖的泉水，给我温暖和力量。感谢我的女友陈晓艳，可爱倔强的你始终坚定的支持我，才使我能顺利的完成论文工作。,25,附录 TFS补充,26,相关工作,NFS，AFSGFSHadoop HDFSKFS,27,记录追加写中变长块带来的问题,每个chunk都增加了一个长度属性增加了master的内存元数据开销Client可能产生小chunk实际中应用产生的数据远远大于一个chunk的大小，所以大部分chunk被填慢如果n个client并发写一个文件，结束时可能有n个chunk的大小小于chunk最大长度,28,变长块对读操作设计的影响,GFS读取offset在client端可以转换为chunk index每个chunk的元数据与master通信一次客户端缓存chunk元数据,TFS必须获得所有chunk的长度才能把读取offset映射到chunk文件打开时获得所有chunk的元数据信息打开之后新增的块不可见,29,写（覆盖写）操作,GFS与记录追加操作使用相同的lease机制保证复本一致性可并发写，但可能导致数据混乱,TFS不支持并发文件上写锁（排他锁）,30,Master操作性能,实验设置是个客户端并发1000个RPC请求结果每秒上千条另一个模拟负载实验每秒3443条RPC响应GFS 200500 Ops/s,31,读缓冲大小,32,附录 MapReduce补充,33,相关工作,MapReduce实现Hadoop MapReduceMapReduce应用Chu2006, Wolfe2007, Xin-jie2007模型改进Dyrad2007, MapReduceMerge其他DeWitt2008Sawzallbigtable2006, hypertable,34,实验设置,TFS9台chunkserverMapReduceMapReduce master与TFS master位于同一台机器上18台worker，其中8台与chunkserver共用排序基准测试程序100字节记录前10字节为Key,35,Reduce数的选择,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小时,generated using David A. Wheeler's 'SLOCCount'.,39,项目代码量,TFS 总计约14,000行C+SLOC Directory SLOC-by-Language (Sorted)12849 ice cpp=7060,java=57893812 master cpp=38122038 chunkserver cpp=20382016 blackbox cpp=1995,sh=211654 app cpp=1533,ansic=1211630 test cpp=16301482 client cpp=1482912 build cpp=852,tcl=30,sh=30815 datatransfer cpp=815558 monitor java=530,cpp=28514 common ansic=365,cpp=149193 util cpp=193133 mapred cpp=13359 distrib sh=5910 top_dir lisp=7,cpp=3,MapReduce 总计约12,000行C+SLOC Directory SLOC-by-Language (Sorted)6963 src_ice cpp=4569,java=23943131 src_client cpp=31312940 test cpp=29402406 src_app cpp=2116,perl=2902172 src_master cpp=21721070 src_worker cpp=1070913 src_monitor java=692,cpp=221535 src_common ansic=365,cpp=170273 src_sversion cpp=27356 distrib sh=5649 build tcl=30,sh=1918 src_util cpp=1813 top_dir lisp=13,