CSCI4180 Introduction to Cloud Computing and Storage
2025/5/11大约 6 分钟
What is this course about?
前半部分是计算，后半是存储。怎么处理海量数据而不卡死，怎么保存海量数据而不撑爆。
核心前提：MapReduce的核心分工
先明确Map/Reduce的核心逻辑，所有分布式算法都是基于这个分工设计：
- Map函数：「分片处理」—— 把大规模数据拆成小分片，每个分片独立计算局部结果（无数据依赖）；
- Reduce函数：「聚合归约」—— 把所有Map的局部结果汇总，计算全局最终结果；
- 迭代型算法（K-Means/PageRank）：多轮MapReduce循环，直到结果收敛（对应你代码里的
while run_next）。
经典算法的核心思路 + Map/Reduce分工
WordCount with Counter（带计数器的词频统计）
经典思路（核心）
WordCount是MapReduce的入门核心场景：原本单机统计海量文本词频会因数据量过大卡死，核心是“分而治之”——先把文本拆分成单词，统计每个分片的局部词频，再汇总所有分片的结果得到全局词频；
Counter（计数器） 是MapReduce的扩展能力：在统计词频的同时，用分布式计数器实时监控任务状态（如总单词数、空行数量、特殊字符数），无需额外遍历数据，提升任务可观测性。
Map/Reduce分工
| 阶段 | Map函数做什么 | Reduce函数做什么 |
|---|---|---|
| 数据处理 | 1. 读取文本分片（按行读取），初始化3个Counter： - TOTAL_WORDS（总单词数）- EMPTY_LINES（空行数）- SPECIAL_CHARS（特殊字符数）2. 逐行处理： - 若行为空， EMPTY_LINES +=1；- 清洗行数据（去标点/转小写），拆分出单词； - 每拆分一个单词， TOTAL_WORDS +=1；若单词含特殊字符，SPECIAL_CHARS +=1；3. 输出局部词频： 单词\t1 | 1. 输入：同一个单词的所有局部计数（如hello\t1、hello\t1）；2. 聚合：累加同一个单词的计数（如 hello\t2）；3. 输出全局词频： 单词\t总次数；4. 无需额外操作Counter（Counter由MapReduce框架自动汇总所有Map节点的计数，任务结束后可直接查看） |
| 结果输出 | - | 1. 输出最终的全局词频表； 2. MapReduce框架自动输出Counter汇总结果（如总单词数=100万、空行数=5000） |
补充说明（Counter的核心价值）
- Counter是MapReduce的分布式监控工具，无需在Map/Reduce中显式传递计数数据，框架会自动汇总所有节点的Counter值；
- 相比“额外统计计数再输出”，Counter更轻量（不占用Reduce的聚合资源），还能实时查看任务进度（比如跑任务时能看到“已统计10万单词”）。
并行Dijkstra（单源最短路径）
经典思路（核心）
Dijkstra原本是单机算法：从起点出发，不断更新“起点到各节点的最短距离”，直到所有节点都被遍历。
并行化核心：把节点/边分片，多节点同时计算局部最短路径，再汇总全局最短值，避免单机处理大规模图的性能瓶颈。
Map/Reduce分工
| 阶段 | Map函数做什么 | Reduce函数做什么 |
|---|---|---|
| 初始化 | 读取图的边数据（格式：起点\t终点\t边权重），输出：- 起点的已知最短距离（如起点A初始为0，其他为∞） - 格式： 节点ID\t(距离, 来源边) | 无（第一轮仅初始化距离表） |
| 迭代计算 | 输入：上一轮Reduce输出的「节点-最短距离」+ 原图边数据 对每条边（u→v，权重w），计算： 新距离 = u的已知距离 + w输出： v\t新距离（局部候选最短距离） | 输入：同一个节点v的所有候选新距离 聚合：保留v的最小距离（全局最短） 输出： v\t全局最短距离 |
| 终止 | 当某轮Reduce输出的距离表无更新（收敛），停止迭代 | - |
PageRank（网页权重排名）
经典思路（核心）
衡量网页重要性：一个网页的权重 = 所有指向它的网页的权重 / 指向网页的出度之和，加上阻尼系数（避免死链）。
并行化核心：把网页链接关系分片，多节点同时计算局部网页的权重贡献，再汇总全局权重。
Map/Reduce分工
| 阶段 | Map函数做什么 | Reduce函数做什么 |
|---|---|---|
| 初始化 | 读取网页链接数据（格式：网页A\t[网页B, 网页C]），给每个网页初始化权重（如所有网页权重=1/N，N是总网页数）输出： 网页ID\t(权重, 出链列表) | 无（第一轮初始化权重） |
| 迭代计算 | 输入：上一轮Reduce输出的「网页-权重+出链」 对网页A（权重R，出链数k），给每个出链网页B分配权重： R/k输出： - 网页B\t分配的权重（贡献值）- 网页A\t出链列表（保留链接关系，供下一轮用） | 输入： 1. 同一个网页的所有贡献值 2. 网页的出链列表 聚合计算： 新权重 = 阻尼系数*总贡献值 + (1-阻尼系数)/N 输出： 网页ID\t(新权重, 出链列表) |
| 终止 | 当某轮权重变化率<阈值（收敛），停止迭代 | - |
K-Means聚类（你的代码核心）
经典思路（核心）
K-Means原本是单机算法：随机选k个聚类中心 → 所有样本分配到最近的中心 → 重新计算每个类的中心 → 循环直到中心不变。
并行化核心：把样本分片，多节点同时分配样本到中心，再汇总所有样本重新计算全局中心。
Map/Reduce分工
| 阶段 | Map函数做什么 | Reduce函数做什么 |
|---|---|---|
| 初始化 | 读取样本数据，加载初始聚类中心（存储于HDFS上的文件） 此阶段不涉及Map/Reduce计算，仅将聚类中心文件分发到集群 | - |
| 迭代计算（Map） | 输入：样本数据 + 聚类中心 对每个样本，计算到k个中心的距离，分配到最近的中心 输出： 中心ID\t(样本特征, 1)（1是样本计数） | 输入：同一个中心ID的所有样本 聚合计算： 1. 汇总该类所有样本的特征之和 2. 统计该类样本总数 3. 计算新中心 = 特征之和 / 样本总数 输出： 中心ID\t新中心坐标 |
| 收敛判断 | 对比本轮新中心和上一轮旧中心的距离（Norm值），若<阈值则停止 | - |
补充说明
在经典的MapReduce（如Hadoop）框架中，除了Mapper和Reducer，还有几个关键的“er”组件，它们共同协作完成分布式计算任务。下面是常见的几个：
| 组件 | 作用 | 出现阶段 |
|---|---|---|
| Combiner | 本地聚合器，在Map端先对输出做一次合并（类似小型的Reduce），减少网络传输的数据量。 | Map阶段之后，Shuffle之前 |
| Partitioner | 决定Map输出的每个键值对应该被发送到哪个Reducer（通过计算键的哈希值等）。 | Map输出写入环形缓冲区时 |
| Shuffler | 不是独立组件，而是指Map输出传输到Reducer的过程，包括排序、合并、复制等。 | Map和Reduce之间的数据传输阶段 |
| RecordReader | 将输入分片解析成键值对（如文本文件的一行作为一个值，偏移量作为键）。 | Map任务读取输入数据时 |
| RecordWriter | 将Reduce输出的键值对写入最终文件（如文本文件、SequenceFile等）。 | Reduce任务输出结果时 |