Designing Data-Intensive Applications Notes

Chapter 1 - 可靠系统

• 以最小出错的方式来设计系统，减少人为出错
• 想办法分离出最容易出错的地方和容易引发故障的接口
• 充分的测试
• 快速的恢复机制以尽量减少故障影响
• 详细而清晰的监控子系统
• 流程化

Chapter 2 - 数据模型和查询语言

关系型和文档型数据库现状

• 文档型：读时模式，读取的时候才去解析具体的字段
• RDS：写时模式，已有的关系经由表结构来确定

关注存储的局部性

SQL 是声明式查询语言，隐藏了数据库引擎的实现细节。如果交由命令式语言，则语句间有顺序关系，无法并行

Chapter 3 - 数据存储和检索

SSTables 基本结构和 LSM-Tree

• 每个日志结构的存储段都是一组 key-value 的序列
• 每个段中的 key 只能出现一次，且按 key 的值进行排序
• Log-Structured Merge-Tree

优缺点

• 合并段可以使用类似归并排序的做法
• 每个段都是按照 key 进行排序，则可知道每个段的取值范围，有利于查找 key
• 写入较快，读取较慢

B-trees

• 将数据库分解成可变大小的段，并始终按顺序写入，这种设计更靠近底层硬件
• 预写日志 WAL

事务处理

• OLTP
• OLAP

数据仓库

• 可能包含 OLTP 数据库的只读副本
• 从 OLTP 数据库中提取（Extract）然后转换（Transform）数据，加载（Load）到数据仓库中，成为 ETL 的过程

列式存储

• 将每列中的所有值存储在一起
• 列压缩，对于同一列来说，可能的值范围会小于等于数据量

Chapter 4 - 数据编码与演化

数据格式和模式变更

• 服务端升级
• 客户端升级并且很长一段时间存在新旧版本
• 向前兼容和向后兼容

数据表示形式

• 内存中，程序的数据结构
  • 不同的语言并不兼容，如 Python pickle 和 Java 的 io.Serializable
  • 并没有考虑版本和向前向后的兼容性
• 文件或者网络中的字节序列

编码格式

• JSON，XML 和 CSV，对人类更友好
• 二进制格式，对机器更友好
• 对不同组织使用同一数据编码格式的难度更高

Thrift 和 Protobuf

• 都是通过格式描述文件生成对应语言的编码解码用的代码
• 最终用于传输是二进制编码数据
• 对于 schema 的变化也都只能对新增字段更好的支持

Avro

• 通过 IDL 来确定传输数据的 schema
• 区分 reader 和 writer 的 schema
• 可用 union 和 null 来规避数据变更问题
• 可以提供一个可查的版本数据库来获知当前的 schema

Chapter 5 - 数据复制

主节点和从节点

• 主节点接收写入请求，从节点在主节点写入后获取其变更日志，保持顺序写入
• 主从节点都能接收读请求

同步复制和异步复制

• 都是关系到主节点的写更新如何复制到从节点中
• 同步复制则保证了主从节点的同步
• 异步复制则有可能导致数据丢失，但相应的吞吐量更高

节点失效，追赶式恢复

主节点失效

• 采用了异步复制，新的主节点出现数据丢失
• 例如使用自增主键，那如果外部的数据系统缓存了某些 id，但恢复时新的主节点计数器落后

复制日志

• 基于语句复制，并不能保证唯一性，如包含 NOW() 语句，或者带自增 ID，多个语句执行顺序不一致
• 基于 WAL（Write Ahead Log） 传输，WAL 的描述偏向底层，如果出现版本升级导致存储格式变化，则会出现恢复失败
• 基于行的逻辑日志复制，如 binlog，表示的是存储引擎层面的改动

复制滞后问题

• 读自己写，写入到了主节点，但还没同步到从节点，这就违反了读写一致性
  • 考虑数据中心的位置也不一定在附近
  • 记录时间戳（逻辑时钟，如版本或者实际时钟），请求时带上用以获取最新的数据
  • 一个账号的多设备
• 单调读
  • 不同的请求落到了同步情况不同的从节点上
  • 可以通过 id hash 到同一个从节点上
• 前缀一致性读
  • 多个关联的数据写入实际上物理存储是隔离的，写入时并不按照顺序来

复制滞后的解决方案

• 多主节点复制
  • 离线客户端操作，会出现断线好久之后重新同步的情况，类同于多主
  • 协作编辑，本地数据同步到服务器和别的正在编辑的用户，需要解决写冲突
  • 冲突解决策略，最终收敛的策略
• 无主节点复制
  • 客户端一次发送多个请求到后端写入
  • 读取时带版本信息，用以确认其最新值
  • quorum && happen-before?

Chapter 6 - 数据分区

每一条数据只属于一个分区，分区的主要目的是为了将数据和查询均匀分布在所有的节点上。

基于哈希分区无法应对如社交媒体名人或者热点信息带来的高度倾斜的负载，只能通过应用层去来减轻不平衡的程度

• 在关键字头或者尾添加随机数将写操作重新分区，但带来读操作需要应用层进行合并

二级索引

• 二级索引往往不能准确标识一条数据
• 基于文档的二级索引，不同的数据分区有不同的索引，查询需要查多个并合并
• 基于词条的二级索引，全局索引，索引自身也分区方便快速查询，写入速度一般，二级索引更新可以异步

分区再平衡

• 直接取模，任何新节点的引入或者节点的删除都会导致所有数据迁移
• 固定分区，分区数小于节点数，每个节点负责某一些分区，分区数需要创建时就确定好
• 动态分区，根据当前实际数据量创建或者删除分区
• 节点比例分区

请求路由

• 典型的服务发现问题，使用如 ZooKeeper 来存放对应关系
• P2P 的模式同步集群状态

一致性哈希？

Chapter 7 - 事务

磁盘和 SSD 都各有好处，如

• 磁盘的坏道率很低，但是整盘完全失效的情况却会概率高点
• SSD 对温度的要求会更高

除了硬件上的各种优劣，软件上的问题也会导致数据的丢失

弱隔离级别

这里的弱是相对串行化来的

读提交，read-committed

• 防止脏读，snapshot
• 防止脏写，通常采用行级锁

其会导致读倾斜，即不可重复读，需要 MVCC，即快照级别的隔离

防止更新丢失，如需要执行 +1 操作，可

• update set value = value + 1，但这种操作可能在 ORM 层面丢失了，回退回原来的两次操作
• 显式加锁
• 数据库可能提供隐式支持，如 PostgreSQL 的可重复读

有些不支持事务的数据库，可能支持原子的 CAS（Compare And Swap）

写倾斜

• 对多个对象的约束，并行的事务无法检测合法性，如排班和会议室的预订
• 可使用显式的加锁
• 可额外加入可暴露出冲突的锁条件，如会议室和时间的所有组合

可串行化

适用串行化的理由

• 不同的隔离级别，各家数据库实现不同
• 应用层代码无法判断是否安全
• OLTP 事务执行很快，只有少量的读写操作，而长时间的分析操作一般是只读
• 内存越来越便宜，可加载全部的数据到内存中

存储过程

采用单线程串行执行的系统往往不支持交互式的多语句事务，相对而言对网络和 IO 的要求更低，但实际上

• 存储过程不好管理，版本管理，调试都相对麻烦
• 现代的也有像 Redis 采用 Lua 来实现存储过程

需要注意的是，这里需要存储过程和内存数据库才能再单线程上执行所有事务变得可能。

而分区问题，又需要组织好数据集来使得单个线程能在单个分区内执行事务。而跨分区的事务就又需要额外的资源来进行协调。

两阶段加锁

two-phase locking, 2PL，现阶段唯一的串行化算法。

多个事务可以同时读取同一对象，但只要出现任何写操作，则必须加锁来进行独占访问。实际实现中，则以共享锁和互斥锁来实现，如 MySQL 中的 Share Lock 和 Exclusive Lock，都需要在 SQL 显式使用，否则就是使用 MVCC 来处理多事务问题。

谓词锁

并不属于某一个对象，而是属于符合某些特定查询条件的所有对象，就是为了防止出现上面说过的会议室预定问题。在实际实现中，则以索引区间锁作为简化和近似。

Chapter 8 - 分布式系统的挑战

故障和部分失效

不可靠网络

• 硬件不可靠
• IP 协议本身也不可靠
• 人为配置错误

需要故障检测，如下线失败节点，重试机制。

不可靠的时钟

• 墙上时钟，即根据某个日历返回当前时间和日期，如编程语言中的 get current time
• 单调时钟，如 Java 中的 System.nanoTIme() ，用于单机上的差值比较，从而为应用层提供单调递增计时，不同节点上的单调时钟没有任何意义
• 墙上时钟需要 NTP 来进行同步，但同步就会遇到如网络问题，服务器故障一类导致收到的结果不可用
• 移动设备用户可调墙上时钟
• 在分布式系统中采用墙上时要严格保证节点的时间同步，如果需要进行排序，最好采用递增计数器
• 线程暂停（gc，线程切换）之前如果进行时间的比较，有可能出现错误的结果，哪怕是单调时钟，最好依赖如信号量等线程同步工具

知识，真相和谎言

• 节点可能已经被认为失效，但其仍可能认为自身没问题
• 用 fencing 令牌来检测无意的误操作，已经过时的节点拒绝请求
• 拜占庭故障，指的是存在可能破环系统的节点，如航天中辐射之后的 CPU 寄存器的不可预测的行为，还有软件的 bug

Chapter 9 - 一致性与共识

为了构建容错系统，最好先建立一套通用的抽象机制和与之对应的技术保证。

事务隔离主要是为了处理并发执行事务时的各种临界条件，而分布式一致性则主要针对延迟和故障等问题来协调副本之间的状态。

可线性化

可串行化强调的是事务执行的结果是与串行执行一致的，可线性化强调的是对单个对象的读写最新值的保证。

依赖条件

• 加锁和主节点选举
• 约束和唯一性保证
• 跨通道的时间依赖
  • 如同时存在队列和 RPC 调用，两者到达顺序不同导致出现不一致的情况

线性化的代价

CAP 理论，可用性和分区容错性，系统只能支持其中两个。但实际上网络分区是一定存在的，一旦发生网络故障要么选择线性，要么选择可用性。

CAP 理论有争议，实际上节点延迟和其它相对网络分区更弱的情况没有考虑进去，并且在多核环境下，也很难考虑线性化。

顺序保证 *

概念

• 全序是指，集合中的任两个元素之间都可以比较的关系。 比如实数中的任两个数都可以比较大小，那么“大小”就是实数集的一个全序关系
• 偏序是指，集合中只有部分元素之间可以比较的关系。 比如复数集中并不是所有的数都可以比较大小，那么“大小”就是复数集的一个偏序关系。
• 在一个可线性化的系统中，存在全序操作关系。
• 因果关系至少可以定义为偏序

因果关系对所发生的事件施加了某种排序，某件事应该发生在某件事之前。我们称之为因果一致性。如

• Git 基于数字签名的上下文关系

可线性化是全序操作关系，系统的行为像是只有一个数据副本。而对因果关系而言，如果两个操作没有 happens-before 的关系，则它们就是并发关系，并发的关系无法排序，这表明因果关系是可定义为偏序。同时，并发就意味着分支和合并。

因果关系可以认为是一种可以容忍网络延迟，又能对网络故障提供容错的最强一致性模型。看似需要线性化的系统，实际上是需要因果一致性。

序列号排序

在存在唯一主节点的系统里面，主节点可生成单调递增的 id 来为每个操作复制。这样结果一定满足因果一致性。而不存在主节点的分布式系统，则需要外部手段来生成唯一自增 ID，如

• 不同节点奇偶 id
• 不同节点负责不同区间
• 通过墙上时钟

Lamport 时间戳

• 每个节点都有一个唯一的标识符
• 每个节点都有一个计数器
• 每个节点都追踪迄今为止看到的最大计数器值，如果发现比自己维护的要大，则修改成该值

实际上，处理时还是需要去收集到所有的请求信息才能去构造请求顺序。所以，还是主从复制的做法更直接有效。为了解决主节点的限制，以及故障时的节点切换，需要全序关系广播和原子广播。

顺序保证的范围是作用在分区之上，如果需要跨分区则需要非常多的工作（如 Kafka）

全序广播通常是指节点间交换信息的协议，要满足以下的基本安全属性

• 可靠发送，如果发送到了一个节点，也必须发送到其它所有节点
• 发送到每个节点的顺序相同

可以将其视为日志，如复制日志，事务日志和预写日志，传递信息则是通过追加日志的形式更新。全序关系模型是基于异步的模型，保证顺序可以发送，但不保证发送成功，而可线性化则强调就近性，读取时保证可以看到最新的输入。

分布式事务和共识

集群节点一致

• 主节点选举
• 原子事务提

两阶段提交 2PC

引入中间的协调者，其通常实现为共享库，运行在相同的进程中

• 阶段 1，协调者询问所有的参与者（多个数据节点）是否可以提交请求
• 阶段 2，提交请求

如果 1 中有任何的节点拒绝，则协调者在 2 中会向所有的节点发送放弃的请求。 而参与者确定了可以提交之后后续不会有放弃的选择，除非协调者确定不提交。对于单点系统而言，两个步骤是合二为一的，即写入事务日志即提交。如果协调者已经确定了阶段 1，则如果在阶段 2 之前失败，则参与者也不会单方面进行放弃。没有协调者的消息，参与者无法知道下一步的行动。协调者本身也应该拥有事务日志，在恢复后来决定是否需要继续未完成的事务。

XA 交易

异构系统下如何实施两阶段提交的一个工业标准。

• 停顿时仍持有锁
• 启发式决策，参与节点在紧急情况下单方面做出决定，放弃或者继续那些停顿的事务

如果协调者是应用服务器的一部分时，则其日志也变成了可靠系统的重要组成部分，要求与数据库本身一样重要。此时，已经不是无状态的系统了。

支持容错的共识

共识算法的基本性质

• 协商一致性（Uniform agreement），所有的节点都接受相同的决议
• 诚实性（Integrity），不能反悔，即不能对一项决议有两次决定
• 合法性（Validity），如果决定了值 v，则一定是由某个节点提议的
• 可终止性（Termination），节点如果不崩溃，则最终一定可以达成某项协议

容错体现在可终止性上，强调一个共识算法不能空转，必须取得实质性的进展。此处，前提是发生崩溃和不可用的节点数必须小于半数。常见算法有

• VSR
• Paxos
• Raft
• Zab

Epoch 和 Quorum

协议定义了一个世代编号，在每个世代里面，主节点是唯一确定的。如果主节点挂掉，则其余节点进行新一轮的选举，选举会赋予一个单调递增的 epoch 号。如果出现两个不同的 epoch 号则更高的获胜。

主节点如果想要做出决定，则须将提议发给其它所有节点，如果没有更高的 epoch 主节点存在时，在对当前提议进行投票。

算上之前的主节点投票，这里会有两轮投票，其中参与投票的节点必须至少有一个参与了最近一次主节点选举。换言之，如果在针对提议的投票中没有出现更高 epoch 号码，则可以认为当前的主节点没有替换。

Chapter 10 - 批处理系统

最简单的批处理就是使用如 awk 等工具进行日志分析。其特点

• 将字节序列视为 ASCII 文本
• 如果需要功能的组合则通过管道进行连接
• 避免使用严格的格式或者二进制
• 避免交互式输入

最大的局限性就是其只能在一台机器上运行。而 MapReduce 就是一个类似于分布式的 UNIX 工具，其进行输入和输出依赖于像 HDFS 这样的分布式文件系统。

Chapter 11 - 流处理系统

流处理系统即把时间流视为一种数据管理机制：一种无界的，持续增量处理的方式。在批处理系统中，通过文件名来标识一组相关的数据，流系统中，则被视为主题或者流。

消息系统

对于不同的消息系统，会有两个问题

• 如果生产者发送消息的速度比消费者快，会发生什么？
  • TCP 和 UNIX 管道会有个固定的缓冲区，如果填满了，发送者会堵塞
• 如果节点崩溃或者暂时离线，是否有消息丢失？
  • 持久性和吞吐量并不能同时满足

如果不通过消息系统，则可以考虑

• UDP 组播，适用于低延迟的场景
• 无代理的消息库（如 ZeroMQ）
• HTTP 或者 RPC 请求

这些方法都需要一个在应用层失效的重传机制，还需要生产者和消费者都是一直在线的。

消息代理，即消息队列，允许一个第三方服务来缓存需要传递的消息。具体体现在 JMS 和 AMQP 的标准上，常见的实现有 RabbitMQ，ActiveMQ。对于已经确认过的消息就会从代理中删除，就无法再接收该消息了。引入了像数据库的持久化存储的日志思想，就有了基于日志的消息存储。常见就是 Kafka。

数据库与流

在使用数据库的过程中，难免会因为缓慢增添外部的缓存，这样就容易出现不一致的情况。

Change Data Capture，CDC，即变更数据捕获。记录了写入数据库的所有变更，并可以复制到其它系统的实行来提取数据。数据库的复制日志解析可以从数据源处拿 CDC。有了这些日志，就可以进行数据的重放。在需要重建索引或者外部缓存时，也可以通过从偏移量为 0 处开始，扫描日志中的所有消息，这也是一个数据库内容的完整副本。相关的日志压缩也是通过扫描指定的 key 获取其最新值来压缩合并。

事件溯源，也可以将涉及到的所有对应用程序状态的变保存为事件的日志。不同的是，事件存储仅支持追加，不鼓励更新和删除。事件通常用来表达用户行为的意图，而不是一种对行为结果进行相应状态更新的机制。用户会发出一个命令，当命令检查完成（合法性校验）之后就变成了一个事件，这是命令和事件的区分。

状态，流和不可变性

通过不可变事件的追加日志，判断问题和恢复也会很方便。除此以外，还会捕获很多的信息，如顾客的意图而不只是购买的最终订单。

通过相同的事件日志可以派生出多个视图，如 Druid 和 Pistachio 都使用 Kafka 作为输入源，通过从事件日志到数据库的转换，能得到基于不同 key 的数据库。这种将数据写入和读取形式分开，并允许不同的读取视图的想法被称为命令查询职责分离（Command Query Responsibility Segregation，CQRS），与此相对的，传统数据库和模式设计的方法是基于数据查询和数据写入的形式相同。

这种模式最大的问题是，事件的捕获和变更日志的捕获通常是异步的，需要处理 “读自己写的” 这种问题。

• 同步执行读取视图的更新，这写入一个事务将写操作合并到一个原子处理中，所以要么是事件日志和读取视图都在同一个存储系统，要不跨不同系统的分布式事务，或者是全序广播
• 从事件日志中导出当前状态
  • 对多对象事务的大部分需求源自单个用户需要在不同地方修改数据的操作
  • 通过事件溯源可以设计一个事件使其成为用户操作的独立描述，将其追加到日志中，这样原子化就会很容易
  • 如果以相同的方式对日志和应用程序进行分区（分区 3 的用户需要更新应用程序分区 3），则简单的单线程消费者不需要对写操作进行并发控制

流处理

和批处理作业最大的不同是，流处理是不会结束的，因此排序无意义，也不能使用排序合并 join，容错机制也必须改变，从头开始运行运作了几年的流处理作业，几乎是不可能的。

长期以来流处理都被用于监控目的，则需要长期对特定事件进行分析，如信用卡消费，交易系统的价格变化。

复杂事件处理（Complex Event Processing）与正则表达式在字符串中搜索特定的字符模式类似，CEP 允许指定规则在流中搜索特定模式的事件。CEP 的查询是长久存储的，来自输入流的事件不断流过他们以匹配事件模式。实现有类似 Samza 这种支持声明式的 SQL 查询。

与 CEP 相对的则是流分析，CEP 专注特定的事件序列，而流分析更多关注大量时间累积的效果和统计指标，如

• 速率
• 在时间窗口的平均值
• 趋势的变化

有时也使用概率算法，如布隆过滤器，常见的实现为 Flink 和 Kafka Streams。

流的事件问题

需要关注的是事件时间和处理时间，如果使用的是处理节点上的本地系统时钟来确定窗口，在节点出现排队，网络故障或性能下降导致节点重启去处理过去的事件，就会出现事件事件和处理时间上延迟会非常明显。

为了调整不正确的设备时钟，需要记录三个时间戳

• 事件发生的事件
• 事件发送到服务器的时间
• 服务器收到事件的时间

第三个时间戳减去第二个则可以估计出设备时钟和服务器时钟的偏移量（还要考虑到网络延迟），将偏移量应用于第一个时间即可估计出一个事件实际发生的真实时间。

窗口类型

定义用于作事件统计的一个事件范围

• 轮转窗口，即一个固定的时间范围，如下午 2 点到 3 点，晚上 7 点 30 分到 7 点 31 分
• 跳跃窗口，有固定的长度，但是允许平滑过渡，如一个五分钟的窗口，之前在统计 10:30 到 10:35 内的事件，设定 hop 是 1 分钟，那下一个窗口则可以是 10:31 到 10:36
• 滑动窗口，包含在彼此的某个间隔内发生的所有事件，然后在事件过期之后从缓冲区中删除
• 会话窗口，将同一用户相关的事件都分组在一起，一旦一个用户一段时间没有活动，则窗口结束

总结

花了大半年时间看了两遍，看下来的总体感觉是我知道了一些东西，以及我还是有很多东西不懂。

特别是第 8 章和第 9 章，分布式的事务和共识的一些知识，属于都了解，但在应用层做开发很少会接触，知道其存在，但有时会不知道其为何要如此设计。整本书算是一个后端开发整体技术的一个总览，并且在很多地方也有较为深入的介绍。是一本好书，希望 2 3 年后再看一遍，希望那时能看懂更多。