Suites

test_snapshot_20233

手里拿着锤子，看什么都像钉子

要让程序员知道要开发产品的细节，可以在任务上描述出软件各种场景给出的各种行为

可以用原型工具把它做出来，而不是非得把完整功能开发出来

许多人都是刚刚听到别人要求做的一个功能，就开始脑补接下来的一切。导致的结果，就是付出的努力毫无意义。

如果一个 RDD 的一个分区，只会影响到下游的一个节点，那么我们就称这样的上下游依赖关系为窄依赖。而如果一个 RDD 的一个分区，会影响到下游的多个节点，那么我们就称这样的上下游关系为宽依赖。

则是叶子节点本身不负责存储，而是采用一个共享的存储层，比如 GFS。Dremel 从 2009 年开始，就逐步把存储层全部迁移到了 GFS 上。

对于很多取值为 NULL 的字段来说，我们并不知道它为空，是因为自己作为一个 Optional 字段，所以没有值，还是由于上一层的 Optional 字段的整个对象为空。

而这个解决方案我们之前也已经用过了，那就是像 Bigtable 一样对数据进行分区。只要行键在同一区间的列存储的数据，存储在相同服务器的硬盘上，我们也就不需要通过网络传输，来把基于列存储的数据，组装成一行行的数据了

更合理的解决方案是行列混合存储。因为，我们需要把一批行相同的数据，放在同一个服务器上。

WAL+MemTable+SSTable 组合的解决方案

而在这种大量、小文件的场景下，是发挥不出 MapReduce 进行顺序文件读写的吞吐量的优势的。

《Hive SQL 的编译过程》

数据存储里，Hive 的数据是直接放在 HDFS 上，通过 HDFS 上不同的目录和文件来做到分区和分桶。分区和分桶，使得 Hive 下很多的 MapReduce 任务可以减少需要扫描的数据，提升了整个系统的性能。

科研人员注重在特定领域的深入了解，追求深入，想要寻求新的想法、突破，找到新的研究方向。而作为工程师，更多是学习理解，并和现有的工程系统加以联系，看看是否可以把整个领域最新的进展和自己的工作结合起来。

我们设计系统的时候，不能光考虑对应系统的功能，如何让整个系统对于其他团队的开发者和使用者易用，也非常关键

在最后的提交执行阶段，三阶段提交为了提升系统的可用性也做了一点小小的改造。在进入最后的提交执行阶段的时候，如果参与者等待协调者超时了，那么参与者不会一直在那里死等，而是会把已经答应的事务执行完成。

所以，TCompactProtocol 对于所有的整数类型的值，都采用了可变长数值（VQL，Variable-length quantity）的表示方式，通过 1~N 个 byte 来表示整数。

而且通常两个字段的编号是连续的。所以这个协议在存储编号的时候，存储的不是编号的值，而是存储编号和上一个编号的差。

我们可以废弃字段，并且这些废弃的字段不会占用存储空间。我们会随着需求变更不断新加字段，数十乃至上百个字段的 struct 在真实的工程场景中是非常正常的。而在这个过程中，很多字段都会被逐步废弃不再使用。如果这些字段仍然要占用存储空间的话，也会是一大浪费。

第二个地方，是在我们读取数据的时候。在读取数据的时候，我们其实是读取 MemTable 加上多个 SSTable 文件合并在一起的一个视图。也就是说，我们从 MemTable 和所有的 SSTable 中，拿到了对应的行键的数据之后，会在内存中合并数据，并根据时间戳或者墓碑标记，来对数据进行“修改”和“删除”，并将数据返回给到客户端。

Major Compaction

最近被读取到的数据，会存放到缓存（Cache）里，而不存在的行键，也会以一个在内存里的布隆过滤器（BloomFilter）进行快速过滤，尽一切可能减少真正需要随机访问硬盘的次数

因为 Bigtable 支持单行事务，所以这两个修改，要么都完成了，要么都没有完成，不会存在一个成功，一个失败的情况。

对于列族，更合理的解读是，它是一张“物理表”，同一个列族下的数据会在物理上存储在一起。而整个表，是一张“逻辑表”

而且 Master 可以根据每个 Tablet Server 的负载进行动态的调度，也就是 Master 还能起到负载均衡（load balance）的作用

Bigtable 里，数据存储和在线服务的职责是完全分离的。我们调度 Tablet 的时候，只是调度在线服务的负载，并不需要把数据也一并搬运走。

在 Bigtable 里，我们就采用了另外一种分区方式，也就是动态区间分区。我们不再是一开始就定义好需要多少个机器，应该怎么分区，而是采用了一种自动去“分裂”（split）的方式来动态地进行分区。

架构师的工作不是作出决策，而是尽可能久地推迟决策，在现在不作出重大决策的情况下构建程序，以便以后有足够信息时再作出决策

列下面如果有值的话，可以存储多个版本

“我怎么早没想到”的数据分区

不得不进行的“翻倍扩容”

额外开销（overhead）

既然只是对访问次数计数，我们自然就可以通过一个 Combiner，把 1 万条相同域名的访问记录做个化简。把它们变成 Key 还是域名，Value 就是有多少次访问的数值这样的记录就好了。而这样一化简，reduce 所在的 worker 需要抓取的数据，就从 1 万条变成了 1 条。

Do one thing, and do it well

5400 转，或者 7200 转的机械硬盘。如果你读过我的《深入浅出计算机组成原理》，你一定还记得机械硬盘的 IOPS 也就是在 70 左右

而对于数据可能重复写入多次的问题，你也可以对每一条要写入的数据生成一个唯一的 ID，并且在里面带上当时的时间戳

GFS 的客户端里面自带了对写入的数据去添加校验和（checksum），并在读取的时候计算来验证数据完整性的功能。

这个“至少一次”的机制，其实很适合 Google 的应用场景。你想像一下，如果你是一个搜索引擎，不断抓取网页然后存到 GFS 上。其实你并不会太在意这个网页信息是不是被重复存了两次，你也不太会在意不同的两个网页存储的顺序

第二种因素是随机的数据写入极有可能要跨越多个 chunk。

独特的 Snapshot 操作

分离控制流和数据流

等到所有次副本都接收完数据后，客户端就会发送一个写请求给到主副本。我在上节课一开始就说过，GFS 面对的是几百个并发的客户端，所以主副本可能会收到很多个客户端的写入请求。主副本自己会给这些请求排一个顺序，确保所有的数据写入是有一个固定顺序的。接下来，主副本就开始按照这个顺序，把刚才 LRU 的缓冲区里的数据写到实际的 chunk 里去。

保障读数据的可用性而设立的 Shadow Master

追加写入（Append），GFS 也只是作出了“至少一次（At Least Once）”这样宽松的保障。

mit 6.824

首先是 Storm 的作者南森·马茨（Nathan Marz）的“Big Data”，现在也有中译本叫做《大数据系统构建》。对于人为错误的容错问题的思考，为我们带来了著名的 Lambda 架构。在我看来，即使到今天 Lambda 架构也并不过时。其次是俗称 DDIA 的这本《数据密集型应用系统设计》，这本书梳理了整个大数据领域的核心技术脉络，是一本非常合适的架构入门书。第三本是专注于流式处理的《Streaming System》，不过目前还没有中译本上市。如果你更喜欢通过视频课程学习，那么去看一看来自 MIT 的课程 6.824 的 Distributed System 绝对错不了。我在这里放上了Youtube和B 站的视频链接。最后是一份很容易被人忽视的资料，就是 2009 年 Jeff Dean 在 Cornell 大学的一个讲座“Designs， Lessons and Advice from Building Large Distributed Systems”的 PPT，我也推荐你去看一看，对于理解大数据系统的真实应用场景很有帮助。

多做交叉阅读和扩展阅读。论文本身往往只有 10 来页，非常精炼，对于很多知识点，往往就只有一个小片段，甚至只有一两句话，所以交叉阅读和扩展阅读少不了。根据你需要深入了解的知识点，你可能要回顾之前已经解读过的论文，也可能需要去阅读一些开源项目的代码，或者是一些计算机经典书籍中相关的章节，帮你彻底理解对应的问题

一篇篇的大数据论文，并不是教科书里的一个章节或者一个知识点，而是对于一个重要的系统问题的解决方案。在读论文之前，先尝试自己去思考和解决对应的问题，有助于你更深刻地理解问题和解决方案的重点。

倾斜分区判定完毕之后，下一步，就是根据 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（写时约束）

周同步，每