环球新动态：Spark系列 - (5) Spark Shuffle

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

环球新动态：Spark系列 - (5) Spark Shuffle

2023-03-02 05:54:34 来源：博客园

目前已经更新完《Java并发编程》,《JVM性能优化》,《Spring核心知识》《Docker教程》和《Spark基础知识》，都是多年面试总结。欢迎关注【后端精进之路】，轻松阅读全部文章。
Java并发编程：
Java并发编程系列-(1) 并发编程基础
Java并发编程系列-(2) 线程的并发工具类
Java并发编程系列-(3) 原子操作与CAS
Java并发编程系列-(4) 显式锁与AQS
Java并发编程系列-(5) Java并发容器
Java并发编程系列-(6) Java线程池
Java并发编程系列-(7) Java线程安全
Java并发编程系列-(8) JMM和底层实现原理
Java并发编程系列-(9) JDK 8/9/10中的并发
Docker教程:

(资料图)
Docker系列-(1) 原理与基本操作
Docker系列-(2) 镜像制作与发布
Docker系列-(3) Docker-compose使用与负载均衡
Docker 安装 Jenkins 并实现项目自动化部署
如何0失误快速搭建K8s环境？你想了解的这都有
JVM性能优化:
JVM性能优化系列-(1) Java内存区域
JVM性能优化系列-(2) 垃圾收集器与内存分配策略
JVM性能优化系列-(3) 虚拟机执行子系统
JVM性能优化系列-(4) 编写高效Java程序
JVM性能优化系列-(5) 早期编译优化
JVM性能优化系列-(6) 晚期编译优化
JVM性能优化系列-(7) 深入了解性能优化
Spring MVC系列：
Spring MVC系列-(1) Spring概述
Spring MVC系列-(2) Bean的装配
Spring MVC系列-(3) Bean的装配
Spring MVC系列-(4) Bean的生命周期
Spring MVC系列-(5) AOP
Spring MVC系列-(6) 声明式事务
Spring MVC系列-(7) IOC初始化流程
Spark系列：
Spark系列 - (1) Spark基础
Spark系列 - (2) Spark核心概念
Spark系列 - (3) Spark SQL
Spark系列 - (4) Spark任务调度
Spark系列 - (5) Spark Shuffle详细解读
Spark系列 - (6) Spark内存管理

5. Spark Shuffle

5.1 Shuffle概念

有些运算需要将各节点上的同一类数据汇集到某一节点进行计算，把这些分布在不同节点的数据按照一定的规则汇集到一起的过程称为Shuffle。

下图是一个简单的Spark Job的运行图，根据宽依赖将任务划分为不同的Stage，

在划分stage时，最后一个stage称为 FinalStage，它本质上是一个ResultStage对象，前面的所有stage被称为ShuffleMapStage。

ShuffleMapStage的结束伴随着shuffle文件的写磁盘。
ResultStage基本上对应代码中的action算子，即将一个函数应用在RDD的各个partition的数据集上，意味着一个job 的运行结束。

触发Shuffle的操作大概分为如下几类：

5.2 核心思想

Shuffle的核心思想可以用上图来表示，前一个Stage的 ShuffleMapTask 进行 Shuffle Write，把数据存储在 BlockManager上面，并且把数据位置元信息上报到Driver 的MapOutTrack组件中，下一个Stage根据数据位置元信息，进行Shuffle Read，拉取上个Stage的输出数据。

Shuffle中的任务个数

1. Map端task个数的确定

Shuffle过程中的task个数由RDD分区数决定，而RDD的分区个数与参数spark.default.parallelism有关.

在Yarn Cluster模式下，如果没有手动设置，则：spark.default.parallelism = max(所有executor使用的core总数，2)。

参与决定分区数的参数defaultMinPartitions也是由该参数确定的，defaultMinPartitions=min(spark.default.parallelism, 2)

由于spark对于一个partition中的最大文件大小有限制（spark.files.maxPartitionBytes = 128 M (默认)），为128M，因此自定义分区时，不能选的过小。

常见的几种情况如下：

2. reduce端的task个数的确定

Reduce端进行数据的聚合，一部分聚合算子可以手动指定并行度，如果没有指定，则以map端的最后一个RDD分区作为其分区数，分区数也就决定了reduce端的task个数。

5.3 HashShuffle

1. 未优化的HashShuffleManager

相对于传统的 MapReduce，Spark 假定大多数情况下 Shuffle 的数据不需要排序，例如 Word Count，强制排序反而会降低性能。因此不在 Shuffle Read 时做 Merge Sort，如果需要合并的操作的话，则会使用聚合（agggregator），即用了一个 HashMap （实际上是一个 AppendOnlyMap）来将数据进行合并。

在 Map Task 过程按照 Hash 的方式重组 Partition 的数据，不进行排序。每个 Map Task 为每个 Reduce Task 生成一个文件，通常会产生大量的文件（即对应为 M*R 个中间文件，其中 M 表示 Map Task 个数，R 表示 Reduce Task 个数），伴随大量的随机磁盘 I/O 操作与大量的内存开销。

总结下这里的两个严重问题：

生成大量文件，占用文件描述符，同时引入 DiskObjectWriter 带来的 Writer Handler 的缓存也非常消耗内存；
如果在 Reduce Task 时需要合并操作的话，会把数据放在一个 HashMap 中进行合并，如果数据量较大，很容易引发 OOM。

2. 优化后的HashShuffleManager

针对上面的第一个问题，Spark做了改进，引入了File Consolidation机制。

一个Executor上所有的Map Task生成的分区文件只有一份，即将所有的Map Task相同的分区文件合并，这样每个 Executor上最多只生成N个分区文件。

这样就减少了文件数，但是假如下游 Stage 的分区数 N 很大，还是会在每个Executor上生成 N 个文件，同样，如果一个 Executor 上有 K 个 Core，还是会开 K*N 个 Writer Handler，所以这里仍然容易导致OOM。

5.4 SortShuffle

SortShuffleManager的运行机制主要分成两种，一种是普通运行机制，另一种是bypass运行机制。当shuffle read task的数量小于等于spark.shuffle.sort.bypassMergeThreshold参数的值时（默认为200），就会启用bypass机制。

1. 普通运行机制

下图说明了普通的SortShuffleManager的原理。在该模式下，数据会先写入一个内存数据结构中，此时根据不同的shuffle算子，可能选用不同的数据结构。如果是reduceByKey这种聚合类的shuffle算子，那么会选用Map数据结构，一边通过Map进行聚合，一边写入内存；如果是join这种普通的shuffle算子，那么会选用Array数据结构，直接写入内存。接着，每写一条数据进入内存数据结构之后，就会判断一下，是否达到了某个临界阈值。如果达到临界阈值的话，那么就会尝试将内存数据结构中的数据溢写到磁盘，然后清空内存数据结构。

在溢写到磁盘文件之前，会先根据key对内存数据结构中已有的数据进行排序。排序过后，会分批将数据写入磁盘文件。默认的batch数量是10000条，也就是说，排序好的数据，会以每批1万条数据的形式分批写入磁盘文件。写入磁盘文件是通过Java的BufferedOutputStream实现的。BufferedOutputStream是Java的缓冲输出流，首先会将数据缓冲在内存中，当内存缓冲满溢之后再一次写入磁盘文件中，这样可以减少磁盘IO次数，提升性能。

一个task将所有数据写入内存数据结构的过程中，会发生多次磁盘溢写操作，也就会产生多个临时文件。最后会将之前所有的临时磁盘文件都进行合并，这就是merge过程，此时会将之前所有临时磁盘文件中的数据读取出来，然后依次写入最终的磁盘文件之中。此外，由于一个task就只对应一个磁盘文件，也就意味着该task为下游stage的task准备的数据都在这一个文件中，因此还会单独写一份索引文件，其中标识了下游各个task的数据在文件中的start offset与end offset。

SortShuffleManager由于有一个磁盘文件merge的过程，因此大大减少了文件数量。比如第一个stage有50个task，总共有10个Executor，每个Executor执行5个task，而第二个stage有100个task。由于每个task最终只有一个磁盘文件，因此此时每个Executor上只有5个磁盘文件，所有Executor只有50个磁盘文件。

2. bypass运行机制

下图说明了bypass SortShuffleManager的原理。bypass运行机制的触发条件如下：

shuffle map task数量小于spark.shuffle.sort.bypassMergeThreshold参数的值。
不是聚合类的shuffle算子（比如reduceByKey）。

此时task会为每个下游task都创建一个临时磁盘文件，并将数据按key进行hash然后根据key的hash值，将key写入对应的磁盘文件之中。当然，写入磁盘文件时也是先写入内存缓冲，缓冲写满之后再溢写到磁盘文件的。最后，同样会将所有临时磁盘文件都合并成一个磁盘文件，并创建一个单独的索引文件。

该过程的磁盘写机制其实跟未经优化的HashShuffleManager是一模一样的，因为都要创建数量惊人的磁盘文件，只是在最后会做一个磁盘文件的合并而已。因此少量的最终磁盘文件，也让该机制相对未经优化的HashShuffleManager来说，shuffle read的性能会更好。

而该机制与普通SortShuffleManager运行机制的不同在于：第一，磁盘写机制不同；第二，不会进行排序。也就是说，启用该机制的最大好处在于，shuffle write过程中，不需要进行数据的排序操作，也就节省掉了这部分的性能开销。

扩展：Tungsten-Sort Based Shuffle / Unsafe Shuffle

从 Spark 1.5.0 开始，Spark 开始了钨丝计划（Tungsten），目的是优化内存和CPU的使用，进一步提升spark的性能。由于使用了堆外内存，而它基于 JDK Sun Unsafe API，故 Tungsten-Sort Based Shuffle 也被称为 Unsafe Shuffle。

它的做法是将数据记录用二进制的方式存储，直接在序列化的二进制数据上 Sort 而不是在 Java 对象上，这样一方面可以减少内存的使用和 GC 的开销，另一方面避免 Shuffle 过程中频繁的序列化以及反序列化。在排序过程中，它提供 cache-efficient sorter，使用一个 8 bytes 的指针，把排序转化成了一个指针数组的排序，极大的优化了排序性能。

但是使用 Tungsten-Sort Based Shuffle 有几个限制，Shuffle 阶段不能有 aggregate 操作，分区数不能超过一定大小（2^24-1，这是可编码的最大 Parition Id），所以像 reduceByKey 这类有 aggregate 操作的算子是不能使用 Tungsten-Sort Based Shuffle，它会退化采用 Sort Shuffle。

从 Spark-1.6.0 开始，把 Sort Shuffle 和 Tungsten-Sort Based Shuffle 全部统一到 Sort Shuffle 中，如果检测到满足 Tungsten-Sort Based Shuffle 条件会自动采用 Tungsten-Sort Based Shuffle，否则采用 Sort Shuffle。从Spark-2.0.0开始，Spark 把 Hash Shuffle 移除，可以说目前 Spark-2.0 中只有一种 Shuffle，即为 Sort Shuffle。

5.5 Shuffle Read

1. 何时开始fetch上一个stage的数据

当 parent stage 的所有 ShuffleMapTasks 结束后再 fetch。

理论上讲一个 ShuffleMapTask 结束后就可以 fetch，但是为了迎合 stage 的概念（即一个 stage 如果其 parent stages 没有执行完，自己是不能被提交执行的），还是选择全部 ShuffleMapTasks 执行完再去 fetch。

2. 边 fetch 边处理还是一次性 fetch 完再处理？

边fetch边处理。

本质上，MapReduce shuffle 阶段就是边 fetch 边使用 combine() 进行处理，只是 combine() 处理的是部分数据。MapReduce 为了让进入 reduce() 的 records 有序，必须等到全部数据都 shuffle-sort 后再开始 reduce()。

Spark 不要求 shuffle 后的数据全局有序，因此没必要等到全部数据 shuffle 完成后再处理。

那么如何实现边 shuffle 边处理，而且流入的 records 是无序的？
使用可以 aggregate 的数据结构，比如 HashMap。每 shuffle 得到（从缓冲的 FileSegment 中 deserialize 出来）一个 record，直接将其放进 HashMap 里面。如果该 HashMap 已经存在相应的 Key，那么直接进行 aggregate 也就是 func(hashMap.get(Key), Value)，并将 func 的结果重新 put(key) 到 HashMap 中去。

3. fetch 来的数据存放到哪里？

刚 fetch 来的 FileSegment 存放在 softBuffer 缓冲区，经过处理后的数据放在内存 + 磁盘上。也可以灵活设置这些数据是“只用内存”还是“内存＋磁盘”。如果spark.shuffle.spill = false就只用内存。

内存使用的是AppendOnlyMap，类似Java的HashMap，内存＋磁盘使用的是ExternalAppendOnlyMap，如果内存空间不足时，ExternalAppendOnlyMap可以将records进行sort后spill到磁盘上，等到需要它们的时候再进行归并。

4. 怎么获得要 fetch 的数据的存放位置？

一个 ShuffleMapStage形成后，会将该 stage 最后一个 final RDD 注册到 MapOutputTrackerMaster，reducer 在 shuffle 的时候去 driver 里面的 MapOutputTrackerMaster 询问 ShuffleMapTask 输出的数据位置。

每个 ShuffleMapTask 完成时会将 FileSegment 的存储位置信息汇报给 MapOutputTrackerMaster。MapOutputTrackerMaster.registerShuffle(shuffleId, rdd.partitions.size)

参考：

https://zhuanlan.zhihu.com/p/67061627
http://lionheartwang.github.io/blog/2018/03/11/spark-shuffle-implementation/
https://toutiao.io/posts/eicdjo/preview

搜索『后端精进之路』并关注，立刻获取最新文章和面试资料。

关键词：磁盘文件数据结构写入磁盘