MapReduce 是一个处理海量数据的 并行程序设计模型

MapReduce

内容
• 问题- MapReduce要解决什么问题？
• 理论- MapReduce的理论基础
• 模型– MapReduce的编程模型
• 实现- MapReduce的实现和评测
• 未来- MapReduce的未来发展趋势

处理海量数据
如何统计Google收集的网页中各个单词出现的次
数？
Goolge收集的网页占用存储空间超过400TB，假
设一台计算机以30MB/sec的速度从磁盘读取数
据，那么所需时间将超过4个月！

Google Cluster
• 采用并行计算技术，可以将时间缩短到3个小时以下。

并行化

并行化时要考虑的问题
• 如何划分工作？
• 工作之间需要同步吗？
• 各线程的工作量均衡吗？
• 如何将工作指派给线程？
• 如何处理故障？
• 如何知道所有的工作都已经完成？
• 最后阶段如何汇总结果？

小结
• 简单的计算任务
– 单词计数、Grep、倒排索引、排序、……
• 海量的输入数据
– 整个互联网，网页数目至少是百亿级
• 集群计算环境
– 超过一万个结点
• 如何充分利用硬件，简化程序设计？

不修改数据
运算次序无关紧要

fun foo(lst: int list) =
sum(lst) + mul(lst) + length(lst)

函数可以做参数
fun DoDouble(f, x) = f (f x)

Map

fun map f [] = []
| map f (x::xs) = (f x) :: (map f xs)

map sqrt [1,4,9,16]

Fold
fun foldl f a [] = a
| foldl f a (x::xs) = foldl f (f(x, a)) xs
fun foldr f a [] = a
| foldr f a (x::xs) = f(x, (foldr f a xs))

foldl (-) 1 [4,8,5]，foldr (-) 1 [4,8,5]

举例
fun foo(lst: int list) =
sum(lst) + mul(lst) + length(lst)
fun sum(lst) = foldl (fn (x,a)=>x+a) 0 lst
fun mul(lst) = foldl (fn (x,a)=>x*a) 1 lst
fun length(lst) = foldl (fn (x,a)=>1+a) 0 lst

Map的并行化

map f [] = []
map f (x:xs) = f x : map xs

在什么条件下可以并行化map?
– 计算是独立的，各个元素上的计算互不影响
– 计算次序不需要从左到右，结果输出顺序任意

Fold的并行化
在什么条件下可以并行化fold?
– 不可以并行化fold
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs

MapReduce
mapreduce fm fr lst =
map (reducePerKey fr) (group (map fm lst))
reducePerKey fr (k,v_list) =
(k, (foldl (fr k) [] v_list))
MapReduce maps a fold over the result of a map!

MapReduce借鉴了函数式程序设计语言的设计思想
– MapReduce is inspired by the map and reduce

primitives
present in Lisp and many other functional languages.
• Lämmel对MapReduce的理论基础作了更深入地探讨
– R. Lämmel. Google’s MapReduce Programming Model –
Revisited. http://www.cs.vu.nl/~ralf/MapReduce/.

程序设计模型
• 用户定义两个函数