《数据密集型应用设计》笔记

Designing Data-Intensive Applications——The Big Ideas Behind Reliable, Scalable, and Maintainable Systems.

第一章：可靠性，可扩展性和可维护性

核心脉络

• 简述可靠性、可扩展性和可维护性
  • 可靠性(reliablity)：在 things go wrong 的情况下仍能正常工作，即当 fault 出现时不会 failure。
  • 可扩展性(scalablity)：描述系统应对负载增长的能力，即使负载增长，也能保证性能。
  • 可维护性(maintainablity)：系统便于理解，易于上手，有较强的可操作性及可塑性。
• 可靠性
  • 提高可靠性的方法
    • 对于硬件 fault，主要通过冗余来提升可靠性。如使用 RAID 预防磁盘损坏，备用电源/双电源供给预防断电。
    • 对于软件 fault，需要做好崩溃/重启后快速恢复，添加监控和报警以便快速定位问题。
    • 对于人为 fault，要最小化错误发生，对人员进行培训，提供沙盒环境以供试错，设计快速恢复以最小化错误发生时的影响，采用蓝绿部署/金丝雀升级以便快速回滚。
  • 可靠性的量化方式
    • 系统正常工作的时间比（可用性）。
    • 数据丢失率（持久性）。
    • 系统恢复速度。
    • 系统的容错性。
• 可扩展性
  • 如何定义一个好的 SLA(Service-Level-Agreement) 指标？
    • 吞吐量：平均 QPS。
    • 响应时间：50th percentile 用于描述系统平均性能；99.9..9th percentile 用于描述离群值（性能拖尾）。
  • 尾延时放大
    • 表明系统受制于性能最差的部分，类似于木桶短板。
    • 业务系统并行批量部署时，整个系统运行会依赖最慢的服务启动。
    • 多库 Query 的性能会依赖最慢的库检索。
  • 队头阻塞
    • 表示队头处理过慢引起后续任务被阻塞住，元素间存在顺序关系。
    • 平台系统按依赖关系进行部署时，数据库系统 rank 低且启动速度慢，导致后续 rank 高的任务被阻塞很久才启动。
    • 消息队列会由于某个异常值处理过慢而引起后续任务处理延时过大。
  • Scaling-out 与 Scaling-up
    • Scaling-out 是水平扩展，通常采用加机器的方式实现，以量取胜。
    • Scaling-up 是垂直扩展，通常使用性能更强的机器来实现，以强取胜。
• 可维护性
  • 可操作性
    • 好的设计：可视化设计，一键式安装，配置集中管理等。
    • 差的表现：繁杂且陈旧的操作文档，工具缺乏自动化。
  • 简单性
    • 好的设计：模块功能单一、界限分明，不过早优化，代码可读性强。
    • 差的表现：混乱复杂的状态机，功能耦合，wraparound & trick。
  • 易演进性
    • 好的设计：完善的版本管理机制，迭代计划，兼容性API。
    • 差的表现：Breaking change，依赖不再维护的库。

扩展延伸

• 系统的容错性可以通过 Chaos Monkey 等方法测试。
• 负载可以用哪些方式描述？
  • Web Server 每秒的请求数.
  • DB 的读写率。
  • 缓存命中率。
  • 在线用户数。

第二章：数据模型和查询语言

核心脉络

• 什么是 NoSQL？

  • NoSQL 指 not-only SQL，主要应对关系模型无法很好支持的 query 而生的查询语言，其最初的起源是一种 hashtag。

• 什么是 Polyglot persistence？

  • Polyglot persistence 指的是不同数据库有各自的特点，不同项目因其需求不同，对存储特性的折衷也不尽相同，因而各自合适的数据库可能也不相同。

• 什么是规范化？如何进行规范化？

  • 规范化是指数据库高效组织数据的一种方式，主要用于消除数据冗余，消除不必要的依赖。
  • 数据库规范化的方式是遵循范式，将相关性比较强的表拆成子表以降低冗余。

• Data Model 和 Query Language 分别是什么，有什么关系？

  • Data Model 用于描述数据特征。
  • Query Language 是特定数据存储的查询语言，查询方式包括声明式与命令式。
  • Query Language 强依附于特定 Data Model。一般来讲，对于不同的 Data Model 所使用的 Query Language 会有所不同，对于同一 Data Model，可能会支持多种 Query Language（如 Cypher, SPARQL）。

• Relational Model、Document Model、Graph Model 各自有哪些特点？

  • Relational Model
    • 数据被组织成关系，每个关系是元组的无序集合。
    • 具有严格的规约(schema on write)。
    • 在处理一对一的问题上十分有效。
  • Document Model
    • 自包含的文档结构，一般可以用 JSON 来描述。
    • 数据格式较为灵活(schema on read)。
    • 处理一对多的问题十分有效。
  • Graph Model
    • 数据之间连接比较复杂，数据以图形的方式建模。
    • 适合处理多对多的问题。

• 各种数据模型如何描述基本关系？

  Model\Relationship	One-to-Many	Many-to-One	Many-to-Many
  Relational	一张主表连接多张从表	多表连接	多表连接
  Document	树状嵌套记录	文档引用	文档引用
  Graph	一个顶点与一个顶点相连	一个顶点与多个顶点相连	多个顶点与多个顶点相连

• 选择数据模型时需要考虑哪些因素？

  • 数据的关系及其复杂度
    • 一对一、简单的多对一及简单的多对多关系倾向于关系模型。
    • 一对多倾向于文档模型。
    • 复杂的多对多倾向于图模型。
  • 数据模型的特点
    • Schema 的灵活性：可以明确地建立数据的 schema，倾向于关系模型；灵活性较强的数据倾向于文档模式。
    • 局部性特点：如果频繁加载整个文档，倾向于文档模型；如只加载很少字段，文档又很长，或者需要 size-enlarged 的字段更新，倾向于关系模型。

扩展延伸

• 减少数据冗余的好处有哪些？
  • 更新时可以减小开销，因其只更新一份即可，无需更新所有副本。
  • 可以规避数据不一致的风险。
• 阻抗失衡：业务模型向数据库模型转换时需要一个翻译层，对象关系模型(ORM)可以用于隐藏掉这一层。
• 解决全表更新的一个方式是读时更新。
• 文档模型可以利用空间局部性，但是要求比较严苛。
  • 获取大型文档中较少的内容时收益低，因此文档要尽可能小。
  • 文档更新引起的尺寸变大的行为(size-enlarged)会重写文档，因此要避免 size-enlarged 更新。
• 命令式语言 vs 声明式语言
  • 命令式语言以一个确定顺序执行一系列操作，而声明式语言只列出满足所需条件及其表示形态，实现由 query 优化器完成。
  • 声明式限制了 query 的灵活性，但避免了命令式手动调优，更简单易用。
• 使用 SQL 进行图搜索的核心问题是无法确定需要 join 的次数。
• 一种数据模型可以用另一种来表示，但表示复杂度会很高。

第三章 存储与检索

核心脉络

• 比较SSTables索引与B-树索引

  	SSTable索引	B-树索引
  代表性数据库	LevelDB, RocksDB	MySQL
  写性能	高	低
  写放大	不明显（WAL、compaction）	较高（WAL、写部分会覆盖整页）
  实现原理	对顺序写的日志进行按 key 排序	以页的形式组织成多叉搜索树
  性能优化策略	后台 compact（按时间、size）以减少磁盘空间占用，降低读放大；分组按 block 压缩以减小磁盘占用的 IO 开销；索引更小，只需要保持起始 key 的索引；使用布隆过滤器缓解读放大	写时复制；压缩key；结合一些日志结构的思想来减少磁盘寻道；增加额外指针便于 range 操作
  故障恢复方式	SST文件一般会以文件形式落盘，无需恢复。但基于内存的SST(memtable)也需要通过WAL来恢复	通过WAL来恢复索引
  读性能	低	高
  读放大	较高，一般取决于SST层数	较低，取决于 B 树的层数
  适用模型	非关系型	关系型
  适用场景	写多读少	读多写少

• 比较 OLTP 与 OLAP

  	OLTP	OLAP
  数据读模式	检索少量记录，按键读取	大量聚合读
  数据写模式	随机写，低时延	批量导入/流式导入
  目标用户	终端用户，web 应用	内部分析，决策制定
  数据大小	G->T 量级	T->P->E 量级
  适合的存储引擎	InnoDB	数据仓库

• 列举除日志结构和 B- 树索引之外其他的索引，以及它们适用的场景

  • clustered index
    • 索引叶子节点存储完整行。典型用于InnoDB主键，适用于主键查询频繁的场景（更适合完整行内容）。
  • covering index
    • 索引叶子节点存储部分列，是一种折衷，适用于部分列很频繁 query 的场景。
  • 多列索引
    • 多个列维度的索引，适用于根据多维联合 query 的场景。
  • 模糊索引
    • 相似 key 索引（可以通过编辑距离来做），适用于灵活性强的 query 场景，如全文搜索引擎。

• 列式存储相比行式存储有什么优势？为什么更适合OLAP？

  • 行存储顺序存储每一行，query 时会将全部的列都加载到内存中；而列存储独立地存储每一列，query 时仅需要加载所需的列；另外列存储的每一列的类型相近，压缩效率更高，网络开销、磁盘占用低。
  • OLAP 数据库通常会存储大量的列，但是在分析时大多只需要极少数的列，使用行式存储内存开销太大， 更适合使用列式存储来灵活地选取所需的列。

扩展阅读

• Bigtable: A Distributed Storage System for Structured Data
  • 列关键字组成的集合叫做列族，列族是访问控制的基本单位。存放在同一列族下的所有数据通常都 属于同一个类型（我们可以把同一个列族下的数据压缩在一起）。一张表中的列族不能太多（最多几百个），并且列族在运行期间很少改变。
  • 访问控制、磁盘和内存的使用统计都是在列族层面进行的。
  • 按时间戳管理多版本，及旧版本的合并。
  • Tablet 根据 row key range 进行的分区。
  • BigTable 内部存储数据的文件是 SSTable 格式的。
  • BigTable 还依赖高可用的、序列化的分布式锁服务组件——chubby（基于 paxos）。
  • BigTable 包含三个组件：连接到客户程序中的库，一个 Master 服务器和多个 Tablet 服务器。
    • Master 服务器：为 Tablet 服务器分配 tablets，检测新加入或过期的 tablet，负载均衡，GFS 文件的 GC，模式修改等。
    • Tablet 服务器：管理 tablet，负责其上 tablets 的读写，分割过大的 tablet。
    • 读不需要通过 Master 服务器，只走 Tablet 服务器。
  • 初始建表时只有一个 tablet，后续随着数据增长，被分割成多个 tablet。

扩展延伸

• 为应用选择合适的数据库系统需要考虑哪些方面？

  • 应用是偏 OLAP 还是 OLTP 的？
  • 应用的数据规模是多大？增长速度如何？
  • 应用的读写 QPS 大致为多少？
  • 应用是否可以容忍部分数据丢失（数据库一致性保证强度，同步、异步还是落盘）？
  • 应用能容忍的延时大致是多少（是否需要使用内存数据库）？

• 索引有什么作用？

  • 使用额外的元数据当做标识，用于快速定位想要的数据。

• 索引有哪些类型？

  • 哈希索引。
  • LSM索引。
  • B树索引。

• 如何快速恢复日志结构索引？

  • 使用分级的方式，内存中只有少量新写的数据，可以很快通过 WAL 恢复。
  • 可以对内存索引做 snapshot，进行快速恢复。

• 如何检查部分数据写入日志结构索引？

  • 使用 checksum 剔除掉不完整的数据。

• Append-Only 日志文件有什么优势？

  • 写吞吐量高，速度快。
  • 并发和崩溃恢复简单很多，不必担心覆盖时发生崩溃。
  • 合并旧段可以避免数据文件分散，减少磁盘碎片。

• 每种索引引擎代表性的数据库系统有哪些？

  • B 树 -> MySQL，postgreSQL。
  • LSM 树 -> LevelDB，RocksDB。
  • Hash 索引 -> Riak，MySQL（引擎之一）。

• 日志索引的 Size-tiered compaction 和 Leveled compaction 有什么不同？

  • Size-tiered compaction：更小更新的 SST 文件源源不断地 merge 到更大更旧的 SST 文件上。
  • Leveled compaction：根据某种策略挑选出 level n 上需要 compact 的 SST 文件，通过 key range 找到对应 level n+1 上的 SST 文件进行合并。

• LSM 索引与 B 树索引有什么不同？

  • LSM 索引面向日志结构，分层SST，适用于写多读少的情况。
  • B 树索引面向页面组织成多叉搜索树，适用于读多写少的情况。

• B 树的分支因子是什么？B树索引存储数据量与层数和分支因子的关系是什么？

  • 分支因子即一个页节点引出子页的数目（叉数），通常为几百。
  • 粗略计算方式：sum = bf ^ L * pageSize

• 如何保证 B 树的稳定性？

  • 使用 WAL 来在数据库崩溃时恢复 B 树。
  • 并发时使用轻量锁以保证数据结构的一致性。

• 应该从哪些方面比较存储引擎的性能？

  • 可用磁盘带宽下的写 QPS（与写放大相关）。
  • 存储开销、磁盘利用率（碎片化相关）。
  • 读吞吐量（与读写放大相关）。
  • 响应时间。

• 不同磁盘类型顺序写入和随机写入性能差异如何？

  • 机械硬盘寻道时间和旋转延时使得顺序写性能要远高于随机写。
  • SSD 会从块中读取页，修改内容写到新的块中，并将之前页标记为脏。顺序写相对于随机写会产生更少垃圾，缓解 GC 压力，带来更好性能。如果每次读写都以块为单位读写，那么顺序写和随机写的性能相当。参考文章

• InnoDB 的 double writes 是怎么回事？

  • 双写主要是为了防止数据刷盘时突然掉电，导致数据不完整。而双写多出一次写是以顺序写的形式 buffer 在磁盘（共享表空间），一旦在刷盘时宕机，可以通过共享表空间找到最近的一个副本来恢复。

• B 树和 LSM 树的写放大是怎么回事？

  • LSM 写放大很典型，因为重复的 compact 和 merge 会导致写操作会额外写入多次；但由于前台是按照 append-only 的方式顺序写的，因此写放大效果不明显。
  • B 树在写入/更新数据时是以页为单位的，即使写入的数据很小，也会写入整个页面。

• 为什么大多数关系型数据库都采用 B 树类型的索引结构？

  • B树索引适合用于读多写少的场景，而关系型数据库大多是此场景。

• 内存数据库的性能优势并不是因为它们不需要从磁盘读取。即使是基于磁盘的存储引擎也可能永远不需要从磁盘读取，因为操作系统缓存最近在内存中使用了磁盘块。相反，它们更快的原因在于省去了将内存数据结构编码为磁盘数据结构的开销。

• 每个列族中，它们将一行中的所有列与行键一起存储，并且不使用列压缩。因此，Bigtable 模型仍然主要是面向行的。

• 数据仓库是什么？相比用 OLTP 系统做分析有什么好处？

  • 数仓是一个专门用作分析的独立数据库，适用于 OLAP，一般采用 ETL 流程。
  • Analytic query 操作代价很高，会影响到 OLTP，因此 OLAP 逐渐从 OLTP 数据库中分离开，而数仓是可以在不影响 OLTP 操作的情况下进行 OLAP 的。

• ETL 是什么？能分别举个例子吗？

  • ETL 指抽取-转化-加载的数据处理流程。
  • 不同业务部门会将来自不同用户需求记录到不同的数据库中，而 OLAP 需要收集全量的信息进行分析并制定决策，这时 E 表示从不同数据中抽取数据（不会影响到正常的 OLAP ）；T 表示将多种抽取到的数据转换成统一的、analysis-friendly 的模式；最终 L 表示将转换好的数据加载到 OLAP 数据库中（一般是数仓）。

• 物化视图和数据立方分别是什么？有什么作用？

  • 物化视图：创建缓存来 cache 住一些常用的聚合操作，避免多次相同的聚合 query 重复地在 raw data 上计算获取。
  • 数据立方是物化视图的一个特例，其表示一个不同维度的聚合网格，其作用是可以通过预计算的方式加速特定 query。

第四章 编码与演化

核心脉络

• 后向兼容 vs 前向兼容

  • 后向兼容指新代码可以读取旧代码写入的数据，指的是对过去兼容。
  • 前向兼容指旧代码可以读取新代码写入的数据，指的是对未来兼容。

• 数据编码的形式

  • 基于特定语言的编码

    • 优点：方便，无需引入第三方库。
    • 缺点：语言的强绑定；无法进行跨语言的扩展；性能和扩展性也没有通用编码方式强。

  • 基于文本的编码方式

    • XML：有严格的 schema，易于统一，不易出错；但解析速度慢，会引入 tag 等外部开销，不易维护。
    • JSON：格式简单，较 XML 更轻量，schemaless，易于解析与维护；但通用性及扩展性不及 XML。
    • CSV：最直观，schemaless，使用灵活；但需要过多的人工介入，需要转义等规则来避免语法上的歧义，外部 parser 支持不够完善。

  • 二进制编码

    	Thrift	Protobuf	Avro
    编码原理	schema = field tag + type + length + content	同前	编码无 field 及 datatype 标识，只有一个长度的标识将 values 连接起来
    前向兼容	旧代码读取新数据时，会忽略掉其不认识的字段	同前	同前（允许删除带有默认值的字段）
    后向兼容	新代码读取到旧数据时，会为新 schema 新增的字段赋以默认值	同前	同前（允许新增带有默认值的字段)

扩展延伸

• 为什么要考虑前后向兼容？

  • 由于 server 端可能存在滚动升级的场景，client 也可以自主选择是否升级到某一版本。这样导致了系统中会同时存在新旧版本的代码，为了能够在这种情况下正常工作，要考虑前后向兼容的问题。

• 什么是编码？什么是解码？

  • 编码指从一个内存结构表示转换成字节序列的过程。
  • 解码指从字节序列转换成内存结构的过程，是编码的逆过程。

• MessagePack 编码的原理是什么？

  • 对 key 与 value 进行二进制编码，并引入部分标识开销。
    • 标识开销：用于描述结构的类型及长度。
    • 内容开销：key/value 的 ASCII 表示（内容的二进制编码）。

• Thrift 和 Protocol Buffers 对比MessagePack 的优势是什么？

  • 编码更紧凑，更节省空间。
  • 对 key 的兼容性更好一些，因其通过 field tag 来标识字段，而不编码 key。

• 简单描述 Thrift 中 BinaryProtocol 和 CompactProtocol 的原理

  • BinaryProtocol：使用 type、field tag、length 和 content ASCII 的方式编码。
  • CompactProtocol 在 BinaryProtocol 基础上引入两个优化：
    • 使用变长整型。
    • 将 filed tag 和 type 打包到一起。

• Thrift 和 Protocol Buffers 如何实现数据类型的演变？

  • 基本不允许跨大类的数据类型更改。
  • int32 向 int64 演变时，在解码时会损失精度。
  • pb 允许从单值向 array 方向演变，类似于 int(11) -> []int{11}

• Avro 如何实现前后向兼容？

  • Avro 通过 schema 中字段名来进行匹配，前向兼容表示 writer schema 较新，reader schema 较旧；而后向兼容表示 writer schema 较旧，但是 reader schema 较新。
  • 为了保证兼容性，只能增删带有默认值的字段，如果新增没有默认值的字段，后向兼容性被打破；如果删除没有默认值的字段，前向兼容性被打破。

• 基于模式的二进制编码相比文本数据格式的优势是什么？

  • 更紧凑，编码速度更快，更省带宽。
  • 由于 schema 的存在，数据更新更容易。
  • 便于检查后向兼容与前向兼容。
  • 自动代码生成对强类型语言更友好。

• 数据在进程之间传递的方式都有哪些？

  • 通过数据库。
  • 通过服务调用。
  • 通过异步消息系统。

• 通过数据库的数据流如何实现前后向兼容？

  • 通常数据库会被多个进程同时访问，并且这些 client 通常会存在多个版本，所以需要保证前后向兼容性。可以通过数据迁移到新 schema，read-fill 等方式保证兼容。

• 什么是 SOA？

  • 一个 server 可能是另一个 service 的 client，通常用这种方法将大型应用划分为很多小型的服务，这种构建应用的架构方式成为 SOA。

• 什么是 REST？什么是 RESTful？

  • REST 是基于 HTTP 原则的设计哲学，只是用简单的数据格式，使用 url 表示资源，并且使用缓存控制、授权等 HTTP feature。
  • 遵从 REST 原则的 API 设计称为 RESTful。

• SOAP 的实现原理是什么？存在什么问题？

  • SOAP 是基于 XML 协议构建网络 API request，旨在避免使用 HTTP feature。
  • 问题是可读性差，对工具支持、代码生成及IDE的依赖性很强，厂商间的互操作性问题较大。

• 远程调用与本地函数调用有哪些区别？

  • 远程调用相对本地调用需要经由网络，涉及编码->网络->解码->处理->编码->网络->解码一整套流程，而网络请求有着很多棘手的问题：
    • 网络情况不可预测。
    • 网络请求可能超时，无法获知结果未返回的原因。
    • 失败重传可能产生 at-least-once 的问题，需要保证幂等性。
    • 网络请求延时高。
    • 有编码解码开销。

• RPC 框架有哪些？

  • 使用 ProtoBuffer 的 Grpc。
  • 使用 Thrift 的 Finagle。
  • 使用 JSON over HTTP 的 Rest.li。

• RPC 如何实现前后向兼容？

  • 可以假设升级的过程是先升级 server 端，后升级 client 端，因此需要保证 request 的后向兼容和 response 的前向兼容即可。
  • 兼容性由底层编码方式保证。

• 使用消息代理相比 RPC 有哪些优势？

  • 削峰、异步、解耦。
  • 重传机制保证消息不会丢。
  • 允许向多个接收者发送。

第五章 复制

核心脉络

分布方式

• Single-Leader
  • 流程：推选出一个主节点，从节点从主节点获取全量数据 snapshot 和增量的数据并加载。当其追上 leader 后成为真正的 follower。
  • 复制方式：同步复制和异步复制。
    • 同步复制只有当副本被复制到所有的 followers 才返回，以保证数据强一致性。
    • 异步复制只要 leader 写成功后便会返回，数据异步地向 followers 复制。异步复制可能会丢数据，只能保证最终一致性。
  • 故障处理：主节点故障应用故障处理机制，启动 failover，选定一个合适的 follower 做为新的 leader，其他 follower 可以感知到发生了主从切换。在主从切换过程中可能会存在数据的丢失。从节点故障只是会降低系统吞吐量，其上的请求会打到其他节点上。
  • 扩容：加机器就可以，扩容时会向主库获取一个 snapshot，当库规模较大时，应避免在主库繁忙时扩容，导致 leader 的压力过大影响性能。
  • 优点：简单，不需要解决数据冲突。
  • 缺点：对于跨数据中心的场景性能较低，网络中断及延迟峰值的应对能力较差。
  • 应用场景：大部分存储系统，如 Redis，Etcd，HDFS 等。
• Multi-Leader
  • 流程：一般用于多数据中心场景，每个数据中心有一个 leader，每个客户端写到其中一个 leader 上，leader 间会异步复制数据，leader 与其 follower 也会异步复制数据。
  • 复制方式：一般采用异步复制。
  • 故障处理：主节点故障仅引起本数据中心发生主从切换，其他 leader 所在数据中心不会切换；从节点故障只会影响读 QPS。
  • 扩容：新增数据中心需要新增一组主从节点；已有数据中心扩容只需要新增 follower。
  • 优点：适合跨数据中心场景，应对网络延迟及延迟峰值更鲁棒。
  • 缺点：系统复杂，数据同步冲突问题不易解决，一致性的保证更低。
• Leaderless
  • 流程：所有节点可以互相通信，形成自治系统，客户端会向所有节点写，直到 quorum 成功返回。
  • 复制方式：读修复不涉及复制，反熵使用异步复制。
  • 故障处理：只要节点故障数小于 quorum，集群就会正常工作。
  • 扩容：新增节点。
  • 优点：避免单点故障，公平性与容错性更强。
  • 缺点：一致性弱，冲突问题不易处理，无主架构出现问题不易排查，不可控。
  • 应用场景：OSPF，基于 gossip 协议的 cassandra。

复制日志的实现

读一致性

写冲突

Quorum

• 什么是 Quorum？
  • 读、写副本数能够 cover 住当前集群节点总数，并且能保证至少有一个节点同时收到了读与写的请求，这样读至少可以读到一个最新写入的副本。
• 如何确定 quorum 数量？
  • 依赖应用，一般都是 N/2+1，对于读 QPS 要求极高，且允许写失败的可以采用 1, N来读写；对于写 QPS 要求极高，且允许读失败，可以采用N，1来读写。
• Quorum 的局限性有哪些？
  • 复制的副本数较多，一般是 N/2+1。
  • 集群中慢节点多时性能较低。
  • 故障节点数无法保证 quorum 时，系统不可用。
  • 网络分区后少数派不可用。
• Sloppy Quorum 解决什么问题？
  • 当集群中正常节点数少于 quorum 时仍可写。

分布式系统

• 多机扩展的目的及方法有哪些？
  • 目的：扩展性、容错性、低延时。
  • 方法：加机器。
• 扩展的方式有哪些？各自有什么优缺点？
  • Scale-up：单机模式可以省去很多分布式带来的问题；但性价比很低，再强也有上限。
  • Scale-out：可以利用廉价机器扩展，性价比高，扩展上限更高；但会引入很多分布式相关的问题（一致性，可用性等）。
• 复制和分区的区别是什么？
  • 复制：在不同节点上拷贝相同的数据。本质是提供冗余，增强容错性，读写分离以增强读 QPS。
  • 分区：将一个大库分成若干子集，提升性能与扩展性。

第六章 分区

核心脉络

• 什么是分区？基本原则是什么？

  • 分区是将大数据库分解成若干小数据库的方式。
  • 基本原则是将数据和查询负载均匀分布在各个节点上。

• 为什么要做分区？分区是必须的吗？

  • 分区主要为了可扩展性，不同分区可以放在集群中不同节点上。
  • 分区有较高复杂度与开销，因此当数据量经长期估算处于一个较小规模时（单机可处理），是不需要分区的。一般在分布式系统中，分区基本是需要的。

• 分区以后会给系统带来哪些原本没有的问题？

  • 读写开销变大，存在跨机器的读写，且需要考虑写一致性。
  • 分区的再均衡会引入很多的网络流量，可能会影响到正常的请求。
  • 查询的延时会变大，因为请求需要路由到对应的机器上，引入转发开销。

• 分区方式

  • 按键分区：

    方式	写 pattern	读 pattern	range pattern	分布均匀程度
    随机分区	Round Robin	Scatter/Gather	Scatter/Gather	很均匀
    范围分区	连续键范围分区	分区内 query	分区内 range	不均匀，易产生热点
    散列分区	散列函数分区	分区内 query	Scatter/Gather	取决于散列函数

  • 按数量分区：

    方式	分区数量的确定方式	优点	缺点
    固定分区	在数据库建立时预创建比节点数更多的分区数，之后保持不变；需要结合数据集规模及对未来数据量预估确定分区数量	操作简单，可以解决硬件不匹配问题	灵活性差，很难选定合适的分区数；数据量难以预估时，分区很难达到合适的大小，无法达到最佳性能
    动态分区	分区会随着 size 增大一分为二，随着 size 减小合二为一	分区数量适应总数据量；能保证分区大小在一个可控范围内	实现复杂；初始单个分区会造成热点效应
    节点分区	每个节点具有固定数量的分区；节点数不变时，分区大小随着数据集增大而增大；当数据集不变时，分区大小随着节点数增加而减小	分区公平性较强，每个分区的大小较为稳定	新节点加入时，随机化可能产生不公平的分割

• 二级索引

  • 通过主键以外的方式查询数据时因为缺少主键的信息定位具体的分区，提升了实现的复杂程度。

  方式	写 pattern	读 pattern	索引本身是否需要分区	索引是否同步更新
  本地索引	仅往主键分区写	Scatter/Gather	不需要	主键分区内更新
  全局索引	往主键分区及二级索引分区写	从二级索引分区读	需要	需要

再均衡

• 定义
  • 将负载从集群中的一个节点向另一个节点移动的过程称为再均衡(rebalance)。
• 触发条件
  • 吞吐量增加，且负载出现明显的不均衡现象。
  • 数据集增大，需要新增节点增加扩展性。
  • 节点出现故障，需要新的节点接管。
• 原则
  • 再均衡之后，负载应该在集群中公平地共享。
  • 再均衡发生时，数据库应该继续接受读写请求。
  • 节点之间只移动必须的数据，以提升再均衡速度，减少网络和磁盘 I/O 负载。

路由请求

第七章 事务

基本概念

• 一句话介绍事务

  • 将一组读写封装成一个原子逻辑，要么同时成功，要么同时失败。

• 使用事务的必要前提

  • 存在并发。
  • 非只读。
  • 无法忍受部分成功部分失败。
  • 一旦提交后不允许记录丢失。

• ACID 与 BASE 的区别

  • ACID 是较为理想化、较严苛的安全性保证。
  • BASE 是去魔化的 ACID，更广泛的定义，更宽松的安全性保证。

• ACID 在 MySQL 中的具体表现

  • 原子性：undo log 用于逐级回滚。
  • 持久性：redo log + binlog 用于在宕机重启后判断提交/回滚。
  • 隔离性：MVCC，默认隔离级别是快照读（可重复读）。
  • 一致性：数据库提供以上三种保障，确保数据一致性。

• NoSQL 中的事务

  • Redis：Redis是单线程内存数据库，事务在 redis 中只体现为逻辑封装，即将一系列操作封装成一个逻辑单元，在此期间不会插入其他 client 的操作。但并不具备原子性，逻辑单元内指令成功与否互不影响。
  • Etcd：支持原子性，默认使用 cas + retry 的乐观策略。

• 事务是否能重试？事务重试会有什么问题？

  • 事务能重试，甚至对于序列化快照隔离这种乐观提交方式，事务重试是家常便饭。
  • 对于逻辑错误，事务重试无法解决问题；对于资源吃紧导致的事务失败，重试会加速系统恶化，甚至引起雪崩。

• 并发事务常见的问题

  • 脏写(Dirty Write)：一个事务覆盖写入了另一个事务未提交的写入。
  • 脏读(Dirty Read)：一个事务读到了另一个事务尚未提交的写入。
  • 不可重复读(Unrepeated Read)：一个事务内部在不同时间点会看到同一数据的不同状态。
  • 幻读(Phantoms)：一个事务的写入操作会影响到另一个事务的搜索结果，仿佛看到了幻象。
  • 更新丢失(Lost Update)：两个事务同时执行读->改->写流程，其中一个写操作直接覆盖掉了另一个写操作的结果。
  • 写偏差(Write Skew)：一个事务根据某个前提筛选出结果并进行更新操作，但写的时候前提已经非真了。

• 并发问题的辨析

  • 脏写和丢失更新的区别

    • 脏写：某一事务写操作发生在另一事务写与提交之间，是前者覆盖后者。
    • 丢失更新：某一事务写操作发生在另一事务读与写之间，是后者覆盖前者。

  • 丢失更新与写偏差的异同

    • 相同点：都是由于写前提发生了变化引起的问题。
    • 不同点：丢失更新的不一致性发生在同一数据上，写偏差的数据不一致发生在不同数据上。

  • 不可重复读与幻读的区别

    • 不可重复读是事务在不同时间读取同一数据不一致的问题。
    • 幻读是事务在不同时间获取数据区间内的记录不一致的问题。

事务隔离级别

• MySQL 与 PostgreSQL 默认的事务隔离级别是什么？
  • MySQL 默认可重复读。
  • PostgreSQL 默认读-提交。
• 存储过程与事务的关系是什么？存储过程能解决事务什么问题？
  • 存储过程是事务的一种载体（容器），事务被塞进存储过程中可以避免交互式等待而导致事务过长。
• 哪些数据库会使用弱事务隔离？
  • 要求吞吐量大的数据库。

读-提交(Read Committed)

• RC 提供哪种基本的保证？
  • 无脏读脏写。
• 什么场景下需要防止脏读？
  • 对一致性要求较高的场景。
• RC 机制在数据库中如何实现？
  • 记录新旧两个版本的数据（n=2 的 MVCC）。
• 数据库行锁与表锁区别是什么？各存在什么问题？
  • 行锁是锁住符合筛选条件的行，表锁是锁住整张表。
  • 行锁锁粒度比较小，并发度高，存在很多并发问题隐患，易产生死锁；表锁粒度较大，并发度低。
• RC 会造成什么样的并发错误？
  • 会造成不可重复读及更高级别的错误。

快照隔离(Snapshot Isolation)

• SI 在什么场景下最有用？
  • 存在只读事务（尤其是只读长事务）。
• SI 实现原理是什么？
  • MVCC 多版本管理，事务开启时启动一个快照，外界的写不会阻塞快照读。
• SI 无法解决什么样的并发错误？
  • 无法解决写偏差与幻读
    • 普通的写偏差可以通过加行锁避免，幻读引起的写偏差需要通过加间隙锁避免。
    • 如果只有快照读而没有更新读保证上锁，很容易出现写偏差。

序列化隔离(Serializability)

• 什么场景下会使用序列化隔离？
  • 无法忍受写偏差及幻读问题的场景。
• 为什么开始引入单线程循环执行事务？哪些数据库在使用单线程？
  • RAM 足够便宜，能将完整活跃数据集存在内存里；OLTP 事务很短，写入操作比较少；而 OLAP 又是只读的，仅需为其提供额外的一致性快照即可。
  • Redis 是单线程数据库。
• 单线程的串行事务，如何在生产环境中提升性能？
  • 避免长事务，可以将事务封装成存储过程。
  • 分区扩展到多 CPU 多核。
• 串行执行的事务实现序列化隔离需要哪些前提？
  • 每个事务都必须小而快。
  • 仅限于活跃数据集可以放入内存的情况。
  • 写入吞吐量必须低到能在单个 CPU 核上处理，如若不然，事务需要能划分至单个分区，且不需要跨分区协调。
  • 跨分区事务是可能的，但是在使用程度上有很大的限制。

两阶段锁(2PL)

• 2PL 是什么？
  • 本质就是读写锁，读不阻塞读，其他互相阻塞。
• 2PL(两阶段锁定) 与 2PC(两阶段提交) 区别是什么？
  • 完全不同的两个东西，2PL 是并发事务防止 race condition 的加锁机制，2PC 是分布式事务中使用到的一致性协议。
• 2PL 与快照隔离的关键区别是什么？
  • 阻塞与不阻塞的关系，2PL 是阻塞的，快照隔离是非阻塞的。
• 谓词锁(Predicate Lock)和索引区间锁(Index-Range Lock)分别是什么？
  • 谓词锁：给所有符合某些搜索条件的对象加锁（多维、精准）。
  • 间隙锁：基于某个索引、给相对于谓词锁粒度更大的区间范围加锁（单位、缩放）。
• 2PL 实现中，锁的类型有哪些？他们是如何协同工作的？
  • 锁的类型主要分三类：
    • 排他锁：写锁。
    • 共享锁：读锁。
    • 谓词锁/间隙锁：防止幻读，一般是读锁。
  • 锁的协同方式如下:
    • 读时看记录上是否有排它锁，有就等。
    • 更新时看是否该记录上有读写锁，有就等。
    • 插入时看是否有间隙锁，有就等。
• 2PL 的性能如何？
  • 吞吐量很差，但并发问题最少。

序列化快照隔离(Serializable Snapshot Isolation)

• SSI 是悲观锁还是乐观锁？
  • 乐观锁。
• SSI 与乐观并发控制的区别是什么？
  • SSI 基于快照，即所有读操作都可以直接成功提交，无需检查隔离是否被违反。
• SSI 与 2PL 的最大区别是什么？
  • SSI 是乐观并发控制，基于快照隔离，不会阻塞只读事务。2PL 是悲观并发控制，写会阻塞读。

生产实践

磁盘故障

• 一项关于固态硬盘的研究发现，在运行的前四年中，30％到80％的硬盘会产生至少一个坏块。相比固态硬盘，磁盘的坏道率较低，但完全失效的概率更高。
• 如果 SSD 断电，可能会在几周内开始丢失数据，具体取决于温度。
• 在实践中，没有一种技术可以提供绝对保证。只有各种降低风险的技术，包括写入磁盘，复制到远程机器和备份——它们可以且应该一起使用。与往常一样，最好抱着怀疑的态度接受任何理论上的“保证”。

ORM与事务

• 对 ORM 框架，需要谨慎使用。
  • 一些 ORM 容易产生非 read-update-write 的应用层代码，导致无法使用数据库的原子操作。
  • 对于一些 ORM，当事务出现异常不会进行重试，而是抛出异常，可能会导致之前的输入被抛弃。这违背支持安全重试机制是终止事务的重点这一原则。

InnoDB 的锁机制

• TL;DR
  • InnoDB 支持多重粒度锁(multiple granularity locking)，允许行锁、表锁共存。
• 锁类型
  • 共享锁(S)：读锁，行级锁。
  • 排它锁(X)：写锁，行级锁。
  • 意向锁(I): 表级锁，表明事务将在该表中申请某种类型(S/X)的行锁。
    • 意向共享锁(IS)：SELECT .... LOCK IN SHARE MODE;
    • 意向排他锁(IX)：SELECT ... FOR UPDATE;
    • IS 和 IX 用来明确某事务正在锁某些行或即将锁某些行。
  • 记录锁(Record Locks)：简称行锁，是一种排它锁。搜索的列必须为唯一索引或者主键列，查询语句必须为精准匹配(=)。
  • 间隙锁(Gap Locks)：对某个范围区间上锁，SELECT c1 FROM t WHERE c1 BETWEEN 10 and 20 FOR UPDATE;
    • 在可重复读的隔离级别下解决幻读问题。
    • 任何间隙锁都不相互排斥，可以让两个间隙锁加在同一范围。
  • 临键锁(Next-Key Locks)：记录锁与间隙锁的结合，同时锁住行及行区间，仅作用于非唯一索引列上，用于解决幻读问题。
  • 插入意向锁(Insert Intention Locks)：插入操作时产生的一种特殊的间隙锁，可以锁定开区间内部分记录。
    • 如果多个事务要插入的数据在同一个区间的不同位置，则这些事务不会相互阻塞。假设有索引记录值为4和7的行。两个事务分别尝试插入5和6，分别用插入意向锁锁住4和7之间的间隙，然后再取得插入行的排它锁，但是锁相互不会冲突，因为插入行没有冲突。但插入意向锁和间隙锁在同一区间范围内相互冲突。

第八章 分布式系统的麻烦

核心脉络

• 什么是部分失效？

  • 系统的某些部分产生了某种不可预知的错误，而其他部分工作正常。
  • 部分失效具备不确定性，可能会正常工作，可能会产生不可预知的行为。

• 有哪些手段可以增加系统的可靠性？

  • 纠错码可以用于纠正通信信道上因噪声/干扰等产生的个别 bit 错误，如 MAC 层 CRC 冗余校验。
  • TCP 可以确保数据包的可靠传输，可以确保丢包重传、包顺序正确性及去重。
  • HDFS datanode 会定期进行块校验(checksum)，以保证数据副本可靠性。

• 除了超时以外有哪些检测节点不工作的方法？

  • 查询数据中心的网络交换机管理界面，检测硬件级别的链路故障。
  • 监控网络流量。

• 把超时当作检测网络故障的唯一方法会面临哪些问题？

  • 由于无法确定合适的超时时间，会引起系统性能下降。
    • 过短的超时时间可以快速地检测故障，但会由于网络抖动等误判节点失效。如果当前系统负载较高，失效节点的负载转移会加重系统的负载，造成级联失效。此外，过早地判断节点失效可能会增加数据不一致的风险。
    • 较长的超时时间意味着长时间的等待，检测节点失效的速度变慢，用户等待时间变长，体验较差。

• 造成网络拥塞和排队的原因都有哪些？

  • 多个节点同时向一个目的地发包，可能填满交换机队列，造成网络丢包。
  • 如果当前接收端 CPU 繁忙，处理不过来请求，则请求会被操作系统排队，等待分配 CPU 时间进行调度处理。
  • 虚拟机环境下的操作系统暂离、挂起会导致在虚拟机监视器中排队。
  • TCP 的拥塞避免及流量控制会使得在发送端排队。

• 有哪些同步的网络？同步的网络有哪些特征？

  • 固话网，其他实时性要求高的网络(URLLC)。
  • 特征
    • 基本不会存在排队。
    • 需要预分配资源，且资源使用不可灵活调整，空闲资源不可占用。
    • 延时有限，可控性高。

• 为什么数据中心网络和互联网使用分组交换？

  • 能够更好地提升资源利用率，提升吞吐量。
  • 主要对突发流量做了优化。
  • 对延时的要求并不像在线音视频业务那么高。

• 什么是 QoS，它的工作原理是什么？

  • QoS 指用户的服务质量，即对数据包转发效果的期望，体现在设备带宽、吞吐量、丢包率、延时等性能要求。在通信领域中通常用 SINR 来衡量，计算机网络中通常影响数据包的调度优先级。
  • QoS 用于对准入、流量进行控制及管理，避免网络拥塞。
    • Best Effort 模型（尽力而为）。
    • DiffServ 模型（区分服务）。
    • IntServe 模型（综合服务-模拟同步网络）。

• 分布式系统中不可靠的时钟会造成哪些问题？

  • 不同步的时钟会导致 LWW(Last Write Win)，会使得某些后发生的事件产生的数据被先发生的事件产生的数据覆盖掉。
  • 如果在分布式系统中使用时间戳描述顺序递增的事件或因果关系，则时钟不同步会导致事件次序混乱，甚至造成因果倒置。

• 单调钟和时钟的区别是什么？

  • 单调钟是持续前进的，不可跳回，用于测量持续时间间隔。单调钟的绝对值无意义。
  • 时钟显示的是当前的日期及时间，会与 NTP 同步并可以向前向后跳越，因此不适合测量精确的时间间隔。

• 什么是时钟的置信区间？

  • 由于本地时钟存在漂移、NTP 同步的精度偏差及网络延时，导致时钟存在一定范围的不确定性。置信区间用来评估这种不确定性，给出时钟实际时间所在的区间。

• 哪些事情会造成进程的暂停？

  • GC STW。
  • 虚拟机挂起。
  • 用户主动挂起进程，如发送 SIGSTOP 信号。
  • 缓慢 IO、IO 排队等，如同步访问磁盘、缺页中断频繁出现导致内存与磁盘频繁交换等。
  • CPU 负载很高时，同一进程两次被调度的间隔较长。

• 什么是拜占庭故障？

  • 分布式环境中节点存在欺诈（不诚实）的行为。

• 关于定时假设和节点失效分别都有哪些系统模型？

  • 定时假设
    • 同步模型：网络延时，时钟误差，进程暂停都是有界限的。
    • 部分同步模型：大多数情况与同步模型类似，但有时会超出界限（常用）。
    • 异步模型：不允许对时机进行任何假设，无法使用超时机制。
  • 节点失效
    • 崩溃-停止：崩溃即终止。
    • 崩溃-恢复：任何时候都可能发生崩溃，崩溃的原因也不止一种，但崩溃后在未来某个时间点可以恢复并再次响应。稳定存储中的结果会保留，易失性存储中的结果会丢失（常用）。
    • 拜占庭故障：节点不仅不可靠，还可能不可信，节点几乎没有可控性。

第九章 一致性与共识算法

线性一致性(Linearizablitiy)

• 简单定义 Linearizability？

  • 让系统看起来好像是只有一个副本，而且所有操作都是原子的。

• 简要概括 Linearizability 与 Serializability 的区别？

  • Linearizability 是新鲜度一致性的保证，一个数据被更新后，能够立马被后续的读操作读到，属于分布式领域的概念。
  • Serializability 是一种较强的隔离机别，对并发事务包含的操作进行调度后的结果和某种把这些事务一个接一个的执行之后的结果一样，属于数据库领域概念。

• Linearizability 有哪些使用场景？

  • 分布式锁。
  • 选主。
  • 唯一性约束。
  • 跨通道的的时序依赖。

• 怎么理解 cross-channel timing dependencies?

  • 异步 goroutine 中的 race condition 引发的问题。
  • 通过异步多线程通信可以解决时序依赖引起的竞争(waitGroup)。

• 为什么说 Dynamo-style 模型(Leaderless)不是 Linearizable 的？ 可以通过哪些变动支持 Linearizability？

  • 因为写操作并不需要写法定人数确认后才认为成功并对外可见，可见性是基于每个节点。存在先前读 quorum 包含了已更新的节点，而后续读 quorum 未包含已更新的节点的情况。
  • 可以通过同步读修复来实现，但性能很差，并且只能保证读写是线性的。

顺序保证

• 线性一致性模型和因果一致性模型有什么关系？

  • 线性一致性是全序的，因果一致性是偏序的。
  • 线性一致性完全是顺序概念，因果一致性仅因果关系是顺序的，无因果关系的允许并发。
  • 线性一致性可以保证因果一致性。

• Multi-leader 或 Leaderless 复制模型中，Lamport timestamps是如何保证因果一致性的？

  • 其定义了因果一致的全序。
  • 每个节点和每个客户端跟踪迄今为止所见到的最大计数值，并在每个请求中包含这个最大计数值。当一个节点收到最大计数值大于自身计数值的请求或响应时，它立即将自己的计数器设置为这个最大值（类似于term）。

• Timestamp 排序的不足体现在什么地方？

  • 适用于事后确定胜利者，对于需要马上响应的请求，其并不知道是否存在其他节点正在并发执行相冲突的操作，即只有在所有操作被收集之后，操作的全序才会出现。
  • 提供的全序是有间隙的序列，无法通过夹逼的思想获知一致性信息。

• 全序广播有哪些应用场景？

  • 数据库复制。
  • 以存储过程实现事务的序列化。
  • fencing token。

分布式事务

• 两阶段提交(2PC)协议中有哪两个角色？

  • 参与者与协调者。

• 在 2PC 协议中，如果协调者失效，会出现什么后果？

  • 根据失效时机不同，结果也不同：
    • 在发送 prepare 阶段前失效，则参与者可以安全地终止。
    • 一旦参与者收到 prepare 请求并作出回复后，协调者在回复 commit/abort 消息前失效时，参与者会陷入迷茫状态，并等待协调者恢复，其所持有的锁一直不会被释放掉。

• 分布式事务有哪些局限性？

  • 协调者可能存在单点问题。
  • 协调者若与无状态服务部署在一起，则其日志可能引入状态。
  • 需要对异构系统进行兼容。
  • 有放大失效的趋势，缺少终止的活性属性，无法实现容错。

共识

• 一个共识算法，需要满足哪些属性？其中哪些是安全属性，哪些是活性？

  • 安全属性
    • 一致同意：不存在两个节点决定不一致。
    • 完整性：没有节点决定两次。
    • 有效性：节点决定的值一定来源于某个节点的提案，不会凭空捏造。
  • 活性
    • 可终止性：所有未崩溃的节点都会完成计算并最终确定一个值。

• Epoch number 的作用是什么？

  • 对 Leader 的独一无二性提供弱保证。实际上在换届期间，存在短暂的双主场景，但并不属于脑裂：
    • 这不是一个长期运行状态，维持时间不会超过一个投票周期。
    • etcd 也有 ReadIndex、Lease read 机制来解决这种状态下的一致性语义问题。

• 与共识相比，2PC 有什么差异？

  • 2PC 协调者不是由选举产生的，存在单点瓶颈。
  • 2PC 要求所有参与者都投赞成票。
  • 2PC 是阻塞的原子提交协议，不具有终止属性，不具有容错性。

扩展延伸

• etcd 与 zookeeper 是线性一致的吗？

  • etcd 可以配置成线性一致的，读写都走 leader。
  • zookeeper 不是线性一致的，而是顺序一致的。

• etcd 的 quorum read 用来解决什么问题？这个问题是否有更简单的解决方法？为什么不默认启用 quorum read？

  • 用来解决因网络分区引起的一致性读问题。
  • 可以通过 ReadIndex 或 Lease read 方式减小网络开销。
  • 网络开销太大，有相对轻量的方法。默认是一致性高于可用性的，不特殊指定clientv3.WithSerializable()就不会读到 stale data。

第十章：批处理

流式计算与批处理

• 比较以下处理方式的特点

  系统	描述	衡量指标
  服务（在线系统）	等待请求，尽快处理，发送响应	响应时间、可用性
  批处理系统（离线系统）	大量有界输入，批量处理生成输出，需要较长时间	吞吐量
  流处理系统（准实时系统）	持续消费输入、处理输入、产生输出；在线服务与离线批处理的折衷	时延、吞吐量

• Unix 哲学中 pipeline 相关设计原则有哪些？

  • 模块化：让每个程序都做好一件事。要做一件新的工作，写一个新程序，而不是通过添加功能让老程序复杂化。
  • 标准化：期待每个程序的输出成为另一个程序的输入。不要将无关信息混入输出；避免使用严格的列数据或二进制输入格式；不要坚持交互式输入。
  • 快速原型设计：设计和构建软件，甚至是操作系统，要尽早尝试。最好在几周内完成，不要犹豫，扔掉笨拙的部分，重建它们。
  • 自动化：优先使用工具来减轻编程任务。即便必须曲线救国编写工具，且在用完后很可能要扔掉大部分。

• MapReduce 与 Unix pipeline 的比较

  比较内容	MR	Unix pipe
  程序逻辑与IO布线松耦合	是	是
  输入输出媒质	分布式文件系统 HDFS	Stdin, Stdout
  中间状态存储媒质	本地磁盘	内存缓冲器
  相邻阶段数据消费的模式	前驱作业完成后才能消费	输出一旦生成就被消费（流水线）
  实现方式	给定框架写回调	统一的接口
  是否支持分布式并行计算	支持	不支持
  是否支持结构化文件格式解析	支持（Avro等编码）	不支持

• 如何理解移动计算比移动数据更划算？MR是否贯彻了这一宗旨？

  • 既然数据是庞大的，而程序要比数据小得多，将数据分发给程序所在节点是不划算的，那么就反其道而行之，将程序分发到数据所在的地方进行计算。
  • MapReduce 倾向于移动计算。调度器试图在其中一台存储输入文件副本的机器上运行每个 Mapper，只要该机器有足够的资源来运行 Mapper 任务。

• 简述 MR 的处理流程

  • Master 接受任务，向 worker 发送程序。
  • 读取相应的输入，根据大小划分出若干 split（由 mapper 数目确定）。
  • Master将 mapper 分配到对应 workers 上，worker 在 map 阶段读取对应的 split，调用 mapper 函数并分区排序输出至本地磁盘。
  • 待所有 maps 完成后 master 将 reducer 分配到对应 worker 上，worker 在 reduce 阶段读取 maps 对应分区，shuffle 并调用 reducer 函数，最终输出至分布式文件系统中。

• MR帮我们隐藏掉哪些复杂的处理？

  • 文件的读写过程。
  • Map，reduce 的调度(worker 容错，tasks 备份)。
  • 中间数据的管理(partitioner，combiner)。

• Mapper 和 reducer 的个数是如何确定的？为什么建议一个系统中 mapper 及 reducer 个数要大于 worker 数目？

  • Mapper 的个数是根据输入确定的，可以配置分片大小(16M~64M)。
  • Reducer 的个数是用户指定的。
  • 为了能够解决 worker 间处理能力不均衡问题（类比 redis cluster slot）。

• MR 倾向于全表扫描而非索引查询的原因是什么？

  • 批处理通常是指在数据集中解析某种关联的全量存在，通常需要计算大量记录的聚合，因此使用全表扫描是合理的。
  • 分布式多机处理维护索引一致性的开销大。

• MR 中如何处理热键带来的数据倾斜？

  • 可以分成两个 MR 处理。第一个 MR 将热键发到多个 reducer 上；第二个 MR 聚合热键的子结果集。

• MR 如果将输出直接 sink 到数据库中会有什么问题？

  • 为每条记录发起一个网络请求，要比批处理任务的正常吞吐量慢几个数量级。
  • 数据库很可能被轻易压垮，其查询性能可能变差。
  • 无法保障原子性。

• 大规模并行计算(MPP)与 Hadoop 的对比

  对比项	MPP	Hadoop
  本质区别	一组机器上并行执行 SQL 查询	可以运行任意程序的通用计算框架
  存储的多样性	专有存储格式	原始数据
  处理模型的方式	SQL 查询	命令式 callback，并衍生出对查询引擎支持，如 pig latin，HQL 等
  故障处理	一损俱损	容错

• 数据流引擎用来解决什么问题？

  • MapReduce 串联后物化中间结果开销太大，且用处不大。
  • 算子可以在输入就绪后立即开始执行，后续阶段无需等待前驱阶段整个完成后再开始，是一种准实时处理。

扩展阅读

• MapReduce: Simplified Data Processing on Large Clusters

  • MR 需要编码人员完成哪些内容？

    • 设定输入输出目录。
    • 指定定 reducer 个数。
    • 编写 mapper和 reducer 函数等。

  • MR 内部机制提供的哪些功能？

    • 输入数据的分区。
    • 将程序调度到集群中一批节点上执行。
    • 处理节点失效的问题。
    • 管理跨节点通信。

  • MR 在节省网络带宽方面有哪些举措？

    • Map 会优先调度程序到拥有其输入文件块副本之一的节点上，这样导致大多数读都是本地读。
    • 中间结果存在执行 map 节点的本地磁盘中，而非 HDFS 上。
    • 允许自定义 Combiner 在数据发送到网络前做部分合并。

  • MR 如何实现容错？

    • Worker 挂了的情况
      • 未完成的 mapper：直接 fail 掉，重新调度。
      • 已完成的 mapper：重新执行，因为很可能 worker 的本地磁盘不可达了。
      • 未完成的 reducer：直接 fail 掉，重新调度。
      • 已完成的 reducer：无需重新执行，因为结果已经存到分布式文件系统了。
    • Master 挂了的情况
      • 论文中没有考虑 master HA，直接挂掉整个 MR。生产环境中 yarn 集群是支持 master 高可用的。

  • MR 如何解决慢节点(straggler)的问题？

    • 采用任务备份执行策略：当一个 MR 操作接近完成时，master 会调度正在处理的任务去其他节点执行用以备份，当主任务或者备份任务之一完成时，就标记此任务已经执行完成。

  • MR 如何进行故障处理的？

    • master 会定期 ping workers，如果规定时间内没有响应，则将相关的 worker 标记为失效，其上的任务会转移到其他 worker 上。