Box
Box
Posts List
  1. 编程模型
  2. 实现
  3. 技巧
  4. 结论
  5. 通俗来说
  6. link

MapReduce:面向大型集群的简化数据处理

MapReduce: Simplified Data Processing on Large Clusters

  • MapReduce既是一种编程模型,也是一种与之关联的、用于处理和产生大数据集的实现。
  • 用户要特化一个map程序去处理key/value对,并产生中间key/value对的集合,以及一个reduce程序去合并有着相同key的所有中间key/value对。

编程模型

  • MapReduce库的使用者用两个函数来表示这个过程:map和reduce。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 考虑一个问题:统计一个很大的文档集合中每个单词出现的次数。使用者能写出与下面的伪代码相似的代码:
map(String key,String value):
// key: 文档名
// value: 文档内容
for each word w in value:
EmitIntermediate(w,"1");

reduce(Stringkey, Iterator values):
// key: 一个单词
// value: 计数值列表
int result = 0;
for each v in values:
result += ParseInt(v);
Emit(AsString(result));
// map函数将每个单词与出现次数一同输出(本例中简单的输出“1”)。reduce函数将针对某个特定词输出的次数都合并相加。
  • 举例:
    • URL访问频次统计:map函数处理网页请求的日志,对每个URL输出〈URL, 1〉。reduce函数将相同URL的所有值相加并输出〈URL, 总次数〉对。

实现

上图展示了我们的实现中MapReduce操作的整体流程。当用户程序调用MapReduce函数时,会发生下面一系列动作(上图中的标号与下面列表顺序相同):

  1. 用户程序中的MapReduce库首先将输入文件切分为M块,每块的大小从16MB到64MB(用户可通过一个可选参数控制此大小)。然后MapReduce库会在一个集群的若干台机器上启动程序的多个副本。
  2. 程序的各个副本中有一个是特殊的——主节点,其它的则是工作节点。主节点将M个map任务和R个reduce任务分配给空闲的工作节点,每个节点一项任务。
  3. 被分配map任务的工作节点读取对应的输入区块内容。它从输入数据中解析出key/value对,然后将每个对传递给用户定义的map函数。由map函数产生的中间key/value对都缓存在内存中。
  4. 缓存的数据对会被周期性的由划分函数分成R块,并写入本地磁盘中。这些缓存对在本地磁盘中的位置会被传回给主节点,主节点负责将这些位置再传给reduce工作节点。
  5. 当一个reduce工作节点得到了主节点的这些位置通知后,它使用RPC调用去读map工作节点的本地磁盘中的缓存数据。当reduce工作节点读取完了所有的中间数据,它会将这些数据按中间key排序,这样相同key的数据就被排列在一起了。同一个reduce任务经常会分到有着不同key的数据,因此这个排序很有必要。如果中间数据数量过多,不能全部载入内存,则会使用外部排序。
  6. reduce工作节点遍历排序好的中间数据,并将遇到的每个中间key和与它关联的一组中间value传递给用户的reduce函数。reduce函数的输出会写到由reduce划分过程划分出来的最终输出文件的末尾。
  7. 当所有的map和reduce任务都完成后,主节点唤醒用户程序。此时,用户程序中的MapReduce调用返回到用户代码中。

技巧

  • 划分函数
  • 顺序保证
  • 合并函数
  • 输入和输出类型
  • 边界效应
  • 略过坏记录
  • 本地执行
  • 状态信息
  • 计数器

结论

  • 约束这个编程模型令并行和分布式计算,以及令这些计算可容错,变得简单了
  • 网络带宽是一种稀缺资源。我们系统中的很多优化都因此针对减少通过网络发送的数据总量:局部性优化允许我们从本地磁盘读,同时将中间文件写入本地磁盘也节省了网络带宽
  • 备用执行可以用于减小缓慢的机器的影响,及应对机器失败和数据丢失

通俗来说

  • MapReduce讲的就是分而治之的程序处理理念,把一个复杂的任务划分为若干个简单的任务分别来做。这里重点思想在于并行计算
  • 举例:统计一篇文章中“的”字的频率,当这篇文章及其长,使用单线程从头到尾计算快还是使用多线程(先将文章分为n段,然后开n个进程,同时计算“的”在各段出现的次数,最后求和)快这里就很明显了吧!
  • MapReduce | Wiki
  • 《机器学习实战》 | 第十五章、大数据与MapReduce
  • 《MapReduce: Simplified Data Processing on Large Clusters》
Supporting
Scan, Support Daidai
  • WeChat scan
  • Alipay scan