Reduce端的Shuffle过程

1. Reduce任务向作业管理器询问Map任务是否已经完成。

• 若完成，则接收不同Map任务传来的数据。

• 如果Reduce任务接收的数据量相当小，则直接存储在缓存中，

• 如果数据量超过了该缓冲区大小的一定比例，则对数据合并后溢写到磁盘中。

2. 随着溢写文件的增多，后台线程会将它们归并成一个大文件。

• 归并的时候还会对键值对进行排序。

3. 磁盘中经过多轮归并后得到若干大文件，直接输入给Reduce任务。

• 这些大文件不会继续归并，而是直接输入给Reduce 任务，这样可以减少磁盘的读写开销。至此，整个Shuffle 过程结束。

自动机有如下基本概念：

符号 ：有某种意义或在这个机器上有效的任意数据(datum)。符号有时就叫做“字母”。

字：通过一些符号串接而形成的有限字符串。

字母表 ：符号的有限集合。字母表经常指示为Sigma ，它是在字母表中所有字母的集合。

语言 ：字的集合，由给顶字母表中的符号形成。可以是也可以不是无限的。

Kleene闭包 ：一个语言可以被认为是所有可能字的子集。所有可能字的集合可以被认为是所有可能的字符串串接的集合。形式上说，所有可能字符串的集合叫做自由幺半群。它被指示为 Sigma *}，上标 * 被称为Kleene星号