mapreduce笔记

MapReduce is  a programming model and an associated implementation for processing and generating large data sets.
首先它是一种编程模型, 它的使用场景是处理/生成大量数据集

1. 编程模型
Map: 获取输入(key-value),生成中间数据(key-value). 所有相同key的中间数据聚为一组
Reduce: 输入为中间数据, 合并这些数据得到较小的结果数据集
伪代码(统计单词总数):

类型:
这里举每个单词出现频率统计的例子:
k1,v1 调用时 k1-为单词, v1-为出现次数,这里为1
list(k2,v2) map的结果, 得到的是单词与对应出现次数的集合, 这里为: (a,1),(b,1),(a,1),(a,1)….
k2,list(v2) 对前面中间数据聚合 (a, 1,1,1) (b,1)
list(v2) 最终结果 (3,1)

适用场景列举:
分布的grep
统计URL访问频率
reverse web-link graph
term-vector per host
inverted index
distributed sort

2. 实现

2.1 执行流程:

2.2 master数据结构
master中保存: 
a. map/reduce任务的状态(执行中,完成)
b. 所有worker的标识
c. map产生的中间数据的位置
2.3容错
a. worker failure
b. master failure
c. semantics in the presence of failures
2.4 locality
为了节约带宽, 优先处理本地数据
由于使用GFS, 数据会分布到所有的集群机器,此时需要根据数据的保存位置优先处理那些位于本地的数据.从而减少带宽耗用.
2.5任务粒度
理论上任务粒度(M,R)是可以计算出来的, master需要进行O(M+R)次的调度决策, 保存O(M*R)个状态在内存.
2.6 backup任务
避免某一个任务因为某种(机器,网络)原因没有完成,导致堵塞其他任务.
when a mapreduce operation is close to comletion(不懂), the master schedules backup executions of the remaining inprogress tasks.
定义当多少task完成时为close to completion. 这样当达到这个值时,启动剩余task的后备task, 这样当任意一个task或它的后备完成时即认为task完成.
3优化, mapreduce库的一些特性
3.1 partition function
结果数据分块函数, hash(key) mod R, hash(Hostname(urlkey)) mod R…

3.2 保持顺序
在一个分区内按照key对结果排序, 从而提高对结果进行基于key的随机访问查找的效率

3.3 合并
通过将相似的结果进行简单合并,从而减少master的调度和带宽耗用, 如统计单词出现次数,在map时会到到很多<a,1>的中间结果, 将这些合并为<a,100>

3.4自定义的输入/输出参数类型

3.5 side-effect
不支持产生多个结果文件的2阶段提交策略,需要user自己控制

3.6 skip bad record
Each worker process installs a signal handler that catches segmentation violations and bus errors. Before
invoking a user Map or Reduce operation, the MapReduce library stores the sequence number of the argument
in a global variable. If the user code generates a signal,Each worker process installs a signal handler that
catches segmentation violations and bus errors. 
Before invoking a user Map or Reduce operation, the MapReduce library stores the sequence number of the argument
in a global variable. If the user code generates a signal,

3.7 本地调试工具

3.8 状态监控

3.9计数器

4.性能表现 略

Comments are closed.