倾斜分区判定完毕之后，下一步，就是根据 advisoryPartitionSizeInBytes 参数指定的目标尺寸，对大分区进行拆分

Spark SQL 必须要仰仗运行时的执行状态，而 Shuffle 中间文件，则是这些状态的唯一来源。

Shuffle 在 Map 阶段往往会对数据做排序，而这恰恰正中 SMJ 机制的下怀。对于已经排好序的两张表，SMJ 的复杂度是 O(M + N)，这样的执行效率与 HJ 的 O(M) 可以说是不相上下。再者，SMJ 在执行稳定性方面，远胜于 HJ，在内存受限的情况下，SMJ 可以充分利用磁盘来顺利地完成关联计算。因此，考虑到 Shuffle SMJ 的诸多优势，Shuffle HJ 就像是关公后面的周仓，Spark SQL 向来对之视而不见，所以对于 HJ 你大概知道它的作用就行。

在任何情况下，不论数据的体量是大是小、不管内存是否足够，Shuffle Join 在功能上都能够“不辱使命”，成功地完成数据关联的计算。

与前两者相比，Nested Loop Join 看上去有些多余，嵌套的双层 for 循环带来的计算复杂度最高：O(M * N)。不过，尺有所短寸有所长，执行高效的 HJ 和 SMJ 只能用于等值关联，也就是说关联条件必须是等式，像 salaries(“id”) < employees(“id”) 这样的关联条件，HJ 和 SMJ 是无能为力的

考虑到 SMJ 对于排序的苛刻要求，后来又有人推出了 HJ 算法。HJ 的设计初衷是以空间换时间，力图将基表扫描的计算复杂度降低至 O(1)。

我们知道，使用 Java Object 来存储数据会引入大量额外的存储开销。为此，Tungsten 设计并实现了一种叫做 Unsafe Row 的二进制数据结构。Unsafe Row 本质上是字节数组，它以极其紧凑的格式来存储 DataFrame 的每一条数据记录，大幅削减存储开销，从而提升数据的存储与访问效率。

而使用 DataFrame API 开发的应用，则会先过一遍 Spark SQL，由 Spark SQL 优化过后再交由 Spark Core 去做执行

数据块的概念与 RDD 数据分区（Partitions）是一致的

LinkedHashMap[BlockId, MemoryEntry]。

Spark 存储系统负责维护所有暂存在内存与磁盘中的数据，这些数据包括 Shuffle 中间文件、RDD Cache 以及广播变量。

coalesce 会降低同一个 stage 计算的并行度，导致 cpu 利用率不高，任务执行时间变长。我们目前有一个实现是需要将最终的结果写成单个 avro 文件，前面的转换过程可能是各种各样的，我们在最后阶段加上 repartition(1).write().format('avro').mode('overwrite').save('path')。最近发现有时前面的转换过程中有排序时，使用 repartition(1) 有时写得单文件顺序不对，使用 coalesce(1) 顺序是对的，但 coalesce(1) 有性能问题。目前想到可以 collect 到 d

collect 算子有两处性能隐患，一个是拉取数据过程中引入的网络开销，另一个 Driver 的 OOM（内存溢出，Out of Memory）

其中 spark.executor.memory 是绝对值，它指定了 Executor 进程的 JVM Heap 总大小。另外两个配置项，spark.memory.fraction 和 spark.memory.storageFraction 都是比例值，它们指定了划定不同区域的空间占比。spark.memory.fraction 用于标记 Spark 处理分布式数据集的内存总大小，这部分内存包括 Execution Memory 和 Storage Memory 两部分，也就是图中绿色的矩形区域。（M – 300）* （1 – mf）刚好就是 User Memory 的区域大小，也就是图中蓝色区域的部分。spark.memory.storageFraction 则用来进一步区分 Execution Memory 和 Storage Memory 的初始大小。我们之前说过，Reserved Memory 固定为 300MB。（M – 300）* mf * sf 是 Storage Memory 的初始大小，相应地，（M – 300）* mf * （1 – sf）就是 Execution Memory 的初始大小。

当一个 RDD 在代码中的引用次数大于 1 时，你可以考虑通过给 RDD 加 Cache 来提升作业性能

对于 Storage Memory 抢占的 Execution Memory 部分，当分布式任务有计算需要时，Storage Memory 必须立即归还抢占的内存，涉及的缓存数据要么落盘、要么清除；对于 Execution Memory 抢占的 Storage Memory 部分，即便 Storage Memory 有收回内存的需要，也必须要等到分布式任务执行完毕才能释放。

在 1.6 版本之后，Spark 推出了统一内存管理模式，在这种模式下，Execution Memory 和 Storage Memory 之间可以相互转化

sortByKey：排序

aggregateByKey

一个 Map 端聚合函数 f1，以及一个 Reduce 端聚合函数 f2

从图中你可以看出来，尽管 reduceByKey 也会引入 Shuffle，但相比 groupByKey 以全量原始数据记录的方式消耗磁盘与网络，reduceByKey 在落盘与分发之前，会先在 Shuffle 的 Map 阶段做初步的聚合计算。比如，在数据分区 0 的处理中，在 Map 阶段，reduceByKey 把 Key 同为 Streaming 的两条数据记录聚合为一条，聚合逻辑就是由函数 f 定义的、取两者之间 Value 较大的数据记录，这个过程我们称之为“Map 端聚合”。相应地，数据经由网络分发之后，在 Reduce 阶段完成的计算，我们称之为“Reduce 端聚合”。

对于所有 Map Task 生成的中间文件，Reduce Task 需要通过网络从不同节点的硬盘中下载并拉取属于自己的数据内容。不同的 Reduce Task 正是根据 index 文件中的起始索引来确定哪些数据内容是“属于自己的”。Reduce 阶段不同于 Reduce Task 拉取数据的过程，往往也被叫做 Shuffle Read。

（Reduce Task Partition ID，Record Key）

当 Map 结构被灌满之后，Spark 根据主键对 Map 中的数据记录做排序，然后把所有内容溢出到磁盘中的临时文件

Map 阶段与 Reduce 阶段的计算过程相对清晰明了，二者都是利用 reduce 运算完成局部聚合与全局聚合。在 reduceByKey 的计算过程中，Shuffle 才是关键。

SchedulerBackend 与集群内所有 Executors 中的 ExecutorBackend 保持周期性通信，双方通过 LaunchedExecutor、RemoveExecutor、StatusUpdate 等消息来互通有无、变更可用计算资源

像上面这种定向到计算节点粒度的本地性倾向，Spark 中的术语叫做 NODE_LOCAL。除了定向到节点，Task 还可以定向到进程（Executor）、机架、任意地址，它们对应的术语分别是 PROCESS_LOCAL、RACK_LOCAL 和 ANY。

以 Actions 算子为起点，从后向前回溯 DAG，以 Shuffle 操作为边界去划分 Stages

DAGScheduler 是任务调度的发起者，DAGScheduler 以 TaskSet 为粒度，向 TaskScheduler 提交任务调度请求

这里有一种特殊的生命周期值得讨论：'static，其生命周期能够存活于整个程序期间。

现在换一种方式思考这个关系，父节点应该拥有其子节点：如果父节点被丢弃了，其子节点也应该被丢弃。然而子节点不应该拥有其父节点：如果丢弃子节点，其父节点应该依然存在。这正是弱引用的例子！

结合 Rc<T> 和 RefCell<T> 来拥有多个可变数据所有者

在任意给定时刻，只能拥有一个可变引用或任意数量的不可变引用 之一（而不是两者）。

所以 Message 值需要的最大空间是存储其最大成员所需的空间大小。

使用 Box<T> 指向堆上的数据

当希望拥有一个值并只关心它的类型是否实现了特定 trait 而不是其具体类型的时候

当有大量数据并希望在确保数据不被拷贝的情况下转移所有权的时候

当有一个在编译时未知大小的类型，而又想要在需要确切大小的上下文中使用这个类型值的时候

版本向量

r 和 w 都常都选择超过半数，如 (n+1)/2

由于 w + r > n 时，总会至少有一个节点（读写子集至少有一个节点的交集）

两个有因果依赖的（先插入，后更新）的语句，在复制到 Leader 2 时，由于速度不同，导致其接收到的数据违反了因果一致性。

多主模型应用场景

让所有有因果关系的事件路由到一个分区。

写后读保证的是写后读顺序，单调读保证的是多次读之间的顺序。

客户端记下本客户端上次改动时的时间戳，在读从副本时，利用此时间戳来看某个从副本是否已经同步了改时间戳之前内容

字段标号不能修改，只能追加。这样旧代码在看到不认识的标号时，省略即可。

在更改模式时（比如 alter table），数据库不允许增加既没有默认值、也不允许为空的列

Avro

向后兼容：新加的字段需为 optional。这样在解析旧数据时，才不会出现字段缺失的情况。

列式存储的写入

不同副本，不同排序

不可能同时对多列进行排序。因为我们需要维护多列间的下标间的对应关系，才可能按行取数据。

聚集索引（clustered index）

性能优化

图模型和网络模型

无论是 BFS、DFS 还是剪枝等实现细节

数据类型和结构由外部决定，你没办法控制数据的变化。

关系模型

元组（tuples）

在每一层，通过对外暴露简洁的数据模型，我们隔离和分解了现实世界的复杂度。

弱 Schema（读时解析）

强 Schema（写时约束）

周同步，每

大数据