Stanford-CS149-并行计算-Lec09-spark

ToniXWD

2024-12-09

这节课虽然介绍的是Spark，但是实际上更多是介绍分布式计算的，Spark只是分布式计算的一种实现。如果你学过MIT 6.824的分布式系统，那么这节课的内容对你来说应该比较简单。这里对Spark的介绍主要是其设计思路, 具体的语法还是需要看官方文档: https://spark.apache.org/docs/latest/quick-start.html

课程主页: https://gfxcourses.stanford.edu/cs149/fall24

1 分布式系统的设计

distributed_system

课程介绍了Warehouse-Scale Cluster（WSC）节点（服务器）这种大型的数据中心架构, 这种架构中, 最小的粒度就是单个服务器, 称为node。多个node通过机架(rack)上的交换机连接组成一个小集群, 这个小集群内的网络通信非常快, 但是跨机架的网络通信非常慢。

2 GFS和HDFS

尽管物理上, 一个数据中心的机器是多个node组成的集群, 但逻辑上, 他们的文件系统是统一的, 经典的分布式文件系统有GFS和HDFS。

distributed_file_system

GFS是Google File System的缩写, 是Google公司开发的一种分布式文件系统, 用于存储和处理大规模数据集。GFS的设计目标是提供高吞吐量、高可靠性和高扩展性的文件存储和访问服务。而HDFS是Hadoop Distributed File System的缩写, 是Apache Hadoop项目的一部分, 用于存储和处理大规模数据集。HDFS的设计目标是提供高吞吐量、高可靠性和高扩展性的文件存储和访问服务。HDFS和GFS在设计上非常相似, 但是HDFS是开源的, 而GFS是Google的私有系统。

GFS和HDFS主要有如下几个基本概念:

Chunk Servers (块服务器) / DataNodes (数据节点)

定义：在 GFS 中被称为 Chunk Servers，在 HDFS 中则称为 DataNodes。它们是实际存储数据的物理机器。
文件分片：当一个大文件被上传到 DFS 时，它会被分割成固定大小的连续块（chunks），通常是64MB到256MB之间。这种分片策略有助于并行处理和优化磁盘读写操作。
复制机制：为了保证数据的安全性和可用性，每个块都会被复制多份（通常是2或3份）。这样即使某些节点发生故障，数据仍然可以从其他副本中恢复。
机架感知：在部署 GFS 时，尽量将同一个块的不同副本放置在不同的机架上。这是因为同一机架内的所有服务器可能会因为电力供应或网络交换机的问题同时失效，而跨机架存放可以显著降低这种风险。

Master Node (主节点) / NameNode (名称节点)

定义：在 GFS 中称为 Master Node，在 HDFS 中称为 NameNode。它是整个 DFS 的核心组件，负责管理和维护文件系统的命名空间以及元数据。
元数据管理：NameNode 存储有关文件和目录结构的信息，包括文件名、权限、修改时间等属性，同时也记录了每个文件的块信息及其所在的位置。这些元数据通常会进行定期备份或复制，以确保即使 NameNode 出现问题，也能迅速恢复。
客户端交互：当客户端应用程序想要读取或写入文件时，首先需要与 NameNode 通信，获取所需块的具体位置信息。然后，客户端可以直接与相应的 DataNodes 进行数据传输，而不必每次都经过 NameNode。

Client Library (客户端库)

功能：客户端库是用户程序与 DFS 之间的接口，提供了简单的 API 来执行文件操作，如创建、删除、读取和写入文件。
工作流程：
- 查询元数据：客户端库会先联系 NameNode，询问特定文件的块分布情况。
- 直接访问数据：一旦得到了块的位置信息，客户端就可以直接连接到对应的 DataNodes 来读取或写入数据，从而减少了 NameNode 的负载压力。
- 透明性：对于最终用户来说，使用 DFS 就像使用本地文件系统一样简单，所有的复杂细节都被客户端库所隐藏。

如果对GFS感兴趣, 可以去学下MIT 6.824的分布式系统课程, 这门课有一章节专门介绍GFS。也可以参考我关于GFS的笔记:

https://tonixwd.github.io/2023/12/30/MIT6.5840/Lec03%E7%AC%94%E8%AE%B0/

https://zhuanlan.zhihu.com/p/675837107

3 MapReduce

课程下一个内容介绍的是MapReduce。MapReduce是一种编程模型, 用于处理和生成大数据集。它由Google提出, 是Google在2004年发表的一篇论文中提出的。MapReduce的主要思想是将大数据集分解成许多小的数据块, 然后通过多个计算节点并行处理这些数据块, 最后将处理结果合并成最终结果。

mapreduce

输入首先会被Map操作映射成多个key-value对, 然后这些key-value对会被Shuffle操作分发到不同的reduce节点, 最后这些reduce节点会将这些key-value对合并成最终结果。需要注意的是, Reduce的输入, 也就是Shuffle的输出, 需要包含这一类key的所有键值对, 因此部分的Reduce任务需要等待多个Map任务完成后才能开始。

做过MIT 6.824的分布式系统课程的同学应该对MapReduce非常熟悉, 这门课有一章节专门介绍MapReduce, 这也是课程的第一个Lab。也可以参考我关于MapReduce的笔记:

https://tonixwd.github.io/2023/12/24/MIT6.5840/Lec01%E7%AC%94%E8%AE%B0/

https://zhuanlan.zhihu.com/p/675446573

https://tonixwd.github.io/2023/12/23/MIT6.5840/Lab1_MapReduce/

https://zhuanlan.zhihu.com/p/675177101

mapreduce_example

上图是一个以统计单词数量为例的MapReduce过程。MapReduce有一个master节点, 负责调度Map和Reduce任务, 以及收集Reduce和Map任务的结果。Map任务的输入是文件, 输出是key-value对, Reduce任务的输入是Map任务的输出, 输出是最终结果。

这个案例中, Map任务的输入是指定文件的每一行, 输出是key-value对, 其中key是单词, value是(这个案例中每行只有1个单词)。
Reduce任务的输入是Map任务的输出, 输出是最终结果, 也就是每个单词的数量。
这里有2个Reduce任务的worker其中一个负责处理key=a的键值对, 另一个负责处理key=b的键值对。
Master节点调度任务时需要考虑局部性, 例如Reduce任务应该优先分配本机或者本rack上的Map任务产生的key-value对。同时Master节点需要收集Map和Reduce任务的结果, 并在错误或异常发生时进行重试。更复杂的场景中, Master节点需要完成对不同节点的性能检测, 从而实现负载均衡的任务分配。

MapReduce的优缺点

MapReduce的优点
1. 简化集群编程：
  - 自动任务划分：MapReduce 框架能够自动将一个复杂的作业划分为多个 Map 和 Reduce 任务，使得开发者无需关心底层的并行化细节。
  - 数据局部性调度：通过将计算尽可能靠近数据存放的位置，减少网络传输成本，提高处理效率。
  - 负载均衡：框架内置了负载均衡机制，确保各个节点的任务分配相对均匀，避免某些节点过载而其他节点空闲。
  - 故障恢复和慢机处理：具备强大的容错能力，可以自动检测和重试失败的任务，并通过投机执行等手段应对慢速机器，保证作业顺利完成。
2. “大数据”分析的简化：
  - MapReduce 为大规模数据集的处理提供了一个简单且有效的模型，使得开发者可以专注于业务逻辑而不是分布式系统的复杂性。
  - 它允许用户在不需要深入了解分布式系统内部工作原理的情况下，利用大量计算资源来处理海量数据。
MapReduce 的缺点
1. 程序结构限制：
  - 简单的程序结构：MapReduce 只支持一种非常基本的程序结构，即先进行 Map 操作，然后对结果按键进行 Reduce 操作。这种模式对于一些更复杂的算法或应用来说可能不够灵活。
  - 迭代算法的效率问题：对于需要多次迭代的算法（如机器学习中的梯度下降、图处理中的PageRank等），MapReduce 每次迭代都需要从磁盘重新加载数据，这会导致大量的I/O开销，影响性能。
2. 多阶段应用程序的支持不足：
  - 复杂应用的需求：随着用户需求的增长，越来越多的应用程序需要更复杂的、多阶段的处理流程，例如迭代式的机器学习算法和图处理。MapReduce 的简单模型难以高效地支持这些需求。
  - 交互式查询的局限性：对于需要快速响应的交互式查询，MapReduce 的批量处理特性显得过于笨重，无法满足实时性要求。
3. 缺乏对DAG的支持：
  - 固定的工作流：MapReduce 的工作流是线性的，只能表示 map 和 reduce 两个阶段。对于需要表达更复杂依赖关系的应用（如有向无环图 DAG），MapReduce 显得力不从心。相比之下，像 DryadLINQ 这样的系统提供了对 DAG 的支持，更适合复杂的多阶段处理。

4 Spark

Spark的设计目标就是解决MapReduce的缺点, 特别是针对那些需要频繁重用中间数据集的集群规模计算任务。这些任务包括迭代式的机器学习算法、图处理算法以及交互式数据挖掘等。为了提高效率，开发者希望避免将中间结果写入持久化分布式文件系统（如 HDFS），而是尽量保持在内存中。Spark也在这个场景下实现了容错机制。

4.1 容错机制

Spark 通过多种方式实现了内存计算的容错性。包含:

数据分区与弹性分布式数据集（RDD）
- RDD 的不可变性：在 Spark 中，所有数据都被组织成弹性分布式数据集（Resilient Distributed Datasets, RDD）。RDD 是一种不可变的、分区的数据集合，支持并行操作。由于 RDD 是不可变的，任何转换操作都会创建一个新的 RDD，而不会修改原始数据。这种设计使得 Spark 可以轻松地追踪数据的依赖关系，并在需要时重新计算丢失的数据。
- 血缘关系（Lineage）：每个 RDD 都记录了它的“血缘关系”，即它是如何从其他 RDD 通过一系列转换操作生成的。当某个分区的数据丢失时，Spark 可以根据血缘信息重新计算该分区，而不需要重新执行整个程序。这大大减少了恢复的成本和时间。
检查点（Checkpointing）
- 定期保存状态：为了防止频繁的重新计算，Spark 提供了检查点机制。用户可以选择将某些重要的 RDD 持久化到可靠的存储系统（如 HDFS）中。这样，在节点故障时，可以从最近的检查点恢复数据，而不是从头开始重新计算整个血缘链。
- 自动检查点：对于迭代式算法或长时间运行的任务，Spark 还可以自动触发检查点，确保中间结果被定期保存，从而减少恢复时的工作量。
日志记录与增量更新
- 窄依赖与宽依赖：Spark 区分了两种类型的依赖关系——窄依赖和宽依赖。窄依赖指的是每个父 RDD 的分区只被一个子 RDD 的分区所使用，而宽依赖则涉及多个父 RDD 的分区被多个子 RDD 的分区使用。对于窄依赖，Spark 可以通过简单的重新计算来恢复丢失的数据；而对于宽依赖，通常会触发检查点或更复杂的恢复策略。
- 日志记录：虽然 Spark 不像某些系统那样维护详细的更新日志，但它可以通过记录任务的执行状态和依赖关系来实现类似的功能。例如，调度器会跟踪每个任务的执行情况，包括哪些任务已经完成、哪些还在进行中。如果某个任务失败，调度器可以根据这些信息决定是否重试该任务或从最近的检查点重新开始。
任务级别的容错
- 任务重试：当某个任务（如 Map 或 Reduce 任务）失败时，Spark 会自动尝试在其他节点上重新执行该任务。由于 Spark 的任务是细粒度的，单个任务的失败不会影响整个作业的执行，只需重新执行失败的任务即可。
- 投机执行（Speculative Execution）：为了应对慢速机器或临时故障，Spark 还支持投机执行。如果某个任务执行时间过长，调度器会在其他节点上启动该任务的副本。一旦任意一个副本完成，另一个副本会被终止。这种方法不仅提高了容错性，还加快了整体处理速度。
持久化与缓存
- 内存中的持久化：Spark 允许用户将 RDD 持久化到内存中，以便后续操作可以直接访问这些数据，而无需重新计算。持久化的 RDD 可以选择不同的存储级别，如仅内存、内存和磁盘、仅磁盘等，以适应不同的性能和容错需求。
- 容错与性能平衡：通过合理设置持久化策略，用户可以在性能和容错性之间找到最佳平衡。例如，对于那些频繁访问但不太可能丢失的数据，可以选择仅内存存储；而对于关键数据，则可以选择内存和磁盘混合存储，以确保即使内存中的数据丢失，也可以从磁盘中恢复。

结合传统 MapReduce 容错机制

检查点与日志：类似于 MapReduce，Spark 也会在每个阶段结束时将结果写入文件系统，作为检查点。此外，调度器会维护一个未完成任务的列表，类似于 MapReduce 中的日志，用于在节点故障时重新调度任务。
功能结构的优势：由于 Spark 程序通常是函数式的，任务可以以细粒度的方式重启。这意味着即使某个节点失败，也只需要重新执行该节点上的特定任务，而不需要重启整个程序。这大大提高了容错效率，减少了恢复时间。

4.2 RDD操作

rdd_operation

RDD首先通过文件输入仅创建, 其可以通过算子不停得生成新的RDD, 这些算子包括map, filter, flatMap, union, intersection, distinct, groupByKey, reduceByKey, aggregateByKey, sortByKey, join, cogroup等。这些算子不具体介绍了, 使用过Numpy的同学应该对这些算子非常熟悉, 并且这些算子基本上称得上见名知意。

4.3 内存持久化

rdd_persist

这个案例代码中, persist算子用于将RDD持久化到内存中, 这样在后续的计算中可以直接使用内存中的数据, 而不需要重新计算。

4.4 RDD的机制

4.4.1 惰性

在Spark中，RDD是一个惰性求值的概念，类似于视图, 其特点如下:

惰性求值：
- RDD的操作分为两类：转换（Transformation）和行动（Action）。
- 转换操作（如map、filter）是惰性的，它们只是定义了数据的转换方式，并不立即执行计算。
- 只有当行动操作（如collect、count）被调用时，Spark才会触发实际的计算。
计算流程的定义：
- RDD通过一系列转换操作定义了数据的处理流程。
- 这些转换操作会生成一个逻辑执行计划，Spark在需要时才会根据这个计划执行计算。
优化执行：
- 惰性求值允许Spark在执行前对整个计算流程进行优化。
- Spark可以通过合并多个转换操作来减少数据的传输和计算开销。
血缘关系（Lineage）：
- RDD记录了其生成过程的血缘关系，这使得Spark可以在数据丢失时通过重新计算来恢复数据。失败时, 只需要在最接近失败位置处发生Action操作的算子开始重新计算。