这是一个完整的 MapReduce 分布式计算框架实现，基于 MIT 6.5840 分布式系统课程实验Lab1。本项目实现了 Google MapReduce 论文中描述的核心架构，包括任务调度、故障恢复和并行处理等功能。

• MIT 6.5840 2025 Lab1
• MapReduce: Simplified Data Processing on Large Clusters

6.5840/
├── src/                        # 源代码目录
│   ├── go.mod                  # Go模块定义 (Go 1.22)
│   ├── main/                   # 主程序目录
│   │   ├── mrcoordinator.go    # 协调器启动程序
│   │   ├── mrsequential.go     # 顺序MapReduce实现（参考）
│   │   ├── mrworker.go         # Worker启动程序
│   │   ├── reset.sh            # 环境重置脚本
│   │   ├── test-mr-many.sh     # 多轮测试脚本
│   │   ├── test-mr.sh          # 主测试脚本
│   │   └── pg-*.txt            # 8个测试文本文件
│   ├── mr/                     # 核心MapReduce实现
│   │   ├── coordinator.go      # 协调器实现（实际编写组件）
│   │   ├── rpc.go              # RPC通信协议（实际编写组件）
│   │   └── worker.go           # Worker实现（实际编写组件）
│   └── mrapps/                 # MapReduce应用插件
│       ├── wc.go               # 单词计数应用
│       ├── indexer.go          # 文本索引应用
│       ├── crash.go            # 故障测试应用
│       ├── nocrash.go          # 稳定版本应用
│       ├── early_exit.go       # 早期退出测试
│       ├── jobcount.go         # 任务计数测试
│       ├── mtiming.go          # Map并行时序测试
│       └── rtiming.go          # Reduce并行时序测试
└── .gitignore                  # Git忽略文件配置

文件位置： src/mr/coordinator.go

功能：

• 任务调度与分配
• 状态管理与监控（Map/Reduce/Done 三阶段）
• 故障检测与恢复（10秒超时机制）
• 并发控制与同步（使用 sync.Mutex）

关键特性：

• 支持任务状态跟踪（idle/in_progress/completed）
• 任务超时自动重新分配
• RPC 服务器提供任务管理接口
• 线程安全的任务队列管理

文件位置： src/mr/worker.go

功能：

• 持续请求并执行任务
• Map 任务处理（读取、映射、分区写入）
• Reduce 任务处理（聚合、排序、输出）
• 与协调器的 RPC 通信

关键特性：

• 支持两种任务类型（map/reduce/wait/exit）
• 原子文件操作保证数据一致性（临时文件 + 重命名）
• JSON 序列化存储中间结果
• 使用 FNV 哈希函数实现键的分区分配

文件位置： src/mr/rpc.go

功能：

• 定义 Worker 与 Coordinator 间的通信接口
• 任务分配与完成通知
• Unix domain socket 通信支持

统计文本文件中每个单词的出现次数。经典的 MapReduce 入门应用。

• Map 函数：将文本分割为单词，生成 (word, "1") 键值对
• Reduce 函数：计算每个单词的出现次数

为文本文件创建倒排索引，支持快速文档检索。

• Map 函数：提取文档中的唯一单词，生成 (word, document) 键值对
• Reduce 函数：汇总包含每个单词的文档列表

应用	功能	测试内容
crash.go	随机崩溃测试	验证系统容错性和故障恢复机制
nocrash.go	稳定版本	用于与 crash.go 对比验证
early_exit.go	早期退出测试	测试 worker 提前退出的处理
mtiming.go	Map 并行时序测试	验证 Map 任务的并行执行
rtiming.go	Reduce 并行时序测试	验证 Reduce 任务的并行执行
jobcount.go	任务计数测试	检测任务重复分配问题

• Go 1.22+
• Unix/Linux 环境
• 支持 GCC 编译器

项目包含 8 个经典文学文本作为测试数据：

文件	大小	内容
pg-being_ernest.txt	135KB	《不可儿戏》奥斯卡·王尔德
pg-dorian_gray.txt	442KB	《道林·格雷的画像》奥斯卡·王尔德
pg-frankenstein.txt	430KB	《弗兰肯斯坦》玛丽·雪莱
pg-grimm.txt	527KB	《格林童话集》格林兄弟
pg-huckleberry_finn.txt	580KB	《哈克贝利·费恩历险记》马克·吐温
pg-metamorphosis.txt	135KB	《变形记》卡夫卡
pg-sherlock_holmes.txt	568KB	《福尔摩斯探案集》柯南·道尔
pg-tom_sawyer.txt	402KB	《汤姆·索亚历险记》马克·吐温

总数据量：~3.2MB

# 进入源代码目录
cd /workspace/6.5840/src/main

# 编译所有应用插件
cd ../mrapps
go build -buildmode=plugin wc.go
go build -buildmode=plugin indexer.go
go build -buildmode=plugin crash.go
go build -buildmode=plugin nocrash.go
go build -buildmode=plugin early_exit.go
go build -buildmode=plugin jobcount.go
go build -buildmode=plugin mtiming.go
go build -buildmode=plugin rtiming.go

# 编译主程序
cd ../main
go build mrcoordinator.go
go build mrworker.go
go build mrsequential.go

# 清理之前的输出
rm -f mr-out-*

# 启动协调器（在窗口1）
cd /workspace/6.5840/src/main
./mrcoordinator pg-*.txt

# 启动 worker（在窗口2）
cd /workspace/6.5840/src/main
./mrworker ../mrapps/wc.so

# 查看结果
cat mr-out-* | sort | more

# 清理之前的输出
rm -f mr-out-*

# 启动协调器
cd /workspace/6.5840/src/main
./mrcoordinator pg-*.txt

# 启动 worker
cd /workspace/6.5840/src/main
./mrworker ../mrapps/indexer.so

# 查看索引结果
cat mr-out-* | sort | more

cd /workspace/6.5840/src/main
./mrsequential ../mrapps/wc.so pg-*.txt

# 进入测试目录
cd /workspace/6.5840/src/main

# 运行完整测试
./test-mr.sh

测试内容：

• ✅ 单词计数功能正确性
• ✅ 文本索引功能正确性
• ✅ Map 任务并行执行
• ✅ Reduce 任务并行执行
• ✅ 任务计数准确性
• ✅ 早期退出处理
• ✅ 故障恢复能力

# 运行 N 轮测试检查系统稳定性
./test-mr-many.sh 3

# 或运行更多轮次
./test-mr-many.sh 10

# 清理所有生成的文件
cd /workspace/6.5840/src/main
./reset.sh

reset.sh 会清理：

• 二进制文件（mrcoordinator, mrworker, mrsequential）
• 插件文件（*.so）
• 输出文件（mr-out-*）
• 中间文件（mr-*）
• 临时目录（mr-tmp/）

*** Starting wc test.
--- wc test: PASS
*** Starting indexer test.
--- indexer test: PASS
*** Starting map parallelism test.
--- map parallelism test: PASS
*** Starting reduce parallelism test.
--- reduce parallelism test: PASS
*** Starting job count test.
--- job count test: PASS
*** Starting early exit test.
--- early exit test: PASS
*** Starting crash test.
--- crash test: PASS
*** PASSED ALL TESTS

1. 输入文件被分割给不同的 Map 任务
2. 每个 Map 任务调用用户定义的 Map 函数
3. 生成中间键值对，使用 ihash(key) 进行分区
4. 输出 nReduce 个中间文件（mr-X-Y，X=Map 任务 ID，Y=Reduce 任务 ID）

1. 每个 Reduce 任务读取对应的中间文件
2. 对键值对按键排序
3. 调用用户定义的 Reduce 函数聚合相同 key 的 values
4. 输出最终结果（mr-out-X，X=Reduce 任务 ID）

• 超时检测：10秒无响应视为任务失败
• 任务重分配：失败任务重新分配给其他 worker
• 原子操作：临时文件 + 重命名保证数据一致性

• 互斥锁：Coordinator 使用 sync.Mutex 保护共享状态
• RPC 并发：支持多 worker 同时请求任务
• 竞态检测：可通过 go run -race 检测并发问题

• 中间文件：mr-X-Y (X=Map 任务 ID, Y=Reduce 任务 ID)
• 最终输出：mr-out-X (X=Reduce 任务 ID)
• 格式规范："%v %v" (键 值)

• RPC 结构体字段必须大写开头（可导出）
• 回复结构体在调用前应初始化为默认值
• Unix 套接字路径格式：/var/tmp/5840-mr-uid

• Worker 间需要共享文件系统
• 临时文件和输出文件使用原子操作
• 确保跨设备文件操作的正确性

• 修改 RPC 使用 TCP/IP 通信
• 配置分布式文件系统（如 GFS、NFS）
• 实现跨机器任务调度

• 实现备份任务机制
• 优化数据本地性
• 添加负载均衡策略

项目提供了一个完整的 Docker 开发环境，基于 Ubuntu 24.04 和 Go 1.22.5：

# 构建镜像
docker build -t mapreduce-dev .

# 运行容器
docker run -it -p 8080:8080 mapreduce-dev

环境包含：

• Go 1.22.5 编译环境
• VS Code 在线编辑器（code-server）
• Git 版本控制
• 中文支持（UTF-8）
• Go 国内代理加速

---

MIT 6.5840 分布式系统课程实验项目 基于 Google MapReduce 论文的经典分布式计算框架实现