这一部分的内容对应于 lec 36，37 的相关内容， (b 大上的参考课程为 [Summer 20])。这一部分其实也可以归结到前一将并行中去，因为涉及的集群计算和分布式框架可以视为是集群级并行。
从指令级并行(ILP)和线程级并行(TLP)到请求级并行(RLP) 和大规模数据级并行(DLP)，我们并行的视角是越来越高的，相应视角下的适用工具也各不相同，这一讲中的主要工具包括 MapReduce 和 Spark，不过本讲侧重于 MapReduce。
阿姆达尔定律(Amdahl‘s Law)
这个定律我们在前文提过，其核心思想是 对系统某一部分进行加速时，其所带来的整体性能提升，受限于该部分在总时间中所占的比例，具体来说；
$$\text{Speedup} = \frac{1}{s + (1-s)/P}$$
其中
- $s$ : 程序中无法被并行化的串行部分所占的时间比例。
- $P$ : 并行部分所能获得的加速比(例如，有N个处理器，理想情况下P = N)。
这一定理告诉我们必须尽全力优化串行部分，因为即使你拥有无限多的处理器，如果程序有10%的代码是串行的，那么最大加速比也不会超过10倍。
放在并行架构上就是Reduce后的最终合并，这一部分的开销是 $s$ 的一部分。
请求级并行(RLP) && 数据级并行(DLP)
请求级并行(Request-Level Parallelism, RLP)，它的常见特征是最小的并行单位是独立的用户请求，且请求间通常没有共享状态或同步需求，或者共享通过数据库等外部系统协调。属于“易并行”问题
数据级并行(Data-Level Parallelism, DLP)，此时的并行单位是单个大型数据集的不同部分，我们需要对同一份数据的多个分区进行相同的操作。而这也是MapReduce和Spark解决的核心问题。
MapReduce 编程模型与执行流程
对于 MapReduce 模型，程序员只需定义两个函数：
- Map函数：
(in_key, in_value) -> list(interm_key, interm_value)，它用于处理输入的键值对，生成一批中间键值对。它将原始数据打散，并为具有相同键的记录“贴上标签”，使它们之后能被送到同一个Reduce节点。
- Reduce函数：
(interm_key, list(interm_value)) -> list(out_value)。它用于接收一个中间键和它对应的所有值的列表，进行合并计算，产生输出结果。
具体到执行流程为：
- 分片（Splitting）： 输入数据被自动切分成大小固定的分片，分布到集群的多个节点上。
- Map阶段： 多个Mapper节点并行处理每个分片，应用用户定义的Map函数。
- Shuffle与排序（Shuffle & Sort）： 这是最关键的一步。框架自动将所有Mapper输出的中间键值对进行排序，并通过网络将相同键的所有值传输到同一个Reducer节点。这个过程对用户透明，但开销巨大。
- Reduce阶段： 多个Reducer节点并行接收已经分好组、排好序的数据，应用用户定义的Reduce函数。
- 输出： 每个Reducer将结果写入最终输出文件（通常是分布式文件系统，如HDFS）。
MapReduce 的另一个优势在于它的容错性，Master节点会监控所有Worker节点。如果一个节点失败，它的任务会被自动重新调度到其他健康节点上执行。这种基于重新执行的容错是MapReduce能在廉价硬件上稳定运行的关键。
Spark：MapReduce的思想进化
与 MapReduce 相比，Spark 的核心改进在于内存的相关操作：
Mapduce的每个Map和Reduce阶段都将结果写入磁盘，Shuffle过程也需要读写磁盘。频繁的磁盘I/O成为主要性能瓶颈。Spark为了解决这个问题，引入了弹性分布式数据集（RDD, Resilient Distributed Datasets）。数据可以尽可能长时间地保留在内存中，只有在内存不足时才会溢出到磁盘。这带来了数量级的性能提升。而且 Spark 提供了更丰富的操作符，这使得表达复杂的数据流变得更加容易和简洁。此外， Spark在遇到转换操作（如map, filter）时并不立即计算，而是构建一个执行计划（DAG）。只有在遇到行动操作（如collect, count）时，它才会优化并执行整个计划。这允许进行强大的全局优化
至于 lec37 ，其核心是介绍数据中心和云计算，特别是仓库级计算机（WSC）的设计、性能指标和能效管理。需要重点解析Amdahl定律的回顾、计算机时代演变、WSC的架构、性能指标（延迟和吞吐量）、能耗管理（PUE）以及实际案例（如Google的数据中心），其涉及的更多是不涉及理论的相关介绍，故笔记略过这一部分。
中的来说，这两讲将我们的视角从单机拉升到了数据中心的高度：
- 定律是底线： Amdahl‘s Law 是所有并行设计者心中的一把尺子，提醒我们优化的重点和并行化的收益上限。
- 抽象是力量： MapReduce 的强大在于它提供了一个极其简单的抽象（Map和Reduce），却能够自动处理分布、调度、容错、网络通信等极其复杂的细节，让普通程序员也能驾驭数千台机器。
- 内存是王道： Spark 代表了大数据处理的发展方向，通过内存计算和更高级的API，极大地提升了开发效率和执行性能，成为当前大数据领域的事实标准。
- 层次化并行： 这一讲完善了我们的并行计算世界观：从芯片内的指令级（ILP）、数据级（SIMD） 和线程级（TLP） 并行，到数据中心级的请求级（RLP） 和数据级（DLP） 并行。不同的问题需要在不同层次上应用不同的并行策略。
理解MapReduce和Spark的思想，不仅是为了处理大数据，更是为了理解如何通过良好的抽象和系统设计，将庞大的硬件资源转化为简单、强大、可靠的编程能力。这是计科中“将复杂性隐藏于接口之下”这一核心思想的极致体现。
发表回复