《DDIA》

数据系统的基石

现今很多应用程序都是数据密集型（data-intensive）的，而非计算密集型（compute-intensive）的。因此 CPU 很少成为这类应用的瓶颈，更大的问题通常来自数据量、数据复杂性、以及数据的变更速度。

数据系统（data system）是一种模糊的统称。在信息社会中，一切皆可信息化，或者，某种程度上来说——数字化。这些数据的采集、存储和使用，是构成信息社会的基础。

常见的数据系统有哪些?

• 存储数据，以便之后再次使用——数据库
• 记住一些非常“重”的操作结果，方便之后加快读取速度——缓存
• 允许用户以各种关键字搜索、以各种条件过滤数据——搜索引擎
• 源源不断的产生数据、并发送给其他进程进行处理——流式处理
• 定期处理累积的大量数据——批处理
• 进行消息的传送与分发——消息队列

这些年来，随着应用需求的进一步复杂化，出现了很多新型的数据采集、存储和处理系统，它们不拘泥于单一的功能，也难以生硬的归到某个类别，例如：

• 缓存 Redis 也可以被用作消息队列；
• 消息队列 Kafka 可以持久化一段时间的日志数据，还可以作为流式处理组件；
• Spark 可以对数据进行批处理、也可以化小批为流，对数据进行流式处理。

可靠性、可扩展性、可维护性

一个应用必须满足各种需求才称得上有用：

• 功能需求（functional requirements）：它应该做什么，比如允许以各种方式存储，检索，搜索和处理数据。
• 非功能性需求（nonfunctional ）：安全性，可靠性，合规性，可扩展性，兼容性和可维护性、可测试性。

可靠性（Reliability） 意味着即使发生故障，系统也能正常工作。故障可能发生在硬件（通常是随机的和不相关的，例如网络抖动、内存故障、机房断电），软件（通常是系统性的 Bug，很难处理，例如无法处理特定输入、系统依赖组件出现故障），和人类（不可避免地时不时出错，系统中最不稳定的是人，比如编码错误）。 容错技术 可以对终端用户隐藏某些类型的故障。

可扩展性（Scalability） 意味着即使在负载增加的情况下也有保持性能的策略。为了讨论可扩展性，我们首先需要定量衡量负载和描述性能的方法。

衡量负载：

• 应用日活月活
• 每秒向 Web 服务器发出的请求
• 数据库中的读写比率
• 聊天室中同时活跃的用户数量
• ……

描述性能：

• 吞吐量
• 响应时间
• 延迟
• ……

应对负载：

• 纵向扩展（scaling up）或 垂直扩展（vertical scaling）：换具有更强大性能的机器。这种方法的优点是简单易行，不需要修改代码或架构，也不会增加网络开销或数据一致性问题。缺点是成本高，性能有上限，可扩展性差，容错性低。
• 横向扩展（scaling out）或 水平扩展（horizontal scaling）：“并联”很多廉价机，分摊负载。这种方法的优点是成本低，性能无上限，可扩展性好，容错性高。缺点是复杂度高，需要修改代码或架构，可能会增加网络开销或数据一致性问题。

如果系统规模很小，尽量还是用性能好一点的机器，可以省去很多麻烦。否则的话，还是要进行横向扩展（可以上云，利用云的可扩展性）。

可维护性（Maintainability） 有许多方面，但实质上是关于工程师和运维团队的生活质量的。

从软件的整个生命周期来看，维护阶段绝对占大头。

但大部分人都喜欢挖坑，不喜欢填坑。因此有必要，在刚开就把坑开的足够好。有三个原则：

• 可维护性（Operability） 便于运维团队无痛接手。
• 简洁性（Simplicity） 便于新手开发平滑上手：这需要一个合理的抽象，并尽量消除各种复杂度。如，层次化抽象。
• 可演化性（Evolvability） 便于后面需求快速适配：避免耦合过紧，将代码绑定到某种实现上。也称为可扩展性（extensibility），可修改性（modifiability） 或可塑性（plasticity）。

数据模型与查询语言

在历史上，数据最开始被表示为一棵大树（层次数据模型），但是这不利于表示多对多的关系，所以发明了关系模型来解决这个问题。最近，开发人员发现一些应用程序也不适合采用关系模型。新的非关系型“NoSQL”数据存储在两个主要方向上存在分歧：

1. 文档数据库的应用场景是：数据通常是自我包含的，而且文档之间的关系非常稀少。
2. 图形数据库用于相反的场景：任意事物都可能与任何事物相关联。

这三种模型（文档，关系和图形）在今天都被广泛使用，并且在各自的领域都发挥很好。一个模型可以用另一个模型来模拟 — 例如，图数据可以在关系数据库中表示 — 但结果往往是糟糕的。这就是为什么我们有着针对不同目的的不同系统，而不是一个单一的万能解决方案。

文档数据库和图数据库有一个共同点，那就是它们通常不会为存储的数据强制一个模式，这可以使应用程序更容易适应不断变化的需求。但是应用程序很可能仍会假定数据具有一定的结构；这只是模式是明确的（写入时强制）还是隐含的（读取时处理）的问题。

每个数据模型都具有各自的查询语言或框架，我们讨论了几个例子：SQL，MapReduce，MongoDB 的聚合管道，Cypher，SPARQL 和 Datalog。我们也谈到了 CSS 和 XSL/XPath，它们不是数据库查询语言，而包含有趣的相似之处。

关系模型与文档模型

下图展示了如何使用关系模型来表示简历（一个 LinkedIn 简介）。

不过，对于一个像简历这样自包含文档的数据结构而言，JSON 表示是非常合适的。

文档型 vs 关系型：

	文档型	关系型
对应关系	数据有天然的一对多、树形嵌套关系，如简历。	通过外键 + Join 可以处理 多对一，多对多关系
代码简化	数据具有文档结构，则文档模型天然合适，用关系模型会使得建模繁琐、访问复杂。但不宜嵌套太深，因为只能手动指定访问路径，或者范围遍历	主键，索引，条件过滤
Join 支持	对 Join 支持的不太好	支持的还可以，但 Join 的实现会有很多难点
模式灵活性	弱 schema，支持动态增加字段	强 schema，修改 schema 代价很大
访问局部性	1. 一次性访问整个文档，较优 2. 只访问文档一部分，较差	分散在多个表中

数据查询语言

声明式（declarative）语言 vs 命令式（imperative）语言:

	声明式（declarative）语言	命令式（imperative）语言
概念	描述控制逻辑而非执行流程	描述命令的执行过程，用一系列语句来不断改变状态
举例	SQL、HTML、CSS、XSL	IMS、CODASYL、C/C++、Java、Python、RubyJS
抽象程度	高	低
解耦程度	与实现解耦。 可以持续优化查询引擎性能；	与实现耦合较深。
解析执行	词法分析 → 语法分析 → 语义分析 生成执行计划 → 执行计划优化	词法分析 → 语法分析 → 语义分析 中间代码生成 → 代码优化 → 目标代码生成
多核并行	声明式更具多核潜力，给了更多运行时优化空间	命令式由于指定了代码执行顺序，编译时优化空间较小。

对声明式语言和命令式语言各有优点，适用场景也不同。

很多现代编程语言都支持混合使用声明式和命令式的特性，以适应不同的需求和场景。例如，Python 支持列表推导（list comprehension）和生成器（generator）等声明式的特性；SQL 支持存储过程（stored procedure）和触发器（trigger）等命令式的特性。

图数据模型

多对多关系是不同数据模型之间具有区别性的重要特征。如果你的应用程序大多数的关系是一对多关系（树状结构化数据），或者大多数记录之间不存在关系，那么使用文档模型是合适的。

但是，要是多对多关系在你的数据中很常见呢？关系模型可以处理多对多关系的简单情况，但是随着数据之间的连接变得更加复杂，将数据建模为图形显得更加自然。

一个图由两种对象组成：顶点（vertices）（也称为节点（nodes） 或实体（entities）），和边（edges）（ 也称为关系（relationships）或弧 （arcs） ）。多种数据可以被建模为一个图形。典型的例子包括：

• 社交图谱：顶点是人，边指示哪些人彼此认识。
• 网络图谱： 顶点是网页，边缘表示指向其他页面的 HTML 链接。

Cypher 是属性图的声明式查询语言，为 Neo4j 图形数据库而发明。

示例（查找所有从美国移民到欧洲的人的 Cypher 查询）：

MATCH
    (person) -[:BORN_IN]->  () -[:WITHIN*0..]-> (us:Location {name:'United States'}),
    (person) -[:LIVES_IN]-> () -[:WITHIN*0..]-> (eu:Location {name:'Europe'})
RETURN person.name

代码解读：找到满足以下两个条件的所有顶点（称之为 person 顶点）：

1. person顶点拥有一条到某个顶点的BORN_IN出边。从那个顶点开始，沿着一系列WITHIN出边最终到达一个类型为Location，name属性为United States的顶点。
2. person顶点还拥有一条LIVES_IN出边。沿着这条边，可以通过一系列WITHIN出边最终到达一个类型为Location，name属性为Europe的顶点。

对于这样的Person顶点，返回其name属性。

存储与查询

一个数据库在最基础的层次上需要完成两件事情：

1. 当你把数据交给数据库时，它应当把数据存储起来；
2. 而后当你向数据库要数据时，它应当把数据返回给你。

查询类型主要分为两大类：

• OLTP（Online Transaction Processing ，联机事务处理）： 可以保证操作的事务性，通常需要用到传统的关系型数据库比如 MySQL，主要操作是增删改查（比如添加用户、用户之间转账）。OLTP 通常处理的数据量不会很大，因为数据量大了之后 OLTP 数据库的响应一般会非常慢。
• OLAP（Online Analytical Processing，联机分析处理）： 对数据做分析然后得出一些结果比如数据报表，主要操作是查询（比如生成网站的流量分析报告）。OLAP 处理的数据量往往很大，并且 OLAP 处理的数据对象是数据仓库（data warehouse）中的数据。

引擎类型	请求数量	数据量	瓶颈	存储格式	用户	场景举例	产品举例
OLTP	相对频繁，侧重在线交易	总体和单次查询都相对较小	Disk Seek	多用行存	比较普遍，一般应用用的比较多	银行交易	MySQL
OLAP	相对较少，侧重离线分析	总体和单次查询都相对巨大	Disk Bandwidth	列存逐渐流行	多为商业用户	商业分析	ClickHouse

其中，OLTP 侧，常用的存储引擎又有两种流派：

流派	主要特点	基本思想	代表
log-structured 流	只允许追加，所有修改都表现为文件的追加和文件整体增删	变随机写为顺序写	Bitcask、LevelDB、RocksDB、Cassandra、Lucene
update-in-place 流	以页（page）为粒度对磁盘数据进行修改	面向页、查找树	B 族树，所有主流关系型数据库和一些非关系型数据库

数据库的底层数据结构

哈希索引

一种基于哈希表的索引结构，在查询的时候只要正确匹配到索引列，就能在 O(1)的时间复杂度内查到记录。

SSTable 和 LSM-Tree

SSTable（Sorted Strings Table）是排序字符串表的简称，来源于 Google Bigtable 论文，被广泛应用于一些耳熟能详的存储引擎中，如 Bigtable、Cassandra、Hbase、RocksDB、LevelDB 等 key-value 型存储引擎。

SSTable 是一种有序的、不可变的、持久化的 key-value 数据结构，它将多个键值对存储在一个文件中，并提供一个索引来快速定位每个键的位置。

SSTable 适合于顺序写入，因为它是不可变的。每次写入操作都会生成一个新的 SSTable 文件，并与旧的文件合并。

相比较于哈希索引，SSTable 的优点有：

• SSTable 是一个稀疏索引（只对部分数据进行索引），因此占用的内存空间较小。SSTable 的索引通常只包含每个数据块的最小和最大键，以及数据块在文件中的偏移量。这样，只需要将索引载入内存，就可以在磁盘上高效地查找任意键。
• SSTable 是有序的，支持区间查询。

LSM-Tree (Log-structured merge-tree)主要由 MemTable、Immutable MemTable、SSTable 组成，其中 MemTable 和 Immutable MemTable 在内存中维护，SSTable 在磁盘维护。

MemTable 是一个有序的内存表，通常基于跳表或红黑树实现。当 MemTable 达到一定大小时，就会转换为 Immutable MemTable（不可变内存表）。 Immutable MemTable 的内容会被写入到磁盘上的 SSTable 中，这个过程称为 Minor Compaction。当每层 SSTable 超过一定大小，就会周期性的进行合并，这个过程称为 Major Compaction。Major Compaction 阶段回清除掉冗余的数据，防止浪费空间。由于 SSTable 都是有序的，可以使用归并排序进行高效合并。

Immutable Memtable 可以看作是只读的 MemTable，是将 MemTable 转为磁盘上的 SSTable 的一种中间状态，可以避免将 MemTable 中的内容序列化到磁盘中时会阻塞写操作。

SSTable 的有序性可以提高 LSM-Tree 的读取性能，也可以支持区间查询。MemTable 可以提高 LSM-Tree 的写入性能，因为它可以将写入操作先缓存在内存中，然后批量地写入到磁盘上。

如果想让一个引擎工程上可用，还会做大量的性能优化。对于 LSM-Tree 来说，包括：

• 优化 SSTable 的查找。常用Bloom Filter。该数据结构可以使用较少的内存为每个 SSTable 做一些指纹，起到一些初筛的作用。
• 层级化组织 SSTable。以控制 Compaction 的顺序和时间。常见的有 size-tiered 和 leveled compaction。LevelDB 便是支持后者而得名。前者比较简单粗暴，后者性能更好，也因此更为常见。

对于 RocksDB 来说，工程上的优化和使用上的优化就更多了。在其 Wiki 上随便摘录几点：

1. Column Family
2. 前缀压缩和过滤
3. 键值分离，BlobDB

但无论有多少变种和优化，LSM-Tree 的核心思想——保存一组合理组织、后台合并的 SSTables ——简约而强大。可以方便的进行范围遍历，可以变大量随机为少量顺序。

B 族树

几乎所有的关系型数据中，B 树都是数据索引标准一般的实现。

与 LSM-Tree 一样，它也支持高效的点查和范围查。但却使用了完全不同的组织方式。

其特点有：

1. 以页（在磁盘上叫 page，在内存中叫 block，通常为 4k）为单位进行组织。
2. 页之间以页 ID 来进行逻辑引用，从而组织成一颗磁盘上的树。

B-Trees vs LSM-Trees:

存储引擎	B-Tree	LSM-Tree	备注
优势	读取更快	写入更快
写放大	1. 数据和 WAL 2. 更改数据时多次覆盖整个 Page	1. 数据和 WAL 2. Compaction	SSD 不能过多擦除。因此 SSD 内部的固件中也多用日志结构来减少随机小写。
写吞吐	相对较低： 1. 大量随机写。	相对较高： 1. 较低的写放大（取决于数据和配置） 2. 顺序写入。 3. 更为紧凑。
压缩率	1. 存在较多内部碎片。	1. 更加紧凑，没有内部碎片。 2. 压缩潜力更大（共享前缀）。	但紧缩不及时会造成 LSM-Tree 存在很多垃圾
后台流量	1. 更稳定可预测，不会受后台 compaction 突发流量影响。	1. 写吞吐过高，compaction 跟不上，会进一步加重读放大。 2. 由于外存总带宽有限，compaction 会影响读写吞吐。 3. 随着数据越来越多，compaction 对正常写影响越来越大。	RocksDB 写入太过快会引起 write stall，即限制写入，以期尽快 compaction 将数据下沉。
存储放大	1. 有些 Page 没有用满	1. 同一个 Key 存多遍
并发控制	1. 同一个 Key 只存在一个地方 2. 树结构容易加范围锁。	同一个 Key 会存多遍，一般使用 MVCC 进行控制。

其他索引结构

• 聚集索引和非聚集索引（cluster indexes and non-cluster indexes）
• 多列索引（Multi-column indexes）
• 全文索引和模糊索引（Full-text search and fuzzy indexes）

列存储

由于传统数据库通常是按行存储的，这意味着对于属性（列）很多的表，哪怕只查询一个属性，也必须从磁盘上取出很多属性，无疑浪费了 IO 带宽、增大了读放大。

于是一个很自然的想法呼之欲出：每一个列分开存储好不好？

将所有数据分列存储在一块，带来了一个意外的好处，由于同一属性的数据相似度高，因此更易压缩。

数仓的超大规模数据量带来了以下瓶颈：

1. 内存处理带宽
2. CPU 分支预测错误和流水线停顿

关于内存的瓶颈可已通过前述的数据压缩来缓解。对于 CPU 的瓶颈可以使用：

1. 列式存储和压缩可以让数据尽可能多地缓存在 L1 中，结合位图存储进行快速处理。
2. 使用 SIMD 用更少的时钟周期处理更多的数据。

由于数仓查询多集中于聚合算子（比如 sum，avg，min，max），列式存储中的存储顺序相对不重要。但也免不了需要对某些列利用条件进行筛选，为此我们可以如 LSM-Tree 一样，对所有行按某一列进行排序后存储。

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

同时，排序后的那一列，压缩效果会更好。

编码与演进

应用程序不可避免地随时间而变化。在大多数情况下，修改应用程序的功能也意味着需要更改其存储的数据：可能需要使用新的字段或记录类型，或者以新方式展示现有数据。

在大型应用程序中，代码变更通常不会立即完成：

• 对于服务端（server-side）应用程序，可能需要执行滚动升级 （rolling upgrade）（也称为阶段发布（staged rollout）），一次将新版本部署到少数几个节点，检查新版本是否运行正常，然后逐渐部完所有的节点。这样无需中断服务即可部署新版本，为频繁发布提供了可行性，从而带来更好的可演化性。
• 对于**客户端（client-side）**应用程序，升不升级就要看用户的心情了。用户可能相当长一段时间里都不会去升级软件。

这意味着，新旧版本的代码以及新旧数据格式可能会在系统中同时共处。系统想要继续顺利运行，就需要保持双向兼容性：

• 向后兼容 (backward compatibility)： 新代码可以读旧数据。
• 向前兼容 (forward compatibility)： 旧代码可以读新数据。

通常，向后兼容性通常并不难实现。最简单的办法就是保留旧代码即可读取旧数据。

向前兼容性可能会更棘手，因为旧版的程序需要忽略新版数据格式中新增的部分。

数据编码格式

程序通常（至少）使用两种形式的数据：

1. 在内存中，数据保存在对象，结构体，列表，数组，哈希表，树等中。 这些数据结构针对 CPU 的高效访问和操作进行了优化（通常使用指针）。
2. 如果要将数据写入文件，或通过网络发送，则必须将其**编码（encode）**为某种自包含的字节序列（例如 JSON 文档）。 由于每个进程都有自己独立的地址空间，一个进程中的指针对任何其他进程都没有意义，所以这个字节序列表示会与通常在内存中使用的数据结构完全不同。

因此， 在这两种表示之间需要进行类型的转化。从内存中的表示到字节序列的转化称为 编码(也称为序列化) ，相反的过程称为 解码(也称为反序列化) 。

许多编程语言都内建了将内存对象编码为字节序列的支持。例如，Java 有java.io.Serializable ，Ruby 有Marshal，Python 有pickle等等。许多第三方库也存在，例如Kryo for Java 。

这些编码库非常方便，可以用很少的额外代码实现内存对象的保存与恢复。但是它们也有一些深层次的问题：

• 编程语言强关联: 与特性的编程语言深度绑定，换个语言就不行了。
• 安全问题：为了恢复相同对象类型的数据，解码过程需要实例化任意类的能力，这通常是安全问题的一个来源。如果攻击者可以让应用程序解码任意的字节序列，他们就能实例化任意的类，这会允许他们做可怕的事情，如远程执行任意代码。
• 向前向后兼容问题：在这些库中，数据版本控制通常是事后才考虑的。因为它们旨在快速简便地对数据进行编码，所以往往忽略了前向后向兼容性带来的麻烦问题。
• 效率问题： 这些库通常是不在乎效率的，例如，Java 的内置序列化由于其糟糕的性能和臃肿的编码而臭名昭着。

JSON，XML 和 CSV 是文本格式，因此具有人类可读性。虽然他们都有一些缺点，不过，仍然很受欢迎。

JSON 比 XML 简洁，但与二进制格式一比，还是太占地方。这一事实导致大量二进制编码版本 JSON & XML 的出现，JSON（MessagePack，BSON，BJSON，UBJSON，BISON 和 Smile 等）（例如 WBXML 和 Fast Infoset）。这些格式已经被各种各样的领域所采用，但是没有一个像 JSON 和 XML 的文本版本那样被广泛采用。

Apache Thrift 和 Protocol Buffers（protobuf）是基于相同原理的二进制编码库。 Protocol Buffers 最初是在 Google 开发的，Thrift 最初是在 Facebook 开发的，并且在 2007~2008 年都是开源的。

Apache Avro 是另一种二进制编码格式，与 Protocol Buffers 和 Thrift 有趣的不同。 它是作为 Hadoop 的一个子项目在 2009 年开始的，因为 Thrift 不适合 Hadoop 的用例。

数据流的类型

• 数据库中的数据流：在数据库中，写入数据库的过程对数据进行编码，从数据库读取的过程对数据进行解码。向后兼容性显然是必要的。否则你未来的自己将无法解码你以前写的东西。
• 服务中的数据流(REST 与 RPC)：对于需要通过网络进行通信的进程 ， 有多种不同的通信方式。最常见的是有两个角色:客户端和服务器。服务器通过网络公开 API，客户端可以连接到服务器以向该 API 发出请求。 服务器公开的 API 称为服务。当服务使用 HTTP 作为底层通信协议时，可称之为 Web 服务。有两种流行的 Web 服务方法：REST 和 SOAP。
• 消息传递中的数据流: 与 RPC 相比，差异在于消息传递通信通常是单向的：发送者通常不期望收到其消息的回复。一个进程可能发送一个响应，但这通常是在一个单独的通道上完成的。这种通信模式是异步的：发送者不会等待消息被传递，而只是发送它，然后忘记它。

小节

在本章中，我们研究了将数据结构转换为网络中的字节或磁盘上的字节的几种方法。我们看到了这些编码的细节不仅影响其效率，更重要的是应用程序的体系结构和部署它们的选项。

特别是，许多服务需要支持滚动升级，其中新版本的服务逐步部署到少数节点，而不是同时部署到所有节点。滚动升级允许在不停机的情况下发布新版本的服务（从而鼓励在罕见的大型版本上频繁发布小型版本），并使部署风险降低（允许在影响大量用户之前检测并回滚有故障的版本）。这些属性对于可演化性，以及对应用程序进行更改的容易性都是非常有利的。

在滚动升级期间，或出于各种其他原因，我们必须假设不同的节点正在运行我们的应用程序代码的不同版本。因此，在系统周围流动的所有数据都是以提供向后兼容性（新代码可以读取旧数据）和向前兼容性（旧代码可以读取新数据）的方式进行编码是重要的。

我们讨论了几种数据编码格式及其兼容性属性：

• 编程语言特定的编码仅限于单一编程语言，并且往往无法提供前向和后向兼容性。
• JSON，XML 和 CSV 等文本格式非常普遍，其兼容性取决于您如何使用它们。他们有可选的模式语言，这有时是有用的，有时是一个障碍。这些格式对于数据类型有些模糊，所以你必须小心数字和二进制字符串。
• 像 Thrift，Protocol Buffers 和 Avro 这样的二进制模式驱动格式允许使用清晰定义的前向和后向兼容性语义进行紧凑，高效的编码。这些模式可以用于静态类型语言的文档和代码生成。但是，他们有一个缺点，就是在数据可读之前需要对数据进行解码。

我们还讨论了数据流的几种模式，说明了数据编码是重要的不同场景：

• 数据库，写入数据库的进程对数据进行编码，并从数据库读取进程对其进行解码
• RPC 和 REST API，客户端对请求进行编码，服务器对请求进行解码并对响应进行编码，客户端最终对响应进行解码
• 异步消息传递（使用消息代理或参与者），其中节点之间通过发送消息进行通信，消息由发送者编码并由接收者解码

我们可以小心地得出这样的结论：前向兼容性和滚动升级在某种程度上是可以实现的。愿您的应用程序的演变迅速、敏捷部署。

分布式数据库

数据复制

复制 的目的是通过互联网络在多台机器上保存相同的数据副本。

复制的原因可能是下面几个：

• 提高访问速度：使数据在地理位置上更接近用户，从而降低访问延迟 （CDN）。
• 提高可用性：当部分组件出现位障，系统依然可以继续工作，从而提高可用性（集群）。
• 提高吞吐量：扩展至多台机器以同时提供数据访问服务，从而提高读吞吐量（集群）。

复制 的挑战在于处理持续有改动的数据，而不在于处理不会改动的数据。

目前的话，通常有三种比较流行的复制数据变化的方法：

• 主从复制
• 多主点复制
• 无主节点复制

主从复制

所有的客户端写入操作都发送到某一个节点(主节点)，由该节点负责将数据更改事件发送到其他副本(从节点)。每个副本都可以接收读请求，但内容可能是过期值。

下面是具有主从复制功能的数据存储系统：

• 关系型，PostgresSQL, MySQL, Oracle Data Guard, SQL Server。
• 非关系型，MongoDB， RethinkDB 和 Expresso。
• 分布式消息队列，Kafka，RabbitMQ

同步复制与异步复制

复制的方式有同步和异步两种，关键区别在于请求何时返回给客户端：

1. 如果等待某副本写完成后，则该副本为同步复制。
2. 如果不等待某副本写完成，则该副本为异步复制。

同步复制从节点数据同步的更快，万一主节点挂掉，从节点通常也有最新的数据（但并不能完全保证一致性）。不过，同步复制也存在阻塞问题，在某个从节点无法同步的情况下，写操作往往会被阻塞直到从节点同步完成。相对应的，异步复制放弃了严格的一致性，而换来了较低的写入延迟。

同步复制与异步复制各有优劣。在实践中，会根据对一致性和可用性的要求，进行取舍。针对所有从节点来说，可以有以下选择：

1. 全同步：所有的从节点都同步写入。如果副本数过多，可能性能较差，当然也可以做并行化、流水线化处理。
2. 半同步：（semi-synchronous），有一些副本为同步，另一些副本为异步。
3. 全异步：所有的从节点都异步写入。网络环境比较好的话，可以这么配置。

新增从节点

一般情况下，我们会给主节点配置多个从节点。试想一下，如果我们需要增加新的从节点的话，主节点的数据该怎么同步到从节点呢？

1. 将主节点某个时间点的数据副本的一致性快照拷贝到新的从节点 。
2. 从节点向主节点请求快照点之后所发生的数据变更日志。这个更改日志在不同的数据库系统有不同的称呼，如 PostgreSQL 将其称为“ log sequence number” (日志序列 号)，而 MySQL 将其称为“binlog coordinates” 。
3. 从节点利用数据变更日志来追赶主节点。

处理节点失效

从节点失效：追赶式恢复

从节点恢复之后向主节点请求失效期间的所有数据变更，收到这些数据变更日志之后，将其应用到本地来追赶主节点。

主节点失效：节点切换

从节点中选择出一个与主节点数据差异最小的作为主节点。

具体来说，包含下面步骤：

1. 确认主节点故障。要防止由于网络抖动造成的误判。一般会用心跳探活，并设置合理超时（timeout）阈值，超过阈值后没有收到该节点心跳，则认为该节点故障。
2. 选择新的主节点。新的主节点可以通过选举（共识问题）或者指定（外部控制程序）来产生。选主时，要保证备选节点数据尽可能的新，以最小化数据损失。
3. 让系统感知新主节点。系统其他参与方，包括从节点、客户端和旧主节点。前两者不多说，旧主节点在恢复时，需要通过某种手段，让其知道已经失去领导权，避免脑裂。

主节点切换时，会遇到很多问题需要解决，比如新老主节点数据冲突（新主节点在上位前没有同步完所有日志，旧主节点恢复后，可能会发现和新主节点数据冲突）、新老主节点角色冲突（脑裂现象）。

复制日志的实现

常见的实现方式有下面几种：

1. 基于语句的复制
2. 基于预写日志( WAL) 传输
3. 基于行的逻辑日志复制

基于语句的复制

主节点记录所执行的每个写请求(更新语句，INSERT、UPDATE 或 DELETE)井将该更新语句作为日志发送给从节点。不过，这种方式在一些情况下并不适用，比如 SQL 语句中有 NOW() 获取当前时间或RAND() 获取一个随机数。

MySQL 5.1 版本之前采用基于操作语句的复制 。现在依然在用，但是默认情况下，如果语句中存在一些不确定性操作， MySQL 会切换到基于行的复制。

基于预写日志(WAL) 传输

预写日志（Write-ahead logging，缩写 WAL）的核心思想是对数据文件的修改必须且只能发生在这些修改已经记录到日志文件之后。

WAL 可以解决宕机和恢复的问题：

• 写 WAL 前宕机了，重启后，数据处于事务未执行的状态。
• 写 WAL 时宕机了，重启后，可以检查到 WAL 数据不正确，回滚当事务前的状态。
• 写 WAL 后宕机了，重启后，把 WAL 中记录的操作，应用到数据库文件中，得到事务执行后的状态。

主流的存储引擎几乎都有 WAL：

1. 对于日志流派（LSM-Tree，如 LevelDB），每次修改先写入 log 文件，防止写入 MemTable 中的数据丢失。
2. 对于原地更新流派（B+ Tree），每次修改先写入 WAL，以进行崩溃恢复。

WAL 除了可以解决宕机和恢复的问题，还具备提高写数据的性能、并发读写等优点。WAL 主要缺点是兼容性差！因为 WAL 描述的数据结构非常底层，与存储引擎紧密耦合。如果数据库的存储格式从一个版本改为另一个版本，那么系统通常无能支持主从节点上运行不同版本的软件。

基于行的逻辑日志复制

复制和存储引擎采用不同的日志格式，这样复制与存储逻辑剥离。这种复制日志称为 逻辑日志 ，以区分物理存储引擎的数据表示。

这种复制日志的实现方式的优势在于逻辑日志与存储引擎逻辑解耦，因此可以更容易地保持向后兼容，从而使主从节点能够运行不同版本的软件甚至是不同的存储引擎。

MySQL 的二进制日志 binlog (当配置为基于行的复制时) 使用该方式。对于外部应用程序来说，逻辑日志格式也更容易解析。如果要将数据库的内容发送到外部系统(如用于离线分析的数据仓库)，或构建自定义索引和缓存等，基于逻辑日志的复制更有优势。

补充 ：MySQL 支持两种复制方式：基于行的复制和基于语句的复制(逻辑复制)。没有哪种模式对所有情况都是完美的，MySQL 能够在这两种复制模式间动态切换。默认情况下使用的是基于语句的复制方式，但如果发现语句无法被正确地复制，就切换到基于行的复制模式。

复制滞后问题

复制滞后是指在多副本的数据系统中，不同副本之间的数据可能存在不一致的情况，因为数据的更新需要一定的时间在网络中传播。

读自己的写

用户在写入不久即查看数据 ， 则新数据可能尚未到达从节点。对用户来讲， 看起来似乎是刚刚提交的数据丢失了。

解决办法：如果用户访问可能会被修改的内容，从主节点读取 ; 否则 ，在从节点读取。这里需要加限制条件比如最近 1 分钟更新的数据，不然可能会导致大量的读请求到主节点。

单调读

用户从不同副本进行了多次读取，读取到的数据不一样（从节点同步主节点数据的进度不一样）。

单调读一致性可以确保不会发生这种异常。只需要确保用户总是从同一个从节点读取数据即可。例如，基于用户 ID 的哈希而不是随机选择副本。

前缀一致读

如果数据库总是以相同的顺序写入，则读取总是看到一致的序列，不会发生这种反常。然而， 在许多分布式数据库中，不同的分区独立运行，因此不存在全局写入顺序。这就导致 当用户从数据库中读数据时，可能会看到数据库的某部分旧值和另 一部分新值。

一个解决方案是确保任何具有因果顺序关系的写人都交给一个分区来完成，但这种方案真实实现效率会大打折扣 。

多主节点复制

单一主节点的情况下，如果主节点出现问题，则会在一定时间内影响写入操作。

多主节点可以解决这个问题。

多主节点复制模式下，系统存在多个主节点，每个都可以接收写请求，客户端将写请求发送到其中的一个 主节点上，由该主节点负责将数据更改事件同步到其他主节点和自己的从节点。

适用场景

多数据中心

每个数据中心内，采用常规的主从复制方案。而在数据中心之间，由各个数据中心的主节点来负责同其他数据中心的主节点进行数据的交换、更新。

离线客户端操作

应用在与网络断开后还需要继续工作的场景也比较适合多主节点复制。

在离线状态下进行的任何更改，会在下次设备上线时，与服务器以及其他设备同步。每个设备都相当于一个主节点，都可以用来接收写请求。比如手机，笔记本电脑和其他设备上的备忘录。

协作编辑

Google Docs 等类似 SaaS 模式的在线协同应用越来越流行。

这种应用允许多人在线同时编辑文档或者电子表格，其背后的原理，与上一节离线工作的客户端很像。

为了实现协同，并解决冲突，可以：

1. 悲观方式。加锁以避免冲突，但粒度需要尽可能小，否则无法允许多人同时编辑一个文档。
2. 乐观方式。允许每个用户无脑写入，然后如果有冲突，交由用户解决。

处理写冲突

多主复制的最大问题是可能发生写冲突， 这意味着必须有方案来解决冲突。

冲突避免

如果应用层可以保证对特定记录的写请求总是通过同一 个主节点，这样就不会发生写冲突。

冲突收敛

如果一个字段有多个更新，则最后一 个写操作将决定该字段的最终值。

实现收敛的冲突解决有以下可能的方式 :

• 给每个写入分配唯 一 的 ID 比如时间戳，时间戳最大的写入成功。虽然这种方法很流行 ，但是很容易造成数据丢失（后面会聊到）。
• 利用预定义好的格式来记录和保留冲突相关的所有信息，然后依靠应用层的逻辑，事后解决冲突 (可能会提示用户)
• ……

无主节点复制

客户端将写请求发送到多个节点上，读取时从多个节点上并行读取，以此检测和纠正某些过期数据。

有节点故障时的写入

基于主副本（leader-based）的模型，在有副本故障时，需要进行故障切换。但在无主模型中，简单忽略它就行。

读修复与反熵

复制模型应确保所有数据最终复制到所有的副本 。当一个失效的节点重新上线之后， 它如何赶上中间错过的那些写请求呢?

• 读修复： 当客户端井行读取多个副本时，可以检测到过期的返回值（以多数副本中读取到的数据为准）。
• 反熵： 一些数据存储有后台进程不断查找副本之间数据的差异，将任何缺少的数据从一个副本复制到另 一个副本。和基于主节点复制的复制日志不同，此反熵过程并不保证以特定的顺序复制写入，并且会引入明显的同步滞后。

检测并发写

多个客户端对相同的主键同时发起写操作可能会发生写冲突。

小节

上面介绍的三种复制方案都有其优点和缺点。主从复制非常流行，主要是因为它很容易理解，也不需要担心冲突问题。而万一出现节点失效、网络中断或者延迟抖动等情况，多主节点和 无主节点复制方案会更加可靠，不过背后的代价则是系统的复杂性和弱 一致性。

复制可以是同步的，也可以是异步的，而一旦发生故障， 二者的表现差异会对系统行 为产生深远的影响。在系统稳定状态下异步复制性能优秀，但仍须认真考虑一旦出现 复制滞后和节点失效两种场景会导致何种影响。万一某个主节点发生故障，而一个异 步更新的从节点被提升为新的主节点，要意识到最新确认的数据可能有丢失的风险。

数据分区

何为分区？

简单来说就是将一个数据量很大的数据库分解为多个数据量比较小的数据库。 分区主要是为了可扩展性。

分区通常与复制结合使用，使得每个分区的副本存储在多个节点上。 这意味着，即使每条记录属于一个分区，它仍然可以存储在多个不同的节点上以获得容错能力。

为什么要分区？

分区目标是 将数据和查询负载均匀分布在各个节点上 。如果每个节点公平分享数据和负载，那么理论上 10 个节点应该能够处理 10 倍的数据量和 10 倍的单个节点的读写吞吐量（暂时忽略复制）。

偏斜和热点？

如果分区是不公平的，一些分区比其他分区有更多的数据或查询，我们称之为偏斜（skew）。数据偏斜的存在使分区效率下降很多。在极端的情况下，所有的负载可能压在一个分区上，其余 9 个节点空闲的，瓶颈落在这一个繁忙的节点上。不均衡导致的高负载的分区被称为热点（hot spot）。

有哪些分区的方式？

• 根据键的范围分区：每个分区指定一块连续的键范围（从最小值到最大值）。这种方式的优势是范围扫描非常简单，缺点是可能会导致偏斜和热点。
• 根据键的散列分区： 由于偏斜和热点的风险，许多分布式数据存储使用散列函数来确定给定键的分区。 一个好的散列函数可以将将偏斜的数据均匀分布。这种方式的缺点是范围查询效率低下。

分区再平衡 ：

随着时间的推移，数据库会有各种变化。

• 查询吞吐量增加，所以您想要添加更多的 CPU 来处理负载。
• 数据集大小增加，所以您想添加更多的磁盘和 RAM 来存储它。
• 机器出现故障，其他机器需要接管故障机器的责任。

所有这些更改都需要数据和请求从一个节点移动到另一个节点。 将负载从集群中的一个节点向另一个节点移动的过程称为再平衡（reblancing）。

有哪些平衡策略？

一定要避免重新对数据进行哈希，这样的耗费成本太大！我们需要的是一种只移动必需数据的方法。

• 固定数量的分区：创建比节点更多的分区，并为每个节点分配多个分区。如果一个节点被添加到集群中，新节点可以从当前每个节点中窃取一些分区，直到分区再次公平分配。如果从集群中删除一个节点，则会发生相反的情况。
• 动态分区： 对于使用键范围分区的数据库（如 HBase 和 RethinkDB），具有固定边界的固定数量的分区将非常不便：如果出现边界错误，则可能会导致一个分区中的所有数据或者其他分区中的所有数据为空。手动重新配置分区边界将非常繁琐。这种情况下动态分区比较好！当分区增长到超过配置的大小时（在 HBase 上，默认值是 10GB），会被分成两个分区，每个分区约占一半的数据。 动态分区的一个优点是分区数量适应总数据量。如果只有少量的数据，少量的分区就足够了，所以开销很小;如果有大量的数据，每个分区的大小被限制在一个可配置的最大值。动态分区不仅适用于数据的范围分区，而且也适用于散列分区。从版本 2.4 开始，MongoDB 同时支持范围和哈希分区，并且都是进行动态分割分区。
• 按节点比例分区：使分区数与节点数成正比——换句话说，每个节点具有固定数量的分区。在这种情况下，每个分区的大小与数据集大小成比例地增长，而节点数量保持不变。但是，当增加节点数时，分区则会调整变得更小。由于较大的数据量通常需要较大数量的节点进行存储，因此这种方法也使每个分区的大小较为稳定。像 Cassandra 和 Ketama 就是使用这种平衡策略。

当客户想要发出请求时，如何知道要连接哪个节点？ 随着分区重新平衡，分区对节点的分配也发生变化。

这个问题可以概括为 服务发现(service discovery) ，它不仅限于数据库。任何可通过网络访问的软件都有这个问题，特别是如果它的目标是高可用性（在多台机器上运行冗余配置）。

常见的方案有：

• 允许客户联系任何节点（例如，通过循环策略的负载均衡（Round-Robin Load Balancer））。如果该节点恰巧拥有请求的分区，则它可以直接处理该请求;否则，它将请求转发到适当的节点，接收回复并传递给客户端。
• 首先将所有来自客户端的请求发送到路由层，它决定了应该处理请求的节点，并相应地转发。此路由层本身不处理任何请求；它仅负责分区的负载均衡。
• 要求客户端知道分区和节点的分配。在这种情况下，客户端可以直接连接到适当的节点，而不需要任何中介。

许多分布式数据系统都依赖于一个独立的协调服务，比如 ZooKeeper 来跟踪集群元数据。 每个节点在 ZooKeeper 中注册自己，ZooKeeper 维护分区到节点的可靠映射。

事务

事务定义

事务是应用程序将多个读写操作组合成一个逻辑单元的一种方式。从概念上讲，事务中的所有读写操作被视作单个操作来执行：整个事务要么成功（提交（commit））要么失败（中止（abort），回滚（rollback））。

如果没有事务，各种错误情况(如进程崩横、网络中断、停电、磁盘已楠、并发竞争等)会导致数据 可能出现各种不 一致。

事务所提供的安全保证，通常由众所周知的首字母缩略词 ACID 来描述，ACID 代表：

• 原子性（Atomicity）： ACID 中的原子性描述了，当客户想进行多次写入，但在一些写操作处理完之后出现故障的情况。例如进程崩溃，网络连接中断，磁盘变满或者某种完整性约束被违反。如果这些写操作被分组到一个原子事务中，并且该事务由于错误而不能完成（提交），则该事务将被中止，并且数据库必须丢弃或撤消该事务中迄今为止所做的任何写入。在不同的场景原子性可能会有不同的含义，比如在在多线程编程中，如果一个线程执行一个原子操作，这意味着另一个线程无法看到该操作的一半结果。
• 一致性（Consistency）：原子性，隔离性和持久性是数据库的属性，而一致性（在 ACID 意义上）是应用程序的属性。应用可能依赖数据库的原子性和隔离属性来实现一致性，但这并不仅取决于数据库。因此，字母 C 不属于 ACID。
• 隔离性（Isolation）：ACID 中的隔离性意味着，同时执行的事务是相互隔离的：它们不能相互冒犯。违反隔离性：一个事务读取另一个事务的未被执行的写入（“脏读”）。
• 持久性（Durability）：持久性是一个承诺，即一旦事务成功完成，即使发生硬件故障或数据库崩溃，写入的任何数据也不会丢失。

弱隔离级别

实现隔离绝不是想象的那么简单。可串行化的隔离会严重影响性能，而许多数据库却不愿意牺牲性能 ，因而更多倾向于采用较弱的隔离级别，它可以防止某些但并非全部的并发问题。

读已提交

最基本的事务隔离级别是读已提交（Read Committed）v，它提供了两个保证：

1. 从数据库读时，只能看到已提交的数据（没有脏读（dirty reads））。
2. 写入数据库时，只会覆盖已经写入的数据（没有脏写（dirty writes））。

一个事务已经将一些数据写入数据库，但事务还没有提交或中止。另一个事务可以看到未提交的数据吗？如果是的话，那就叫做脏读（dirty reads） 。

如果两个事务同时尝试更新数据库中的相同对象，会发生什么情况？我们不知道写入的顺序是怎样的，但是我们通常认为后面的写入会覆盖前面的写入。

但是，如果先前的写入是尚未提交事务的一部分，是否还是被覆盖？如果是，那就是 脏写（dirty write） 。

在读已提交的隔离级别上运行的事务必须防止脏写，通常是延迟第二次写入，直到第一次写入事务提交或中止为止。

读已提交是一个非常流行的隔离级别。这是 Oracle 11g，PostgreSQL，SQL Server 2012，MemSQL 和其他许多数据库的默认设置

如何实现呢？

最常见的情况是，数据库通过使用行锁（row-level lock） 来防止脏写。使用锁的方式也能防止脏读，不过不太建议这样做。大多数数据库都会这样做：对于写入的每个对象，数据库都会记住旧的已提交值，和由当前持有写入锁的事务设置的新值。 当事务正在进行时，任何其他读取对象的事务都会拿到旧值。 只有当新值提交后，事务才会切换到读取新值。

快照级别隔离与可重复读

不可重复读也叫读取偏差。

快照隔离（snapshot isolation） 是这个问题最常见的解决方案。想法是，每个事务都从数据库的一致快照（consistent snapshot） 中读取——也就是说，事务可以看到事务开始时在数据库中提交的所有数据。即使这些数据随后被另一个事务更改，每个事务也只能看到该特定时间点的旧数据。

以下内容摘自维基百科对快照隔离的介绍：

很多重要的数据库管理系统已经采用了快照隔离，如 InterBase, Firebird, Oracle, MySQL, PostgreSQL, SQL Anywhere, MongoDB 与 Microsoft SQL Server (从 2005)。原因是快照隔离比可串行性隔离级别的性能更好，且能避免绝大多数并发异常。快照隔离一般用多版本并发控制(MVCC)实现。 快照隔离避免了 ISO SQL-92 所列举的并发异常现象，但不是 SQL-92 定义的无并发异常的可串行化。

为了实现快照隔离，数据库必须可能保留一个对象的几个不同的提交版本，因为各种正在进行的事务可能需要看到数据库在不同的时间点的状态。因为它并排维护着多个版本的对象，所以这种技术被称为多版本并发控制（MVCC, multi-version concurrentcy control）。

下图说明了 PostgreSQL 如何实现基于 MVCC 的快照级别隔离 (其他实现基本类 似)。当事务开始时， 首先赋予一个唯一的、单调递增的事务 ID (txid)。每当事 务向数据库写入新内容时，所写的数据都会被标记写入者的 事务 ID。

快照级别隔离对于只读事务特别有效。但是，具体到实现，许多数据库却对它有着不 同的命名。 Oracle 称之为可串行化， PostgreSQL 和 MySQL 则称为可重复读。

防止更新丢失

许多数据库提供了原子更新操作，原子操作通常采用对读取对象加独占锁的方式来实现，这样在更新被提交之前不会其 事务可以读它。

如果数据库不支持内置原子操作，另一种防止更新丢失的方法是由应用程序显式锁定待更新的对象。

原子操作和锁都是通过强制“读-修改-写回”操作序列串行执行来防止丢失更新。另 一种思路则是先让他们并发执行，但如果事务管理器检测到了更新丢失风险，则会中止当前事务，并强制回退到安全的“读-修改-写回”方式。

该方法的一 个优点是数据库完全可以借助快照级别隔离来高效地执行检查。的确， PostgreSQL 的可重复读， Oracle 的可串行化以及 SQL Server 的快照级别隔离等，都可以自动检测何时发生了更新丢失，然后会中止违规的那个事务。但是， MySQL/ InnoDB 的可重复读却并不支持检测更新丢失。有些观点认为数据库必须防止更新丢失，要不然就不能宣称符合快照级别隔离。如果基于这样的定义，那么 MySQL 就属于没有完全支持快照级别隔离。

写倾斜与幻读

当多个事务同时写入同一对象时引发了两种竞争条件，即前面章节所讨论的脏写和更新丢失。为了避免数据不一致，需要借助数据库的一些内置机制，或者采取手动加 锁、执行原子操作等。

试想这样一种情况：当前有 3 名医生，医院规定至少 2 名医生值班。其中的 2 个医生通过程序同时请假，他们同时点了请假按钮。每笔事务总是首先检查是否至少有 3 名医生目前在值班。如果是的话，则可以请假成功。由于数据库正在使用快照级别隔离，两个检查都返回有 3 名医生在值班， 所以 2 个事务都安全地进入到下一个阶段。他俩都顺利请假成功，这个是不允许的！

再比如两个用户同时创建相同的用户名成功，但是系统是不允许存在相同用户名的用户的。

这种异常情况称为 写倾斜。它既不是一 种脏写，也不是更新丢失，两笔事务更新的是两个不同的对象 。这里的写冲突并不那么直接，但很显然这的确是某种竞争状态 。试想：如果两笔事务是串行执行， 则第 2 个医生的申请肯定被拒绝;只有同时执行两个事务时才会引发该异常。

串行化

可串行化隔离通常被认为是最强的隔离级别。它保证即使事务可能会井行执行，但最终的结果与每次一个即串行执行结果相同。但是，由于各种原因，串行化隔离级别并没有被广泛使用。

目前大多数提供可串行化的数据库都使用了以下三种技术之一：

1. 严格按照串行顺序执行(参阅本章后面的“实际的串行执行”)。
2. 两阶段锁定(参阅本章后面的“两阶段加锁”)，几十年来这几乎是唯一可行的选择。
3. 乐观井发控制技术，例如可串行化的快照 隔离(参阅本章后面的“可串行化的快 照隔离”)。

近三十年来，可以说数据库只有一种被广泛使用的串行化算哉，那就是两阶段加锁。

两阶段加锁方怯类似，但锁的强制性更高。多个事务可以同时读取同 一对象，但只要出现任何写操作( 包括修改或删除)，则必须加锁以独占访问。

两阶段加锁虽然 可以保证串行化，但性能差强人意且无法扩展(由于串行执行)。

弱级别隔离虽然性 能不错，但容易引发各种边界条件( 如更新丢失， 写倾斜 ，幻读等)。那么，串行化 隔离与性能是不是从根本上就是互相冲突而无法兼得吗?

或许并非如此。一种称为可串行化的快照隔离( Serializable Snapshot Isolation, SSI) 算告看起来让人眼前一亮。它提 供了完整的可串行性保证，而性能相比于快照 隔离损失很小。

并发事务带来的问题及解决方案总结

个人之前的笔记 ：

在典型的应用程序中，多个事务并发运行，经常会操作相同的数据来完成各自的任务（多个用户对统一数据进行操作）。并发虽然是必须的，但可能会导致以下的问题。

• **脏读（Dirty read）😗*当一个事务正在访问数据并且对数据进行了修改，而这种修改还没有提交到数据库中，这时另外一个事务也访问了这个数据，然后使用了这个数据。因为这个数据是还没有提交的数据，那么另外一个事务读到的这个数据是“脏数据”，依据“脏数据”所做的操作可能是不正确的。
• **丢失修改（Lost to modify）😗*指在一个事务读取一个数据时，另外一个事务也访问了该数据，那么在第一个事务中修改了这个数据后，第二个事务也修改了这个数据。这样第一个事务内的修改结果就被丢失，因此称为丢失修改。 例如：事务 1 读取某表中的数据 A=20，事务 2 也读取 A=20，事务 1 修改 A=A-1，事务 2 也修改 A=A-1，最终结果 A=19，事务 1 的修改被丢失。
• **不可重复读（Unrepeatableread）😗*指在一个事务内多次读同一数据。在这个事务还没有结束时，另一个事务也访问该数据。那么，在第一个事务中的两次读数据之间，由于第二个事务的修改导致第一个事务两次读取的数据可能不太一样。这就发生了在一个事务内两次读到的数据是不一样的情况，因此称为不可重复读。
• **幻读（Phantom read）😗*幻读与不可重复读类似。它发生在一个事务（T1）读取了几行数据，接着另一个并发事务（T2）插入了一些数据时。在随后的查询中，第一个事务（T1）就会发现多了一些原本不存在的记录，就好像发生了幻觉一样，所以称为幻读。

书中内容整理 ：

• 脏读：客户端读到了其他客户端尚未提交的写人。读已提交以及更强的隔离级别可以防止脏读。
• 脏写：客户端覆盖了另一个客户端尚未提交的写入。几乎所有的数据库实现都可以防止脏写。
• 读倾斜(不可重复读)：客户在不同的时间点看到了不同值。快照隔离是最用的防范手段， 即事务总是在某个时间点的一致性快照中读取数据。通常采用多版本井发控制(MVCC )来实现快照隔离。
• 更新丢失：两个客户端同时执行读-修改-写入操作序列，出现了其中一个覆盖了另一个的写 入，但又没有包含对方最新值的情况，最终导致了部分修改数据发生了丢失。快照隔离的一些实现可以自动防止这种异常，而另 一 些则需要手动锁定查询结果(SELECT FOR UPDATE)。
• 写倾斜：事务首先查询数据，根据返回的结果而作出某些决定，然后修改数据库 。当事务提交时，支持决定的前提条件已不再成立。只有可串行化的隔离才能防止这种异常。
• 幻读：事务读取了某些符合查询条件的对象，同时另 一个客户端执行写入，改变了先前的查询结果。快照隔离可以防止简单的幻读，但写倾斜情况需要特殊处理，例如采用区间范围锁。

弱隔离级别可以防止上面的某些异常，但还需要应用开发人员手动处理其他复杂情况(例如，显式加锁) 。只有可串行化的隔离可以防止所有这些问题 。我们主要讨论了 实现可串行化隔离的三种不同方位:

• 严格串行执行事务：如果每个事务的执行速度非常快，且单个 CPU 核可以满足事务的吞吐量要求，严 格串行执行是一个非常简单有效的方案。
• 两阶段加锁：几十年来，这一直是实现可串行化的标准方式，但还是有很多系统出于性能原因 而放弃使用它。
• 可串行化的快照隔离 (SSI)：一种最新的算出， 可以避免前面方法的大部分缺点 。它秉持乐观预期的原则，允许多个事务并发执行而不互相阻塞;仅当事务尝试提交肘，才检查可能的冲突， 如果发现违背了串行化，则某些事务会被中止。

分布式系统的挑战

故障与部分失效

在单节点上开发程序时，通常它应该以一种确定性的方式运行: 要么工作，要么出错。

在分布式系统中，可能会出现系统的一部分工作正常，但其他某些部分出现难以预测 的故障，我们称之为“部分失效”。问题的难点就在于这种部分失效是不确定的:如果涉及多个节点和网络 ，几乎肯定会碰到有时网络正常，有时则莫名的失败。

为了容忍错误，第一步是 检测错误，但即使这样也很有挑战。多数系统没有检测节点是否发生故障的准确机制，因此， 分布式算法更多依靠超时来确定远程节点是否仍然可用 。但是，超时无法区分网络和节点故障 ，且可变的网络延迟有时会导致节点被误认为发生崩溃。

不可靠的网络

网络是跨节点通信的唯一途径，但是，一个节点可以发送消息(数据包)到另 一个节点不一定会成功，可能会遇到问题比如远程接收节点可能已经失效(例如崩溃或关机)。

网络分区 ：当网络的 一部分由于网络故障而与其他部分断开，称之为网络分区或网络分割 。 为避免与第 6 章存储系统 的分区(分片)产生棍 淆 ，本书采用更通用的术语“网络故障”。

不可靠的时钟

时钟和计时非常重要。有许多应用程序以各种方式依赖于时钟，例如 :

1. 某个请求是否超时了？
2. 某项服务的 99%的响应时间是多少？
3. 在过去的五分钟内 ，服务平均每秒处理多少个查询？
4. 用户在我们的网站上浏览花了多长时间?
5. 这篇文章什么时候发表？
6. ……

跨节点通信不可能即时完成 ：在分布式系统中， 时间总是件棘手的问题，由于跨节点通信不可能即时完成，消息经由网络从一台机器到另一台机器总是需要花费时间。收到消息的时间应该晚于发送的时间，但是由于网络的不确定延迟，精确测量面临着很多挑战。这些情况使得多节点 通信时很难确定事情发生的先后顺序。

并且，各个机器上通常都有自己的时钟硬件设备，这些设备并非绝对准确，即每台机器都维护自己本地的时间版本。想让各个机器之间的时间同步的话，可以采用 网络时间协议(Network Time Protocol, NTP)，它可以根据一组专门的时间服务器来调整本地时间。

进程暂停

在许多编程语言和操作系统中，线程和进程可能暂停一段无限制的时间比如 JVM 的垃圾回收就可能导致 stop-the-world 。

总结

网络、时钟和进程的不可靠性是否是不可避免的自然规律？

不是！的确有可能给网络提供硬实时的响应保证和有限的延迟，但是这样做非常昂贵，且导致硬件资源的利用率降低。大多数非安全关键系统会选择便宜而不可靠，而不是昂贵和可靠。

一致性和共识

布式系统最重要的抽象之一就是共识（consensus）：就是让所有的节点对某件事达成一致。

一旦达成共识，应用可以将其用于各种目的。例如，假设你有一个单主复制的数据库。如果主库挂点，并且需要故障切换到另一个节点，剩余的数据库节点可以使用共识来选举新的领导者。正如在“处理节点宕机”中所讨论的那样，重要的是只有一个领导者，且所有的节点都认同其领导。如果两个节点都认为自己是领导者，这种情况被称为脑裂（split brain），且经常导致数据丢失。正确实现共识有助于避免这种问题。

在最终一致的数据库，如果你在同一时刻问两个不同副本相同的问题，可能会得到两个不同的答案。如果数据库可以提供只有一个副本的假象（即，只有一个数据副本），那么事情就简单太多了。

线性一致性（linearizability） 的目标就是使多副本数据看起来好像只有一个副本一样，并使其上所有操作都原子性地生效。

虽然线性一致性因为简单易懂而很吸引人 —— 它使数据库表现的好像单线程程序中的一个变量一样，但它有着速度缓慢的缺点，特别是在网络延迟很大的环境中。

因果性对系统中的事件施加了顺序（什么发生在什么之前，基于因与果）。与线性一致不同，线性一致性将所有操作放在单一的全序时间线中，因果一致性为我们提供了一个较弱的一致性模型：某些事件可以是并发的，所以版本历史就像是一条不断分叉与合并的时间线。因果一致性没有线性一致性的协调开销，而且对网络问题的敏感性要低得多。

达成共识意味着以这样一种方式决定某件事：所有节点一致同意所做决定，且这一决定不可撤销。

有很多重要的场景都需要集群节点达成某种一致，例如 :

• 领导选举：在单主复制的数据库中，所有节点需要就哪个节点是领导者达成一致。如果一些节点由于网络故障而无法与其他节点通信，则可能会对领导权的归属引起争议。在这种情况下，共识对于避免错误的故障切换非常重要。错误的故障切换会导致两个节点都认为自己是领导者（脑裂，参阅“处理节点宕机”）。如果有两个领导者，它们都会接受写入，它们的数据会发生分歧，从而导致不一致和数据丢失。
• 原子事务提交：对于支持跨节点或跨分区事务的数据库，会面临这样的问题 : 某个事务可能在一 些节点上执行成功，但在其他节点却不幸发生了失败。为了维护事务的原子性(ACID)，所有节点必须对事务的结果达成一致:要么全部成功提交(假定没有出错)，要么中止回滚(如果出现了错误)。这也就是我们常说的分布式事务。XA 事务解决了保持多个参与者（数据系统）相互一致的现实的重要问题，但它也引入了严重的运维问题比如保证协调者高可用。并且，事务协调者本身就是一种数据库（存储了事务的结果），因此需要像其他重要数据库一样小心地打交道。

通过深入挖掘，结果我们发现很广泛的一系列问题实际上都可以归结为共识问题，并且彼此等价（从这个意义上来讲，如果你有其中之一的解决方案，就可以轻易将它转换为其他问题的解决方案）。这些等价的问题包括：

• 线性一致性的 CAS 寄存器： 寄存器需要基于当前值是否等于操作给出的参数，原子地决定是否设置新值。
• 原子事务提交： 数据库必须决定是否提交或中止分布式事务。
• 全序广播： 消息系统必须决定传递消息的顺序。
• 锁和租约：当几个客户端争抢锁或租约时，由锁来决定哪个客户端成功获得锁。
• 成员/协调服务： 给定某种故障检测器（例如超时），系统必须决定哪些节点活着，哪些节点因为会话超时需要被宣告死亡。
• 唯一性约束：当多个事务同时尝试使用相同的键创建冲突记录时，约束必须决定哪一个被允许，哪些因为违反约束而失败。

如果你只有一个节点，或者你愿意将决策的权能分配给单个节点，所有这些事都很简单。这就是在单领导者数据库中发生的事情：所有决策权归属于领导者，这就是为什么这样的数据库能够提供线性一致的操作，唯一性约束，完全有序的复制日志，以及更多。

但如果该领导者失效，或者如果网络中断导致领导者不可达，这样的系统就无法取得任何进展。应对这种情况可以有三种方法：

1. 等待领导者恢复，接受系统将在这段时间阻塞的事实。许多 XA/JTA 事务协调者选择这个选项。这种方法并不能完全解决共识问题，因为它不满足终止性条件：如果领导者续命失败，系统可能会永久阻塞。
2. 人工故障切换，让人类选择一个新的领导者节点，并重新配置系统使之生效，许多关系型数据库都采用这种方方式。这是一种来自“天意”的共识 —— 由计算机系统之外的运维人员做出决定。故障切换的速度受到人类行动速度的限制，通常要比计算机慢（得多）。
3. 使用算法自动选择一个新的领导者。这种方法需要一种共识算法，建议采用那些经过验证的共识系统来确保正确处理各种网络异常。

ZooKeeper 等工具以一种类似外包方式为应用提供了重要的共识服务、故障检测和成员服务 等。虽然用起来依然有挑战，但远比自己开发共识算住要好得多( 正确处理好第 8 章分布式系统的挑战中的所有问题绝非易事)。如果面临的问题最终可以归结为共识，井且还有容错需求，那么这里给的建议是采用如 ZooKeeper 等验证过的系统 。

更新: 2025-12-04 17:06:37
原文: https://www.yuque.com/snailclimb/to3hqu/ngqg67xgyly50lgp