参考多篇文档、博客，仅供学习记录，参考资料见文末。
1.简介MapReduce用于大规模数据集（大于1TB）的并行运算。概念"Map（映射）“和"Reduce（归约）”，是它们的主要思想，都是从函数式编程语言里借来的，还有从矢量编程语言里借来的特性。 当前的软件实现是指定一个Map（映射）函数，用来把一组键值对映射成一组新的键值对，指定并发的Reduce（归约）函数，用来保证所有映射的键值对中的每一个共享相同的键组。
2004年谷歌提出了MapReduce, 在此之前谷歌程序员面对的大规模数据集,常常需要编程实现:
- 统计某个关键词的现的频率,计算pageRank
- 对大规模数据按词频排序
- 对多台机器上的文件进行grep等
在MapReduce的关键是两个功能：Map和Reduce。不同Map并行执行，Map和Reduce之间串行执行，所有的Map执行完毕，执行Reduce。
Map输入数据首先被分成更小的块。然后将每个块分配给一个mapper进行处理。map函数实现要给key排序。
例如，如果一个文件有 100 条记录要处理，则 100 个mapper可以一起运行，每个mapper处理一条记录。或者也许 50 个mapper可以一起运行，每个mapper处理两条记录。Hadoop 框架根据要处理的数据大小和每个mapper服务器上可用的内存块来决定使用多少个映射器。
Reduce在所有mapper完成处理后，框架会在将结果传递给reducer之前对结果进行混合和排序。当mapper仍在进行中时，reducer无法启动。具有相同key的所有map输出值都分配给单个reducer，然后聚合该key的值。
RPCRPC（Remote Procedure Call）是指远程过程调用，该协议允许运行于一台计算机的程序调用另一个地址空间（通常为一个开放网络的一台计算机）的子程序，而程序员就像调用本地程序一样，无需额外地为这个交互作用编程（无需关注细节）。RPC是一种服务器-客户端（Client/Server）模式，经典实现是一个通过发送请求-接受回应进行信息交互的系统。
也就是说两台服务器A、B，一个应用部署在A服务器上，想要调用B服务器上应用提供的函数/方法，由于不在一个内存空间，不能直接调用，需要通过网络来表达调用的语义和传达调用的数据。
数据倾斜在MapReduce的shuffle阶段，将相同的key拉取到一个Reduce上计算，若某一种key的数据量远远大于其他的key的数据量，造成某一个Reduce Task计算量过大，计算耗时较长，导致整个任务的计算速度及效率大大下降。
数据倾斜一般的两种表现：
① 大部分Reduce Task执行完成特别快，某一个Reduce Task执行特别慢，耗时长；
② 某一个Reduce Task出现OOM，内存溢出，任务失败。
MapReduce中的数据倾斜解决方案：
①自定义combiner类。在map shuffle阶段对数据压缩，相当于做一次Reduce，相同的key先进行聚合运算。从而减少流向Reduce端的文件数量和数据量。
②分析导致数据倾斜的key，在Map阶段将造成倾斜的key分成多组，例如aaa 这个 key，map 时随机在aaa 后面加上 1,2,3,4 这四个数字之一，把key 先分成四组，先进行一次运算，之后再恢复 key 进行最终运算。
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调用返回到用户代码中。
8.主节点维持多种数据结构。它会存储每个map和reduce任务的状态（空闲、处理中、完成），和每台工作机器的ID（对应非空闲的任务）。
9.主节点是将map任务产生的中间文件的位置传递给reduce任务的通道。因此，主节点要存储每个已完成的map任务产生的R个中间文件的位置和大小。位置和大小信息的更新情况会在map任务完成时接收到。这些信息会被逐步发送到正在处理中的reduce任务节点处。
3.应用场景分布式Grep：map函数在匹配到给定的pattern时输出一行。reduce函数只是将给定的中间数据复制到输出上。
URL访问频次统计：map函数处理网页请求的日志，对每个URL输出〈URL, 1〉。reduce函数将相同URL的所有值相加并输出〈URL, 总次数〉对。
倒转Web链接图：map函数在source页面中针对每个指向target的链接都输出一个〈target, source〉对。reduce函数将与某个给定的target相关联的所有source链接合并为一个列表，并输出〈target, list(source)〉对。
每个主机的关键词向量：关键词向量是对出现在一个文档或一组文档中的最重要的单词的概要，其形式为〈单词, 频率〉对。map函数针对每个输入文档（其主机名可从文档URL中提取到）输出一个〈主机名, 关键词向量〉对。给定主机的所有文档的关键词向量都被传递给reduce函数。reduce函数将这些关键词向量相加，去掉其中频率最低的关键词，然后输出最终的〈主机名, 关键词向量〉对。
倒排索引：map函数解析每个文档，并输出一系列〈单词, 文档ID〉对。reduce函数接受给定单词的所有中间对，将它们按文档ID排序，再输出〈单词, list(文档ID)〉对。所有输出对的集合组成了一个简单的倒排索引。用户可以很轻松的扩展这个过程来跟踪单词的位置。
分布式排序：map函数从每条记录中提取出key，并输出〈key, 记录〉对。reduce函数不改变这些中间对，直接输出。
- 把一个文件拆分
- 把产生的三个作业对应三段文件进行并行处理
- mapping，把每一段文本按照单词拆分
- shuffling，把相同数据分到同一个节点上去合并，这样才能统计出来最终结果。
- reduce干的事情就是把我们shuffling之后的相同单词的个数加起来。
https://www.talend.com/resources/what-is-mapreduce/
https://hardcore.feishu.cn/docs/doccnxwr1i2y3Ak3WXmFlWLaCbh
https://corbinhu.github.io/2020/04/25/Data-Tilt-Reasons-and-Solutions-in-MapReduce/
