concurrency-mapreduce 实验指导
该实验指导文档在实验编写完成后进行了修缮与逆向更新
更贴合实际的项目进度
MapReduce 实验指导
实验分析
本项目是 OSTEP(Operating Systems: Three Easy Pieces) 的并发 MapReduce 实验。目标是实现一个单机多线程简化版 MapReduce 框架,核心是实现 mapreduce.h 中声明的函数并设计线程安全的中心数据结构。
1. 理解数据流
整个框架的数据流是:
1 | argv[1..n] 文件列表 |
在写代码之前,建议把这条数据流画在纸上,标注每一步的输入和输出。这是理解后续所有实现细节的基础。
2. 设计核心数据结构(最关键的难点)
需要一个线程安全的数据结构来承接 MR_Emit() 发射的键/值对,并能被 reducer 线程按分区、按键排序地读取。
实际采用方案:分区内按 key 聚合 + 延迟分配
采用三层嵌套结构:
1 | MR_master { |
关键特性:
- 分区粒度锁:每个
MR_partition持有独立的pthread_mutex_t,不同分区的并发写入天然无竞争。 - 键级锁:每个
MR_key_values内部持有独立的pthread_mutex_t,保护values_iter迭代器,保证 reducer 线程安全消费。 - 写入时去重:
MR_Emit阶段即完成 key 去重——同一 key 的多次 emit 会将 value 追加到同一个MR_key_values.values[]中,无需 map 后额外合并。 - 延迟分配:
kvs_groups数组预分配骨架(raw memory),仅在 key 首次出现时才调用MR_key_values_init初始化对应 slot。未使用的 slot 仅占裸内存,无资源泄漏。 - 深拷贝:框架对 key 和 value 均进行
malloc+strcpy,不依赖用户内存生命周期。
数据结构类型定义
1 | // 中间键-值列表对单元 |
3. 实现步骤
| 步骤 | 内容 | 涉及文件 |
|---|---|---|
| Step 1 | 实现线程池 — thread_pool.h/.c,生产者-消费者模型,支持创建/添加任务/销毁 |
thread_pool.c |
| Step 2 | 实现中心数据结构 — MR_key_values、MR_partition、MR_master 的 init/destroy/push 操作 |
MR_master.c |
| Step 3 | 实现 MR_DefaultHashPartition() — djb2 哈希算法,hash = hash * 33 + c |
mapreduce.c |
| Step 4 | 实现 MR_Emit() — 通过 Partitioner 计算分区索引,调用 MR_partition_push() 写入 |
mapreduce.c |
| Step 5 | 实现 MR_Run() 的 mapper 阶段 — 创建线程池,为每个文件创建一个 map 任务,等待全部完成 |
mapreduce.c |
| Step 6 | 实现排序 — quick_kv_sort() 对每个分区内的 kvs_groups 按 key 字典序排序 |
MR_master.c |
| Step 7 | 实现 MR_partition_iter_get() — Getter 迭代器:按 key 查找 MR_key_values,加锁返回下一个 value |
mapreduce.c |
| Step 8 | 实现 MR_Run() 的 reducer 阶段 — 为每个唯一 key 创建 reduce 任务,等待全部完成 |
mapreduce.c |
| Step 9 | 实现释放链 — MR_master_destroy → MR_partition_destroy → MR_key_values_destroy |
MR_master.c |
| Step 10 | 编写 wordcount 测试 + 编译运行验证 | main.c |
4. 并发控制要点
两级锁设计
- 分区级锁(
MR_partition.mutex):保护kvs_groups数组的结构变更(添加新 key、扩容)。多个 mapper 线程并发写入不同分区时天然无竞争;写入同一分区时互斥。 - 键级锁(
MR_key_values.mutex):保护values_iter迭代器。reduce 阶段 reducer 线程迭代消费 value 时加锁。
同步点
- Map → Sort:
thread_pool_destroy(map_pool)内部pthread_join等待所有 mapper 完成后,才开始排序。 - Sort → Reduce:排序在单线程中完成(
MR_Run主线程),之后才创建 reduce 任务。 - Reduce 只读:reduce 阶段不再有写入,
MR_partition_has_key()无锁查找是安全的。
为什么不在 map 阶段就开始排序(流水线化)
第一版不做流水线是正确性优先的选择。map 全部完成再统一排序和 reduce,避免了”排序中又有新 key 插入”的复杂同步问题。如果需要性能优化,可以在后续版本中引入条件变量做流水线。
5. 内存管理要点
- 深拷贝:
MR_Emit传入的 key/value 可能来自用户的栈或短期堆内存(如strsep返回的指针),框架必须在MR_key_values_init和MR_key_values_push_value中进行malloc+strcpy。 - 释放链:释放顺序与创建顺序相反。
MR_key_values_destroy释放 key 和 values 的内部内存,但不释放 kvs 结构体本身——它由partition->kvs_groups数组统一free。 - 延迟分配:
MR_partition_init仅分配数组骨架,不初始化内部 slot。未使用的 slot 不会泄漏 mutex 或 values 数组。扩容时 (realloc) 新增的 slot 同样是 raw memory,在取用时才MR_key_values_init。 - 排序注意事项:
quick_kv_sort对MR_key_values做原地交换(struct swap)。由于MR_key_values包含pthread_mutex_t,在 Linux NPTL 实现下pthread_mutex_t是清零内存,realloc的逐字节拷贝和排序中的 struct swap 在实际运行中安全。从标准严格角度看,包含 mutex 的结构体不应逐字节拷贝——可考虑将 mutex 改为指针或单独分配来规避,但在本实验中保持简洁。
6. 测试程序
main.c 中实现了 Word Count:
- Map:逐行读取文件,
strsep按空白字符分词,对每个 token 调用MR_Emit(token, "1") - Reduce:通过 Getter 迭代计数
"1"的出现次数,输出"%s %d\n"
1 | # 编译 |
Makefile 关键配置:
1 | CC = gcc |
7. 总结
- 线程池 — 可复用的通用组件,先实现并验证
- 中心数据结构 —
MR_key_values→MR_partition→MR_master,自底向上 MR_DefaultHashPartition()+MR_Emit()— 数据能写入MR_Run()mapper 阶段 — 多线程 map 跑通- 排序 —
quick_kv_sort按 key 字典序 MR_partition_iter_get()— Getter 迭代器实现MR_Run()reducer 阶段 — 多线程 reduce 跑通- 释放链 — 全部 destroy 正确调用
- wordcount 测试 —
./mapreduce test.txt验证输出