编辑“︁MapReduce框架”︁

{{DISPLAYTITLE:MapReduce框架}}  
'''MapReduce'''是一种用于大规模数据处理的编程模型和框架，由Google在2004年提出。它通过将计算任务分解为两个主要阶段——'''Map'''和'''Reduce'''——来实现并行和分布式计算，适用于处理海量数据集。  

== 概述 ==  
MapReduce框架的核心思想是“分而治之”。它将输入数据分割成多个小块，分配给集群中的多个节点并行处理，最后将结果汇总。这种设计使得MapReduce能够高效处理TB甚至PB级别的数据。  

=== 主要组件 ===  
* '''Map阶段'''：将输入数据转换为键值对（key-value pairs）。  
* '''Shuffle阶段'''：将相同键的数据分组并传输到Reduce节点。  
* '''Reduce阶段'''：对分组后的数据进行聚合或计算。  

== 工作原理 ==  
以下是MapReduce的工作流程：  

<mermaid>  
flowchart LR  
    A[输入数据] --> B(Map阶段)  
    B --> C(Shuffle阶段)  
    C --> D(Reduce阶段)  
    D --> E[输出结果]  
</mermaid>  

=== 详细步骤 ===  
1. **输入分片**：输入数据被分割成固定大小的块（如64MB或128MB）。  
2. **Map任务**：每个分片由一个Map任务处理，生成中间键值对。  
3. **Shuffle**：中间键值对按键分组，并发送到对应的Reduce节点。  
4. **Reduce任务**：对每组键值对执行聚合或计算，生成最终结果。  

== 代码示例 ==  
以下是一个简单的MapReduce示例，用于统计文本中单词的出现次数（WordCount）。  

=== Map函数（Python伪代码） ===  
<syntaxhighlight lang="python">  
def map_function(document):  
    for word in document.split():  
        yield (word, 1)  
</syntaxhighlight>  

=== Reduce函数（Python伪代码） ===  
<syntaxhighlight lang="python">  
def reduce_function(key, values):  
    yield (key, sum(values))  
</syntaxhighlight>  

=== 输入与输出示例 ===  
'''输入'''（两行文本）：  
<pre>  
hello world  
hello mapreduce  
</pre>  

'''Map阶段输出'''：  
<pre>  
("hello", 1), ("world", 1), ("hello", 1), ("mapreduce", 1)  
</pre>  

'''Shuffle阶段'''（按键分组）：  
<pre>  
("hello", [1, 1]), ("world", [1]), ("mapreduce", [1])  
</pre>  

'''Reduce阶段输出'''：  
<pre>  
("hello", 2), ("world", 1), ("mapreduce", 1)  
</pre>  

== 实际应用案例 ==  
MapReduce广泛应用于以下场景：  
* '''搜索引擎索引构建'''：Google使用MapReduce生成网页索引。  
* '''日志分析'''：统计用户访问频率或错误日志。  
* '''机器学习'''：分布式训练模型（如PageRank算法）。  

== 数学基础 ==  
MapReduce的并行性可以通过以下公式表示：  
<math>  
T_{\text{total}} = T_{\text{map}} + T_{\text{shuffle}} + T_{\text{reduce}}  
</math>  
其中：  
* <math>T_{\text{map}}</math> 是Map阶段的时间复杂度，通常为O(N)。  
* <math>T_{\text{shuffle}}</math> 取决于网络带宽和数据量。  
* <math>T_{\text{reduce}}</math> 是Reduce阶段的时间复杂度，通常为O(M)，M为唯一键的数量。  

== 优缺点 ==  
=== 优点 ===  
* 高容错性：节点故障时任务可重新分配。  
* 可扩展性：支持数千台服务器并行计算。  

=== 缺点 ===  
* 不适合实时计算：批处理模式导致延迟较高。  
* 中间数据存储开销：Shuffle阶段需写入磁盘。  

== 总结 ==  
MapReduce是大规模数据处理的基石框架，适合离线批处理任务。尽管后续出现了更高效的框架（如Spark），但其核心思想仍深刻影响分布式计算领域。初学者可通过实现WordCount等经典案例深入理解其设计哲学。  

{{Stub}}

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:并行与分布式算法]]