SQL Optimizer 解析

https://bytedance.feishu.cn/file/boxcn9uWBTLWg2a8GIUSRJ0Txqb

https://live.juejin.cn/4354/yc_SQL

hash join和sort merge join：https://blog.csdn.net/lp284558195/article/details/80717219

大数据体系和SQL

SQL 的一生

    1. img
    2. Parser
      1. 把文本变成抽象语法树结构（AST）
      2. 涉及词法分析阶段（拆分字符串，提取关键字，字符串，数值等）和语法分析阶段（把词条按照定义的语法规则组装成抽象语法树结构）
      3. 和编译原理课程里的“前端”知识相关
    3. Analyzer
      1. 访问库/表元信息并绑定
      2. 判断 SQL 是否合理，比如数据库，表和列名是否存在，列的数据类型是否正确
      3. 将 AST 转换成逻辑计划树（在某些系统中这个工作由一个 Converter 完成）

  2. 逻辑计划树

    1. 所谓逻辑计划树，可以理解为逻辑地描述一个 SQL 如何一步步地执行查询和计算，最终得到执行结果的一个分步骤地计划。树中每个节点是是一个算子，定义了对数据集合的计算操作（过滤，排序，聚合，连接），边代表了数据的流向，从孩子节点流向父节点。之所以称它为逻辑的，是因为算子定义的是逻辑的计算操作，没有指定实际的算法，比如对于逻辑的排序算子，逻辑计划树里没有指定使用快排还是堆排。

  3. 查询优化

    1. SQL 是一种声明式语言，用户只描述做什么，没有告诉数据库怎么做
    2. 查询优化的目标是为 SQL 找到一个正确的且执行代价最小的执行计划
    3. 查询优化器是数据库的大脑，最复杂的模块，很多相关问题都是 NP 的
    4. 一般 SQL 越复杂，Join 的表越多，数据量越大，查询优化的意义就越大，因为不同执行方式的性能差别可能有成百上千倍
      1. 类比 gcc/g++ 编译程序时的编译级别（-O1, -O2, -O3），经过编译优化的程序运行效率更高

  4. 物理执行计划

    1. 优化器的输出是一个分布式的物理执行计划。
    2. 分布式物理执行计划的目标是在单机 Plan 的基础上最小化数据移动和最大化本地 Scan，生成 PlanFragment 树。
    3. 一个 PlanFragment 封装了在一台机器上对数据集的操作逻辑。每个 PlanFragment 可以在每个 executor 节点生成 1 个或多个执行实例，不同执行实例处理不同的数据集，通过并发来提升查询性能。
    4. Plan 分布式化的方法是增加 shuffle 算子，执行计划树会以 shuffle 算子为边界拆分为PlanFragment。

  5. Executor

    1. Executor 按照物理执行计划扫描和处理数据，充分利用机器资源（CPU 流水线，乱序执行，cache，SIMD）

常见的查询优化器

RBO

Rule-based Optimizer

  • 基于关系代数等价规则对逻辑计划进行变换
  • 实现上：
    • Pattern：定义了特定结构的 Operator 子树（结构）
    • Rule：定义了如何将其匹配的节点替换（Substitute）为新形态，从而生成新的、等价的Operator 树（原地替换）
    • 优化器搜索过程被抽象为不断匹配 Pattern 然后应用 Rule 转换，直到没有可以匹配的 rule
  • 局限性：
    • 无法解决多表连接问题
    • 无法确定和选择最优的分布式 Join/Aggregate 执行方式

列裁剪

scan时只扫描select选中的列

谓词下推

如有where条件，在scan时就过滤掉

传递闭包

如有jion on条件，可将一个表的where scan 传递给另一个表的 where scan

Runtime Filter（min-max filter，in-list filter，bloom filter）

jion前2个表都有filter，可将一个表filter后的一些索引特性在运行时传递给另一个表，这是另一个表进行filter时就可以减少很大一部分数据

Join 消除

谓词合并

小结

主流RBO实现一般都有几百条基于经验归纳得到的优化规则

实现简单，优化速度块，但不能保证最优的执行计划

CBO

Cost-based Optimizer

过程

使用一个模型估算执行计划的代价，选择代价最小的执行计划

分而治之，执行计划的代价等于所有算子的执行代价之和

通过 RBO 得到（所有）可能的等价执行计划（非原地替换）

算子代价包含 CPU，cache misses，memory，disk I/O，network I/O 等代价

  • 和算子的统计信息有关，比如输入、输出结果的行数，每行大小等
  • 叶子算子 scan：通过统计原始表数据得到
    • 中间算子：根据一定的推导规则，从下层算子的统计信息推导得到
    • 和具体的算子类型，以及算子的物理实现有关（e.g. hash join vs. sort join）

使用动态规划枚举所有执行计划，选出执行代价最小的执行计划

统计信息

  • 基表统计信息
    • 表或者分区级别：行数、行平均大小、表在磁盘中占用了多少字节等
    • 列级别：min、max、num nulls、num、not nulls、num、distinct value(NDV)、histogram 等
  • 推导统计信息
    • 选择率（selectivity） ：对于某一个过滤条件，查询会从表中返回多大比例的数据
    • 基数（cardinality） ：基本含义是表的 unique 行数，在查询计划中常指算子需要处理的行数

统计信息的收集方式

三种

统计信息推导规则

统计信息的问题

小结

CBO使用代价模型和统计信息估算执行计划的代价

CBO使用贪心或者动态规划算法寻求最优执行计划

社区开源实践

Apache Calcite

主流的查询优化器都包含RBO/CBO

Apache Calcite是大数据领域很流行的查询优化器

Apache Calcite RBO定义了很多优化规则，使用pattern匹配子树，执行等价变换

Apache Calcite CBO基于Volcano/Cascade 框架

Volcano/Cascade的精髓Memo、动态规划、剪枝

前沿趋势

存储计算分离

HSAP, HTAP, HTSAP

Cloud Native, Serverless

数据仓库，数据湖，湖仓一体，联邦查询

智能化

  • AI4DB
    • 自配置：智能调参（OtterTune，QTune）、负载预测、负载调度
    • 自诊断和自愈合：软硬件错误、错误恢复和迁移
    • 自优化：统计信息估计（ Learned cardinalities ）、代价估计、学习型优化器（IBM DB2 LEO），索引推荐，视图推荐
  • DB4AI
    • 内嵌人工智能算法（MLSQL，SQLFlow）
    • 内嵌机器学习框架（SparkML， Alink， dl-on-flink ）

流/批/OLAP 一体的 Flink 引擎介绍

https://bytedance.feishu.cn/file/boxcni8teJOjd4vUsgxn8rL0ylc

https://live.juejin.cn/4354/yc_OLAP

批处理

所谓 批处理 是指把一项数据处理任务先分解成更小粒度的任务，把这些任务分布在集群中的各台实例上进行计算，之后把各实例上的计算结果重新计算和组合成最终结果。批处理系统通常会操作大量的静态的数据，并等到这些数据全部处理完成后才能得到返回的结果。

批处理方式使用的数据集通常有以下特征：

  • 有界：批处理数据集代表数据的有限集合
  • 持久：数据通常始终存储在某种类型的持久存储位置中
  • 大量：批处理操作通常是处理极为海量数据集的唯一方法

流处理

流处理 方式会随时对进入系统的数据进行实时的计算，这种模式不需要针对整个数据集执行操作，而是对通过系统传输的每个数据项执行操作。流处理中的数据集是 无边界 的，这就产生了几个重要的影响：

  • 完整数据集只能代表截至目前已经进入到系统中的数据总量。
  • 工作数据集也许更相关，在特定时间只能代表某个单一数据项。
  • 处理工作是基于事件的，除非明确停止否则没有“尽头”。处理结果立刻可用，并会随着新数据的抵达继续更新。

混合处理

在大数据处理技术中流派中，除了单纯的批处理和流处理模式之外，还有一些处理框架既可以进行批处理也可以进行流处理，我们称之为混合处理框架。虽然专注于一种处理方式可能非常适合特定场景，但是混合框架为数据处理提供了通用的解决方案。这些框架可以用相同或相关的组件和 API 处理两种类型的数据，借此让不同的处理需求得以简化。混合处理框架中目前比较著名的就是 Spark 和 Flink 。

完全一次保证：故障后应正确恢复有状态运算符中的状态；

低延迟：越低越好。许多应用程序需要亚秒级延迟；

高吞吐量：随着数据速率的增长，通过管道推送大量数据至关重要；

强大的计算模型：框架应该提供一种编程模型，该模型不限制用户并允许各种各样的应用程序在没有故障的情况下，容错机制的开销很低；

流量控制：来自慢速算子的反压应该由系统和数据源自然吸收，以避免因消费者缓慢而导致崩溃或降低性能；

乱序数据的支持：支持由于其他原因导致的数据乱序达到、延迟到达后，计算出正确的结果；

完备的流式语义：支持窗口等现代流式处理语义抽象；

Google Dataflow Model 的开源引擎实现。

Apache Flink 在开源生态上的能力比较强大，可以支持：

流批一体：支持流式计算和批式计算；

OLAP：Flink 可以支持 OLAP 这种短查询场景；

Flink ML：pyFlink、ALink、AIFlow 等生态支持 Flink 在 ML 场景的应用；

Gelly：图计算；

Stateful Function：支持有状态的 FAAS 场景；

  • JobManager（JM）负责整个任务的协调工作，包括：调度 task、触发协调 Task 做 Checkpoint、协调容错恢复等，核心有下面三个组件：

    • Dispatcher: 接收作业，拉起 JobManager 来执行作业，并在 JobMaster 挂掉之后恢复作业；
    • JobMaster: 管理一个 job 的整个生命周期，会向 ResourceManager 申请 slot，并将 task 调度到对应 TM 上；
    • ResourceManager：负责 slot 资源的管理和调度，Task manager 拉起之后会向 RM 注册；

  • TaskManager（TM）：负责执行一个 DataFlow Graph 的各个 task 以及 data streams 的 buffer 和数据交换。

批式计算是流式计算的特例，Everything is Streams，有界数据集（批式数据）也是一种数据流、一种特殊的数据流；

站在 Flink 的角度，Everything is Streams，无边界数据集是一种数据流，一个无边界的数据流可以按时间切段成一个个有边界的数据集，所以有界数据集（批式数据）也是一种数据流。因此，不管是有边界的数据集（批式数据）还是无边界数据集，Flink 都可以天然地支持，这是 Flink 支持流批一体的基础。并且 Flink 在流批一体上，从上面的 API 到底层的处理机制都是统一的，是真正意义上的流批一体。

Apache Flink 主要从以下几个模块来做流批一体：

  • SQL 层；
  • DataStream API 层统一，批和流都可以使用 DataStream API 来开发；
  • Scheduler 层架构统一，支持流批场景；
  • Failover Recovery 层 架构统一，支持流批场景；
  • Shuffle Service 层架构统一，流批场景选择不同的 Shuffle Service；

Flink 做 OLAP 的优势

  • 统一引擎：流处理、批处理、OLAP 统一使用 Flink 引擎；
    • 降低学习成本，仅需要学习一个引擎；
    • 提高开发效率，很多 SQL 是流批通用；
    • 提高维护效率，可以更集中维护好一个引擎；
  • 既有优势：利用 Flink 已有的很多特性，使 OLAP 使用场景更为广泛；
    • 使用流处理的内存计算、Pipeline；
    • 支持代码动态生成；
    • 也可以支持批处理数据落盘能力；
  • 相互增强：OLAP 能享有现有引擎的优势，同时也能增强引擎能力
    • 无统计信息场景的优化；
    • 开发更高效的算子；
    • 使 Flink 同时兼备流、批、OLAP 处理的能力，成为更通用的框架。

Flink OLAP 场景的挑战

  • 秒级和毫秒级的小作业；

  • 作业频繁启停、资源碎片；

    • Flink OLAP 计算相比流式和批式计算，最大的特点是 Flink OLAP 计算是一个面向秒级和毫秒级的小作业，作业在启动过程中会频繁申请内存、网络以及磁盘资源，导致 Flink 集群内产生大量的资源碎片；

  • Latency + 高 APS 要求；

    • OLAP 最大的特点是查询作业对 Latency 和 QPS 有要求的，需要保证作业在 Latency 的前提下提供比较高的并发调度和执行能力，这就对 Flink 引擎提出了一个新的要求。

  • Flink OLAP 架构现状

    • Client：提交 SQL Query；
    • Gateway：接收 Client 提交的 SQL Query，对 SQL 进行语法解析和查询优化，生成 Flink 作业执行计划，提交给 Session 集群；
    • Session Cluster：执行作业调度及计算，并返回结果。
      • JobManager 管理作业的执行，在接收到 Gateway 提交过来的作业逻辑执行计划后，将逻辑执行计划转换为物理执行计划，为每个物理计算任务分配资源，将每个计算任务分发给不同的 TaskManager 执行，同时管理作业以及每个计算任务执行状态；
      • TaskManager执行具体的计算任务，采用线程模型，为每个计算任务创建计算线程，根据计算任务的上下游数据依赖关系跟上游计算任务建立/复用网络连接，向上游计算任务发送数据请求，并处理上游分发给它的数据。

Flink 在 OLAP 架构上的问题与设想

  • 架构与功能模块：
    • JobManager 与 ResourceManager 在一个进程内启动，无法对JobManager 进行水平扩展；
    • Gateway 与 Flink Session Cluster 互相独立，无法进行统一管理；
  • 作业管理及部署模块：
    • JobManager 处理和调度作业时，负责的功能比较多，导致单作业处理时间长、并占用了过多的内存；
    • TaskManager 部署计算任务时，任务初始化部分耗时验证，消耗大量 CPU；
  • 资源管理及计算任务调度：
    • 资源申请及资源释放流程链路过长；
    • Slot 作为资源管理单元，JM 管理 slot 资源，导致 JM 无法感知到 TM 维度的资源分布，使得资源管理完全依赖于 ResourceManager；
  • 其他：
    • 作业心跳与 Failover 机制，并不合适 AP 这种秒级或毫秒级计算场景；
    • AP 目前使用 Batch 算子进行计算，这些算子初始化比较耗时；

精选案例讲解

Exactly Once 语义在 Flink 中的实现

https://bytedance.feishu.cn/file/boxcnFPburXr95rMNel1SHOvISg

https://live.juejin.cn/4354/yc_Once

数据流和动态表

  • 如何在实时数据流中定义 SQL 语义中的表？

    • 动态表 ： 随时间不断变化的表，在任意时刻，可以像查询静态批处理表一样查询它们

  • 实时流的查询特点？

    • 查询从不终止
    • 查询结果会不断更新，并且会产生一个新的动态表
    • 结果的动态表也可转换成输出的实时流

  • 动态表到实时流的转换

    • Append-only Stream: Append-only 流（只有 INSERT 消息）
    • Retract Stream: Retract 流（同时包含 INSERT 消息和 DELETE 消息）
    • Upsert Stream:: Upsert 流（同时包含 UPSERT 消息和 DELETE 消息）

算子状态

在流式计算中，会存在有状态的计算逻辑（算子）

比如，需要计算某个用户在网上的点击量，该用户在网站当前的总点击次数就是算子状态，对于新的输入数据，先判断是否是该用户的点击行为，如果是，则将保留的点击次数（状态）增加一，并将当前累加结果输出。

Exactly-Once 和 Checkpoint

一致性保证语义

  • At-most-once：每条数据消费至多一次，处理延迟低

  • At-least-once：每条数据消费至少一次，一条数据可能存在重复消费

  • Exactly-once：每条数据都被消费且仅被消费一次，仿佛故障从未发生

端到端 Exactly-Once 实现

Chandy-Lamport算法

解耦了快照制作和数据处理过程，各个算子制作完成状态快照后就可以正常处理数据，不用等下游算子制作制作完成快照； 在快照制作和 Barrier Alignment 过程中需要暂停处理数据，仍然会增加数据处理延迟； 快照保存到远端也有可能极为耗时。

Checkpoint 能保证每条数据都对各个有状态的算子更新一次，sink 输出算子仍然可能下发重复的数据； 严格意义的端到端的 Exactly-once 语义需要特殊的 sink 算子实现。

两阶段提交协议（2PC）

  • Coordinator：协作者，同步和协调所有节点处理逻辑的中心节点

  • Participant：参与者，被中心节点调度的其他执行处理逻辑的业务节点

事务开启：在 sink task 向下游写数据之前，均会开启一个事务，后续所有写数据的操作均在这个事务中执行，事务未提交前，事务写入的数据下游不可读； 预提交阶段：JobManager 开始下发 Checkpoint Barrier，当各个处理逻辑接收到 barrier 后停止处理后续数据，对当前状态制作快照，此时 sink 也不在当前事务下继续处理数据（处理后续的数据需要新打开下一个事务）。状态制作成功则向 JM 成功的消息，失败则发送失败的消息； 提交阶段：若 JM 收到所有预提交成功的消息，则向所有处理逻辑（包括 sink）发送可以提交此次事务的消息，sink 接收到此消息后，则完成此次事务的提交，此时下游可以读到这次事务写入的数据；若 JM 有收到预提交失败的消息，则通知所有处理逻辑回滚这次事务的操作，此时 sink 则丢弃这次事务提交的数据下。

流式计算中的 Window 计算

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

https://bytedance.feishu.cn/file/boxcn5expS9gYOnxpZUBayXPwVg

https://live.juejin.cn/4354/yc_Window

Watermark

Watermark定义：当前系统认为的事件时间所在的真实时间。

简单来说 Watermark 是一个时间戳，表示已经收集完毕的数据的最大 event time，换句话说 event time 小于 Watermark 的数据不应该再出现，基于这个前提我们才有可能将 event time 窗口视为完整并输出结果。

  • 怎么观察一个任务中的watermark是多少，是否是正常的

    • 一般通过Flink Web UI上的信息来观察当前任务的watermark情况
    • 这个问题是生产实践中最容易遇到的问题，大家在开发事件时间的窗口任务的时候，经常会忘记了设置watermark，或者数据太少，watermark没有及时的更新，导致窗口一直不能触发。

  • 如果有部分partition/subtask会断流，应该如何处理

    • 数据断流是很常见的问题，有时候是业务数据本身就有这种特点，比如白天有数据，晚上没有数据。在这种情况下，watermark默认是不会更新的，因为它要取上游subtask发来的watermark中的最小值。此时我们可以用一种IDLE状态来标记这种subtask，被标记为这种状态的subtask，我们在计算watermark的时候，可以把它先排除在外。这样就可以保证有部分partition断流的时候，watermark仍然可以继续更新。

  • 算子对于时间晚于watermark的数据的处理

    • 对于迟到数据，不同的算子对于这种情况的处理可以有不同的实现（主要是根据算子本身的语义来决定的）
    • 比如window对于迟到的数据，默认就是丢弃；比如双流join，对于迟到数据，可以认为是无法与之前正常数据join上。

Window

TUMBLE Window （滚动窗口）

HOP Window （滑动窗口）

SESSION Window （会话窗口）

迟到数据处理

根据上面说到的watermark原理，watermark驱动某个窗口触发输出之后，这个窗口如果后面又来了数据，那这种情况就属于是迟到的数据了。（注意，不是数据的时间晚于watermark就算是迟到，而是它所属的窗口已经被触发了，才算迟到）。

对于迟到的数据，我们现在有两种处理方式：

  1. 使用side output方式，把迟到的数据转变成一个单独的流，再由用户自己来决定如何处理这部分数据

  2. 直接drop掉

注意：side output只有在DataStream的窗口中才可以用，在SQL中目前还没有这种语义，所以暂时只有drop这一个策略。

增量计算 VS 全量计算

  • 增量计算：每条数据到来后，直接参与计算（但是还不需要输出结果）

  • 全量计算：每条数据到来后，先放到一个buffer中，这个buffer会存储到状态里，直到窗口触发输出的时候，才把所有数据拿出来统一进行计算

EMIT触发

正常的窗口都是窗口结束的时候才会进行输出,EMIT触发就是在这种情况下，可以提前把窗口内容输出出来的一种机制。比如我们可以配置一个1天的窗口，每隔5s输出一次它的最新结果，那这样下游就可以更快的获取到窗口计算的结果了。

这种emit的场景就是一个典型的retract的场景，发送的结果类似于+[1], -[1], +[2], -[2], +[4]这样子。这样才能保证window的输出的最终结果是符合语义的。

Window Offset

滑动窗口的时间戳是按照unix timestamp来算的。比如我们要用一个一周的窗口，想要的是从周一开始，到周日结束，但是按照上面这种方式计算出来的窗口的话，就是从周四开始的

Window 高级优化

Mini-batch

赞一小批数据再进行计算，这批数据每个key的state访问只有一次，这样在单个key的数据比较集中的情况下，对于状态访问可以有效的降低频率，最终提升性能。

Local-global

所谓的local-global，就是将原本的聚合划分成两阶段，第一阶段先做一个local的聚合，这个阶段不需要数据shuffle，是直接跟在上游算子之后进行处理的；第二个阶段是要对第一个阶段的结果做一个merge

Distinct状态复用

对于distinct的优化，一般批里面的引擎都是通过把它优化成aggregate的方式来处理，但是在流式window中，我们不能直接这样进行优化，要不然算子就变成会下发retract的数据了。

滑动窗口pane复用

将窗口的状态划分成更小粒度的pane，比如上面3小时窗口、1小时滑动的情况，可以把pane设置为1h，这样每来一条数据，我们就只更新这条数据对应的pane的结果就可以了。当窗口需要输出结果的时候，只需要将这个窗口对应的pane的结果merge起来就可以了。

Spark 原理与实践

https://www.bilibili.com/video/BV11A411L7CK

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

https://bytedance.feishu.cn/file/boxcnvEmKZp3gR3Q1swBBrrxDJb

https://live.juejin.cn/4354/yc_Spark

大数据处理引擎Spark介绍

Spark下载编译

1、官网download

2、查看运行是需要的依赖、参数配置等等

1

tree . -L 1

3、查看客户端的命令

1

tree ./bin -L 1

Spark运行架构和工作原理

Spark生态组件：

  • Spark Core：Spark核心组件，它实现了Spark的基本功能，包含任务调度、内存管理、错误恢复、与存储系统交互等模块。

  • Spark SQL：用来操作结构化数据的核心组件，通过Spark SQL可以直接查询Hive、HBase等多种外部数据源中的数据。

  • Spark Structured Streaming：Spark提供的流式计算框架，支持高吞吐量、可容错处理的实时流式数据处理。

  • MLlib：Spark提供的关于机器学习功能的算法程序库，包括分类、回归、聚类、协同过滤算法等，还提供了模型评估、数据导入等额外的功能。

  • GraphX：Spark提供的分布式图处理框架，拥有对图计算和图挖掘算法的API接口以及丰富的功能和运算符。

  • 独立调度器、Yarn、Mesos、Kubernetes：Spark框架可以高效地在一个到数千个节点之间伸缩计算，集群管理器则主要负责各个节点的资源管理工作，为了实现这样的要求，同时获得最大灵活性，Spark支持在各种集群管理器（Cluster Manager）上运行。

Spark 运行架构和工作原理：

  • Application（应用）：Spark上运行的应用。Application中包含了一个驱动器（Driver）进程和集群上的多个执行器（Executor）进程。

  • Driver Program（驱动器）：运行main()方法并创建SparkContext的进程。

  • Cluster Manager（集群管理器）：用于在集群上申请资源的外部服务（如：独立部署的集群管理器、Mesos或者Yarn）。

  • Worker Node（工作节点）：集群上运行应用程序代码的任意一个节点。

  • Executor（执行器）：在集群工作节点上为某个应用启动的工作进程，该进程负责运行计算任务，并为应用程序存储数据。

  • Task（任务）：执行器的工作单元。

  • Job（作业）：一个并行计算作业，由一组任务（Task）组成，并由Spark的行动（Action）算子（如：save、collect）触发启动。

  • Stage（阶段）：每个Job可以划分为更小的Task集合，每组任务被称为Stage。

Spark目前支持几个集群管理器：

  • Standalone ：Spark 附带的简单集群管理器，可以轻松设置集群。

  • Apache Mesos：通用集群管理器，也可以运行 Hadoop MapReduce 和服务应用程序。（已弃用）

  • Hadoop YARN： Hadoop 2 和 3 中的资源管理器。

  • Kubernetes：用于自动部署、扩展和管理容器化应用程序的开源系统。

SparkCore

RDD(Resilient Distributed Dataset)：弹性分布式数据集，是一个容错的、并行的数据结构

RDD算子：对任何函数进行某一项操作都可以认为是一个算子，RDD算子是RDD的成员函数

Transform(转换)算子: 根据已有RDD创建新的RDD

Action(动作)算子: 将在数据集上运行计算后的数值返回到驱动程序，从而触发真正的计算

DAG(Directed Acyclic Graph): 有向无环图，Spark中的RDD通过一系列的转换算子操作和行动算子操作形成了一个DAG

DAGScheduler：将作业的DAG划分成不同的Stage，每个Stage都是TaskSet任务集合，并以TaskSet为单位提交给TaskScheduler。

TaskScheduler：通过TaskSetManager管理Task，并通过集群中的资源管理器（Standalone模式下是Master，Yarn模式下是ResourceManager）把Task发给集群中Worker的Executor

Shuffle：Spark中数据重分发的一种机制。

SparkSQL

DataFrame： 是一种以RDD为基础的分布式数据集， 被称为SchemaRDD

Catalyst：SparkSQL核心模块，主要是对执行过程中的执行计划进行处理和优化

DataSource：SparkSQL支持通过 DataFrame 接口对各种数据源进行操作。

Adaptive Query Execution：自适应查询执行

Runtime Filter：运行时过滤

Codegen：生成程序代码的技术或系统，可以在运行时环境中独立于生成器系统使用

SparkSql执行过程：

  • Unresolved Logical Plan：未解析的逻辑计划，仅仅是数据结构，不包含任何数据信息。

  • Logical Plan：解析后的逻辑计划，节点中绑定了各种优化信息。

  • Optimized Logical Plan：优化后的逻辑计划

  • Physical Plans：物理计划列表

  • Selected Physical Plan 从列表中按照一定的策略选取最优的物理计划

业界挑战与实践

向量化(vectorization)：将循环转换为向量操作的编译器优化

代码生成(Codegen：Code generation)：生成程序代码的技术或系统，可以在运行时环境中独立于生成器系统使用

大数据 Shuffle 原理与实践

https://bytedance.feishu.cn/file/boxcnQaV9uaxTp4xF0d1vEK5W3c

https://live.juejin.cn/4354/yc_Shuffle

shuffle概述

https://www.cnblogs.com/lintong-zf/p/14231356.html

所谓shuffle就是指把数据打乱重新组合。指数据从map task输出到reduce task输入的这段过程。

Mapreduce

  • map阶段：在单机上进行的针对一小块数据的计算
  • shuffle阶段：在map阶段的基础上，进行数据移动
  • reduce阶段：对移动后的数据进行处理，依然是在单机上处理一小份数据

为什么shuffle如此重要

  • 数据shuffle表示了不同分区数据交换的过程，不同的shuffle策略性能差异较大。目前在各个引擎中shuffle都是优化的重点，在spark框架中，shuffle是支撑spark进行大规模复杂数据处理的基石。

shuffle算子

常见的触发shuffle的算子

  • repartition

    • coalesce、repartition

    重分区一般会shuffle，因为需要在整个集群中，对之前所有的分区的数据进行随机，均匀的打乱，然后把数据放入下游新的指定数量的分区内。

  • ByKey

    • groupByKey、reduceByKey、aggregateByKey、combineByKey、sortByKeysortBy

    byKey类的操作要对一个key，进行聚合操作，那么肯定要保证集群中，所有节点上的相同的key，移动到同一个节点上进行处理。

  • Join

    • cogroup、join

    两个rdd进行join，就必须将相同join key的数据，shuffle到同一个节点上，然后进行相同key的两个rdd数据的笛卡尔乘积。

shuffle过程

HashShuffle

  • 优点：不需要排序
  • 缺点：打开，创建的文件过多

SortShuffle

  • 优点：打开的文件少、支持map-side combine
  • 缺点：需要排序

TungstenSortShuffle

  • 优点：更快的排序效率，更高的内存利用效率
  • 缺点：不支持map-side combine

push shuffle