concurrency-mapreduce

MapReduce 程序设计

原始论文


实验目标

  • 学习 MapReduce 范式的通用特性
  • 使用线程和相关函数实现一个正确且高效的 MapReduce 框架
  • 获得更多编写并发代码的经验

MapReduce框架总体思路

用户只需要定义 Map() 与 Reduce() 函数,交由框架处理该函数指针即可

  • Map(): 接受一个输入对,并产生一组中间键值对。
  • Reduce(): MapReduce库 将具有相同中间键K的中间值分组在一起,传入该函数
    • 接受一个中间键K和该键的一组值。将这些值进行合并为更小的集合
    • 通常,每次对 Reduce() 的调用产生零个或一个输出值
    • 中间值通过迭代器提供给用户的reduce函数

MapReduce 可将许多不同类型的相关计算映射到该框架上。
并且多个 mapper 可以同时运行,多个 reducer 也可以同时运行。
用户不必亲自操作编写并行化程序,只需要编写 Map() 与 Reduce() 函数,并交由该框架提供的相关基础设施即可。


框架总体流程

  1. argv[1..n] 文件列表作为输入分片
  2. Mapper 线程池 (num_mappers 个线程) -> 并发调用用户的 Map()
  3. Map() 内部调用 MR_Emit(key, value) 发射中间数据
  4. MR_Emit 根据 Partitioner 将 key 路由到目标分区,在分区内部完成 key 去重与 value 聚合(同一 key 的多个 value 归入同一 MR_key_values)
  5. 所有 map 任务完成后,每个分区内的 kvs_groups 按 key 字典序升序排序
  6. Reducer 线程池 (num_reducers 个线程) -> 为每个唯一 key 创建一个 reduce 任务,调用 Reduce()

框架结构

用户侧

  • 定义 Map 函数
    • 将传入的 (k0, v0) 转化为中间键值对 (k1, v1)
    • 调用 MR_Emit() 函数,发送中间键值对
  • 定义 Reduce 函数
    • 通过 Getter 函数迭代获取分区中该 key 对应的所有 value
    • 对 values 进行归并,输出最终结果

数据结构层

中心数据结构——三层嵌套

1
2
3
4
5
6
7
8
9
10
MR_master {
partitions[] { // 分区层:按 Partitioner 哈希分桶
MR_partition { // 每个分区持有独立的互斥锁
kvs_groups[] { // 键-值列表对层:每个唯一 key 对应一个 MR_key_values
key // 键(深拷贝)
values[] // 该键对应的所有值(深拷贝)
}
}
}
}
  • 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// MapReduce使用的不同的函数指针类型

typedef char *(*Getter)(char *key, int partition_number);
typedef void (*Mapper)(char *file_name);
typedef void (*Reducer)(char *key, Getter get_func, int partition_number);
typedef unsigned long (*Partitioner)(char *key, int num_partitions);

// 需要实现的外部函数

void MR_Emit(char *key, char *value);

unsigned long MR_DefaultHashPartition(char *key, int num_partitions);

/**
* 接收:
* - 给定程序的命令行参数
* - 指向Map函数的指针
* - MapReduce库创建的线程数量
* - 指向Reduce函数的指针
* - reducer数量
* - 指向分区函数的指针
*/
void MR_Run(int argc, char *argv[],
Mapper map, int num_mappers,
Reducer reduce, int num_reducers,
Partitioner partition);
  • 该库需要创建 num_mappers 个线程(线程池)执行map任务

  • 创建 num_reducers 个线程执行reduce任务

  • 该库需要创建一种内部数据结构将键值对从mapper传递到reducer

  • MR_Emit() 函数,从许多不同的mapper接收键值对,并以一种后续reducer可访问的方式存储

    • 该实验的关键就在于如何设计这个数据结构
  • MR_DefaultHashPartition() 函数,接收一个key,将其映射为 0 到 num_partitions - 1 的数字

    • 在MapReduce内部使用
  • 对于每个分区,键应该按照键的升序排列;当特定的reducer线程工作时,Reduce函数应按顺序对该分区的每个键进行调用


关键设计决策

线程安全策略

采用两级锁设计:

  1. 分区级锁(MR_partition.mutex):保护 kvs_groups 数组的结构变更(添加新 key、扩容)。map 阶段多个 mapper 线程并发写入不同分区时天然无竞争;写入同一分区时互斥。
  2. 键级锁(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
2
./mapreduce test.txt         # 单文件
./mapreduce file1 file2 ... # 多文件并发

项目文件结构

1
2
3
4
5
6
7
8
9
10
concurrency-mapreduce/
├── mapreduce.h # 公共接口声明(MR_Run, MR_Emit, MR_DefaultHashPartition)
├── mapreduce.c # 框架主逻辑(MR_Run 调度、迭代器、线程任务包装)
├── MR_master.h # 中心数据结构声明(MR_key_values, MR_partition, MR_master)
├── MR_master.c # 数据结构操作实现(init/destroy/push/sort)
├── thread_pool.h # 线程池声明
├── thread_pool.c # 线程池实现
├── main.c # 测试用例:Word Count
├── Makefile
└── mapreduce.md # 本文档