读书笔记-数据密集型应用设计

发表于 更新于 Disqus：

本书原著为英文，即《Designing Data-Intensive Applications》，主要讲述数据库底层原理和设计思路，读来受益颇多。

基本原则

我们期望数据系统可靠、可扩展、可维护，但是由于 CAP 原理的限制，我们无法完全做到这些，因此在设计分布式数据库系统时，必然存在各种考量与限制。这里的数据库，指的不是狭义的关系型数据库，或者非关系型数据库。而是一种广泛的Data System，包括消息队列、RDBMS, NOSQL, 以及图数据库、列式数据库等等负责存储数据的组件。

可靠性

考量以下几点：

  1. 提供正常正确的功能；
  2. 错误容忍性；
  3. 性能；
  4. 安全认证；

其中错误容忍性又分为硬件错误（如断电、内存不足、磁盘不足、网络断开等）和软件错误（各种软件 bug 等），以及人工错误（操作错误、输入错误等）

可扩展性

当组件性能、容量无法满足需求时，组件能够通过扩展的方式满足需求，这就是所谓的可扩展性。

书中举了 Twitter 的 timeline 设计作为例子，我们知道 timeline 展示的是 follower 的发布的状态，那么不考虑任何优化的情况下，设计如下：如果用关系型来描述的话，需要一个 user 表，一个用户 follow 关系表，一个 tweets 表，对于 user id 为 1 的用户，其首页的 timeline 生成是

1
select t.* from tweets t join follow f on f.follower_id=t.user_id where f.user_id=1 order by t.created_at limit 20;

显然 tweets 表会迅速膨胀成一个超大的表，这种设计不能满足性能的需求。采用写扩散的方案，将每个用户的 timeline 独立存储，用户新的 post 插入 tweets 表后，还要将这个 tweet 插入用户的 follower的timeline 缓存中。除了这个方案以外，还有很多其他的方法，比如使用消息队列。用户 ins/del po, follow/unfollow some one 触发事件，需要对 timeline 进行重新生成。Twitter最终采用了两种方案混合的方式。

性能描述的常用指标包括：延迟、吞吐量、响应时间等。平均响应时间有时候并不能很好的描述性能，中位数响应时间更合适（一半的请求小于该时间，另一半的大于该时间）。中位数响应时间即 50%分位响应时间，如果要求的更严格，可能需要使用 95%分位响应时间等，甚至 99.9%分位。99%分位以上的又被称为尾部延迟。

一般将可扩展性分为水平扩展和垂直扩展，两者可以结合起来。如果系统具有自动根据负载进行扩展的能力，这种系统是所谓的“弹性系统”。

可维护性

这里主要指的是系统本身简单可维护，且代码清晰易改动。可维护性显然不仅仅是架构的问题，涉及到方方面面吧，比如：

  1. 系统健康监控
  2. 错误跟踪系统
  3. 自动化部署
  4. 完善的文档系统
  5. 优雅的抽象，模块化
  6. 持续迭代

显然这些其实项目管理的内容。

数据模型和查询语言

常见的数据模型包括关系型数据模型，文档性数据模型，网络数据模型和图数据模型

关系型数据模型

关系型数据库是最经典的数据库，也是最常用的模型。在 1 对多环境下，文档性数据模型（一般是类 JSON 格式）可以很好的描述数据关系；但是多对多就比较麻烦了。而且现在已有的文档型数据库中，大部分是不支持不同表格之前关联查询的。

随着技术的进步，关系型数据库和文档型数据库产生了一些融合，现在关系型数据库一般也支持 JSON 字段了，虽然这种有效的融合本质上是反模式的。

关系型数据库统一使用 sql 语言操作，sql 是一种 DML，类似 CSS。文档型、图数据库的查询语言不通用由各个实现自己定义。当然随着分布式关系型数据库的发展，sql 仍然是最重要的数据操纵语言。

图数据模型比较复杂，按着一般图的概念，结点和关系构成了整张图。属性图模型的设计如下：

  1. 一个图中会记录节点和关系
  2. 关系可以用来关联两个节点
  3. 节点和关系都可以拥有自己的属性
  4. 可以赋予节点多个标签(类别)

在某些应用场景里（如社交网络、金融风控等多对多场景），图数据库在描述关系上具有无与伦比的优势，可以大幅简化查询设计。除了属性图外，还有其他图数据模型实现，如 Triple-Stores，将数据存为主谓宾三元组，一般是使用 SPARQL 进行查询；然后还有 RDF 数据模型，一般使用 XML 语言描述。

存储和取回

本章阐述了数据库底层存储和查询的原理。文中先举例了一个 KV 数据库最简单的实现，将数据存在文件中，写入就直接写在文件尾部，读取则用 tail 值（逆序查找即可）。这种直接写到文件尾部的只读文件，本质上是一种 log.

当然这个实现有个很明显的问题：写入很快，但是查找很慢。如果 key 根本不存在，需要遍历整个文件，因此需要引入索引(index)的实现。比如这里将所有的 key 存入一个红黑树或者哈希表，然后存放对应的偏移量作为值，即成为一个索引。

由于数据存入文件是 append only 的，很容易导致磁盘空间耗尽，因此需要周期性的对文件进行压缩。对于 KV 数据库而言，每个 key 值最后对应的 value 是唯一的，所谓的压缩其实就是将对同一个 key 的赋值仅保留最后一个。显然这个过程可以分片同步进行（类似归并排序的流程），也可以放在后台进行，不影响前台正常的读写。

哈希索引是最快的查询索引，仅需要 O(1)时间，但是问题是哈希表必须存入内存之中，一般多用在内存数据库中。而对于存储在磁盘上的数据，一般使用 b-tree 来存放。

SSTABLE 和 LSM-TREE

如果将上述实现的 KV 数据库中的 KEY 排序，得到的表就是所谓 SSTABLE(SORTED STRING TABLE)，这种表格归并和查找的速度都明显超过普通的文件，这样就不再需要额外的完整索引来进行查找加速（但是可能需要稀疏索引来加速搜索）。

SSTABLE 在内存中可以使用各种平衡二叉树，比如红黑树或者 AVL 树。为了性能考虑，先把数据写入内存表（即缓存），然后等到内存中的数据达到一定的阈值后，再序列化写入硬盘，写入硬盘的部分也可以分片。最后，周期性运行数据压缩，消除冗余 key 值。

SSTABLE 的设计比较完善，考虑到掉电问题，还需要对内存表的操作保留一份日志，以便进行错误恢复。可以使用 WAL（WRITE AHEAD LOG)日志来记录。

以上思路，就是所谓的 LOG STRUCTURED MERGE-TREE, 即 LSM-TREE，Lucence 这个搜索引擎在底层即使用了这种数据结构，然后 Level DB 等数据库也使用了这种数据结构，Level 指的是数据归并压缩时使用的策略。将 key 根据范围划分为不同的 Level，从而用来加速归并和压缩的速度。

可以使用Bloom filters算法加速搜索，确认 key 不存在。

B-TREE

b-tree 是磁盘存储数据时最常用的索引结构，这是一种自平衡多路查找树，特点是能够保持较低的高度。

b-tree 将数据抽象成固定大小的 block 或者说 page，一般是 4Kb 每页（机器硬盘），每次读写一页。每个 page 里面是数据和指向其他 page 的指针，这棵树也有一个根节点，是每次搜索的开始。每页包含指向子叶的指针数，即所谓的“分支因子”（一般是几百个）。page 里面是索引列的有序键值，但是这个键值是稀疏的排序，树的高度被保证为较小的值，这样通过 3~4 层的搜索能够找到大部分 key 值。

还有一些常见的其他的优化措施，如 WAL 啊，多线程保护（latch）啊，写时复制啊，或者使用变体的分型树、b+树、b*树等.

对比B-Tree和LSM-Tree，后者拥有更好的写性能（速度和吞吐量），前者拥有更好的读性能。同时，后者由于会定期重写SSTables清除碎片，对磁盘空间的需求量也小的多。但是LSM-Tree在压缩数据时会影响磁盘的IO性能，进而影响到数据库的读写速度。

聚簇索引与非聚簇索引

简单来说，直接将值放在索引里的是聚簇索引；放的是数据的引用/指针的则是非聚簇索引。后者需要回表索取原始数据，所以性能会差一些。综合两者的被称为覆盖索引。

多列索引

简单的实现是直接将多列拼接成同一个 key，复杂情况使用其他优化的数据结构。Mysql中通常成为复合索引，适用最左匹配原则。

GIS 中的地理位置索引，包含经度和纬度，一般使用 R-TREE 来实现。

全文索引

对于搜索引擎，需要的是进行模糊查询，一般的索引技术不能满足需求。数据结构以外，还需要结合分词技术、机器学习等其他技术才能满足各种需求。

内存数据库

随着内存价格的降低和容量的增加，全内存型数据库也开始涌现。对于 IO 性能要求较高的场合，大量使用内存数据库（如游戏）。关系型内存数据库常见的如 voltdb，KV 型的如 redis 等。

内存数据库速度快的原因不是把所有数据都放在内存里，因为传统关系型数据库也有 cache，这个优势并没有想象的那么大。内存数据库避免了序列化/反序列化的额外负担，同时还可以实现一些无法在磁盘中实现的功能，如 Redis 中的 set, zset 等。

内存数据库可以存放超过内存大小的数据，简单来说就是将最近未使用的数据写入磁盘，需要的时候再重载入内存，类似操作系统的虚拟内存技术。随着非易失性内存技术的发展，最终硬盘和内存将会殊途同归，也就不用再考虑这些问题了。

OLTP 与 OLAP

前者用于大量写入，对事务的性能要求较高，后者用于数据分析。

刚开始的时候都用普通 db，随着量级的发展，OLAP 一般使用独立的数仓来完成。数仓将 OLTP 数据库中的数据进行 ETL，存入专门用来数据分析的 db. OLAP 数据库和 OLTP 使用不同的优化方式，前者使用了一些其他的索引技术。

OLAP 一般使用星型模型/雪花模型，将多维度数据聚合到事实表中，从而避免大量 join 查询。此外，OLAP 会使用列式数据库（如HBase），列式可以更方便的进行数据压缩，对查询进行更好的优化。

列式数据库的写入很麻烦，一般使用 LSM-TREE 进行优化，先写入内存，异步写入文件。

除了这些技术以外，还有很多其他辅助手段用来提升 OLAP 的查询速度，如物化视图。对于需要经常查询的聚合数据，适用物化视图相当于加了个触发器，自动根据原始数据更新对应的聚合数据表。这样查询的时候就不要实时聚合，大幅度提高了查询速度。

编码与迭代

本章主要讨论消息序列化的编码结构（不是字符编码），以及这些编码形式如何应对字段变更、滚动升级等需求。

二进制序列化

各个语言有自己的二进制序列化机制，但是一般并不推荐使用，其兼容性、适用性和安全性都有一些问题。不过二进制序列化速度一般比纯文本格式要快一些。

JSON, XML 和二进制编码

一般情况下，JSON 和 XML 足够用了，除了一些缺点。JSON 的问题是只支持浮点数，且无法指定精度，有溢出风险。XML 的话就是有点过于笨重，但是支持 XPATH 这种高级检索语言。基于 JSON 和 XML 也有一些二进制编码。

如果使用 RPC 通信，可以考虑使用二进制编码，例如 Thift 或者 Protobuf，此外还有 Avro 等.

显然 JSON 是通过字段的 key 值来保持兼容性的，而 XML 则使用属性。而 Thift 和 Protobuf 则使用的是字段的 tag，旧的代码读到不认识的 tag，就会忽略掉对应的字段，从而保持兼容性。当然，这里有个问题，新增的字段不可定义为required，就如同给关系型数据库新增字段不能为 NOT NULL 且没有 DEFAULT 值一样。如果是移除字段，也只能移除optional的，且该字段的 tag 将来一定不能被重复使用。如果想要修改字段类型，就有一定的风险，需要视字段间的兼容性和精度而定。protobuf3移除了这两个关键字（并且加入了map），所有的字段都被视为optional.protobuf的一个问题是他不允许嵌套的array和map（当然可以通过嵌套message变相实现），Thrift则允许。

对于 Avro，其 IDL 里面根本没有 tag，读方的 schema 和写方的 schema 可以不一致，avro 会自动处理兼容的字段，忽略不兼容的字段（或者赋默认值）。Avro 是为了给 Hadoop 使用的，这种设计的目的是为了关系型数据库增减字段时不需要人工手动修改 IDL 的 schema.

HTTP, RPC, MQ

基于不同传输协议的数据封装讨论，都是一些开发者耳熟能详的知识点，不再赘述。

副本集

副本集一般有三种架构：single leader，multi leader， no leader。对应mysql，一主多从的架构有MHA，多主的架构有PXC。副本集的主要目的是保证数据高可用，副效果是降低单机的负载。

主从模式

即单主模式，写到 leader，leader 通过 log 或者 Stream 同步到 follower，读的时候可以从从库读，也可以从主库读（即读写分离）。

主库到从库的同步可能是同步或异步的，后者会出现读出的数据是 old data 的情况。

故障恢复：如果从库 down 了，重启后通过日志重新同步即可；但是如果主库 down 了，就需要重新选举一个 leader，否则整个服务就不可用了。选举的过程包括：

  1. 认定 leader down，一般使用 timeout
  2. 选举新的 leader；一般使用具有最新数据的副本当leader（共识问题）
  3. 使用选举出来的新 leader

需要解决的问题：

  1. 如果 follower 与 leader 之间的数据同步是异步进行的，old leader down 之前可能还没来得及将数据同步给其他 follower，那么新的 leader 就有丢失一部分数据。old leader 恢复后，需要成为 follower，并丢弃这部分未同步的内容；这种丢弃是很危险的，有可能出现各种问题；
  2. 可能会出现两个节点都以为自己是 leader 的问题，即所谓的脑裂问题；
  3. 判定服务 down 的 timeout 确定；
  4. 原来的主库重新上线后，可能有冲突要解决；

副本 log 的实现原理

对于关系型数据库而言，一种显而易见的实现方式是将所有写语句(CREATE, UPDATE, DELETE, ALTER)都记录到日志里，follower 依序重复执行这些语句。但是这里可能有一些问题：

  1. 有些函数是不可能重复执行的，如 RAND(), NOW()之类的；
  2. 如果依赖已经存在的数据，必须保证执行顺序，这意味着不能并发执行 log 中的语句；
  3. 有副作用的语句在各个副本集中造成的副作用可能不一致；

这些问题可以通过将非确定性的语句修改为确定性的（即将 NOW()的结果记录）来解决，MySQL 则直接使用了 ROW-BASED 将行数据覆盖的方法（又称为 logic log）来解决。还可以使用 WAL 这种直接修改磁盘字节的方法来进行，这种方法最大的问题是要求所有的 follower 必须和 leader 保持同样的二进制结构（如存储引擎），这会导致无法平滑升级服务。最后还有一种基于触发器实现的同步，一般是在应用层同步数据时当作工具来使用。

副本 log 的问题

  1. 读写一致性问题。用户写完以后立刻读，必须保证读到的是刚写的数据，但是由于从库的同步是异步的，所以可能会出问题；主从异步同步模式仅仅能保证最终一致性，而不是实时强一致；
  2. 数据时序性问题。如果用户使用了一系列的读（落到不同的 follower 上），可能由于同步进度的问题，导致部分读到的是新数据，部分是旧数据；

解决方案：

  1. 如果能明确区分数据属于用户自己，则直接从主库读取；
  2. 最简单的方案是用户总是从同一个副本中读取（即所谓的单调读）；不过这样还要考虑副本down了的HA；然而除了这种顺序以外，还有一种：假设用户A和用户B在对话，二者读的是不同的从库。那么用户C在旁观这种对话过程中，可能观察到错误的对话顺序。在IM群聊中这种场景比较常见，对应这样的场景，需要保证一个群总是对应唯一的服务器节点，保证这种因果关系的顺序性。

换句话来说，这两个问题都没有完美的解决方案，只能根据业务的实际情况来区别对待。

多 leader 模式

单主模式情况下，如果服务器和主库的网络发生故障，服务就不再可用。在局域网中这种情况基本不太可能，但是如果存在多个数据中心（异地），这时候各个 data center 各有一个 leader 是更合适的，所有的写发往 local 的 leader，然后由 leader 之间相互同步。显然，多 leader 之间的数据同步会引发各种问题。而且新加入的节点需要同步全量数据，开销很大。

还有一种特殊的多 leader 模式：如果应用需要能够离线工作（如日历），但是设备没有连接上英特网，那么此时设备本地的 db 就是 leader.

多主模式下，两个不同节点的事务可能都提交成功，但是db之间合并数据时可能会出现冲突。解决方案：

  1. 避免这种情况，根据用户的 ip 地址就近选择数据中心，游戏分服就是这样解决的。但是如果用户换了地方，原来账号的体验就会比较差了。
  2. 自动解决冲突：数据加入时间戳（自增 ID），使用最新的值解决冲突（即LWW，会丢数据）；或者允许用户自定义冲突解决代码，当发现冲突时自动调用这段代码；
  3. 手动解决冲突：数据库记录下所有冲突，当该值被阅读时，返回所有值，提示用户手动解决冲突，CouchDB 使用该方案；

多 leader 之间同步拓扑：

  1. 环形拓扑：每个 leader 只同步给另外一个 leader，这里要注意单节点挂掉的问题；
  2. 星形拓扑：使用一个 root 节点，其他所有节点与该节点进行同步，root 节点可能挂掉；
  3. all to all，每个节点和其他所有节点拓扑，这时要注意时序问题；

总的来说，目前多主模式在实际运行中的冲突问题还没有完美的自动化解决方案，需要根据业务场景确定策略。

leaderless 模式

这种模式没有主从，客户端的读写同时发送给所有的结点。如果有节点 down 掉，写请求会忽略挂掉的结点；当结点恢复后，会出现数据不一致的问题，客户端从多份节点数据中选取时，选取 version number 较大的数据，作为准确的数据返回。

上面这种宕机情况，数据修复方案：

  1. 客户端修复，客户端发现某个节点的数据版本落后于其他节点，那么就将最新版本的数据写入其他节点；这个的问题就是有些数据可能不怎么会被读到，数据长时间存在不一致的问题；
  2. 多节点之间自动同步，异步，无特定拓扑顺序，所以可能滞后很多；

多节点同时读取还有读取/写入数量，以及可信度的问题。一般而言，一共有 n 个结点，至少写入 w 个节点保证写成功，至少读取 r 个节点保证读成功，则必须有w+r>n才能保证系统的可靠性。一般情况下，n 是一个奇数，w=r=(n+1)/2. 当然可以根据实际需要调整 w 和 r，以协调自己所需的性能和可靠性。

显然 leaderless 模式会遇到和 multi-leader 类似的问题：时序问题、冲突问题，解决方案也类似。

版本向量

一种多客户端写入时解决冲突的方案，即对客户端的每个请求创建的数据都生成一个版本号。在返回客户端时，除了原始数据外也将数据的版本号返回客户端，客户端请求的时候带着本地的最新版本号，这样就可以根据数据的版本进行自动的数据合并。

分片

数据分片与副本集不同，是将数据进行垂直切分，也就是所谓的 sharding 技术，经常与副本技术配合使用。对于 KV 型数据库，常见的分区策略包括：

  1. 按 key 值范围，缺点是分区可能不均匀；
  2. 按 key 值的 hash 值范围，解决不均匀问题。此时要注意 hash 值必须唯一，如 md5。这会引入一个新问题：无法范围查询 key 值，因为他们不再毗邻。Cassandra 的解决方案是用联合主键，如果第一位确认，后面的还能保证都在一个 partition 上，如(user_id, timestamp)；
  3. 即使使用了 hash，有时候也会遇到单点过热问题，如社交网络上某个名人的行为总会引起大的数据波动，这个只能在应用层解决了；

次级索引

对于 RDBMS，除了主键，一般还有其他索引，如果访问需要通过多个索引字段进行，分片的方式就需要斟酌了。次级索引包括：

  1. 分区本地索引；此时范围查询的请求只能发给所有分片，然后再归并查询结果(scatter/gather);
  2. 全局索引；即对全局数据进行规约后的索引，但是全局索引也要分片，只是分片的方案需要根据业务来取舍；

再平衡

在运行一段时间后，数据在各个分片中可能不太均衡，或者需要增加/减少节点，需要将数据在节点之中进行数据搬运。这被称为再平衡。

  1. 一个简单的方案是为每个节点预先分配多个分区，当新的节点加入时将其他节点的部分分区数据迁移到该节点即可；删除节点执行反向操作；这个方案的问题是，预分配的分区数量可能难以确定；
  2. 使用动态分区。数据库会根据数据量的大小动态增加或者缩减分区个数；当然初始数据量很小的时候，可能只需要一个分区，此时可以预分区；
  3. 每个节点的分区数保持不变；当加入新节点时，增加对应数量的分区。这样可以更好的平衡各个节点；

使用一致性哈希算法，可以有效减少再平衡时需要移动的数据数量。

再平衡后的服务发现问题：服务器需要知道从哪个节点取数据。一般来说有3个解决方案：

  1. 服务器自己知道：将分区依据写成配置。手动再平衡完毕后修改配置；
  2. 使用代理的路由层，代理知道如何寻址；注意路由层本身也应该是个分布式的组件（例如zookeeper）；
  3. 随便发给任意一个节点，节点自己转发；

除了方案1的静态配置，其他两个方案需要动态发现正确的路由。这涉及到分布式环境的共识问题，

事务

关系型数据库一般都有 ACID 特性，其中 A 指的是原子性，即一件事要么发生，要么不发生，即使这件事里面包含多个动作；I 指的是隔离性，不同事务之间不相互影响，不会出现脏读等问题；D 指的是持久化能力；而 C 指的是一致性，这个其实无法由数据库来保证，在分布式系统里，最终一致性需要很多条件才能保证。

原子性

一般数据库都能保证单对象写入的原子性，但是只有少部分数据库能保证多对象写入的原子性（即支持事务）。

隔离性

那么根据不同的隔离级别，有以下几种弱隔离性实现：脏读->不可重复读->可重复读（幻读）->串行化.

数据库一般默认使用 MVCC 技术实现隔离。不可重复读一般情况下没啥影响，但是如果数据库同时在进行备份，可能中间状态就丢了，大部分db的默认隔离级别是这个。

使用 MVCC 将隔离级别上升为可重复读，或者说叫快照隔离（mysql默认该级别）。此时当事务开始时，会获得一个事务全局递增的唯一事务编号，而更新将会被拆分成删除+创建。这样，一个更新操作实际上产生了两个版本的数据。当一个事务开始时，做如下判定：

  1. 首先确定当前正在进行但还未提交的事务，使用这些事务开始前的数据版本；
  2. 已经 rollback 的事务，其数据修改被直接废弃；
  3. 事务 ID 号大于当前事务的提交，不管事务有没有提交，忽略其提交结果；
  4. 除了上诉情况以外，其他的写入可以被当前事务感知到；

这种实现对索引的使用：多个版本同个字段使用索引，使用 B 树时，update 不是直接修改 page，而是产生一个新 page，也就是copy-on-write。

写丢失

两个事务同时写，一个的写入可能会丢失。解决方案：

  1. 原子写入，包括使用CAS。但是用ORM的时候有时候会很难写出k=k+1这种语句，因为k会被直接解释为变量当前的值；
  2. 使用悲观锁，即select ... for update，不过在数据不存在时，不能用这个方案；而是要使用类似数据库的upsert语义方言。如mysql的ON DUPLICATE UPDATE，oracle的merge；
  3. 部分 db（不含 mysql）实现了 lost update detection，可以自动侦测到该问题；

幻读问题

可重复读会导致幻读，如果想要解决这个问题，只能使用串行化，这种隔离的实现方案包括：

  1. 单线程执行所有事务，这样就自动串行化了。如 Redis、VoltDB（使用存储过程，将读写都写在一起，优化方案）；
  2. 2PL，即两阶段锁。类似读写锁，如果事务对对象没有写入，就允许共享同一个对象。但是一旦开始写入，则使用排他锁进行独占；这比单独的写锁性能更好（这是显然的）；

序列化算法

  1. 共享锁、排他锁、读写锁；
  2. 谓词锁。即对某个条件产生锁，即使该条件下尚不存在数据。显然谓词锁可能会大幅度降低数据库的性能（创建太多），他的替代品是：
  3. 间隙锁。即对搜索条件使用的某个字段的索引进行加锁；但是如果无法命中索引的话，会退化成表锁，大幅度影响性能；

将最后两个隔离方案结合起来，就是所谓的serializable snapshot isolation，即 SSI，这是一个新算法（2008 年提出），在 PostgreSQL 9.1 以后使用，较有潜力。

分布式系统的问题

局部失败

分布式系统某个节点挂掉引起的一系列问题。

  1. 如果是单主集群，需要重新选举；
  2. 需要考虑节点恢复后如何重新纳入集群；
  3. 需要考虑如何判定节点挂掉，一般是用网络超时，但是这个值比较难以假定；
  4. 考虑单节点阻塞导致的丢包问题；

时序问题

分布式系统不同节点之间的时钟同步。

  1. 依赖时序策略的影响，如 LWW（可以使用逻辑时钟代替墙上时钟）；
  2. NTP 同步的精确度，NTP 本身的延迟，NTP 服务本身的不可靠性；
  3. Google spanner 的时钟策略，返回一个[least, most]的时钟范围，保证准确的时间落在该范围之内；

系统阻塞

  1. GC 引起的 stop the world
  2. 单线程阻塞

其他原因造成的系统结点卡顿，以至于其他结点访问超时，误以为该节点挂了。

一致性

线性一致性(Linearizability)

所谓线性一致性，指的是对于一个分布式系统的多个副本集，读出的结果永远都是一致的（就好像从唯一一个副本集中读出的一样）。该一致性模型是我们能实现的最强一致性模型，所以又被称为 strong consistency.这种模型假设操作具有一个全局有效时钟的时间戳，但是这个时钟仅具有有限的精确度。要求时间戳在前的进程先执行，换句话说，所有的操作都不是并发的，而是有严格的顺序的（全序）。

单 leader 的副本集群，理论上可以做到线性一致，但是在节点故障的时候可能出现脑裂等问题，此时就会违反线性一致性；而多 leader 节点一定不会是线性一致的，无 leader 集群则不一定，取决于配置（只有 read repair 策略下或许可行，但是这个效率很低，故一般认为不保证。）。另外 LWW 策略必然是非线性的（依赖时钟）。

在某些场景下，只允许线性一致性，比如 leader 选举等。显然该一致性的性能是最差的。

因果一致性(causal consistency)

当一个读操作后面跟着一个写操作时，这两个事件就具有潜在的因果关系，同样，读操作也与为读操作提供数据的写操作因果相关。没有因果关系的操作被称为并发的。

所有进程必须以相同的顺序看到具有潜在因果关系的写操作，不同机器上的进程可以以不同的顺序被看到并发的写操作。

实现因果一致性要求跟踪哪些进程看到了哪些写操作。这就意味着必须构建和维护一张记录哪些操作依赖于哪些操作的依赖关系图。一种实现方法是版本（向量）时间戳。

几乎所有的分布式系统都支持因果一致性。前面讨论的事务追踪数据过期抛出失败，也就是保证了因果一致性。

使用 Lamport 时间戳可以保证因果一致性，其实现原理如下：

  1. 不同的结点各有自己的编号 n；
  2. 每个结点使用自己的计数器 c；
  3. 使用(c, n)表示 lamport 时间戳；
  4. 客户端/node 跟踪 c 值，当 node 发现客户端请求的 c 值大于自身 c 值时，立刻将自身 c 值设为请求的 c 值（对客户端亦然）；
  5. 定义当 n 相等时 c 值较小的逻辑时间较小；否则 n 值较小的逻辑时间较小；

显然 lamport 时间戳定义了一个全序的操作序列。问题在于这个顺序必须在动作执行完成后（即 node 返回后）才能确定下来，这对于某些场合不够用（比如唯一约束）。

弱一致性(weak consistency)

引入同步变量 S，其仅有一个关联操作 synchronize(S)，该操作同步数据存储的所有本地拷贝。

使用同步变量来部分地定义一致性就得到称为弱一致性模型，其具有三个属性：

  • 对数据存储所关联的同步变量的访问是顺序一致的；
  • 每个拷贝完成所有先前执行的写操作之前，不允许对同步变量进行任何操作；
  • 所有先前对同步变量执行的操作都执行完毕之前，不允许对数据项进行任何读或写操作。

CAP 理论

在网络分区的情况下，一致性和高可用性只能取其一，即所谓 CAP 理论。CAP 理论在最开始时(2000 年)对分布式系统的设计起到了很重要的指导作用，但是现在要考虑的情况要复杂的多，因此一般不再提起该理论。

全序广播

通过单 Leader 多 Follower 机制，在 Leader 节点上对所有操作进行排序，从而决定了整个操作顺序，并将操作顺序进行广播。

全序广播要求满足如下两个属性总是被满足：

  • 可靠的交付,没有消息丢失：
  • 如果消息被传递到一个节点，它将被传递给所有节点。完全有序传递，消息以相同的顺序传递给每个节点。

全序广播是异步的：消息保证以固定的顺序可靠地传递，但不能保证何时传递消息（因此存在节点可能落后于其他节点）。而线性化一致性能够保证：每次读操作能够读到最新值的写入。我们可以依托于全序广播，在存储上实现线性化一致性。全序广播需要一个序列生成器，然而这又是一个共识问题。

共识

所谓共识，指的就是最终一致性。在理论上，如果节点可能崩溃，则共识不可能达成（FLP）。不过在现实中，节点崩溃是可以探测的，所以共识还是可以达成的。

二阶段提交

当客户端准备提交事务时，协调者（事务管理器）开始阶段 1：所有参与者进行预提交，根据响应，分为两种情况：

  1. 所有节点准备完毕（使用 transaction id，完成相关写入）。进入阶段 2，开始真正的 commit；
  2. 任一节点未正确响应，进入 abort;

显然，各节点即使准备完毕，也可能因为异常导致并未正确提交，所以该节点在未做出正确答复之前，协调者会持续询问。

但是如果协调者也挂了，2PC就会卡住，必须等待协调者恢复，此时的状态称为存疑事务。

三阶段提交

改进的二阶段提交，加入了询问机制。该协议假设网络延迟有界，这不符合正常的场景，所以一般还是用2PC.

异构系统的分布式事务方案：XA事务

这是一种协议，由数据库自己实现。具体来说就是应用程序自己充当协调者发起异构系统之间的二阶段提交。

paxos 算法

paxos 算法是分布式系统实现最终共识的当前唯一正确算法，raft 等算法只是其变种。他解决的是最终一致性（共识）问题，这个前面提的一致性不是一个概念。其流程如下：

阶段一：

(a) Proposer选择一个提案编号N，然后向半数以上的Acceptor发送编号为N的Prepare请求。

(b) 如果一个Acceptor收到一个编号为N的Prepare请求，且N大于该Acceptor已经响应过的所有Prepare请求的编号，那么它就会将它已经接受过的编号最大的提案（如果有的话）作为响应反馈给Proposer，同时该Acceptor承诺不再接受任何编号小于N的提案。

阶段二：

(a) 如果Proposer收到半数以上Acceptor对其发出的编号为N的Prepare请求的响应，那么它就会发送一个针对[N,V]提案的Accept请求给半数以上的Acceptor。注意：V就是收到的响应中编号最大的提案的value，如果响应中不包含任何提案，那么V就由Proposer自己决定。

(b) 如果Acceptor收到一个针对编号为N的提案的Accept请求，只要该Acceptor没有对编号大于N的Prepare请求做出过响应，它就接受该提案。

批处理

这一章介绍了一些常用的处理工具，包括unix上常见的sed、awk等小工具和map-reduce. 后续还介绍了流式数据处理需要注意的问题。