concurrency-mapreduce
MapReduce 程序设计
原始论文
实验目标
- 学习 MapReduce 范式的通用特性
- 使用线程和相关函数实现一个正确且高效的 MapReduce 框架
- 获得更多编写并发代码的经验
MapReduce框架总体思路
用户只需要定义 Map() 与 Reduce() 函数,交由框架处理该函数指针即可
Map(): 接受一个输入对,并产生一组中间键值对。Reduce():MapReduce库将具有相同中间键K的中间值分组在一起,传入该函数- 接受一个中间键K和该键的一组值。将这些值进行合并为更小的集合
- 通常,每次对
Reduce()的调用产生零个或一个输出值 - 中间值通过迭代器提供给用户的reduce函数
MapReduce 可将许多不同类型的相关计算映射到该框架上。
并且多个 mapper 可以同时运行,多个 reducer 也可以同时运行。
用户不必亲自操作编写并行化程序,只需要编写 Map() 与 Reduce() 函数,并交由该框架提供的相关基础设施即可。
框架总体流程
- argv[1..n] 文件列表作为输入分片
- Mapper 线程池 (num_mappers 个线程) -> 并发调用用户的 Map()
- Map() 内部调用 MR_Emit(key, value) 发射中间数据
- MR_Emit 根据 Partitioner 将 key 路由到目标分区,在分区内部完成 key 去重与 value 聚合(同一 key 的多个 value 归入同一 MR_key_values)
- 所有 map 任务完成后,每个分区内的 kvs_groups 按 key 字典序升序排序
- Reducer 线程池 (num_reducers 个线程) -> 为每个唯一 key 创建一个 reduce 任务,调用 Reduce()
框架结构
用户侧
- 定义 Map 函数
- 将传入的 (k0, v0) 转化为中间键值对 (k1, v1)
- 调用 MR_Emit() 函数,发送中间键值对
- 定义 Reduce 函数
- 通过 Getter 函数迭代获取分区中该 key 对应的所有 value
- 对 values 进行归并,输出最终结果
数据结构层
中心数据结构——三层嵌套
1 | MR_master { |
- MR_master:顶层中心数据结构,持有一个
MR_partition数组。分区数量 = 输入文件数量。 - MR_partition:每个分区通过独立的
pthread_mutex_t实现分区级别的并发保护——不同分区的写操作天然无竞争。内部通过MR_key_values *kvs_groups动态数组管理该分区内的所有唯一 key。 - MR_key_values:每个唯一 key 对应一个
MR_key_values实例。内部持有该 key 的所有 value(动态char **values数组扩容),以及一个values_iter迭代器指针和独立的pthread_mutex_t,供 reducer 线程安全地迭代消费。
框架层
mapreduce.h 提供的公共接口
| 函数 | 说明 |
|---|---|
MR_Run() |
启动 MapReduce 框架,创建线程池、调度 map/reduce 任务 |
MR_Emit() |
被 Map 函数调用,发射中间键值对到分区 |
MR_DefaultHashPartition() |
默认哈希分区函数(DJB hash) |
MR_master.h 提供的数据结构操作
| 函数 | 说明 |
|---|---|
MR_key_values_init() |
初始化一个 MR_key_values 实例(深拷贝 key、预分配 values 数组、初始化互斥锁) |
MR_key_values_destroy() |
释放 key 和所有 value、销毁互斥锁(不释放 kvs 结构体本身——由所属数组统一管理) |
MR_key_values_push_value() |
向 MR_key_values 追加一个 value(深拷贝、自动扩容) |
MR_partition_init() |
初始化分区(延迟分配:仅分配 kvs_groups 数组骨架,不初始化内部 slot) |
MR_partition_destroy() |
释放分区内所有已使用的 MR_key_values 及其数组 |
MR_partition_has_key() |
在分区内线性查找指定 key,返回其 MR_key_values 指针或 NULL |
MR_partition_push() |
线程安全地将 (key, value) 写入分区:查重 → 添加新 key 或追加 value |
MR_master_create() |
创建中心数据结构,初始化所有分区 |
MR_master_destroy() |
销毁所有分区并释放中心结构 |
quick_kv_sort() |
对分区内的 kvs_groups 按 key 字典序升序进行快速排序 |
内部静态函数
| 函数 | 说明 |
|---|---|
MR_partition_add_key() |
在分区内添加一个新 key(检查重复、扩容 kvs_groups、初始化新 slot) |
MR_partition_iter_get() |
Getter 实现:通过 key 查找 MR_key_values,加锁返回下一个 value,value 耗尽时返回 NULL 并解锁 |
map_task_worker() |
线程池任务包装:调用用户的 Map 函数 |
reduce_task_worker() |
线程池任务包装:调用用户的 Reduce 函数 |
原头文件提供的声明
1 | // MapReduce使用的不同的函数指针类型 |
该库需要创建
num_mappers个线程(线程池)执行map任务创建
num_reducers个线程执行reduce任务该库需要创建一种内部数据结构将键值对从mapper传递到reducer
MR_Emit()函数,从许多不同的mapper接收键值对,并以一种后续reducer可访问的方式存储- 该实验的关键就在于如何设计这个数据结构
MR_DefaultHashPartition()函数,接收一个key,将其映射为0到num_partitions - 1的数字- 在MapReduce内部使用
对于每个分区,键应该按照键的升序排列;当特定的reducer线程工作时,Reduce函数应按顺序对该分区的每个键进行调用
关键设计决策
线程安全策略
采用两级锁设计:
- 分区级锁(
MR_partition.mutex):保护kvs_groups数组的结构变更(添加新 key、扩容)。map 阶段多个 mapper 线程并发写入不同分区时天然无竞争;写入同一分区时互斥。 - 键级锁(
MR_key_values.mutex):保护values_iter迭代器。reduce 阶段多个 reducer 线程迭代不同 key 时天然无竞争;理论上同一 key 不会被多个 reducer 消费,但锁保证了防御性安全。
MR_partition_has_key() 本身不加锁——在 map 阶段它仅在 MR_partition_push() 持有分区锁时调用;在 reduce 阶段数据已只读,无需锁。
内存管理策略
深拷贝:MR_Emit 传入的 key 和 value 均为用户栈/堆内存(可能在 Map 返回后失效),框架在 MR_key_values_init 和 MR_key_values_push_value 中一律 malloc + strcpy 进行深拷贝。框架拥有所有数据副本的生命周期。
延迟分配:MR_partition_init 仅分配 kvs_groups 数组的骨架内存(raw memory),不调用 MR_key_values_init 初始化内部 slot。当 key 首次出现时,MR_partition_add_key 才对对应 slot 进行初始化(MR_key_values_init(kvs, key, 1))。未被使用的 slot 仅占裸内存,无资源泄漏。kvs_groups 初始容量为 0 时首次扩容设为 4,之后按 2 倍扩容。
释放链:MR_master_destroy → MR_partition_destroy → MR_key_values_destroy → free 各层内存。MR_key_values_destroy 不释放 kvs 结构体自身——它由 partition->kvs_groups 数组统一释放。
排序
对每个分区内的 kvs_groups(MR_key_values 数组)按 key 字段字典序进行快速排序。排序在 map 全部完成、reduce 启动之前执行,保证 reduce 按 key 升序遍历。
线程池实现
通用的生产者-消费者线程池(与 concurrency-webserver 实验相同):
thread_pool_create(n):创建 n 个工作线程 + 任务队列thread_pool_add_task(task, arg, pool):将任务节点入队,pthread_cond_signal唤醒一个等待线程thread_pool_destroy(pool):设置 shutdown 标志,pthread_cond_broadcast唤醒所有线程,pthread_join等待全部退出
测试用例
main.c 实现了 Word Count(实验项目README.md文件中提供):
- Map:逐行读取文件,
strsep按空白字符分词,对每个 token 调用MR_Emit(token, "1") - Reduce:通过 Getter 迭代计数 “1” 的出现次数,输出
key count
1 | ./mapreduce test.txt # 单文件 |
项目文件结构
1 | concurrency-mapreduce/ |