MapReduce编程模型-北京大学数学科学学院.PDF

信息科学系 低年级讨论班 （2） 裘宗燕 北京大学数学学院信息科学系 2010年3月～6月 本科生讨论班报告（2 ） 北京大学数学学院信息科学系 裘宗燕 2010年2月18 日/1 MapReduce分布式编程 《代码之美》第23章 本科生讨论班报告（2 ） 北京大学数学学院信息科学系 裘宗燕 2010年2月18 日/2 概要 本章描述Google 的Map-Reduce 的设计和实现 MapReduce 是一种用于解决大规模数据处理的编程模型，开发的初 衷是为了简化Google 大规模计算程序的开发工作量 MapReduce 程序能在大量廉价计算机构成的集群上自动并行化和执 行。在此过程中，需要特别关注的问题包括： 输入数据的划分 集群上程序执行的调度 机器错误的处置 机器间通讯的管理 目标是使毫无并行和分布式系统设计经验的程序员也能很好地利用大型 分布式系统里的资源（存储，通讯，计算能力等） 本科生讨论班报告（2 ） 北京大学数学学院信息科学系 裘宗燕 2010年2月18 日/3 示例 设有200亿个文档，要统计每个独立单词在这些文档里出现的次数 如果每个文档有20K，总数据量为400T （1T=1024G） 一台计算机读入这些数据大约需要4个月 如果不怕等的时间长，机器的内存足够大，程序很容易写： 示例 23-1 朴素非并行的单词统计程序 mapstring, int word_count; for each document d { for each word w in d { word_count[w]++; } } ... 把统计数据保存到持久性存储器 ... // 第一行定义了一个计数表格（通常为一个hash表） // 循环中遇到一个单词，就将对应的计数值加一 本科生讨论班报告（2 ） 北京大学数学学院信息科学系 裘宗燕 2010年2月18 日/4 示例 加速计算的一个方法是并行地对每个文档做同样工作 示例23-2，并行化的单词计数程序 Mutex lock; // 用一个锁保护word_count mapstring, int word_count; for each document d in parallel { for each word w in d { lock.Lock( ); word_count[w]++; lock.Unlock( ); } } ... 把统计数据保存到持久性存储器 ... 文档输入工作可以很好地并行化 实际中启动线程有些麻烦，这里用伪代码，忽略了一些复杂描述 主要问题是共享的数据结构word_count 。用一个数据结构可能造成严重的争 用，成为性能瓶颈。可能改进是把数据结构分为很多桶（buckets），每个桶 用一把锁，根据单词找锁和桶，可缓解这个问题（代码在下页） 本科生讨论班报告（2 ） 北京大学数学学院信息科学系 裘宗燕 2010年2月18 日/5 示例 示例23-3，使用分块存储的并行单词计数程序 程序仍然很简单 struct CountTable { Mutex lock; 伸缩性（scalability ）不超过一台 mapstring, int word_co