concurrency-mapreduce 实验指导

该实验指导文档在实验编写完成后进行了修缮与逆向更新
更贴合实际的项目进度

MapReduce 实验指导

实验分析

本项目是 OSTEP(Operating Systems: Three Easy Pieces) 的并发 MapReduce 实验。目标是实现一个单机多线程简化版 MapReduce 框架,核心是实现 mapreduce.h 中声明的函数并设计线程安全的中心数据结构。


1. 理解数据流

整个框架的数据流是:

1
2
3
4
5
6
argv[1..n] 文件列表
→ Mapper 线程池 (num_mappers 个线程) → 调用用户的 Map()
→ Map() 内部调用 MR_Emit(key, value) 发射中间数据
→ 中间数据按 Partitioner 分区 → MR_Emit 内部完成 key 去重与 value 聚合
→ map 全部完成后,每个分区按 key 升序排序
→ Reducer 线程池 (num_reducers 个线程) → 每个唯一 key 调用一次 Reduce()

在写代码之前,建议把这条数据流画在纸上,标注每一步的输入和输出。这是理解后续所有实现细节的基础。


2. 设计核心数据结构(最关键的难点)

需要一个线程安全的数据结构来承接 MR_Emit() 发射的键/值对,并能被 reducer 线程按分区、按键排序地读取。

实际采用方案:分区内按 key 聚合 + 延迟分配

采用三层嵌套结构:

1
2
3
4
5
6
7
8
9
10
11
12
13
MR_master {
partitions[] { // 顶层:分区数组
MR_partition { // 分区层:一把互斥锁 + 动态数组
mutex
kvs_groups[] { // 键-值列表对层
key // 深拷贝的键
values[] // 深拷贝的值列表(动态扩容)
values_iter // 迭代器指针(reduce 阶段消费用)
mutex // 键级锁(保护迭代器)
}
}
}
}

关键特性:

  • 分区粒度锁:每个 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 中间键-值列表对单元
typedef struct MR_key_values {
char *key; // 键(深拷贝)
char **values; // 值列表(动态数组)
int values_size; // 当前值数量
int values_capacity; // 值列表容量
int values_iter; // 迭代器索引
pthread_mutex_t mutex; // 键级互斥锁
} MR_key_values;

// 分区
typedef struct MR_partition {
pthread_mutex_t mutex; // 分区级互斥锁
MR_key_values *kvs_groups; // 键值列表对数组
int groups_capacity; // 数组容量
int num_kvs_groups; // 当前已使用的唯一 key 数量
} MR_partition;

// 中心数据结构
typedef struct MR_master {
MR_partition *partitions; // 分区数组
int num_partitions; // 分区数量
} MR_master;

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
2
3
4
5
6
# 编译
make

# 运行
./mapreduce test.txt # 单文件
./mapreduce file1.txt file2.txt # 多文件并发

Makefile 关键配置:

1
2
3
CC = gcc
CFLAGS = -g -Wall -Werror -O
LINK = -lpthread -lc

7. 总结

  1. 线程池 — 可复用的通用组件,先实现并验证
  2. 中心数据结构 — MR_key_values → MR_partition → MR_master,自底向上
  3. MR_DefaultHashPartition() + MR_Emit() — 数据能写入
  4. MR_Run() mapper 阶段 — 多线程 map 跑通
  5. 排序 — quick_kv_sort 按 key 字典序
  6. MR_partition_iter_get() — Getter 迭代器实现
  7. MR_Run() reducer 阶段 — 多线程 reduce 跑通
  8. 释放链 — 全部 destroy 正确调用
  9. wordcount 测试 — ./mapreduce test.txt 验证输出