数据密集型应用设计（DDIA）

DDIA 笔记-腾讯云开发者社区-腾讯云 (tencent.com)

第三章：存储与检索 (vonng.com)

《第一部分：数据系统基础》

第一章 可靠性、可伸缩性和可维护性

第二章 数据模型与查询语言

数据模型

在计算机科学和数据库中，常见的数据模型包括以下几种：

1. 层次模型（Hierarchical Model）：
   层次模型是一种树状的数据结构，其中数据组织成为一个以父节点和子节点之间具有父子关系的层级结构。这种模型适合表示具有明确父子关系的数据。层次模型的代表是IBM的IMS（Information Management System）。

2. 网状模型（Network Model）：
   网状模型是一种网络连接的数据结构，其中数据可以具有多对多的关系。它通过指针连接数据记录，并且一个数据记录可以连接到多个其他记录。网状模型主要用于处理复杂的关系和连接，常见的网状数据库系统是IDMS（Integrated Database Management System）。

3. 关系模型（Relational Model）：
   关系模型是一种基于关系代数的数据模型，它使用表格（关系）来组织和管理数据。关系模型将数据划分为各种属性，每个属性在关系中表示为列，每个实体在关系中表示为行。关系模型最成熟且广泛使用，常用的关系型数据库包括MySQL，Oracle，SQL Server等。

4. 对象模型（Object Model）：
   对象模型是一种基于面向对象思想的数据模型，它将数据和操作封装到对象中，用于描述现实世界中的实体和其之间的关系。对象模型适合表示复杂的结构和关系，常用的对象数据库有MongoDB。

5. 文档模型（Document Model）：
   文档模型是一种无模式（Schema-less）的数据模型，数据以自包含的文档形式存储，如JSON或XML。文档模型适合存储半结构化数据和灵活、动态的数据模式。常用的文档数据库有MongoDB和CouchDB。

6. 键值模型（Key-Value Model）：
   键值模型是一种简单的数据模型，它将数据存储为键值对，每个键都是唯一的。这种模型适用于快速查询和存储大量简单数据的场景，常见的键值数据库有Redis和Memcached。

这些是常见的数据模型，并且每种模型有其特定的使用场景和优势。根据实际需求和数据结构，可以选择适合的数据模型来组织和管理数据。

在其父记录中存储嵌套记录（图 2-1 中的一对多关系，如 positions，education 和 contact_info），而不是在单独的表中。

2.1 关系模型与文档模型

2.1.1 一对多，多对多

当实体之间存在多对多、一对多和没有关系的情况时，可以根据具体的需求和数据特点选择适合的数据模型。以下是针对不同关系的建议：

1. 多对多关系：

   • 关系型数据库模型（如关系型数据库表）：可以使用中间表来表示多对多关系。中间表包含两个外键，分别指向两个实体的主键。这种模型适用于需要对关系进行复杂查询和操作的场景。
   • 图形模型：可以使用图形模型来表示多对多关系。每个实体作为图的节点，关系作为图的边。这种模型适用于需要进行复杂关系分析和图算法的场景。

2. 一对多关系：

   • 关系型数据库模型：可以使用外键来表示一对多关系。在多的一方添加一个外键，指向一的一方的主键。这种模型适用于需要进行一对多关系查询和操作的场景。
   • 文档数据库模型：可以使用嵌套文档或引用文档的方式来表示一对多关系。在一的一方嵌套多的一方的文档，或者在多的一方引用一的一方的文档。这种模型适用于需要以文档为单位进行查询和操作的场景。

3. 没有关系：

   • 关系型数据库模型：如果实体之间没有关系，可以将它们分别存储在不同的表中。每个表代表一个实体，没有外键关联。这种模型适用于需要对实体进行独立查询和操作的场景。
   • 文档数据库模型：可以将每个实体作为一个独立的文档存储，没有嵌套或引用关系。这种模型适用于需要以文档为单位进行查询和操作的场景。

选择适合的数据模型需要考虑以下因素：

• 数据查询和操作的需求：不同的数据模型对查询和操作的支持程度不同，需要根据具体需求选择适合的模型。
• 数据的复杂性和规模：如果数据之间的关系复杂且数据量大，图形模型可能更适合。如果数据之间的关系简单且数据量较小，关系型数据库模型可能更适合。
• 数据一致性和完整性要求：关系型数据库模型通常提供更严格的数据一致性和完整性约束，适用于对数据完整性要求较高的场景。

需要根据具体的业务需求和数据特点进行评估和选择合适的数据模型。

2.2 数据查询语言

当引入关系模型时，关系模型包含了一种查询数据的新方法：SQL 是一种 声明式 查询语言，而 IMS 和 CODASYL 使用 命令式 代码来查询数据库。

命令式语言告诉计算机以特定顺序执行某些操作。可以想象一下，逐行地遍历代码，评估条件，更新变量，并决定是否再循环一遍。

在声明式查询语言（如 SQL 或关系代数）中，你只需指定所需数据的模式 - 结果必须符合哪些条件，以及如何将数据转换（例如，排序，分组和集合） - 但不是如何实现这一目标。数据库系统的查询优化器决定使用哪些索引和哪些连接方法，以及以何种顺序执行查询的各个部分。

2.2.1 声明式

2.2.2 命令式

2.3 图数据模型

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

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

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

• 社交图谱

  顶点是人，边指示哪些人彼此认识。

• 网络图谱

  顶点是网页，边缘表示指向其他页面的 HTML 链接。

• 公路或铁路网络

  顶点是交叉路口，边线代表它们之间的道路或铁路线。

可以将那些众所周知的算法运用到这些图上：例如，汽车导航系统搜索道路网络中两点之间的最短路径，PageRank 可以用在网络图上来确定网页的流行程度，从而确定该网页在搜索结果中的排名。

在刚刚给出的例子中，图中的所有顶点代表了相同类型的事物（人、网页或交叉路口）。不过，图并不局限于这样的同类数据：同样强大地是，图提供了一种一致的方式，用来在单个数据存储中存储完全不同类型的对象。例如，Facebook 维护一个包含许多不同类型的顶点和边的单个图：顶点表示人，地点，事件，签到和用户的评论；边缘表示哪些人是彼此的朋友，哪个签到发生在何处，谁评论了哪条消息，谁参与了哪个事件，等等【35】。

在本节中，我们将使用 图 2-5 所示的示例。它可以从社交网络或系谱数据库中获得：它显示了两个人，来自爱达荷州的 Lucy 和来自法国 Beaune 的 Alain。他们已婚，住在伦敦。

图 2-5 图数据结构示例（框代表顶点，箭头代表边）

有几种不同但相关的方法用来构建和查询图表中的数据。在本节中，我们将讨论属性图模型（由 Neo4j，Titan 和 InfiniteGraph 实现）和三元组存储（triple-store）模型（由 Datomic，AllegroGraph 等实现）。我们将查看图的三种声明式查询语言：Cypher，SPARQL 和 Datalog。除此之外，还有像 Gremlin 【36】这样的图形查询语言和像 Pregel 这样的图形处理框架（见 第十章）。

第三章 存储与检索

第三章：存储与检索 (vonng.com)

存储数据结构结构 ：散列索引、B树、SSTable、LSM树

3.1 驱动数据库的数据结构

数据库存储的数据结构 通常考虑 内存模型 + 硬盘模型；
对比数据结构的优劣也要从这两方面出发。

3.1.1 散列索引

必须存储在内存中。

（AOF）是在追加写入一个文件 —— 所以如何避免最终用完硬盘空间？一种好的解决方案是，将日志分为特定大小的 段（segment），当日志增长到特定尺寸时关闭当前段文件，并开始写入一个新的段文件。然后，我们就可以对这些段进行 压缩（compaction），如 图 3-2 所示。这里的压缩意味着在日志中丢弃重复的键，只保留每个键的最近更新。

（压缩 和 分段合并）

图 3-2 键值更新日志（统计猫咪视频的播放次数）的压缩，只保留每个键的最近值

图 3-3 同时执行压缩和分段合并

下面几点都是实现过程中需要认真考虑的问题：

• 文件格式

  CSV 不是日志的最佳格式。使用二进制格式更快，更简单：首先以字节为单位对字符串的长度进行编码，然后是原始的字符串（不需要转义）。

• 删除记录

  如果要删除一个键及其关联的值，则必须在数据文件中追加一个特殊的删除记录（逻辑删除，有时被称为墓碑，即 tombstone）。当日志段被合并时，合并过程会通过这个墓碑知道要将被删除键的所有历史值都丢弃掉。

• 崩溃恢复

  如果数据库重新启动，则内存散列映射将丢失。原则上，你可以通过从头到尾读取整个段文件并记录下来每个键的最近值来恢复每个段的散列映射。但是，如果段文件很大，可能需要很长时间，这会使服务的重启比较痛苦。 Bitcask 通过将每个段的散列映射的快照存储在硬盘上来加速恢复，可以使散列映射更快地加载到内存中。

• 部分写入记录

  数据库随时可能崩溃，包括在将记录追加到日志的过程中。 Bitcask 文件包含校验和，允许检测和忽略日志中的这些损坏部分。

• 并发控制

  由于写操作是以严格的顺序追加到日志中的，所以常见的实现是只有一个写入线程。也因为数据文件段是仅追加的或者说是不可变的，所以它们可以被多个线程同时读取。

乍一看，仅追加日志似乎很浪费：为什么不直接在文件里更新，用新值覆盖旧值？仅追加的设计之所以是个好的设计，有如下几个原因：

• 追加和分段合并都是顺序写入操作，通常比随机写入快得多，尤其是在磁性机械硬盘上。在某种程度上，顺序写入在基于闪存的 固态硬盘（SSD） 上也是好的选择【4】。我们将在“比较 B 树和 LSM 树”中进一步讨论这个问题。
• 如果段文件是仅追加的或不可变的，并发和崩溃恢复就简单多了。例如，当一个数据值被更新的时候发生崩溃，你不用担心文件里将会同时包含旧值和新值各自的一部分。
• 合并旧段的处理也可以避免数据文件随着时间的推移而碎片化的问题。

但是，散列表索引也有其局限性：

• 散列表必须能放进内存。如果你有非常多的键，那真是倒霉。原则上可以在硬盘上维护一个散列映射，不幸的是硬盘散列映射很难表现优秀。它需要大量的随机访问 I/O，而后者耗尽时想要再扩充是很昂贵的，并且需要很烦琐的逻辑去解决散列冲突【5】。
• 范围查询效率不高。例如，你无法轻松扫描 kitty00000 和 kitty99999 之间的所有键 —— 你必须在散列映射中单独查找每个键。

3.1.2 SSTable 和 LSM 树

排序字符串表（Sorted String Table）（ Log Struct Merge 树）

图 3-5 具有内存索引的 SSTable

内存表：

构建和维护SSTables

到目前为止还不错，但是如何让你的数据能够预先排好序呢？毕竟我们接收到的写入请求可能以任何顺序发生。

虽然在硬盘上维护有序结构也是可能的（请参阅 “B 树”），但在内存保存则要容易得多。有许多可以使用的众所周知的树形数据结构，例如红黑树或 AVL 树【2】。使用这些数据结构，你可以按任何顺序插入键，并按排序顺序读取它们。

现在我们可以让我们的存储引擎以如下方式工作：

• 有新写入时，将其添加到内存中的平衡树数据结构（例如红黑树）。这个内存树有时被称为 内存表（memtable）。
• 当 内存表 大于某个阈值（通常为几兆字节）时，将其作为 SSTable 文件写入硬盘。这可以高效地完成，因为树已经维护了按键排序的键值对。新的 SSTable 文件将成为数据库中最新的段。当该 SSTable 被写入硬盘时，新的写入可以在一个新的内存表实例上继续进行。
• 收到读取请求时，首先尝试在内存表中找到对应的键，如果没有就在最近的硬盘段中寻找，如果还没有就在下一个较旧的段中继续寻找，以此类推。
• 时不时地，在后台运行一个合并和压缩过程，以合并段文件并将已覆盖或已删除的值丢弃掉。

这个方案效果很好。它只会遇到一个问题：如果数据库崩溃，则最近的写入（在内存表中，但尚未写入硬盘）将丢失。为了避免这个问题，我们可以在硬盘上保存一个单独的日志，每个写入都会立即被追加到这个日志上，就像在前面的章节中所描述的那样。这个日志没有按排序顺序，但这并不重要，因为它的唯一目的是在崩溃后恢复内存表。每当内存表写出到 SSTable 时，相应的日志都可以被丢弃。

用SSTables制作LSM树

硬盘结构模型 LSM

这种索引结构最早由 Patrick O’Neil 等人发明，且被命名为日志结构合并树（或 LSM 树）【10】，它是基于更早之前的日志结构文件系统【11】来构建的。基于这种合并和压缩排序文件原理的存储引擎通常被称为 LSM 存储引擎。

3.1.3 B 树

3.1.4 其他索引结构

3.2 事务 /分析（Transition / Analysis）

事务不一定具有 ACID（原子性，一致性，隔离性和持久性）属性。事务处理只是意味着允许客户端进行低延迟的读取和写入 —— 而不是只能定期运行（例如每天一次）的批处理作业。

表 3-1 比较事务处理和分析系统的特点

属性	事务处理系统 OLTP	分析系统 OLAP
主要读取模式	查询少量记录，按键读取	在大批量记录上聚合
主要写入模式	随机访问，写入要求低延时	批量导入（ETL）或者事件流
主要用户	终端用户，通过 Web 应用	内部数据分析师，用于决策支持
处理的数据	数据的最新状态（当前时间点）	随时间推移的历史事件
数据集尺寸	GB ~ TB	TB ~ PB

3.2.1 数据仓库

数据仓库是一个独立的数据库，分析人员可以查询他们想要的内容而不影响 OLTP 操作

3.2.2 星型和雪花型

分析型业务中，数据模型的多样性则少得多。许多数据仓库都以相当公式化的方式使用，被称为星型模式（也称为维度建模【55】）

图3.9中的示例模式 显示了可能在食品零售商处找到的数据仓库。在模式的中心是一个所谓的事实表（在这个例子中，它被称为 fact_sales）。事实表的每一行代表在特定时间发生的事件（这里，每一行代表客户购买的产品）。如果我们分析的是网站流量而不是零售量，则每行可能代表一个用户的页面浏览或点击。

图 3-9 用于数据仓库的星型模式的示例

事实被视为单独的事件，因为这样可以在以后分析中获得最大的灵活性。但是，这意味着事实表可以变得非常大。像苹果、沃尔玛或 eBay 这样的大企业在其数据仓库中可能有几十 PB 的交易历史，其中大部分保存在事实表中【56】。

事实表中的一些列是属性，例如产品销售的价格和从供应商那里购买的成本（可以用来计算利润率）。事实表中的其他列是对其他表（称为维度表）的外键引用。由于事实表中的每一行都表示一个事件，因此这些维度代表事件发生的对象、内容、地点、时间、方式和原因。

3.3 列式存储

第四章 编码与演化

当数据 格式（format） 或 模式（schema） 发生变化时，通常需要对应用程序代码进行相应的更改（例如，为记录添加新字段，然后修改程序开始读写该字段）。但在大型应用程序中，代码变更通常不会立即完成：

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

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

• 向后兼容 (backward compatibility)

  新的代码可以读取由旧的代码写入的数据。

• 向前兼容 (forward compatibility)

  旧的代码可以读取由新的代码写入的数据。

向后兼容性通常并不难实现：新代码的作者当然知道由旧代码使用的数据格式，因此可以显示地处理它（最简单的办法是，保留旧代码即可读取旧数据）。

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

本章中将介绍几种编码数据的格式，包括 JSON、XML、Protocol Buffers、Thrift 和 Avro。尤其将关注这些格式如何应对模式变化，以及它们如何对新旧代码数据需要共存的系统提供支持。然后将讨论如何使用这些格式进行数据存储和通信：在 Web 服务中，表述性状态传递（REST） 和 远程过程调用（RPC），以及 消息传递系统（如 Actor 和消息队列）。

4.1 编码数据的格式

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

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

4.1.1 JSON、XML和二进制变体

当我们谈到可以被多种编程语言读写的标准编码时，JSON 和 XML 是最显眼的角逐者。它们广为人知，广受支持，也 “广受憎恶”。 XML 经常收到批评：过于冗长与且过份复杂【9】。 JSON 的流行则主要源于（通过成为 JavaScript 的一个子集）Web 浏览器的内置支持，以及相对于 XML 的简单性。 CSV 是另一种流行的与语言无关的格式，尽管其功能相对较弱。

JSON，XML 和 CSV 属于文本格式，因此具有人类可读性（尽管它们的语法是一个热门争议话题）。除了表面的语法问题之外，它们也存在一些微妙的问题：

4.1.2 Thrift与Protocol Buffers

Apache Thrift 【15】和 Protocol Buffers（protobuf）【16】是基于相同原理的二进制编码库。 Protocol Buffers 最初是在 Google 开发的，Thrift 最初是在 Facebook 开发的，并且都是在 2007~2008 开源的【17】。 Thrift 和 Protocol Buffers 都需要一个模式来编码任何数据。要在 Thrift 的 例 4-1 中对数据进行编码，可以使用 Thrift 接口定义语言（IDL） 来描述模式，如下所示：

struct Person {
    1: required string       userName,
    2: optional i64          favoriteNumber,
    3: optional list<string> interests
}

Protocol Buffers 的等效模式定义看起来非常相似：

message Person {
    required string user_name       = 1;
    optional int64  favorite_number = 2;
    repeated string interests       = 3;
}

4.1.3 Avro

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

Avro 也使用模式来指定正在编码的数据的结构。 它有两种模式语言：一种（Avro IDL）用于人工编辑，一种（基于 JSON）更易于机器读取。

我们用 Avro IDL 编写的示例模式可能如下所示：

record Person {
    string                userName;
    union { null, long }  favoriteNumber = null;
    array<string>         interests;
}

等价的 JSON 表示：

{
    "type": "record",
    "name": "Person",
    "fields": [
        {"name": "userName", "type": "string"},
        {"name": "favoriteNumber", "type": ["null", "long"], "default": null},
        {"name": "interests", "type": {"type": "array", "items": "string"}}
    ]
}

4.2 数据流的类型

数据如何在流程之间流动的一些最常见的方式：

• 通过数据库（请参阅 “数据库中的数据流”）
• 通过服务调用（请参阅 “服务中的数据流：REST 与 RPC”）
• 通过异步消息传递（请参阅 “消息传递中的数据流”）

4.2.1 数据库中的数据流

4.2.2 服务中的数据流：REST 与 RPC

4.2.3 消息传递中的数据流

《第二部分：分布式数据》

第五章 复制

望能复制数据，可能出于各种各样的原因：

• 使得数据与用户在地理上接近（从而减少延迟）
• 即使系统的一部分出现故障，系统也能继续工作（从而提高可用性）
• 伸缩可以接受读请求的机器数量（从而提高读取吞吐量）

三种流行的变更复制算法：单领导者（single leader，单主），多领导者（multi leader，多主） 和 无领导者（leaderless，无主）。

在 “复制延迟问题” 一节，我们将更加精确地了解最终一致性，并讨论诸如 读己之写（read-your-writes） 和 单调读（monotonic read） 等内容。

5.1 领导者和追随者

每一次向数据库的写入操作都需要传播到所有副本上，否则副本就会包含不一样的数据。最常见的解决方案被称为 基于领导者的复制（leader-based replication） （也称 主动/被动（active/passive） 复制或 主/从（master/slave） 复制），如 图 5-1 所示。它的工作原理如下：

1. 其中一个副本被指定为 领导者（leader），也称为 主库（master|primary） 。当客户端要向数据库写入时，它必须将请求发送给该 领导者，其会将新数据写入其本地存储。
2. 其他副本被称为 追随者（followers），亦称为 只读副本（read replicas）、从库（slaves）、备库（ secondaries） 或 热备（hot-standby）[^i]。每当领导者将新数据写入本地存储时，它也会将数据变更发送给所有的追随者，称之为 复制日志（replication log） 或 变更流（change stream）。每个跟随者从领导者拉取日志，并相应更新其本地数据库副本，方法是按照与领导者相同的处理顺序来进行所有写入。
3. 当客户想要从数据库中读取数据时，它可以向领导者或任一追随者进行查询。但只有领导者才能接受写入操作（从客户端的角度来看从库都是只读的）。

[^i]: 不同的人对 热（hot）、温（warm） 和 冷（cold） 备份服务器有不同的定义。例如在 PostgreSQL 中，热备（hot standby） 指的是能接受客户端读请求的副本。而 温备（warm standby） 只是追随领导者，但不处理客户端的任何查询。

图 5-1 基于领导者的（主/从）复制

5.1.1 同步 / 异步 复制

5.1.5 复制日志的实现

语句复制

在最简单的情况下，主库记录下它执行的每个写入请求（语句，即 statement）并将该语句日志发送给从库。对于关系数据库来说，这意味着每个 INSERT、UPDATE 或 DELETE 语句都被转发给每个从库，每个从库解析并执行该 SQL 语句，就像直接从客户端收到一样。

预写日志（WAL）

write ahead log

在 第三章 中，我们讨论了存储引擎如何在磁盘上表示数据，我们也发现了通常会将写操作追加到日志中：

• 对于日志结构存储引擎（请参阅 “SSTables 和 LSM 树”），日志是主要的存储位置。日志段在后台压缩，并进行垃圾回收。
• 对于覆写单个磁盘块的 B 树，每次修改都会先写入 预写式日志（Write Ahead Log, WAL），以便崩溃后索引可以恢复到一个一致的状态。

虽然听上去很合理，但有很多问题会搞砸这种复制方式：

• 任何调用 非确定性函数（nondeterministic） 的语句，可能会在每个副本上生成不同的值。例如，使用 NOW() 获取当前日期时间，或使用 RAND() 获取一个随机数。
• 如果语句使用了 自增列（auto increment），或者依赖于数据库中的现有数据（例如，UPDATE ... WHERE <某些条件>），则必须在每个副本上按照完全相同的顺序执行它们，否则可能会产生不同的效果。当有多个并发执行的事务时，这可能成为一个限制。
• 有副作用的语句（例如：触发器、存储过程、用户定义的函数）可能会在每个副本上产生不同的副作用，除非副作用是绝对确定性的。

传输预写式日志（WAL）

在 第三章 中，我们讨论了存储引擎如何在磁盘上表示数据，我们也发现了通常会将写操作追加到日志中：

• 对于日志结构存储引擎（请参阅 “SSTables 和 LSM 树”），日志是主要的存储位置。日志段在后台压缩，并进行垃圾回收。
• 对于覆写单个磁盘块的 B 树，每次修改都会先写入 预写式日志（Write Ahead Log, WAL），以便崩溃后索引可以恢复到一个一致的状态。

逻辑日志复制（基于行）

另一种方法是对复制和存储引擎使用不同的日志格式，这样可以将复制日志从存储引擎的内部实现中解耦出来。这种复制日志被称为逻辑日志（logical log），以将其与存储引擎的（物理）数据表示区分开来。

关系数据库的逻辑日志通常是以行的粒度来描述对数据库表的写入记录的序列：

• 对于插入的行，日志包含所有列的新值。
• 对于删除的行，日志包含足够的信息来唯一标识被删除的行，这通常是主键，但如果表上没有主键，则需要记录所有列的旧值。
• 对于更新的行，日志包含足够的信息来唯一标识被更新的行，以及所有列的新值（或至少所有已更改的列的新值）。

基于触发器的复制

到目前为止描述的复制方法是由数据库系统实现的，不涉及任何应用程序代码。在很多情况下，这就是你想要的。但在某些情况下需要更多的灵活性。例如，如果你只想复制数据的一个子集，或者想从一种数据库复制到另一种数据库，或者如果你需要冲突解决逻辑（请参阅 “处理写入冲突”），则可能需要将复制操作上移到应用程序层。

一些工具，如 Oracle Golden Gate【19】，可以通过读取数据库日志，使得其他应用程序可以使用数据。另一种方法是使用许多关系数据库自带的功能：触发器和存储过程。

触发器允许你将数据更改（写入事务）发生时自动执行的自定义应用程序代码注册在数据库系统中。触发器有机会将更改记录到一个单独的表中，使用外部程序读取这个表，再加上一些必要的业务逻辑，就可以将数据变更复制到另一个系统去。例如，Databus for Oracle【20】和 Bucardo for Postgres【21】就是这样工作的。

基于触发器的复制通常比其他复制方法具有更高的开销，并且比数据库内置的复制更容易出错，也有很多限制。然而由于其灵活性，它仍然是很有用的。

5.2 复制延迟问题

5.2.1 读之以写

5.2.2 单调读

5.2.3 一致前缀读

5.2.4 复制延迟解决方案

5.3 多主复制

5.3.3 多主复制拓扑

复制拓扑（replication topology）用来描述写入操作从一个节点传播到另一个节点的通信路径。如果你有两个主库，如 图 5-7 所示，只有一个合理的拓扑结构：主库 1 必须把它所有的写入都发送到主库 2，反之亦然。当有两个以上的主库，多种不同的拓扑都是可能的。图 5-8 举例说明了一些例子。

图 5-8 三种可以在多主复制中使用的拓扑示例。

最常见的拓扑是全部到全部（all-to-all，如 图 5-8 (c)），其中每个主库都将其写入发送给其他所有的主库。然而，一些更受限的拓扑也会被使用到：例如，默认情况下 MySQL 仅支持 环形拓扑（circular topology）【34】，其中每个节点都从一个节点接收写入，并将这些写入（加上自己的写入）转发给另一个节点。另一种流行的拓扑结构具有星形的形状 [^v]：一个指定的根节点将写入转发给所有其他节点。星形拓扑可以推广到树。

[^v]: 不要与星型模式混淆（请参阅 “星型和雪花型：分析的模式”），其中描述了数据模型的结构，而不是节点之间的通信拓扑。

在环形和星形拓扑中，写入可能需要在到达所有副本之前通过多个节点。因此，节点需要转发从其他节点收到的数据更改。为了防止无限复制循环，每个节点被赋予一个唯一的标识符，并且在复制日志中，每次写入都会使用其经过的所有节点的标识符进行标记【43】。当一个节点收到用自己的标识符标记的数据更改时，该数据更改将被忽略，因为节点知道它已经被处理过。

环形和星形拓扑的问题是，如果只有一个节点发生故障，则可能会中断其他节点之间的复制消息流，导致它们无法通信，除非节点被修复。拓扑结构可以重新配置为跳过发生故障的节点，但在大多数部署中，这种重新配置必须手动完成。更密集连接的拓扑结构（例如全部到全部）的容错性更好，因为它允许消息沿着不同的路径传播，可以避免单点故障。

另一方面，全部到全部的拓扑也可能有问题。特别是，一些网络链接可能比其他网络链接更快（例如由于网络拥塞），结果是一些复制消息可能 “超越” 其他复制消息，如 图 5-9 所示。

图 5-9 使用多主复制时，写入可能会以错误的顺序到达某些副本。

在 图 5-9 中，客户端 A 向主库 1 的表中插入一行，客户端 B 在主库 3 上更新该行。然而，主库 2 可以以不同的顺序接收写入：它可能先接收到更新（从它的角度来看，是对数据库中不存在的行的更新），稍后才接收到相应的插入（其应该在更新之前）。

这是一个因果关系的问题，类似于我们在 “一致前缀读” 中看到的：更新取决于先前的插入，所以我们需要确保所有节点先处理插入，然后再处理更新。仅仅在每一次写入时添加一个时间戳是不够的，因为时钟不可能被充分地同步，所以主库 2 就无法正确地对这些事件进行排序（见 第八章）。

要正确排序这些事件，可以使用一种称为 版本向量（version vectors） 的技术，本章稍后将讨论这种技术（请参阅 “检测并发写入”）。然而，许多多主复制系统中的冲突检测技术实现得并不好。例如，在撰写本文时，PostgreSQL BDR 不提供写入的因果排序【27】，而 Tungsten Replicator for MySQL 甚至都不做检测冲突【34】。

如果你正在使用基于多主复制的系统，那么你应该多了解这些问题，仔细阅读文档，并彻底测试你的数据库，以确保它确实提供了你想要的保证。

5.4 无主复制

第六章 分区（片）

**分区 (partition)**，在 MongoDB，Elasticsearch 和 Solr Cloud 中被称为 **分片 (shard)**，在 HBase 中称之为 **区域 (Region)**，Bigtable 中则是 **表块（tablet）**，Cassandra 和 Riak 中是 **虚节点（vnode)**，Couchbase 中叫做 **虚桶 (vBucket)*。但是 *分区 (partitioning) 是最约定俗成的叫法。

6.1 分区与复制

6.2 键值数据模型 – 的分区

6.2.1 键的范围分区

6.2.2 键的散列分区

6.2.3 负载偏斜与热点消除

6.3 分区与次级索引

次级索引的问题是它们不能整齐地映射到分区。有两种用次级索引对数据库进行分区的方法：基于文档的分区（document-based） 和 基于关键词（term-based）的分区

使用场景：次级索引是关系型数据库的基础，并且在文档数据库中也很普遍。许多键值存储（如 HBase 和 Volde-mort）为了减少实现的复杂度而放弃了次级索引，但是一些（如 Riak）已经开始添加它们，因为它们对于数据模型实在是太有用了。并且次级索引也是 Solr 和 Elasticsearch 等搜索服务器的基石。

6.3.1 基于文档的次级索引分区

确保你的索引与底层数据保持一致。 竞争条件和间歇性写入失败（其中一些更改已保存，但其他更改未保存）很容易导致数据不同步 - 请参阅 “多对象事务的需求”。

在这种索引方法中，每个分区是完全独立的：每个分区维护自己的次级索引，仅覆盖该分区中的文档。它不关心存储在其他分区的数据。无论何时你需要写入数据库（添加，删除或更新文档），只需处理包含你正在编写的文档 ID 的分区即可。出于这个原因，文档分区索引 也被称为 本地索引（而不是将在下一节中描述的 全局索引）。

如果要搜索红色汽车，则需要将查询发送到所有分区，并合并所有返回的结果。

这种查询分区数据库的方法有时被称为 分散 / 聚集（scatter/gather），并且可能会使次级索引上的读取查询相当昂贵。即使并行查询分区，分散 / 聚集也容易导致尾部延迟放大。

6.3.2 基于关键词的次级索引分区

我们可以构建一个覆盖所有分区数据的 全局索引，而不是给每个分区创建自己的次级索引（本地索引）。但是，我们不能只把这个索引存储在一个节点上，因为它可能会成为瓶颈，违背了分区的目的。全局索引也必须进行分区，但可以采用与主键不同的分区方式。（简历全局索引，并进行分区存储）

优点：读取更有效率：不需要 分散 / 收集 所有分区

缺点：全局索引的缺点在于写入速度较慢且较为复杂，写入单个文档现在可能会影响索引的多个分区

6.4 分区再平衡 – Rebalance

反面教材：hash mod N

节点大量迁移 ： 模 N（mod N）方法的问题是，如果节点数量 N 发生变化，大多数键将需要从一个节点移动到另一个节点。

固定数量的分区

定义：固定分区数量，例如10个节点（Node），划分100个分区

节点增加：将闲置分区分给新节点

节点减少：将删除节点分区 重新分配到 现有节点

只有分区在节点之间的移动。分区的数量不会改变，键所指定的分区也不会改变。唯一改变的是分区所在的节点。

问题：在网络上传输大量的数据需要一些时间 — 所以在传输过程中，原有分区仍然会接受读写操作。

使用场景分析：

在这种配置中，分区的数量通常在数据库第一次建立时确定，之后不会改变。

如果数据集的总大小难以预估（例如，可能它开始很小，但随着时间的推移会变得更大），选择正确的分区数是困难的。由于每个分区包含了总数据量固定比率的数据，因此每个分区的大小与集群中的数据总量成比例增长。如果分区非常大，再平衡和从节点故障恢复变得昂贵。但是，如果分区太小，则会产生太多的开销。当分区大小 “恰到好处” 的时候才能获得很好的性能，如果分区数量固定，但数据量变动很大，则难以达到最佳性能。

动态分区

对于使用键范围分区的数据库（请参阅 “根据键的范围分区”），具有固定边界的固定数量的分区将非常不便：如果出现边界错误，则可能会导致一个分区中的所有数据或者其他分区中的所有数据为空。手动重新配置分区边界将非常繁琐。

按键的范围进行分区的数据库（如 HBase 和 RethinkDB）会动态创建分区。当分区增长到超过配置的大小时（在 HBase 上，默认值是 10GB），会被分成两个分区，每个分区约占一半的数据【26】。与之相反，如果大量数据被删除并且分区缩小到某个阈值以下，则可以将其与相邻分区合并。此过程与 B 树顶层发生的过程类似（请参阅 “B 树”）。

按节点比例分区

通过动态分区，分区的数量与数据集的大小成正比，因为拆分和合并过程将每个分区的大小保持在固定的最小值和最大值之间。另一方面，对于固定数量的分区，每个分区的大小与数据集的大小成正比。在这两种情况下，分区的数量都与节点的数量无关。

Cassandra 和 Ketama 使用的第三种方法是使分区数与节点数成正比 —— 换句话说，每个节点具有固定数量的分区【23,27,28】。在这种情况下，每个分区的大小与数据集大小成比例地增长，而节点数量保持不变，但是当增加节点数时，分区将再次变小。由于较大的数据量通常需要较大数量的节点进行存储，因此这种方法也使每个分区的大小较为稳定。

当一个新节点加入集群时，它随机选择固定数量的现有分区进行拆分，然后占有这些拆分分区中每个分区的一半，同时将每个分区的另一半留在原地。随机化可能会产生不公平的分割，但是平均在更大数量的分区上时（在 Cassandra 中，默认情况下，每个节点有 256 个分区），新节点最终从现有节点获得公平的负载份额。 Cassandra 3.0 引入了另一种再平衡的算法来避免不公平的分割【29】。

随机选择分区边界要求使用基于散列的分区（可以从散列函数产生的数字范围中挑选边界）。实际上，这种方法最符合一致性哈希的原始定义【7】（请参阅 “一致性哈希”）。最新的哈希函数可以在较低元数据开销的情况下达到类似的效果【8】。

6.5 请求路由

第七章 事务

(6条消息) 浅析分布式系统之体系结构 - 事务与隔离级别（多对象、多操作）上篇_snefsnef的博客-CSDN博客

(6条消息) 浅析分布式系统之体系结构 - 事务与隔离级别（多对象、多操作）下篇_snefsnef的博客-CSDN博客

第八章 分布式系统的麻烦

8.1 故障与部分失效

8.2 不可靠的网络

8

8.3 不可靠的时钟

8.3.1 单调钟与日历时钟

8.3.2 时钟同步与准确性

8.3.3 依赖同步时钟

8.3.4 进程暂停

8.4 知识、真相与谎言

8.4.1 真相由多数定义

8.4.2 拜占庭故障

8.4.3 拜占庭将军问题

《第九章》 一致性与共识

好死还是赖活着？ —— Jay Kreps, 关于 Kafka 与 Jepsen 的若干笔记 (2013)

---

[TOC]

正如 第八章 所讨论的，分布式系统中的许多事情可能会出错。处理这种故障的最简单方法是简单地让整个服务失效，并向用户显示错误消息。如果无法接受这个解决方案，我们就需要找到容错的方法 —— 即使某些内部组件出现故障，服务也能正常运行。

在本章中，我们将讨论构建容错分布式系统的算法和协议的一些例子。我们将假设 第八章 的所有问题都可能发生：网络中的数据包可能会丢失、重新排序、重复推送或任意延迟；时钟只是尽其所能地近似；且节点可以暂停（例如，由于垃圾收集）或随时崩溃。

构建容错系统的最好方法，是找到一些带有实用保证的通用抽象，实现一次，然后让应用依赖这些保证。这与 第七章 中的事务处理方法相同：通过使用事务，应用可以假装没有崩溃（原子性），没有其他人同时访问数据库（隔离），存储设备是完全可靠的（持久性）。即使发生崩溃，竞态条件和磁盘故障，事务抽象隐藏了这些问题，因此应用不必担心它们。

现在我们将继续沿着同样的路线前进，寻求可以让应用忽略分布式系统部分问题的抽象概念。例如，分布式系统最重要的抽象之一就是 共识（consensus）：就是让所有的节点对某件事达成一致。正如我们在本章中将会看到的那样，要可靠地达成共识，且不被网络故障和进程故障所影响，是一个令人惊讶的棘手问题。

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

在本章后面的 “分布式事务与共识” 中，我们将研究解决共识和相关问题的算法。但首先，我们首先需要探索可以在分布式系统中提供的保证和抽象的范围。

我们需要了解可以做什么和不可以做什么的范围：在某些情况下，系统可以容忍故障并继续工作；在其他情况下，这是不可能的。我们将深入研究什么可能而什么不可能的限制，既通过理论证明，也通过实际实现。我们将在本章中概述这些基本限制。

分布式系统领域的研究人员几十年来一直在研究这些主题，所以有很多资料 —— 我们只能介绍一些皮毛。在本书中，我们没有空间去详细介绍形式模型和证明的细节，所以我们会按照直觉来介绍。如果你有兴趣，参考文献可以提供更多的深度。

9.1 一致性保证

在 “复制延迟问题” 中，我们看到了数据库复制中发生的一些时序问题。如果你在同一时刻查看两个数据库节点，则可能在两个节点上看到不同的数据，因为写请求在不同的时间到达不同的节点。无论数据库使用何种复制方法（单主复制，多主复制或无主复制），都会出现这些不一致情况。

大多数复制的数据库至少提供了 最终一致性，这意味着如果你停止向数据库写入数据并等待一段不确定的时间，那么最终所有的读取请求都会返回相同的值【1】。换句话说，不一致性是暂时的，最终会自行解决（假设网络中的任何故障最终都会被修复）。最终一致性的一个更好的名字可能是 收敛（convergence），因为我们预计所有的副本最终会收敛到相同的值【2】。

然而，这是一个非常弱的保证 —— 它并没有说什么时候副本会收敛。在收敛之前，读操作可能会返回任何东西或什么都没有【1】。例如，如果你写入了一个值，然后立即再次读取，这并不能保证你能看到刚才写入的值，因为读请求可能会被路由到另外的副本上。（请参阅 “读己之写” ）。

对于应用开发人员而言，最终一致性是很困难的，因为它与普通单线程程序中变量的行为有很大区别。对于后者，如果将一个值赋给一个变量，然后很快地再次读取，不可能读到旧的值，或者读取失败。数据库表面上看起来像一个你可以读写的变量，但实际上它有更复杂的语义【3】。

在与只提供弱保证的数据库打交道时，你需要始终意识到它的局限性，而不是意外地作出太多假设。错误往往是微妙的，很难找到，也很难测试，因为应用可能在大多数情况下运行良好。当系统出现故障（例如网络中断）或高并发时，最终一致性的边缘情况才会显现出来。

本章将探索数据系统可能选择提供的更强一致性模型。它不是免费的：具有较强保证的系统可能会比保证较差的系统具有更差的性能或更少的容错性。尽管如此，更强的保证能够吸引人，因为它们更容易用对。只有见过不同的一致性模型后，才能更好地决定哪一个最适合自己的需求。

分布式一致性模型 和我们之前讨论的事务隔离级别的层次结构有一些相似之处【4,5】（请参阅 “弱隔离级别”）。尽管两者有一部分内容重叠，但它们大多是无关的问题：事务隔离主要是为了 避免由于同时执行事务而导致的竞争状态，而分布式一致性主要关于 在面对延迟和故障时如何协调副本间的状态。

本章涵盖了广泛的话题，但我们将会看到这些领域实际上是紧密联系在一起的：

• 首先看一下常用的 最强一致性模型 之一，线性一致性（linearizability），并考察其优缺点。
• 然后我们将检查分布式系统中 事件顺序 的问题，特别是因果关系和全局顺序的问题。
• 在第三节的（“分布式事务与共识”）中将探讨如何原子地提交分布式事务，这将最终引领我们走向共识问题的解决方案。

9.2 线性一致性

在 最终一致 的数据库，如果你在同一时刻问两个不同副本相同的问题，可能会得到两个不同的答案。这很让人困惑。如果数据库可以提供只有一个副本的假象（即，只有一个数据副本），那么事情就简单太多了。那么每个客户端都会有相同的数据视图，且不必担心复制滞后了。

这就是 线性一致性（linearizability） 背后的想法【6】（也称为 原子一致性（atomic consistency）【7】，强一致性（strong consistency），立即一致性（immediate consistency） 或 外部一致性（external consistency ）【8】）。线性一致性的精确定义相当微妙，我们将在本节的剩余部分探讨它。但是基本的想法是让一个系统看起来好像只有一个数据副本，而且所有的操作都是原子性的。有了这个保证，即使实际中可能有多个副本，应用也不需要担心它们。

在一个线性一致的系统中，只要一个客户端成功完成写操作，所有客户端从数据库中读取数据必须能够看到刚刚写入的值。要维护数据的单个副本的假象，系统应保障读到的值是最近的、最新的，而不是来自陈旧的缓存或副本。换句话说，线性一致性是一个 新鲜度保证（recency guarantee）。为了阐明这个想法，我们来看看一个非线性一致系统的例子。

图 9-1 这个系统是非线性一致的，导致了球迷的困惑

图 9-1 展示了一个关于体育网站的非线性一致例子【9】。Alice 和 Bob 正坐在同一个房间里，都盯着各自的手机，关注着 2014 年 FIFA 世界杯决赛的结果。在最后得分公布后，Alice 刷新页面，看到宣布了获胜者，并兴奋地告诉 Bob。Bob 难以置信地刷新了自己的手机，但他的请求路由到了一个落后的数据库副本上，手机显示比赛仍在进行。

如果 Alice 和 Bob 在同一时间刷新并获得了两个不同的查询结果，也许就没有那么令人惊讶了。因为他们不知道服务器处理他们请求的精确时刻。然而 Bob 是在听到 Alice 惊呼最后得分 之后，点击了刷新按钮（启动了他的查询），因此他希望查询结果至少与爱丽丝一样新鲜。但他的查询返回了陈旧结果，这一事实违背了线性一致性的要求。

什么使得系统线性一致？

线性一致性背后的基本思想很简单：使系统看起来好像只有一个数据副本。然而确切来讲，实际上有更多要操心的地方。为了更好地理解线性一致性，让我们再看几个例子。

图 9-2 显示了三个客户端在线性一致数据库中同时读写相同的键 x。在分布式系统文献中，x 被称为 寄存器（register），例如，它可以是键值存储中的一个 键，关系数据库中的一 行，或文档数据库中的一个 文档。

图 9-2 如果读取请求与写入请求并发，则可能会返回旧值或新值

为了简单起见，图 9-2 采用了用户请求的视角，而不是数据库内部的视角。每个柱都是由客户端发出的请求，其中柱头是请求发送的时刻，柱尾是客户端收到响应的时刻。因为网络延迟变化无常，客户端不知道数据库处理其请求的精确时间 —— 只知道它发生在发送请求和接收响应之间的某个时刻。[^i]

[^i]: 这个图的一个微妙的细节是它假定存在一个全局时钟，由水平轴表示。即使真实的系统通常没有准确的时钟（请参阅 “不可靠的时钟”），但这种假设是允许的：为了分析分布式算法，我们可以假设一个精确的全局时钟存在，不过算法无法访问它【47】。算法只能看到由石英振荡器和 NTP 产生的实时逼近。

在这个例子中，寄存器有两种类型的操作：

• ����(�)⇒�read(x)⇒v表示客户端请求读取寄存器 x 的值，数据库返回值 v。
• �����(�,�)⇒�write(x,v)⇒r 表示客户端请求将寄存器 x 设置为值 v ，数据库返回响应 r （可能正确，可能错误）。

在 图 9-2 中，x 的值最初为 0，客户端 C 执行写请求将其设置为 1。发生这种情况时，客户端 A 和 B 反复轮询数据库以读取最新值。 A 和 B 的请求可能会收到怎样的响应？

• 客户端 A 的第一个读操作，完成于写操作开始之前，因此必须返回旧值 0。
• 客户端 A 的最后一个读操作，开始于写操作完成之后。如果数据库是线性一致性的，它必然返回新值 1：因为读操作和写操作一定是在其各自的起止区间内的某个时刻被处理。如果在写入结束后开始读取，则读取处理一定发生在写入完成之后，因此它必须看到写入的新值。
• 与写操作在时间上重叠的任何读操作，可能会返回 0 或 1 ，因为我们不知道读取时，写操作是否已经生效。这些操作是 并发（concurrent） 的。

但是，这还不足以完全描述线性一致性：如果与写入同时发生的读取可以返回旧值或新值，那么读者可能会在写入期间看到数值在旧值和新值之间来回翻转。这不是我们所期望的仿真 “单一数据副本” 的系统。[^ii]

[^ii]: 如果读取（与写入同时发生时）可能返回旧值或新值，则称该寄存器为 常规寄存器（regular register）【7,25】

为了使系统线性一致，我们需要添加另一个约束，如 图 9-3 所示

图 9-3 任何一个读取返回新值后，所有后续读取（在相同或其他客户端上）也必须返回新值。

在一个线性一致的系统中，我们可以想象，在 x 的值从 0 自动翻转到 1 的时候（在写操作的开始和结束之间）必定有一个时间点。因此，如果一个客户端的读取返回新的值 1，即使写操作尚未完成，所有后续读取也必须返回新值。

图 9-3 中的箭头说明了这个时序依赖关系。客户端 A 是第一个读取新的值 1 的位置。在 A 的读取返回之后，B 开始新的读取。由于 B 的读取严格在发生于 A 的读取之后，因此即使 C 的写入仍在进行中，也必须返回 1（与 图 9-1 中的 Alice 和 Bob 的情况相同：在 Alice 读取新值之后，Bob 也希望读取新的值）。

我们可以进一步细化这个时序图，展示每个操作是如何在特定时刻原子性生效的。图 9-4 显示了一个更复杂的例子【10】。

在 图 9-4 中，除了读写之外，还增加了第三种类型的操作：

• ���(�,����,����)⇒�cas(x,vold,vnew)⇒r 表示客户端请求进行原子性的 比较与设置 操作。如果寄存器 �x 的当前值等于 ����vold ，则应该原子地设置为 ����vnew 。如果 �≠����x=vold ，则操作应该保持寄存器不变并返回一个错误。 �r 是数据库的响应（正确或错误）。

图 9-4 中的每个操作都在我们认为执行操作的时候用竖线标出（在每个操作的条柱之内）。这些标记按顺序连在一起，其结果必须是一个有效的寄存器读写序列（每次读取都必须返回最近一次写入设置的值）。

线性一致性的要求是，操作标记的连线总是按时间（从左到右）向前移动，而不是向后移动。这个要求确保了我们之前讨论的新鲜度保证：一旦新的值被写入或读取，所有后续的读都会看到写入的值，直到它被再次覆盖。

图 9-4 可视化读取和写入看起来已经生效的时间点。 B 的最后读取不是线性一致性的

图 9-4 中有一些有趣的细节需要指出：

• 第一个客户端 B 发送一个读取 x 的请求，然后客户端 D 发送一个请求将 x 设置为 0，然后客户端 A 发送请求将 x 设置为 1。尽管如此，返回到 B 的读取值为 1（由 A 写入的值）。这是可以的：这意味着数据库首先处理 D 的写入，然后是 A 的写入，最后是 B 的读取。虽然这不是请求发送的顺序，但这是一个可以接受的顺序，因为这三个请求是并发的。也许 B 的读请求在网络上略有延迟，所以它在两次写入之后才到达数据库。

• 在客户端 A 从数据库收到响应之前，客户端 B 的读取返回 1 ，表示写入值 1 已成功。这也是可以的：这并不意味着在写之前读到了值，这只是意味着从数据库到客户端 A 的正确响应在网络中略有延迟。

• 此模型不假设有任何事务隔离：另一个客户端可能随时更改值。例如，C 首先读取 1 ，然后读取 2 ，因为两次读取之间的值由 B 更改。可以使用原子 比较并设置（cas） 操作来检查该值是否未被另一客户端同时更改：B 和 C 的 cas 请求成功，但是 D 的 cas 请求失败（在数据库处理它时，x 的值不再是 0 ）。

• 客户 B 的最后一次读取（阴影条柱中）不是线性一致性的。 该操作与 C 的 cas 写操作并发（它将 x 从 2 更新为 4 ）。在没有其他请求的情况下，B 的读取返回 2 是可以的。然而，在 B 的读取开始之前，客户端 A 已经读取了新的值 4 ，因此不允许 B 读取比 A 更旧的值。再次，与 图 9-1 中的 Alice 和 Bob 的情况相同。

  这就是线性一致性背后的直觉。 正式的定义【6】更准确地描述了它。 通过记录所有请求和响应的时序，并检查它们是否可以排列成有效的顺序，以测试一个系统的行为是否线性一致性是可能的（尽管在计算上是昂贵的）【11】。

线性一致性与可串行化

线性一致性 容易和 可串行化 相混淆，因为两个词似乎都是类似 “可以按顺序排列” 的东西。但它们是两种完全不同的保证，区分两者非常重要：

*可串行化*

可串行化（Serializability） 是事务的隔离属性，每个事务可以读写多个对象（行，文档，记录）—— 请参阅 “单对象和多对象操作”。它确保事务的行为，与它们按照 某种 顺序依次执行的结果相同（每个事务在下一个事务开始之前运行完成）。这种执行顺序可以与事务实际执行的顺序不同。【12】。

*线性一致性*

线性一致性（Linearizability） 是读取和写入寄存器（单个对象）的 新鲜度保证。它不会将操作组合为事务，因此它也不会阻止写入偏差等问题（请参阅 “写入偏差和幻读”），除非采取其他措施（例如 物化冲突）。

一个数据库可以提供可串行化和线性一致性，这种组合被称为严格的可串行化或 强的单副本可串行化（strong-1SR）【4,13】。基于两阶段锁定的可串行化实现（请参阅 “两阶段锁定” 一节）或 真的串行执行（请参阅 “真的串行执行”一节）通常是线性一致性的。

但是，可串行化的快照隔离（请参阅 “可串行化快照隔离”）不是线性一致性的：按照设计，它从一致的快照中进行读取，以避免读者和写者之间的锁竞争。一致性快照的要点就在于 它不会包括该快照之后的写入，因此从快照读取不是线性一致性的。

依赖线性一致性

线性一致性在什么情况下有用？观看体育比赛的最后得分可能是一个轻率的例子：滞后了几秒钟的结果不太可能在这种情况下造成任何真正的伤害。然而对于少数领域，线性一致性是系统正确工作的一个重要条件。

锁定和领导选举

一个使用单主复制的系统，需要确保领导者真的只有一个，而不是几个（脑裂）。一种选择领导者的方法是使用锁：每个节点在启动时尝试获取锁，成功者成为领导者【14】。不管这个锁是如何实现的，它必须是线性一致的：所有节点必须就哪个节点拥有锁达成一致，否则就没用了。

诸如 Apache ZooKeeper 【15】和 etcd 【16】之类的协调服务通常用于实现分布式锁和领导者选举。它们使用一致性算法，以容错的方式实现线性一致的操作（在本章后面的 “容错共识” 中讨论此类算法）[^iii]。还有许多微妙的细节来正确地实现锁和领导者选举（例如，请参阅 “领导者和锁” 中的防护问题），而像 Apache Curator 【17】这样的库则通过在 ZooKeeper 之上提供更高级别的配方来提供帮助。但是，线性一致性存储服务是这些协调任务的基础。

[^iii]: 严格地说，ZooKeeper 和 etcd 提供线性一致性的写操作，但读取可能是陈旧的，因为默认情况下，它们可以由任何一个副本提供服务。你可以选择请求线性一致性读取：etcd 称之为 法定人数读取（quorum read）【16】，而在 ZooKeeper 中，你需要在读取之前调用 sync()【15】。请参阅 “使用全序广播实现线性一致的存储”。

分布式锁也在一些分布式数据库（如 Oracle Real Application Clusters（RAC）【18】）中有更细粒度级别的使用。RAC 对每个磁盘页面使用一个锁，多个节点共享对同一个磁盘存储系统的访问权限。由于这些线性一致的锁处于事务执行的关键路径上，RAC 部署通常具有用于数据库节点之间通信的专用集群互连网络。

约束和唯一性保证

唯一性约束在数据库中很常见：例如，用户名或电子邮件地址必须唯一标识一个用户，而在文件存储服务中，不能有两个具有相同路径和文件名的文件。如果要在写入数据时强制执行此约束（例如，如果两个人试图同时创建一个具有相同名称的用户或文件，其中一个将返回一个错误），则需要线性一致性。

这种情况实际上类似于一个锁：当一个用户注册你的服务时，可以认为他们获得了所选用户名的 “锁”。该操作与原子性的比较与设置（CAS）非常相似：将用户名赋予声明它的用户，前提是用户名尚未被使用。

如果想要确保银行账户余额永远不会为负数，或者不会出售比仓库里的库存更多的物品，或者两个人不会都预定了航班或剧院里同一时间的同一个位置。这些约束条件都要求所有节点都同意一个最新的值（账户余额，库存水平，座位占用率）。

在实际应用中，宽松地处理这些限制有时是可以接受的（例如，如果航班超额预订，你可以将客户转移到不同的航班并为其提供补偿）。在这种情况下，可能不需要线性一致性，我们将在 “及时性与完整性” 中讨论这种宽松的约束。

然而，一个硬性的唯一性约束（关系型数据库中常见的那种）需要线性一致性。其他类型的约束，如外键或属性约束，可以不需要线性一致性【19】。

跨信道的时序依赖

注意 图 9-1 中的一个细节：如果 Alice 没有惊呼得分，Bob 就不会知道他的查询结果是陈旧的。他会在几秒钟之后再次刷新页面，并最终看到最后的分数。由于系统中存在额外的信道（Alice 的声音传到了 Bob 的耳朵中），线性一致性的违背才被注意到。

计算机系统也会出现类似的情况。例如，假设有一个网站，用户可以上传照片，一个后台进程会调整照片大小，降低分辨率以加快下载速度（缩略图）。该系统的架构和数据流如 图 9-5 所示。

图像缩放器需要明确的指令来执行尺寸缩放作业，指令是 Web 服务器通过消息队列发送的（请参阅 第十一章）。 Web 服务器不会将整个照片放在队列中，因为大多数消息代理都是针对较短的消息而设计的，而一张照片的空间占用可能达到几兆字节。取而代之的是，首先将照片写入文件存储服务，写入完成后再将给缩放器的指令放入消息队列。

图 9-5 Web 服务器和图像缩放器通过文件存储和消息队列进行通信，打开竞争条件的可能性。

如果文件存储服务是线性一致的，那么这个系统应该可以正常工作。如果它不是线性一致的，则存在竞争条件的风险：消息队列（图 9-5 中的步骤 3 和 4）可能比存储服务内部的复制（replication）更快。在这种情况下，当缩放器读取图像（步骤 5）时，可能会看到图像的旧版本，或者什么都没有。如果它处理的是旧版本的图像，则文件存储中的全尺寸图和缩略图就产生了永久性的不一致。

出现这个问题是因为 Web 服务器和缩放器之间存在两个不同的信道：文件存储与消息队列。没有线性一致性的新鲜性保证，这两个信道之间的竞争条件是可能的。这种情况类似于 图 9-1，数据库复制与 Alice 的嘴到 Bob 耳朵之间的真人音频信道之间也存在竞争条件。

线性一致性并不是避免这种竞争条件的唯一方法，但它是最容易理解的。如果你可以控制额外信道（例如消息队列的例子，而不是在 Alice 和 Bob 的例子），则可以使用在 “读己之写” 讨论过的类似方法，不过会有额外的复杂度代价。

实现线性一致的系统

我们已经见到了几个线性一致性有用的例子，让我们思考一下，如何实现一个提供线性一致语义的系统。

由于线性一致性本质上意味着 “表现得好像只有一个数据副本，而且所有的操作都是原子的”，所以最简单的答案就是，真的只用一个数据副本。但是这种方法无法容错：如果持有该副本的节点失效，数据将会丢失，或者至少无法访问，直到节点重新启动。

使系统容错最常用的方法是使用复制。我们再来回顾 第五章 中的复制方法，并比较它们是否可以满足线性一致性：

• 单主复制（可能线性一致）

  在具有单主复制功能的系统中（请参阅 “领导者与追随者”），主库具有用于写入的数据的主副本，而追随者在其他节点上保留数据的备份副本。如果从主库或同步更新的从库读取数据，它们 可能（potential） 是线性一致性的 [^iv]。然而，实际上并不是每个单主数据库都是线性一致性的，无论是因为设计的原因（例如，因为使用了快照隔离）还是因为在并发处理上存在错误【10】。

  [^iv]: 对单主数据库进行分区（分片），使得每个分区有一个单独的领导者，不会影响线性一致性，因为线性一致性只是对单一对象的保证。 交叉分区事务是一个不同的问题（请参阅 “分布式事务与共识”）。

  从主库读取依赖一个假设，你确定地知道领导者是谁。正如在 “真相由多数所定义” 中所讨论的那样，一个节点很可能会认为它是领导者，而事实上并非如此 —— 如果具有错觉的领导者继续为请求提供服务，可能违反线性一致性【20】。使用异步复制，故障切换时甚至可能会丢失已提交的写入（请参阅 “处理节点宕机”），这同时违反了持久性和线性一致性。

• 共识算法（线性一致）

  一些在本章后面讨论的共识算法，与单主复制类似。然而，共识协议包含防止脑裂和陈旧副本的措施。正是由于这些细节，共识算法可以安全地实现线性一致性存储。例如，Zookeeper 【21】和 etcd 【22】就是这样工作的。

• 多主复制（非线性一致）

  具有多主程序复制的系统通常不是线性一致的，因为它们同时在多个节点上处理写入，并将其异步复制到其他节点。因此，它们可能会产生需要被解决的写入冲突（请参阅 “处理写入冲突”）。这种冲突是因为缺少单一数据副本所导致的。

• 无主复制（也许不是线性一致的）

  对于无主复制的系统（Dynamo 风格；请参阅 “无主复制”），有时候人们会声称通过要求法定人数读写（ �+�>�w+r>n ）可以获得 “强一致性”。这取决于法定人数的具体配置，以及强一致性如何定义（通常不完全正确）。

  基于日历时钟（例如，在 Cassandra 中；请参阅 “依赖同步时钟”）的 “最后写入胜利” 冲突解决方法几乎可以确定是非线性一致的，由于时钟偏差，不能保证时钟的时间戳与实际事件顺序一致。宽松的法定人数（请参阅 “宽松的法定人数与提示移交”）也破坏了线性一致的可能性。即使使用严格的法定人数，非线性一致的行为也是可能的，如下节所示。

线性一致性和法定人数

直觉上在 Dynamo 风格的模型中，严格的法定人数读写应该是线性一致性的。但是当我们有可变的网络延迟时，就可能存在竞争条件，如 图 9-6 所示。

图 9-6 非线性一致的执行，尽管使用了严格的法定人数

在 图 9-6 中，�x 的初始值为 0，写入客户端通过向所有三个副本（ �=3,�=3n=3,w=3 ）发送写入将 �x 更新为 1。客户端 A 并发地从两个节点组成的法定人群（ �=2r=2 ）中读取数据，并在其中一个节点上看到新值 1 。客户端 B 也并发地从两个不同的节点组成的法定人数中读取，并从两个节点中取回了旧值 0 。

法定人数条件满足（ �+�>�w+r>n ），但是这个执行是非线性一致的：B 的请求在 A 的请求完成后开始，但是 B 返回旧值，而 A 返回新值。 （又一次，如同 Alice 和 Bob 的例子 图 9-1）

有趣的是，通过牺牲性能，可以使 Dynamo 风格的法定人数线性化：读取者必须在将结果返回给应用之前，同步执行读修复（请参阅 “读修复和反熵”） ，并且写入者必须在发送写入之前，读取法定数量节点的最新状态【24,25】。然而，由于性能损失，Riak 不执行同步读修复【26】。 Cassandra 在进行法定人数读取时，确实 在等待读修复完成【27】；但是由于使用了最后写入胜利的冲突解决方案，当同一个键有多个并发写入时，将不能保证线性一致性。

而且，这种方式只能实现线性一致的读写；不能实现线性一致的比较和设置（CAS）操作，因为它需要一个共识算法【28】。

总而言之，最安全的做法是：假设采用 Dynamo 风格无主复制的系统不能提供线性一致性。

线性一致性的代价

一些复制方法可以提供线性一致性，另一些复制方法则不能，因此深入地探讨线性一致性的优缺点是很有趣的。

我们已经在 第五章 中讨论了不同复制方法的一些用例。例如对多数据中心的复制而言，多主复制通常是理想的选择（请参阅 “运维多个数据中心”）。图 9-7 说明了这种部署的一个例子。

图 9-7 网络中断迫使在线性一致性和可用性之间做出选择。

考虑这样一种情况：如果两个数据中心之间发生网络中断会发生什么？我们假设每个数据中心内的网络正在工作，客户端可以访问数据中心，但数据中心之间彼此无法互相连接。

使用多主数据库，每个数据中心都可以继续正常运行：由于在一个数据中心写入的数据是异步复制到另一个数据中心的，所以在恢复网络连接时，写入操作只是简单地排队并交换。

另一方面，如果使用单主复制，则主库必须位于其中一个数据中心。任何写入和任何线性一致的读取请求都必须发送给该主库，因此对于连接到从库所在数据中心的客户端，这些读取和写入请求必须通过网络同步发送到主库所在的数据中心。

在单主配置的条件下，如果数据中心之间的网络被中断，则连接到从库数据中心的客户端无法联系到主库，因此它们无法对数据库执行任何写入，也不能执行任何线性一致的读取。它们仍能从从库读取，但结果可能是陈旧的（非线性一致）。如果应用需要线性一致的读写，却又位于与主库网络中断的数据中心，则网络中断将导致这些应用不可用。

如果客户端可以直接连接到主库所在的数据中心，这就不是问题了，那些应用可以继续正常工作。但只能访问从库数据中心的客户端会中断运行，直到网络连接得到修复。

CAP定理

这个问题不仅仅是单主复制和多主复制的后果：任何线性一致的数据库都有这个问题，不管它是如何实现的。这个问题也不仅仅局限于多数据中心部署，而可能发生在任何不可靠的网络上，即使在同一个数据中心内也是如此。问题面临的权衡如下：[^v]

• 如果应用需要线性一致性，且某些副本因为网络问题与其他副本断开连接，那么这些副本掉线时不能处理请求。请求必须等到网络问题解决，或直接返回错误。（无论哪种方式，服务都 不可用）。
• 如果应用不需要线性一致性，那么某个副本即使与其他副本断开连接，也可以独立处理请求（例如多主复制）。在这种情况下，应用可以在网络问题前保持可用，但其行为不是线性一致的。

[^v]: 这两种选择有时分别称为 CP（在网络分区下一致但不可用）和 AP（在网络分区下可用但不一致）。 但是，这种分类方案存在一些缺陷【9】，所以最好不要这样用。

因此，不需要线性一致性的应用对网络问题有更强的容错能力。这种见解通常被称为 CAP 定理【29,30,31,32】，由 Eric Brewer 于 2000 年命名，尽管 70 年代的分布式数据库设计者早就知道了这种权衡【33,34,35,36】。

CAP 最初是作为一个经验法则提出的，没有准确的定义，目的是开始讨论数据库的权衡。那时候许多分布式数据库侧重于在共享存储的集群上提供线性一致性的语义【18】，CAP 定理鼓励数据库工程师向分布式无共享系统的设计领域深入探索，这类架构更适合实现大规模的网络服务【37】。 对于这种文化上的转变，CAP 值得赞扬 —— 它见证了自 00 年代中期以来新数据库的技术爆炸（即 NoSQL）。

CAP定理没有帮助

CAP 有时以这种面目出现：一致性，可用性和分区容错性：三者只能择其二。不幸的是这种说法很有误导性【32】，因为网络分区是一种故障类型，所以它并不是一个选项：不管你喜不喜欢它都会发生【38】。

在网络正常工作的时候，系统可以提供一致性（线性一致性）和整体可用性。发生网络故障时，你必须在线性一致性和整体可用性之间做出选择。因此，CAP 更好的表述成：在分区时要么选择一致，要么选择可用【39】。一个更可靠的网络需要减少这个选择，但是在某些时候选择是不可避免的。

在 CAP 的讨论中，术语可用性有几个相互矛盾的定义，形式化作为一个定理【30】并不符合其通常的含义【40】。许多所谓的 “高可用”（容错）系统实际上不符合 CAP 对可用性的特殊定义。总而言之，围绕着 CAP 有很多误解和困惑，并不能帮助我们更好地理解系统，所以最好避免使用 CAP。

CAP 定理的正式定义仅限于很狭隘的范围【30】，它只考虑了一个一致性模型（即线性一致性）和一种故障（网络分区 [^vi]，或活跃但彼此断开的节点）。它没有讨论任何关于网络延迟，死亡节点或其他权衡的事。 因此，尽管 CAP 在历史上有一些影响力，但对于设计系统而言并没有实际价值【9,40】。

在分布式系统中有更多有趣的 “不可能” 的结果【41】，且 CAP 定理现在已经被更精确的结果取代【2,42】，所以它现在基本上成了历史古迹了。

[^vi]: 正如 “真实世界的网络故障” 中所讨论的，本书使用 分区（partition） 指代将大数据集细分为小数据集的操作（分片；请参阅 第六章）。与之对应的是，网络分区（network partition） 是一种特定类型的网络故障，我们通常不会将其与其他类型的故障分开考虑。但是，由于它是 CAP 的 P，所以这种情况下我们无法避免混乱。

线性一致性和网络延迟

虽然线性一致是一个很有用的保证，但实际上，线性一致的系统惊人的少。例如，现代多核 CPU 上的内存甚至都不是线性一致的【43】：如果一个 CPU 核上运行的线程写入某个内存地址，而另一个 CPU 核上运行的线程不久之后读取相同的地址，并没有保证一定能读到第一个线程写入的值（除非使用了 内存屏障（memory barrier） 或 围栏（fence）【44】）。

这种行为的原因是每个 CPU 核都有自己的内存缓存和存储缓冲区。默认情况下，内存访问首先走缓存，任何变更会异步写入主存。因为缓存访问比主存要快得多【45】，所以这个特性对于现代 CPU 的良好性能表现至关重要。但是现在就有几个数据副本（一个在主存中，也许还有几个在不同缓存中的其他副本），而且这些副本是异步更新的，所以就失去了线性一致性。

为什么要做这个权衡？对多核内存一致性模型而言，CAP 定理是没有意义的：在同一台计算机中，我们通常假定通信都是可靠的。并且我们并不指望一个 CPU 核能在脱离计算机其他部分的条件下继续正常工作。牺牲线性一致性的原因是 性能（performance），而不是容错。

许多分布式数据库也是如此：它们是 为了提高性能 而选择了牺牲线性一致性，而不是为了容错【46】。线性一致的速度很慢 —— 这始终是事实，而不仅仅是网络故障期间。

能找到一个更高效的线性一致存储实现吗？看起来答案是否定的：Attiya 和 Welch 【47】证明，如果你想要线性一致性，读写请求的响应时间至少与网络延迟的不确定性成正比。在像大多数计算机网络一样具有高度可变延迟的网络中（请参阅 “超时与无穷的延迟”），线性读写的响应时间不可避免地会很高。更快地线性一致算法不存在，但更弱的一致性模型可以快得多，所以对延迟敏感的系统而言，这类权衡非常重要。在 第十二章 中将讨论一些在不牺牲正确性的前提下，绕开线性一致性的方法。

顺序保证

之前说过，线性一致寄存器的行为就好像只有单个数据副本一样，且每个操作似乎都是在某个时间点以原子性的方式生效的。这个定义意味着操作是按照某种良好定义的顺序执行的。我们将操作以看上去被执行的顺序连接起来，以此说明了 图 9-4 中的顺序。

顺序（ordering） 这一主题在本书中反复出现，这表明它可能是一个重要的基础性概念。让我们简要回顾一下其它曾经出现过 顺序 的上下文：

• 在 第五章 中我们看到，领导者在单主复制中的主要目的就是，在复制日志中确定 写入顺序（order of write）—— 也就是从库应用这些写入的顺序。如果不存在一个领导者，则并发操作可能导致冲突（请参阅 “处理写入冲突”）。
• 在 第七章 中讨论的 可串行化，是关于事务表现的像按 某种先后顺序（some sequential order） 执行的保证。它可以字面意义上地以 串行顺序（serial order） 执行事务来实现，或者允许并行执行，但同时防止序列化冲突来实现（通过锁或中止事务）。
• 在 第八章 讨论过的在分布式系统中使用时间戳和时钟（请参阅 “依赖同步时钟”）是另一种将顺序引入无序世界的尝试，例如，确定两个写入操作哪一个更晚发生。

事实证明，顺序、线性一致性和共识之间有着深刻的联系。尽管这个概念比本书其他部分更加理论化和抽象，但对于明确系统的能力范围（可以做什么和不可以做什么）而言是非常有帮助的。我们将在接下来的几节中探讨这个话题。

顺序与因果关系

顺序 反复出现有几个原因，其中一个原因是，它有助于保持 因果关系（causality）。在本书中我们已经看到了几个例子，其中因果关系是很重要的：

• 在 “一致前缀读”（图 5-5）中，我们看到一个例子：一个对话的观察者首先看到问题的答案，然后才看到被回答的问题。这是令人困惑的，因为它违背了我们对 因（cause） 与 果（effect） 的直觉：如果一个问题被回答，显然问题本身得先在那里，因为给出答案的人必须先看到这个问题（假如他们并没有预见未来的超能力）。我们认为在问题和答案之间存在 因果依赖（causal dependency）。
• 图 5-9 中出现了类似的模式，我们看到三位领导者之间的复制，并注意到由于网络延迟，一些写入可能会 “压倒” 其他写入。从其中一个副本的角度来看，好像有一个对尚不存在的记录的更新操作。这里的因果意味着，一条记录必须先被创建，然后才能被更新。
• 在 “检测并发写入” 中我们观察到，如果有两个操作 A 和 B，则存在三种可能性：A 发生在 B 之前，或 B 发生在 A 之前，或者 A 和 B并发。这种 此前发生（happened before） 关系是因果关系的另一种表述：如果 A 在 B 前发生，那么意味着 B 可能已经知道了 A，或者建立在 A 的基础上，或者依赖于 A。如果 A 和 B 是 并发 的，那么它们之间并没有因果联系；换句话说，我们确信 A 和 B 不知道彼此。
• 在事务快照隔离的上下文中（“快照隔离和可重复读”），我们说事务是从一致性快照中读取的。但此语境中 “一致” 到底又是什么意思？这意味着 与因果关系保持一致（consistent with causality）：如果快照包含答案，它也必须包含被回答的问题【48】。在某个时间点观察整个数据库，与因果关系保持一致意味着：因果上在该时间点之前发生的所有操作，其影响都是可见的，但因果上在该时间点之后发生的操作，其影响对观察者不可见。读偏差（read skew） 意味着读取的数据处于违反因果关系的状态（不可重复读，如 图 7-6 所示）。
• 事务之间 写偏差（write skew） 的例子（请参阅 “写入偏差与幻读”）也说明了因果依赖：在 图 7-8 中，爱丽丝被允许离班，因为事务认为鲍勃仍在值班，反之亦然。在这种情况下，离班的动作因果依赖于对当前值班情况的观察。可串行化快照隔离 通过跟踪事务之间的因果依赖来检测写偏差。
• 在爱丽丝和鲍勃看球的例子中（图 9-1），在听到爱丽丝惊呼比赛结果后，鲍勃从服务器得到陈旧结果的事实违背了因果关系：爱丽丝的惊呼因果依赖于得分宣告，所以鲍勃应该也能在听到爱丽斯惊呼后查询到比分。相同的模式在 “跨信道的时序依赖” 一节中，以 “图像大小调整服务” 的伪装再次出现。

因果关系对事件施加了一种 顺序：因在果之前；消息发送在消息收取之前。而且就像现实生活中一样，一件事会导致另一件事：某个节点读取了一些数据然后写入一些结果，另一个节点读取其写入的内容，并依次写入一些其他内容，等等。这些因果依赖的操作链定义了系统中的因果顺序，即，什么在什么之前发生。

如果一个系统服从因果关系所规定的顺序，我们说它是 因果一致（causally consistent） 的。例如，快照隔离提供了因果一致性：当你从数据库中读取到一些数据时，你一定还能够看到其因果前驱（假设在此期间这些数据还没有被删除）。

因果顺序不是全序的

全序（total order） 允许任意两个元素进行比较，所以如果有两个元素，你总是可以说出哪个更大，哪个更小。例如，自然数集是全序的：给定两个自然数，比如说 5 和 13，那么你可以告诉我，13 大于 5。

然而数学集合并不完全是全序的：{a, b} 比 {b, c} 更大吗？好吧，你没法真正比较它们，因为二者都不是对方的子集。我们说它们是 无法比较（incomparable） 的，因此数学集合是 偏序（partially order） 的：在某些情况下，可以说一个集合大于另一个（如果一个集合包含另一个集合的所有元素），但在其他情况下它们是无法比较的 [^译注i]。

[^译注i]: 设 R 为非空集合 A 上的关系，如果 R 是自反的、反对称的和可传递的，则称 R 为 A 上的偏序关系。简称偏序，通常记作≦。一个集合 A 与 A 上的偏序关系 R 一起叫作偏序集，记作 (�,�)(A,R) 或 (�,≦)(A,≦)。全序、偏序、关系、集合，这些概念的精确定义可以参考任意一本离散数学教材。

全序和偏序之间的差异反映在不同的数据库一致性模型中：

• 线性一致性

  在线性一致的系统中，操作是全序的：如果系统表现的就好像只有一个数据副本，并且所有操作都是原子性的，这意味着对任何两个操作，我们总是能判定哪个操作先发生。这个全序在 图 9-4 中以时间线表示。

• 因果性

  我们说过，如果两个操作都没有在彼此 之前发生，那么这两个操作是并发的（请参阅 “此前发生” 的关系和并发）。换句话说，如果两个事件是因果相关的（一个发生在另一个事件之前），则它们之间是有序的，但如果它们是并发的，则它们之间的顺序是无法比较的。这意味着因果关系定义了一个偏序，而不是一个全序：一些操作相互之间是有顺序的，但有些则是无法比较的。

因此，根据这个定义，在线性一致的数据存储中是不存在并发操作的：必须有且仅有一条时间线，所有的操作都在这条时间线上，构成一个全序关系。可能有几个请求在等待处理，但是数据存储确保了每个请求都是在唯一时间线上的某个时间点自动处理的，不存在任何并发。

并发意味着时间线会分岔然后合并 —— 在这种情况下，不同分支上的操作是无法比较的（即并发操作）。在 第五章 中我们看到了这种现象：例如，图 5-14 并不是一条直线的全序关系，而是一堆不同的操作并发进行。图中的箭头指明了因果依赖 —— 操作的偏序。

如果你熟悉像 Git 这样的分布式版本控制系统，那么其版本历史与因果关系图极其相似。通常，一个 提交（Commit） 发生在另一个提交之后，在一条直线上。但是有时你会遇到分支（当多个人同时在一个项目上工作时），合并（Merge） 会在这些并发创建的提交相融合时创建。

线性一致性强于因果一致性

那么因果顺序和线性一致性之间的关系是什么？答案是线性一致性 隐含着（implies） 因果关系：任何线性一致的系统都能正确保持因果性【7】。特别是，如果系统中有多个通信通道（如 图 9-5 中的消息队列和文件存储服务），线性一致性可以自动保证因果性，系统无需任何特殊操作（如在不同组件间传递时间戳）。

线性一致性确保因果性的事实使线性一致系统变得简单易懂，更有吸引力。然而，正如 “线性一致性的代价” 中所讨论的，使系统线性一致可能会损害其性能和可用性，尤其是在系统具有严重的网络延迟的情况下（例如，如果系统在地理上散布）。出于这个原因，一些分布式数据系统已经放弃了线性一致性，从而获得更好的性能，但它们用起来也更为困难。

好消息是存在折衷的可能性。线性一致性并不是保持因果性的唯一途径 —— 还有其他方法。一个系统可以是因果一致的，而无需承担线性一致带来的性能折损（尤其对于 CAP 定理不适用的情况）。实际上在所有的不会被网络延迟拖慢的一致性模型中，因果一致性是可行的最强的一致性模型。而且在网络故障时仍能保持可用【2,42】。

在许多情况下，看上去需要线性一致性的系统，实际上需要的只是因果一致性，因果一致性可以更高效地实现。基于这种观察结果，研究人员正在探索新型的数据库，既能保证因果一致性，且性能与可用性与最终一致的系统类似【49,50,51】。

这方面的研究相当新鲜，其中很多尚未应用到生产系统，仍然有不少挑战需要克服【52,53】。但对于未来的系统而言，这是一个有前景的方向。

捕获因果关系

我们不会在这里讨论非线性一致的系统如何保证因果性的细节，而只是简要地探讨一些关键的思想。

为了维持因果性，你需要知道哪个操作发生在哪个其他操作之前（happened before）。这是一个偏序：并发操作可以以任意顺序进行，但如果一个操作发生在另一个操作之前，那它们必须在所有副本上以那个顺序被处理。因此，当一个副本处理一个操作时，它必须确保所有因果前驱的操作（之前发生的所有操作）已经被处理；如果前面的某个操作丢失了，后面的操作必须等待，直到前面的操作被处理完毕。

为了确定因果依赖，我们需要一些方法来描述系统中节点的 “知识”。如果节点在发出写入 Y 的请求时已经看到了 X 的值，则 X 和 Y 可能存在因果关系。这个分析使用了那些在欺诈指控刑事调查中常见的问题：CEO 在做出决定 Y 时是否 知道 X ？

用于确定 哪些操作发生在其他操作之前 的技术，与我们在 “检测并发写入” 中所讨论的内容类似。那一节讨论了无领导者数据存储中的因果性：为了防止丢失更新，我们需要检测到对同一个键的并发写入。因果一致性则更进一步：它需要跟踪整个数据库中的因果依赖，而不仅仅是一个键。可以推广版本向量以解决此类问题【54】。

为了确定因果顺序，数据库需要知道应用读取了哪个版本的数据。这就是为什么在 图 5-13 中，来自先前操作的版本号在写入时被传回到数据库的原因。在 SSI 的冲突检测中会出现类似的想法，如 “可串行化快照隔离” 中所述：当事务要提交时，数据库将检查它所读取的数据版本是否仍然是最新的。为此，数据库跟踪哪些数据被哪些事务所读取。

序列号顺序

虽然因果是一个重要的理论概念，但实际上跟踪所有的因果关系是不切实际的。在许多应用中，客户端在写入内容之前会先读取大量数据，我们无法弄清写入因果依赖于先前全部的读取内容，还是仅包括其中一部分。显式跟踪所有已读数据意味着巨大的额外开销。

但还有一个更好的方法：我们可以使用 序列号（sequence nunber） 或 时间戳（timestamp） 来排序事件。时间戳不一定来自日历时钟（或物理时钟，它们存在许多问题，如 “不可靠的时钟” 中所述）。它可以来自一个 逻辑时钟（logical clock），这是一个用来生成标识操作的数字序列的算法，典型实现是使用一个每次操作自增的计数器。

这样的序列号或时间戳是紧凑的（只有几个字节大小），它提供了一个全序关系：也就是说每个操作都有一个唯一的序列号，而且总是可以比较两个序列号，确定哪一个更大（即哪些操作后发生）。

特别是，我们可以使用 与因果一致（consistent with causality） 的全序来生成序列号 [^vii]：我们保证，如果操作 A 因果地发生在操作 B 前，那么在这个全序中 A 在 B 前（ A 具有比 B 更小的序列号）。并行操作之间可以任意排序。这样一个全序关系捕获了所有关于因果的信息，但也施加了一个比因果性要求更为严格的顺序。

[^vii]: 与因果关系不一致的全序很容易创建，但没啥用。例如你可以为每个操作生成随机的 UUID，并按照字典序比较 UUID，以定义操作的全序。这是一个有效的全序，但是随机的 UUID 并不能告诉你哪个操作先发生，或者操作是否为并发的。

在单主复制的数据库中（请参阅 “领导者与追随者”），复制日志定义了与因果一致的写操作。主库可以简单地为每个操作自增一个计数器，从而为复制日志中的每个操作分配一个单调递增的序列号。如果一个从库按照它们在复制日志中出现的顺序来应用写操作，那么从库的状态始终是因果一致的（即使它落后于领导者）。

非因果序列号生成器

如果主库不存在（可能因为使用了多主数据库或无主数据库，或者因为使用了分区的数据库），如何为操作生成序列号就没有那么明显了。在实践中有各种各样的方法：

• 每个节点都可以生成自己独立的一组序列号。例如有两个节点，一个节点只能生成奇数，而另一个节点只能生成偶数。通常，可以在序列号的二进制表示中预留一些位，用于唯一的节点标识符，这样可以确保两个不同的节点永远不会生成相同的序列号。
• 可以将日历时钟（物理时钟）的时间戳附加到每个操作上【55】。这种时间戳并不连续，但是如果它具有足够高的分辨率，那也许足以提供一个操作的全序关系。这一事实应用于* 最后写入胜利 * 的冲突解决方法中（请参阅 “有序事件的时间戳”）。
• 可以预先分配序列号区块。例如，节点 A 可能要求从序列号 1 到 1,000 区块的所有权，而节点 B 可能要求序列号 1,001 到 2,000 区块的所有权。然后每个节点可以独立分配所属区块中的序列号，并在序列号告急时请求分配一个新的区块。

这三个选项都比单一主库的自增计数器表现要好，并且更具可伸缩性。它们为每个操作生成一个唯一的，近似自增的序列号。然而它们都有同一个问题：生成的序列号与因果不一致。

因为这些序列号生成器不能正确地捕获跨节点的操作顺序，所以会出现因果关系的问题：

• 每个节点每秒可以处理不同数量的操作。因此，如果一个节点产生偶数序列号而另一个产生奇数序列号，则偶数计数器可能落后于奇数计数器，反之亦然。如果你有一个奇数编号的操作和一个偶数编号的操作，你无法准确地说出哪一个操作在因果上先发生。

• 来自物理时钟的时间戳会受到时钟偏移的影响，这可能会使其与因果不一致。例如 图 8-3 展示了一个例子，其中因果上晚发生的操作，却被分配了一个更早的时间戳。[^vii]

  [^viii]: 可以使物理时钟时间戳与因果关系保持一致：在 “全局快照的同步时钟” 中，我们讨论了 Google 的 Spanner，它可以估计预期的时钟偏差，并在提交写入之前等待不确定性间隔。这种方法确保了实际上靠后的事务会有更大的时间戳。但是大多数时钟不能提供这种所需的不确定性度量。

• 在分配区块的情况下，某个操作可能会被赋予一个范围在 1,001 到 2,000 内的序列号，然而一个因果上更晚的操作可能被赋予一个范围在 1 到 1,000 之间的数字。这里序列号与因果关系也是不一致的。

兰伯特时间戳

尽管刚才描述的三个序列号生成器与因果不一致，但实际上有一个简单的方法来产生与因果关系一致的序列号。它被称为兰伯特时间戳，莱斯利・兰伯特（Leslie Lamport）于 1978 年提出【56】，现在是分布式系统领域中被引用最多的论文之一。

图 9-8 说明了兰伯特时间戳的应用。每个节点都有一个唯一标识符，和一个保存自己执行操作数量的计数器。 兰伯特时间戳就是两者的简单组合：（计数器，节点 ID）(�������,������)(counter,nodeID)。两个节点有时可能具有相同的计数器值，但通过在时间戳中包含节点 ID，每个时间戳都是唯一的。

图 9-8 Lamport 时间戳提供了与因果关系一致的全序。

兰伯特时间戳与物理的日历时钟没有任何关系，但是它提供了一个全序：如果你有两个时间戳，则 计数器 值大者是更大的时间戳。如果计数器值相同，则节点 ID 越大的，时间戳越大。

迄今，这个描述与上节所述的奇偶计数器基本类似。使兰伯特时间戳因果一致的关键思想如下所示：每个节点和每个客户端跟踪迄今为止所见到的最大 计数器 值，并在每个请求中包含这个最大计数器值。当一个节点收到最大计数器值大于自身计数器值的请求或响应时，它立即将自己的计数器设置为这个最大值。

这如 图 9-8 所示，其中客户端 A 从节点 2 接收计数器值 5 ，然后将最大值 5 发送到节点 1 。此时，节点 1 的计数器仅为 1 ，但是它立即前移至 5 ，所以下一个操作的计数器的值为 6 。

只要每一个操作都携带着最大计数器值，这个方案确保兰伯特时间戳的排序与因果一致，因为每个因果依赖都会导致时间戳增长。

兰伯特时间戳有时会与我们在 “检测并发写入” 中看到的版本向量相混淆。虽然两者有一些相似之处，但它们有着不同的目的：版本向量可以区分两个操作是并发的，还是一个因果依赖另一个；而兰伯特时间戳总是施行一个全序。从兰伯特时间戳的全序中，你无法分辨两个操作是并发的还是因果依赖的。 兰伯特时间戳优于版本向量的地方是，它更加紧凑。

光有时间戳排序还不够

虽然兰伯特时间戳定义了一个与因果一致的全序，但它还不足以解决分布式系统中的许多常见问题。

例如，考虑一个需要确保用户名能唯一标识用户帐户的系统。如果两个用户同时尝试使用相同的用户名创建帐户，则其中一个应该成功，另一个应该失败（我们之前在 “领导者和锁” 中提到过这个问题）。

乍看之下，似乎操作的全序关系足以解决这一问题（例如使用兰伯特时间戳）：如果创建了两个具有相同用户名的帐户，选择时间戳较小的那个作为胜者（第一个抓到用户名的人），并让带有更大时间戳者失败。由于时间戳上有全序关系，所以这个比较总是可行的。

这种方法适用于事后确定胜利者：一旦你收集了系统中的所有用户名创建操作，就可以比较它们的时间戳。然而当某个节点需要实时处理用户创建用户名的请求时，这样的方法就无法满足了。节点需要 马上（right now） 决定这个请求是成功还是失败。在那个时刻，节点并不知道是否存在其他节点正在并发执行创建同样用户名的操作，罔论其它节点可能分配给那个操作的时间戳。

为了确保没有其他节点正在使用相同的用户名和较小的时间戳并发创建同名账户，你必须检查其它每个节点，看看它在做什么【56】。如果其中一个节点由于网络问题出现故障或不可达，则整个系统可能被拖至停机。这不是我们需要的那种容错系统。

这里的问题是，只有在所有的操作都被收集之后，操作的全序才会出现。如果另一个节点已经产生了一些操作，但你还不知道那些操作是什么，那就无法构造所有操作最终的全序关系：来自另一个节点的未知操作可能需要被插入到全序中的不同位置。

总之：为了实现诸如用户名上的唯一约束这种东西，仅有操作的全序是不够的，你还需要知道这个全序何时会尘埃落定。如果你有一个创建用户名的操作，并且确定在全序中没有任何其他节点可以在你的操作之前插入对同一用户名的声称，那么你就可以安全地宣告操作执行成功。

如何确定全序关系已经尘埃落定，这将在 全序广播 一节中详细说明。

全序广播

如果你的程序只运行在单个 CPU 核上，那么定义一个操作全序是很容易的：可以简单认为就是 CPU 执行这些操作的顺序。但是在分布式系统中，让所有节点对同一个全局操作顺序达成一致可能相当棘手。在上一节中，我们讨论了按时间戳或序列号进行排序，但发现它还不如单主复制给力（如果你使用时间戳排序来实现唯一性约束，就不能容忍任何错误，因为你必须要从每个节点都获取到最新的序列号）。

如前所述，单主复制通过选择一个节点作为主库来确定操作的全序，并在主库的单个 CPU 核上对所有操作进行排序。接下来的挑战是，如果吞吐量超出单个主库的处理能力，这种情况下如何扩展系统；以及，如果主库失效（“处理节点宕机”），如何处理故障切换。在分布式系统文献中，这个问题被称为 全序广播（total order broadcast） 或 原子广播（atomic broadcast）[^ix]【25,57,58】。

[^ix]: “原子广播” 是一个传统的术语，非常混乱，而且与 “原子” 一词的其他用法不一致：它与 ACID 事务中的原子性没有任何关系，只是与原子操作（在多线程编程的意义上 ）或原子寄存器（线性一致存储）有间接的联系。全序组播（total order multicast）是另一个同义词。

顺序保证的范围

每个分区各有一个主库的分区数据库，通常只在每个分区内维持顺序，这意味着它们不能提供跨分区的一致性保证（例如，一致性快照，外键引用）。 跨所有分区的全序是可能的，但需要额外的协调【59】。

全序广播通常被描述为在节点间交换消息的协议。 非正式地讲，它要满足两个安全属性：

• 可靠交付（reliable delivery）

  没有消息丢失：如果消息被传递到一个节点，它将被传递到所有节点。

• 全序交付（totally ordered delivery）

  消息以相同的顺序传递给每个节点。

正确的全序广播算法必须始终保证可靠性和有序性，即使节点或网络出现故障。当然在网络中断的时候，消息是传不出去的，但是算法可以不断重试，以便在网络最终修复时，消息能及时通过并送达（当然它们必须仍然按照正确的顺序传递）。

使用全序广播

像 ZooKeeper 和 etcd 这样的共识服务实际上实现了全序广播。这一事实暗示了全序广播与共识之间有着紧密联系，我们将在本章稍后进行探讨。

全序广播正是数据库复制所需的：如果每个消息都代表一次数据库的写入，且每个副本都按相同的顺序处理相同的写入，那么副本间将相互保持一致（除了临时的复制延迟）。这个原理被称为 状态机复制（state machine replication）【60】，我们将在 第十一章 中重新回到这个概念。

与之类似，可以使用全序广播来实现可串行化的事务：如 “真的串行执行” 中所述，如果每个消息都表示一个确定性事务，以存储过程的形式来执行，且每个节点都以相同的顺序处理这些消息，那么数据库的分区和副本就可以相互保持一致【61】。

全序广播的一个重要表现是，顺序在消息送达时被固化：如果后续的消息已经送达，节点就不允许追溯地将（先前）消息插入顺序中的较早位置。这个事实使得全序广播比时间戳排序更强。

考量全序广播的另一种方式是，这是一种创建日志的方式（如在复制日志、事务日志或预写式日志中）：传递消息就像追加写入日志。由于所有节点必须以相同的顺序传递相同的消息，因此所有节点都可以读取日志，并看到相同的消息序列。

全序广播对于实现提供防护令牌的锁服务也很有用（请参阅 “防护令牌”）。每个获取锁的请求都作为一条消息追加到日志末尾，并且所有的消息都按它们在日志中出现的顺序依次编号。序列号可以当成防护令牌用，因为它是单调递增的。在 ZooKeeper 中，这个序列号被称为 zxid 【15】。

使用全序广播实现线性一致的存储

如 图 9-4 所示，在线性一致的系统中，存在操作的全序。这是否意味着线性一致与全序广播一样？不尽然，但两者之间有着密切的联系 [^x]。

[^x]: 从形式上讲，线性一致读写寄存器是一个 “更容易” 的问题。 全序广播等价于共识【67】，而共识问题在异步的崩溃 - 停止模型【68】中没有确定性的解决方案，而线性一致的读写寄存器 可以 在这种模型中实现【23,24,25】。 然而，支持诸如 比较并设置（CAS, compare-and-set），或 自增并返回（increment-and-get） 的原子操作使它等价于共识问题【28】。 因此，共识问题与线性一致寄存器问题密切相关。

全序广播是异步的：消息被保证以固定的顺序可靠地传送，但是不能保证消息 何时 被送达（所以一个接收者可能落后于其他接收者）。相比之下，线性一致性是新鲜性的保证：读取一定能看见最新的写入值。

但如果有了全序广播，你就可以在此基础上构建线性一致的存储。例如，你可以确保用户名能唯一标识用户帐户。

设想对于每一个可能的用户名，你都可以有一个带有 CAS 原子操作的线性一致寄存器。每个寄存器最初的值为空值（表示未使用该用户名）。当用户想要创建一个用户名时，对该用户名的寄存器执行 CAS 操作，在先前寄存器值为空的条件，将其值设置为用户的账号 ID。如果多个用户试图同时获取相同的用户名，则只有一个 CAS 操作会成功，因为其他用户会看到非空的值（由于线性一致性）。

你可以通过将全序广播当成仅追加日志【62,63】的方式来实现这种线性一致的 CAS 操作：

1. 在日志中追加一条消息，试探性地指明你要声明的用户名。
2. 读日志，并等待你刚才追加的消息被读回。[^xi]
3. 检查是否有任何消息声称目标用户名的所有权。如果这些消息中的第一条就是你自己的消息，那么你就成功了：你可以提交声称的用户名（也许是通过向日志追加另一条消息）并向客户端确认。如果所需用户名的第一条消息来自其他用户，则中止操作。

[^xi]: 如果你不等待，而是在消息入队之后立即确认写入，则会得到类似于多核 x86 处理器内存的一致性模型【43】。 该模型既不是线性一致的也不是顺序一致的。

由于日志项是以相同顺序送达至所有节点，因此如果有多个并发写入，则所有节点会对最先到达者达成一致。选择冲突写入中的第一个作为胜利者，并中止后来者，以此确定所有节点对某个写入是提交还是中止达成一致。类似的方法可以在一个日志的基础上实现可串行化的多对象事务【62】。

尽管这一过程保证写入是线性一致的，但它并不保证读取也是线性一致的 —— 如果你从与日志异步更新的存储中读取数据，结果可能是陈旧的。 （精确地说，这里描述的过程提供了 顺序一致性（sequential consistency）【47,64】，有时也称为 时间线一致性（timeline consistency）【65,66】，比线性一致性稍微弱一些的保证）。为了使读取也线性一致，有几个选项：

• 你可以通过在日志中追加一条消息，然后读取日志，直到该消息被读回才执行实际的读取操作。消息在日志中的位置因此定义了读取发生的时间点（etcd 的法定人数读取有些类似这种情况【16】）。
• 如果日志允许以线性一致的方式获取最新日志消息的位置，则可以查询该位置，等待该位置前的所有消息都传达到你，然后执行读取。 （这是 Zookeeper sync() 操作背后的思想【15】）。
• 你可以从同步更新的副本中进行读取，因此可以确保结果是最新的（这种技术用于链式复制（chain replication）【63】；请参阅 “关于复制的研究”）。

使用线性一致性存储实现全序广播

上一节介绍了如何从全序广播构建一个线性一致的 CAS 操作。我们也可以把它反过来，假设我们有线性一致的存储，接下来会展示如何在此基础上构建全序广播。

最简单的方法是假设你有一个线性一致的寄存器来存储一个整数，并且有一个原子 自增并返回 操作【28】。或者原子 CAS 操作也可以完成这项工作。

该算法很简单：每个要通过全序广播发送的消息首先对线性一致寄存器执行 自增并返回 操作。然后将从寄存器获得的值作为序列号附加到消息中。然后你可以将消息发送到所有节点（重新发送任何丢失的消息），而收件人将按序列号依序传递（deliver）消息。

请注意，与兰伯特时间戳不同，通过自增线性一致性寄存器获得的数字形式上是一个没有间隙的序列。因此，如果一个节点已经发送了消息 4 并且接收到序列号为 6 的传入消息，则它知道它在传递消息 6 之前必须等待消息 5 。兰伯特时间戳则与之不同 —— 事实上，这是全序广播和时间戳排序间的关键区别。

实现一个带有原子性 自增并返回 操作的线性一致寄存器有多困难？像往常一样，如果事情从来不出差错，那很容易：你可以简单地把它保存在单个节点内的变量中。问题在于处理当该节点的网络连接中断时的情况，并在该节点失效时能恢复这个值【59】。一般来说，如果你对线性一致性的序列号生成器进行过足够深入的思考，你不可避免地会得出一个共识算法。

这并非巧合：可以证明，线性一致的 CAS（或自增并返回）寄存器与全序广播都等价于 共识 问题【28,67】。也就是说，如果你能解决其中的一个问题，你可以把它转化成为其他问题的解决方案。这是相当深刻和令人惊讶的洞察！

现在是时候正面处理共识问题了，我们将在本章的其余部分进行讨论。

9.4 分布式事务与共识

共识 是分布式计算中最重要也是最基本的问题之一。从表面上看似乎很简单：非正式地讲，目标只是 让几个节点达成一致（get serveral nodes to agree on something）。你也许会认为这不会太难。不幸的是，许多出故障的系统都是因为错误地轻信这个问题很容易解决。

尽管共识非常重要，但关于它的内容出现在本书的后半部分，因为这个主题非常微妙，欣赏细微之处需要一些必要的知识。即使在学术界，对共识的理解也是在几十年的过程中逐渐沉淀而来，一路上也有着许多误解。现在我们已经讨论了复制（第五章），事务（第七章），系统模型（第八章），线性一致以及全序广播（本章），我们终于准备好解决共识问题了。

节点能达成一致，在很多场景下都非常重要，例如：

• 领导选举

  在单主复制的数据库中，所有节点需要就哪个节点是领导者达成一致。如果一些节点由于网络故障而无法与其他节点通信，则可能会对领导权的归属引起争议。在这种情况下，共识对于避免错误的故障切换非常重要。错误的故障切换会导致两个节点都认为自己是领导者（脑裂，请参阅 “处理节点宕机”）。如果有两个领导者，它们都会接受写入，它们的数据会发生分歧，从而导致不一致和数据丢失。

• 原子提交

  在支持跨多节点或跨多分区事务的数据库中，一个事务可能在某些节点上失败，但在其他节点上成功。如果我们想要维护事务的原子性（就 ACID 而言，请参阅 “原子性”），我们必须让所有节点对事务的结果达成一致：要么全部中止 / 回滚（如果出现任何错误），要么它们全部提交（如果没有出错）。这个共识的例子被称为 原子提交（atomic commit） 问题 [^xii]。

  [^xii]: 原子提交的形式化与共识稍有不同：原子事务只有在 所有 参与者投票提交的情况下才能提交，如果有任何参与者需要中止，则必须中止。 共识则允许就 任意一个 被参与者提出的候选值达成一致。 然而，原子提交和共识可以相互简化为对方【70,71】。 非阻塞 原子提交则要比共识更为困难 —— 请参阅 “三阶段提交”。

共识的不可能性

你可能已经听说过以作者 Fischer，Lynch 和 Paterson 命名的 FLP 结果【68】，它证明，如果存在节点可能崩溃的风险，则不存在 总是 能够达成共识的算法。在分布式系统中，我们必须假设节点可能会崩溃，所以可靠的共识是不可能的。然而这里我们正在讨论达成共识的算法，到底是怎么回事？

答案是 FLP 结果是在 异步系统模型 中被证明的（请参阅 “系统模型与现实”），而这是一种限制性很强的模型，它假定确定性算法不能使用任何时钟或超时。如果允许算法使用 超时 或其他方法来识别可疑的崩溃节点（即使怀疑有时是错误的），则共识变为一个可解的问题【67】。即使仅仅允许算法使用随机数，也足以绕过这个不可能的结果【69】。

因此，虽然 FLP 是关于共识不可能性的重要理论结果，但现实中的分布式系统通常是可以达成共识的。

在本节中，我们将首先更详细地研究 原子提交 问题。具体来说，我们将讨论 两阶段提交（2PC, two-phase commit） 算法，这是解决原子提交问题最常见的办法，并在各种数据库、消息队列和应用服务器中被实现。事实证明 2PC 是一种共识算法，但不是一个非常好的共识算法【70,71】。

通过对 2PC 的学习，我们将继续努力实现更好的一致性算法，比如 ZooKeeper（Zab）和 etcd（Raft）中使用的算法。

原子提交与两阶段提交

在 第七章 中我们了解到，事务原子性的目的是在多次写操作中途出错的情况下，提供一种简单的语义。事务的结果要么是成功提交，在这种情况下，事务的所有写入都是持久化的；要么是中止，在这种情况下，事务的所有写入都被回滚（即撤消或丢弃）。

原子性可以防止失败的事务搅乱数据库，避免数据库陷入半成品结果和半更新状态。这对于多对象事务（请参阅 “单对象和多对象操作”）和维护次级索引的数据库尤其重要。每个次级索引都是与主数据相分离的数据结构 —— 因此，如果你修改了一些数据，则还需要在次级索引中进行相应的更改。原子性确保次级索引与主数据保持一致（如果索引与主数据不一致，就没什么用了）。

从单节点到分布式原子提交

对于在单个数据库节点执行的事务，原子性通常由存储引擎实现。当客户端请求数据库节点提交事务时，数据库将使事务的写入持久化（通常在预写式日志中，请参阅 “让 B 树更可靠”），然后将提交记录追加到磁盘中的日志里。如果数据库在这个过程中间崩溃，当节点重启时，事务会从日志中恢复：如果提交记录在崩溃之前成功地写入磁盘，则认为事务被提交；否则来自该事务的任何写入都被回滚。

因此，在单个节点上，事务的提交主要取决于数据持久化落盘的 顺序：首先是数据，然后是提交记录【72】。事务提交或终止的关键决定时刻是磁盘完成写入提交记录的时刻：在此之前，仍有可能中止（由于崩溃），但在此之后，事务已经提交（即使数据库崩溃）。因此，是单一的设备（连接到单个磁盘的控制器，且挂载在单台机器上）使得提交具有原子性。

但是，如果一个事务中涉及多个节点呢？例如，你也许在分区数据库中会有一个多对象事务，或者是一个按关键词分区的次级索引（其中索引条目可能位于与主数据不同的节点上；请参阅 “分区与次级索引”）。大多数 “NoSQL” 分布式数据存储不支持这种分布式事务，但是很多关系型数据库集群支持（请参阅 “实践中的分布式事务”）。

在这些情况下，仅向所有节点发送提交请求并独立提交每个节点的事务是不够的。这样很容易发生违反原子性的情况：提交在某些节点上成功，而在其他节点上失败：

• 某些节点可能会检测到违反约束或冲突，因此需要中止，而其他节点则可以成功进行提交。
• 某些提交请求可能在网络中丢失，最终由于超时而中止，而其他提交请求则通过。
• 在提交记录完全写入之前，某些节点可能会崩溃，并在恢复时回滚，而其他节点则成功提交。

如果某些节点提交了事务，但其他节点却放弃了这些事务，那么这些节点就会彼此不一致（如 图 7-3 所示）。而且一旦在某个节点上提交了一个事务，如果事后发现它在其它节点上被中止了，它是无法撤回的。出于这个原因，一旦确定事务中的所有其他节点也将提交，节点就必须进行提交。

事务提交必须是不可撤销的 —— 事务提交之后，你不能改变主意，并追溯性地中止事务。这个规则的原因是，一旦数据被提交，其结果就对其他事务可见，因此其他客户端可能会开始依赖这些数据。这个原则构成了 读已提交 隔离等级的基础，在 “读已提交” 一节中讨论了这个问题。如果一个事务在提交后被允许中止，所有那些读取了 已提交却又被追溯声明不存在数据 的事务也必须回滚。

（提交事务的结果有可能通过事后执行另一个补偿事务（compensating transaction）来取消【73,74】，但从数据库的角度来看，这是一个单独的事务，因此任何关于跨事务正确性的保证都是应用自己的问题。）

两阶段提交简介

两阶段提交（two-phase commit） 是一种用于实现跨多个节点的原子事务提交的算法，即确保所有节点提交或所有节点中止。 它是分布式数据库中的经典算法【13,35,75】。 2PC 在某些数据库内部使用，也以 XA 事务 的形式对应用可用【76,77】（例如 Java Transaction API 支持）或以 SOAP Web 服务的 WS-AtomicTransaction 形式提供给应用【78,79】。

图 9-9 说明了 2PC 的基本流程。2PC 中的提交 / 中止过程分为两个阶段（因此而得名），而不是单节点事务中的单个提交请求。

图 9-9 两阶段提交（2PC）的成功执行

不要把2PC和2PL搞混了

两阶段提交（2PC）和两阶段锁定（请参阅 “两阶段锁定”）是两个完全不同的东西。 2PC 在分布式数据库中提供原子提交，而 2PL 提供可串行化的隔离等级。为了避免混淆，最好把它们看作完全独立的概念，并忽略名称中不幸的相似性。

2PC 使用一个通常不会出现在单节点事务中的新组件：协调者（coordinator，也称为 事务管理器，即 transaction manager）。协调者通常在请求事务的相同应用进程中以库的形式实现（例如，嵌入在 Java EE 容器中），但也可以是单独的进程或服务。这种协调者的例子包括 Narayana、JOTM、BTM 或 MSDTC。

正常情况下，2PC 事务以应用在多个数据库节点上读写数据开始。我们称这些数据库节点为 参与者（participants）。当应用准备提交时，协调者开始阶段 1 ：它发送一个 准备（prepare） 请求到每个节点，询问它们是否能够提交。然后协调者会跟踪参与者的响应：

• 如果所有参与者都回答 “是”，表示它们已经准备好提交，那么协调者在阶段 2 发出 提交（commit） 请求，然后提交真正发生。
• 如果任意一个参与者回复了 “否”，则协调者在阶段 2 中向所有节点发送 中止（abort） 请求。

这个过程有点像西方传统婚姻仪式：司仪分别询问新娘和新郎是否要结婚，通常是从两方都收到 “我愿意” 的答复。收到两者的回复后，司仪宣布这对情侣成为夫妻：事务就提交了，这一幸福事实会广播至所有的参与者中。如果新娘与新郎之一没有回复 “我愿意”，婚礼就会中止【73】。

系统承诺

这个简短的描述可能并没有说清楚为什么两阶段提交保证了原子性，而跨多个节点的一阶段提交却没有。在两阶段提交的情况下，准备请求和提交请求当然也可以轻易丢失。 2PC 又有什么不同呢？

为了理解它的工作原理，我们必须更详细地分解这个过程：

1. 当应用想要启动一个分布式事务时，它向协调者请求一个事务 ID。此事务 ID 是全局唯一的。
2. 应用在每个参与者上启动单节点事务，并在单节点事务上捎带上这个全局事务 ID。所有的读写都是在这些单节点事务中各自完成的。如果在这个阶段出现任何问题（例如，节点崩溃或请求超时），则协调者或任何参与者都可以中止。
3. 当应用准备提交时，协调者向所有参与者发送一个 准备 请求，并打上全局事务 ID 的标记。如果任意一个请求失败或超时，则协调者向所有参与者发送针对该事务 ID 的中止请求。
4. 参与者收到准备请求时，需要确保在任意情况下都的确可以提交事务。这包括将所有事务数据写入磁盘（出现故障，电源故障，或硬盘空间不足都不能是稍后拒绝提交的理由）以及检查是否存在任何冲突或违反约束。通过向协调者回答 “是”，节点承诺，只要请求，这个事务一定可以不出差错地提交。换句话说，参与者放弃了中止事务的权利，但没有实际提交。
5. 当协调者收到所有准备请求的答复时，会就提交或中止事务作出明确的决定（只有在所有参与者投赞成票的情况下才会提交）。协调者必须把这个决定写到磁盘上的事务日志中，如果它随后就崩溃，恢复后也能知道自己所做的决定。这被称为 提交点（commit point）。
6. 一旦协调者的决定落盘，提交或放弃请求会发送给所有参与者。如果这个请求失败或超时，协调者必须永远保持重试，直到成功为止。没有回头路：如果已经做出决定，不管需要多少次重试它都必须被执行。如果参与者在此期间崩溃，事务将在其恢复后提交 —— 由于参与者投了赞成，因此恢复后它不能拒绝提交。

因此，该协议包含两个关键的 “不归路” 点：当参与者投票 “是” 时，它承诺它稍后肯定能够提交（尽管协调者可能仍然选择放弃）；以及一旦协调者做出决定，这一决定是不可撤销的。这些承诺保证了 2PC 的原子性（单节点原子提交将这两个事件合为了一体：将提交记录写入事务日志）。

回到婚姻的比喻，在说 “我愿意” 之前，你和你的新娘 / 新郎有中止这个事务的自由，只要回复 “没门！” 就行（或者有类似效果的话）。然而在说了 “我愿意” 之后，你就不能撤回那个声明了。如果你说 “我愿意” 后晕倒了，没有听到司仪说 “你们现在是夫妻了”，那也并不会改变事务已经提交的现实。当你稍后恢复意识时，可以通过查询司仪的全局事务 ID 状态来确定你是否已经成婚，或者你可以等待司仪重试下一次提交请求（因为重试将在你无意识期间一直持续）。

协调者失效

我们已经讨论了在 2PC 期间，如果参与者之一或网络发生故障时会发生什么情况：如果任何一个 准备 请求失败或者超时，协调者就会中止事务。如果任何提交或中止请求失败，协调者将无条件重试。但是如果协调者崩溃，会发生什么情况就不太清楚了。

如果协调者在发送 准备 请求之前失败，参与者可以安全地中止事务。但是，一旦参与者收到了准备请求并投了 “是”，就不能再单方面放弃 —— 必须等待协调者回答事务是否已经提交或中止。如果此时协调者崩溃或网络出现故障，参与者什么也做不了只能等待。参与者的这种事务状态称为 存疑（in doubt） 的或 不确定（uncertain） 的。

情况如 图 9-10 所示。在这个特定的例子中，协调者实际上决定提交，数据库 2 收到提交请求。但是，协调者在将提交请求发送到数据库 1 之前发生崩溃，因此数据库 1 不知道是否提交或中止。即使 超时 在这里也没有帮助：如果数据库 1 在超时后单方面中止，它将最终与执行提交的数据库 2 不一致。同样，单方面提交也是不安全的，因为另一个参与者可能已经中止了。

图 9-10 参与者投赞成票后，协调者崩溃。数据库 1 不知道是否提交或中止

没有协调者的消息，参与者无法知道是提交还是放弃。原则上参与者可以相互沟通，找出每个参与者是如何投票的，并达成一致，但这不是 2PC 协议的一部分。

可以完成 2PC 的唯一方法是等待协调者恢复。这就是为什么协调者必须在向参与者发送提交或中止请求之前，将其提交或中止决定写入磁盘上的事务日志：协调者恢复后，通过读取其事务日志来确定所有存疑事务的状态。任何在协调者日志中没有提交记录的事务都会中止。因此，2PC 的 提交点 归结为协调者上的常规单节点原子提交。

三阶段提交

两阶段提交被称为 阻塞（blocking）- 原子提交协议，因为存在 2PC 可能卡住并等待协调者恢复的情况。理论上，可以使一个原子提交协议变为 非阻塞（nonblocking） 的，以便在节点失败时不会卡住。但是让这个协议能在实践中工作并没有那么简单。

作为 2PC 的替代方案，已经提出了一种称为 三阶段提交（3PC） 的算法【13,80】。然而，3PC 假定网络延迟有界，节点响应时间有限；在大多数具有无限网络延迟和进程暂停的实际系统中（见 第八章），它并不能保证原子性。

通常，非阻塞原子提交需要一个 完美的故障检测器（perfect failure detector）【67,71】—— 即一个可靠的机制来判断一个节点是否已经崩溃。在具有无限延迟的网络中，超时并不是一种可靠的故障检测机制，因为即使没有节点崩溃，请求也可能由于网络问题而超时。出于这个原因，2PC 仍然被使用，尽管大家都清楚可能存在协调者故障的问题。

实践中的分布式事务

分布式事务的名声毁誉参半，尤其是那些通过两阶段提交实现的。一方面，它被视作提供了一个难以实现的重要的安全性保证；另一方面，它们因为导致运维问题，造成性能下降，做出超过能力范围的承诺而饱受批评【81,82,83,84】。许多云服务由于其导致的运维问题，而选择不实现分布式事务【85,86】。

分布式事务的某些实现会带来严重的性能损失 —— 例如据报告称，MySQL 中的分布式事务比单节点事务慢 10 倍以上【87】，所以当人们建议不要使用它们时就不足为奇了。两阶段提交所固有的性能成本，大部分是由于崩溃恢复所需的额外强制刷盘（fsync）【88】以及额外的网络往返。

但我们不应该直接忽视分布式事务，而应当更加仔细地审视这些事务，因为从中可以汲取重要的经验教训。首先，我们应该精确地说明 “分布式事务” 的含义。两种截然不同的分布式事务类型经常被混淆：

• 数据库内部的分布式事务

  一些分布式数据库（即在其标准配置中使用复制和分区的数据库）支持数据库节点之间的内部事务。例如，VoltDB 和 MySQL Cluster 的 NDB 存储引擎就有这样的内部事务支持。在这种情况下，所有参与事务的节点都运行相同的数据库软件。

• 异构分布式事务

  在 异构（heterogeneous） 事务中，参与者是由两种或两种以上的不同技术组成的：例如来自不同供应商的两个数据库，甚至是非数据库系统（如消息代理）。跨系统的分布式事务必须确保原子提交，尽管系统可能完全不同。

数据库内部事务不必与任何其他系统兼容，因此它们可以使用任何协议，并能针对特定技术进行特定的优化。因此数据库内部的分布式事务通常工作地很好。另一方面，跨异构技术的事务则更有挑战性。

恰好一次的消息处理

异构的分布式事务处理能够以强大的方式集成不同的系统。例如：消息队列中的一条消息可以被确认为已处理，当且仅当用于处理消息的数据库事务成功提交。这是通过在同一个事务中原子提交 消息确认 和 数据库写入 两个操作来实现的。藉由分布式事务的支持，即使消息代理和数据库是在不同机器上运行的两种不相关的技术，这种操作也是可能的。

如果消息传递或数据库事务任意一者失败，两者都会中止，因此消息代理可能会在稍后安全地重传消息。因此，通过原子提交 消息处理及其副作用，即使在成功之前需要几次重试，也可以确保消息被 有效地（effectively） 恰好处理一次。中止会抛弃部分完成事务所导致的任何副作用。

然而，只有当所有受事务影响的系统都使用同样的 原子提交协议（atomic commit protocol） 时，这样的分布式事务才是可能的。例如，假设处理消息的副作用是发送一封邮件，而邮件服务器并不支持两阶段提交：如果消息处理失败并重试，则可能会发送两次或更多次的邮件。但如果处理消息的所有副作用都可以在事务中止时回滚，那么这样的处理流程就可以安全地重试，就好像什么都没有发生过一样。

在 第十一章 中将再次回到 “恰好一次” 消息处理的主题。让我们先来看看允许这种异构分布式事务的原子提交协议。

XA事务

X/Open XA（扩展架构（eXtended Architecture） 的缩写）是跨异构技术实现两阶段提交的标准【76,77】。它于 1991 年推出并得到了广泛的实现：许多传统关系数据库（包括 PostgreSQL、MySQL、DB2、SQL Server 和 Oracle）和消息代理（包括 ActiveMQ、HornetQ、MSMQ 和 IBM MQ） 都支持 XA。

XA 不是一个网络协议 —— 它只是一个用来与事务协调者连接的 C API。其他语言也有这种 API 的绑定；例如在 Java EE 应用的世界中，XA 事务是使用 Java 事务 API（JTA, Java Transaction API） 实现的，而许多使用 Java 数据库连接（JDBC, Java Database Connectivity） 的数据库驱动，以及许多使用 Java 消息服务（JMS） API 的消息代理都支持 Java 事务 API（JTA）。

XA 假定你的应用使用网络驱动或客户端库来与 参与者（数据库或消息服务）进行通信。如果驱动支持 XA，则意味着它会调用 XA API 以查明操作是否为分布式事务的一部分 —— 如果是，则将必要的信息发往数据库服务器。驱动还会向协调者暴露回调接口，协调者可以通过回调来要求参与者准备、提交或中止。

事务协调者需要实现 XA API。标准没有指明应该如何实现，但实际上协调者通常只是一个库，被加载到发起事务的应用的同一个进程中（而不是单独的服务）。它在事务中跟踪所有的参与者，并在要求它们 准备 之后收集参与者的响应（通过驱动回调），并使用本地磁盘上的日志记录每次事务的决定（提交 / 中止）。

如果应用进程崩溃，或者运行应用的机器报销了，协调者也随之往生极乐。然后任何带有 准备了 但未提交事务的参与者都会在疑虑中卡死。由于协调程序的日志位于应用服务器的本地磁盘上，因此必须重启该服务器，且协调程序库必须读取日志以恢复每个事务的提交 / 中止结果。只有这样，协调者才能使用数据库驱动的 XA 回调来要求参与者提交或中止。数据库服务器不能直接联系协调者，因为所有通信都必须通过客户端库。

怀疑时持有锁

为什么我们这么关心存疑事务？系统的其他部分就不能继续正常工作，无视那些终将被清理的存疑事务吗？

问题在于 锁（locking）。正如在 “读已提交” 中所讨论的那样，数据库事务通常获取待修改的行上的 行级排他锁，以防止脏写。此外，如果要使用可串行化的隔离等级，则使用两阶段锁定的数据库也必须为事务所读取的行加上共享锁（请参阅 “两阶段锁定”）。

在事务提交或中止之前，数据库不能释放这些锁（如 图 9-9 中的阴影区域所示）。因此，在使用两阶段提交时，事务必须在整个存疑期间持有这些锁。如果协调者已经崩溃，需要 20 分钟才能重启，那么这些锁将会被持有 20 分钟。如果协调者的日志由于某种原因彻底丢失，这些锁将被永久持有 —— 或至少在管理员手动解决该情况之前。

当这些锁被持有时，其他事务不能修改这些行。根据数据库的不同，其他事务甚至可能因为读取这些行而被阻塞。因此，其他事务没法儿简单地继续它们的业务了 —— 如果它们要访问同样的数据，就会被阻塞。这可能会导致应用大面积进入不可用状态，直到存疑事务被解决。

从协调者故障中恢复

理论上，如果协调者崩溃并重新启动，它应该干净地从日志中恢复其状态，并解决任何存疑事务。然而在实践中，孤立（orphaned） 的存疑事务确实会出现【89,90】，即无论出于何种理由，协调者无法确定事务的结果（例如事务日志已经由于软件错误丢失或损坏）。这些事务无法自动解决，所以它们永远待在数据库中，持有锁并阻塞其他事务。

即使重启数据库服务器也无法解决这个问题，因为在 2PC 的正确实现中，即使重启也必须保留存疑事务的锁（否则就会冒违反原子性保证的风险）。这是一种棘手的情况。

唯一的出路是让管理员手动决定提交还是回滚事务。管理员必须检查每个存疑事务的参与者，确定是否有任何参与者已经提交或中止，然后将相同的结果应用于其他参与者。解决这个问题潜在地需要大量的人力，并且可能发生在严重的生产中断期间（不然为什么协调者处于这种糟糕的状态），并很可能要在巨大精神压力和时间压力下完成。

许多 XA 的实现都有一个叫做 启发式决策（heuristic decisions） 的紧急逃生舱口：允许参与者单方面决定放弃或提交一个存疑事务，而无需协调者做出最终决定【76,77,91】。要清楚的是，这里 启发式 是 可能破坏原子性（probably breaking atomicity） 的委婉说法，因为它违背了两阶段提交的系统承诺。因此，启发式决策只是为了逃出灾难性的情况而准备的，而不是为了日常使用的。

分布式事务的限制

XA 事务解决了保持多个参与者（数据系统）相互一致的现实的和重要的问题，但正如我们所看到的那样，它也引入了严重的运维问题。特别来讲，这里的核心认识是：事务协调者本身就是一种数据库（存储了事务的结果），因此需要像其他重要数据库一样小心地打交道：

• 如果协调者没有复制，而是只在单台机器上运行，那么它是整个系统的失效单点（因为它的失效会导致其他应用服务器阻塞在存疑事务持有的锁上）。令人惊讶的是，许多协调者实现默认情况下并不是高可用的，或者只有基本的复制支持。
• 许多服务器端应用都是使用无状态模式开发的（受 HTTP 的青睐），所有持久状态都存储在数据库中，因此具有应用服务器可随意按需添加删除的优点。但是，当协调者成为应用服务器的一部分时，它会改变部署的性质。突然间，协调者的日志成为持久系统状态的关键部分 —— 与数据库本身一样重要，因为协调者日志是为了在崩溃后恢复存疑事务所必需的。这样的应用服务器不再是无状态的了。
• 由于 XA 需要兼容各种数据系统，因此它必须是所有系统的最小公分母。例如，它不能检测不同系统间的死锁（因为这将需要一个标准协议来让系统交换每个事务正在等待的锁的信息），而且它无法与 SSI（请参阅 可串行化快照隔离）协同工作，因为这需要一个跨系统定位冲突的协议。
• 对于数据库内部的分布式事务（不是 XA），限制没有这么大 —— 例如，分布式版本的 SSI 是可能的。然而仍然存在问题：2PC 成功提交一个事务需要所有参与者的响应。因此，如果系统的 任何 部分损坏，事务也会失败。因此，分布式事务又有 扩大失效（amplifying failures） 的趋势，这又与我们构建容错系统的目标背道而驰。

这些事实是否意味着我们应该放弃保持几个系统相互一致的所有希望？不完全是 —— 还有其他的办法，可以让我们在没有异构分布式事务的痛苦的情况下实现同样的事情。我们将在 第十一章 和 第十二章 回到这些话题。但首先，我们应该概括一下关于 共识 的话题。

容错共识

非正式地，共识意味着让几个节点就某事达成一致。例如，如果有几个人 同时（concurrently） 尝试预订飞机上的最后一个座位，或剧院中的同一个座位，或者尝试使用相同的用户名注册一个帐户。共识算法可以用来确定这些 互不相容（mutually incompatible） 的操作中，哪一个才是赢家。

共识问题通常形式化如下：一个或多个节点可以 提议（propose） 某些值，而共识算法 决定（decides） 采用其中的某个值。在座位预订的例子中，当几个顾客同时试图订购最后一个座位时，处理顾客请求的每个节点可以 提议 将要服务的顾客的 ID，而 决定 指明了哪个顾客获得了座位。

在这种形式下，共识算法必须满足以下性质【25】：[^xiii]

[^xiii]: 这种共识的特殊形式被称为 统一共识（uniform consensus），相当于在具有不可靠故障检测器的异步系统中的 常规共识（regular consensus）【71】。学术文献通常指的是 进程（process） 而不是节点，但我们在这里使用 节点（node） 来与本书的其余部分保持一致。

• 一致同意（Uniform agreement）

  没有两个节点的决定不同。

• 完整性（Integrity）

  没有节点决定两次。

• 有效性（Validity）

  如果一个节点决定了值 v ，则 v 由某个节点所提议。

• 终止（Termination）

  由所有未崩溃的节点来最终决定值。

一致同意 和 完整性 属性定义了共识的核心思想：所有人都决定了相同的结果，一旦决定了，你就不能改变主意。有效性 属性主要是为了排除平凡的解决方案：例如，无论提议了什么值，你都可以有一个始终决定值为 null 的算法。；该算法满足 一致同意 和 完整性 属性，但不满足 有效性 属性。

如果你不关心容错，那么满足前三个属性很容易：你可以将一个节点硬编码为 “独裁者”，并让该节点做出所有的决定。但如果该节点失效，那么系统就无法再做出任何决定。事实上，这就是我们在两阶段提交的情况中所看到的：如果协调者失效，那么存疑的参与者就无法决定提交还是中止。

终止 属性形式化了容错的思想。它实质上说的是，一个共识算法不能简单地永远闲坐着等死 —— 换句话说，它必须取得进展。即使部分节点出现故障，其他节点也必须达成一项决定（终止 是一种 活性属性，而另外三种是 安全属性 —— 请参阅 “安全性和活性”）。

共识的系统模型假设，当一个节点 “崩溃” 时，它会突然消失而且永远不会回来。（不像软件崩溃，想象一下地震，包含你的节点的数据中心被山体滑坡所摧毁，你必须假设节点被埋在 30 英尺以下的泥土中，并且永远不会重新上线）在这个系统模型中，任何需要等待节点恢复的算法都不能满足 终止 属性。特别是，2PC 不符合终止属性的要求。

当然如果 所有 的节点都崩溃了，没有一个在运行，那么所有算法都不可能决定任何事情。算法可以容忍的失效数量是有限的：事实上可以证明，任何共识算法都需要至少占总体 多数（majority） 的节点正确工作，以确保终止属性【67】。多数可以安全地组成法定人数（请参阅 “读写的法定人数”）。

因此 终止 属性取决于一个假设，不超过一半的节点崩溃或不可达。然而即使多数节点出现故障或存在严重的网络问题，绝大多数共识的实现都能始终确保安全属性得到满足 —— 一致同意，完整性和有效性【92】。因此，大规模的中断可能会阻止系统处理请求，但是它不能通过使系统做出无效的决定来破坏共识系统。

大多数共识算法假设不存在 拜占庭式错误，正如在 “拜占庭故障” 一节中所讨论的那样。也就是说，如果一个节点没有正确地遵循协议（例如，如果它向不同节点发送矛盾的消息），它就可能会破坏协议的安全属性。克服拜占庭故障，稳健地达成共识是可能的，只要少于三分之一的节点存在拜占庭故障【25,93】。但我们没有地方在本书中详细讨论这些算法了。

共识算法和全序广播

最著名的容错共识算法是 视图戳复制（VSR, Viewstamped Replication）【94,95】，Paxos 【96,97,98,99】，Raft 【22,100,101】以及 Zab 【15,21,102】 。这些算法之间有不少相似之处，但它们并不相同【103】。在本书中我们不会介绍各种算法的详细细节：了解一些它们共通的高级思想通常已经足够了，除非你准备自己实现一个共识系统。（可能并不明智，相当难【98,104】）

大多数这些算法实际上并不直接使用这里描述的形式化模型（提议与决定单个值，并满足一致同意、完整性、有效性和终止属性）。取而代之的是，它们决定了值的 顺序（sequence），这使它们成为全序广播算法，正如本章前面所讨论的那样（请参阅 “全序广播”）。

请记住，全序广播要求将消息按照相同的顺序，恰好传递一次，准确传送到所有节点。如果仔细思考，这相当于进行了几轮共识：在每一轮中，节点提议下一条要发送的消息，然后决定在全序中下一条要发送的消息【67】。

所以，全序广播相当于重复进行多轮共识（每次共识决定与一次消息传递相对应）：

• 由于 一致同意 属性，所有节点决定以相同的顺序传递相同的消息。
• 由于 完整性 属性，消息不会重复。
• 由于 有效性 属性，消息不会被损坏，也不能凭空编造。
• 由于 终止 属性，消息不会丢失。

视图戳复制，Raft 和 Zab 直接实现了全序广播，因为这样做比重复 一次一值（one value a time） 的共识更高效。在 Paxos 的情况下，这种优化被称为 Multi-Paxos。

单主复制与共识

在 第五章 中，我们讨论了单主复制（请参阅 “领导者与追随者”），它将所有的写入操作都交给主库，并以相同的顺序将它们应用到从库，从而使副本保持在最新状态。这实际上不就是一个全序广播吗？为什么我们在 第五章 里一点都没担心过共识问题呢？

答案取决于如何选择领导者。如果主库是由运维人员手动选择和配置的，那么你实际上拥有一种 独裁类型 的 “共识算法”：只有一个节点被允许接受写入（即决定写入复制日志的顺序），如果该节点发生故障，则系统将无法写入，直到运维手动配置其他节点作为主库。这样的系统在实践中可以表现良好，但它无法满足共识的 终止 属性，因为它需要人为干预才能取得 进展。

一些数据库会自动执行领导者选举和故障切换，如果旧主库失效，会提拔一个从库为新主库（请参阅 “处理节点宕机”）。这使我们向容错的全序广播更进一步，从而达成共识。

但是还有一个问题。我们之前曾经讨论过脑裂的问题，并且说过所有的节点都需要同意是谁领导，否则两个不同的节点都会认为自己是领导者，从而导致数据库进入不一致的状态。因此，选出一位领导者需要共识。但如果这里描述的共识算法实际上是全序广播算法，并且全序广播就像单主复制，而单主复制需要一个领导者，那么…

这样看来，要选出一个领导者，我们首先需要一个领导者。要解决共识问题，我们首先需要解决共识问题。我们如何跳出这个先有鸡还是先有蛋的问题？

纪元编号和法定人数

迄今为止所讨论的所有共识协议，在内部都以某种形式使用一个领导者，但它们并不能保证领导者是独一无二的。相反，它们可以做出更弱的保证：协议定义了一个 纪元编号（epoch number，在 Paxos 中被称为 投票编号，即 ballot number，在视图戳复制中被称为 视图编号，即 view number，以及在 Raft 中被为 任期号码，即 term number），并确保在每个时代中，领导者都是唯一的。

每次当现任领导被认为挂掉的时候，节点间就会开始一场投票，以选出一个新领导。这次选举被赋予一个递增的纪元编号，因此纪元编号是全序且单调递增的。如果两个不同的时代的领导者之间出现冲突（也许是因为前任领导者实际上并未死亡），那么带有更高纪元编号的领导说了算。

在任何领导者被允许决定任何事情之前，必须先检查是否存在其他带有更高纪元编号的领导者，它们可能会做出相互冲突的决定。领导者如何知道自己没有被另一个节点赶下台？回想一下在 “真相由多数所定义” 中提到的：一个节点不一定能相信自己的判断 —— 因为只有节点自己认为自己是领导者，并不一定意味着其他节点接受它作为它们的领导者。

相反，它必须从 法定人数（quorum） 的节点中获取选票（请参阅 “读写的法定人数”）。对领导者想要做出的每一个决定，都必须将提议值发送给其他节点，并等待法定人数的节点响应并赞成提案。法定人数通常（但不总是）由多数节点组成【105】。只有在没有意识到任何带有更高纪元编号的领导者的情况下，一个节点才会投票赞成提议。

因此，我们有两轮投票：第一次是为了选出一位领导者，第二次是对领导者的提议进行表决。关键的洞察在于，这两次投票的 法定人群 必须相互 重叠（overlap）：如果一个提案的表决通过，则至少得有一个参与投票的节点也必须参加过最近的领导者选举【105】。因此，如果在一个提案的表决过程中没有出现更高的纪元编号。那么现任领导者就可以得出这样的结论：没有发生过更高时代的领导选举，因此可以确定自己仍然在领导。然后它就可以安全地对提议值做出决定。

这一投票过程表面上看起来很像两阶段提交。最大的区别在于，2PC 中协调者不是由选举产生的，而且 2PC 则要求 所有 参与者都投赞成票，而容错共识算法只需要多数节点的投票。而且，共识算法还定义了一个恢复过程，节点可以在选举出新的领导者之后进入一个一致的状态，确保始终能满足安全属性。这些区别正是共识算法正确性和容错性的关键。

共识的局限性

共识算法对于分布式系统来说是一个巨大的突破：它为其他充满不确定性的系统带来了基础的安全属性（一致同意，完整性和有效性），然而它们还能保持容错（只要多数节点正常工作且可达，就能取得进展）。它们提供了全序广播，因此它们也可以以一种容错的方式实现线性一致的原子操作（请参阅 “使用全序广播实现线性一致的存储”）。

尽管如此，它们并不是在所有地方都用上了，因为好处总是有代价的。

节点在做出决定之前对提议进行投票的过程是一种同步复制。如 “同步复制与异步复制” 中所述，通常数据库会配置为异步复制模式。在这种配置中发生故障切换时，一些已经提交的数据可能会丢失 —— 但是为了获得更好的性能，许多人选择接受这种风险。

共识系统总是需要严格多数来运转。这意味着你至少需要三个节点才能容忍单节点故障（其余两个构成多数），或者至少有五个节点来容忍两个节点发生故障（其余三个构成多数）。如果网络故障切断了某些节点同其他节点的连接，则只有多数节点所在的网络可以继续工作，其余部分将被阻塞（请参阅 “线性一致性的代价”）。

大多数共识算法假定参与投票的节点是固定的集合，这意味着你不能简单的在集群中添加或删除节点。共识算法的 动态成员扩展（dynamic membership extension） 允许集群中的节点集随时间推移而变化，但是它们比静态成员算法要难理解得多。

共识系统通常依靠超时来检测失效的节点。在网络延迟高度变化的环境中，特别是在地理上散布的系统中，经常发生一个节点由于暂时的网络问题，错误地认为领导者已经失效。虽然这种错误不会损害安全属性，但频繁的领导者选举会导致糟糕的性能表现，因系统最后可能花在权力倾扎上的时间要比花在建设性工作的多得多。

有时共识算法对网络问题特别敏感。例如 Raft 已被证明存在让人不悦的极端情况【106】：如果整个网络工作正常，但只有一条特定的网络连接一直不可靠，Raft 可能会进入领导者在两个节点间频繁切换的局面，或者当前领导者不断被迫辞职以致系统实质上毫无进展。其他一致性算法也存在类似的问题，而设计能健壮应对不可靠网络的算法仍然是一个开放的研究问题。

成员与协调服务

像 ZooKeeper 或 etcd 这样的项目通常被描述为 “分布式键值存储” 或 “协调与配置服务”。这种服务的 API 看起来非常像数据库：你可以读写给定键的值，并遍历键。所以如果它们基本上算是数据库的话，为什么它们要把工夫全花在实现一个共识算法上呢？是什么使它们区别于其他任意类型的数据库？

为了理解这一点，简单了解如何使用 ZooKeeper 这类服务是很有帮助的。作为应用开发人员，你很少需要直接使用 ZooKeeper，因为它实际上不适合当成通用数据库来用。更有可能的是，你会通过其他项目间接依赖它，例如 HBase、Hadoop YARN、OpenStack Nova 和 Kafka 都依赖 ZooKeeper 在后台运行。这些项目从它那里得到了什么？

ZooKeeper 和 etcd 被设计为容纳少量完全可以放在内存中的数据（虽然它们仍然会写入磁盘以保证持久性），所以你不会想着把所有应用数据放到这里。这些少量数据会通过容错的全序广播算法复制到所有节点上。正如前面所讨论的那样，数据库复制需要的就是全序广播：如果每条消息代表对数据库的写入，则以相同的顺序应用相同的写入操作可以使副本之间保持一致。

ZooKeeper 模仿了 Google 的 Chubby 锁服务【14,98】，不仅实现了全序广播（因此也实现了共识），而且还构建了一组有趣的其他特性，这些特性在构建分布式系统时变得特别有用：

• 线性一致性的原子操作

  使用原子 CAS 操作可以实现锁：如果多个节点同时尝试执行相同的操作，只有一个节点会成功。共识协议保证了操作的原子性和线性一致性，即使节点发生故障或网络在任意时刻中断。分布式锁通常以 租约（lease） 的形式实现，租约有一个到期时间，以便在客户端失效的情况下最终能被释放（请参阅 “进程暂停”）。

• 操作的全序排序

  如 “领导者和锁” 中所述，当某个资源受到锁或租约的保护时，你需要一个防护令牌来防止客户端在进程暂停的情况下彼此冲突。防护令牌是每次锁被获取时单调增加的数字。ZooKeeper 通过全序化所有操作来提供这个功能，它为每个操作提供一个单调递增的事务 ID（zxid）和版本号（cversion）【15】。

• 失效检测

  客户端在 ZooKeeper 服务器上维护一个长期会话，客户端和服务器周期性地交换心跳包来检查节点是否还活着。即使连接暂时中断，或者 ZooKeeper 节点失效，会话仍保持在活跃状态。但如果心跳停止的持续时间超出会话超时，ZooKeeper 会宣告该会话已死亡。当会话超时时（ZooKeeper 称这些节点为 临时节点，即 ephemeral nodes），会话持有的任何锁都可以配置为自动释放。

• 变更通知

  客户端不仅可以读取其他客户端创建的锁和值，还可以监听它们的变更。因此，客户端可以知道另一个客户端何时加入集群（基于新客户端写入 ZooKeeper 的值），或发生故障（因其会话超时，而其临时节点消失）。通过订阅通知，客户端不用再通过频繁轮询的方式来找出变更。

在这些功能中，只有线性一致的原子操作才真的需要共识。但正是这些功能的组合，使得像 ZooKeeper 这样的系统在分布式协调中非常有用。

将工作分配给节点

ZooKeeper/Chubby 模型运行良好的一个例子是，如果你有几个进程实例或服务，需要选择其中一个实例作为主库或首选服务。如果领导者失败，其他节点之一应该接管。这对单主数据库当然非常实用，但对作业调度程序和类似的有状态系统也很好用。

另一个例子是，当你有一些分区资源（数据库，消息流，文件存储，分布式 Actor 系统等），并需要决定将哪个分区分配给哪个节点时。当新节点加入集群时，需要将某些分区从现有节点移动到新节点，以便重新平衡负载（请参阅 “分区再平衡”）。当节点被移除或失效时，其他节点需要接管失效节点的工作。

这类任务可以通过在 ZooKeeper 中明智地使用原子操作，临时节点与通知来实现。如果设计得当，这种方法允许应用自动从故障中恢复而无需人工干预。不过这并不容易，尽管已经有不少在 ZooKeeper 客户端 API 基础之上提供更高层工具的库，例如 Apache Curator 【17】。但它仍然要比尝试从头实现必要的共识算法要好得多，这样的尝试鲜有成功记录【107】。

应用最初只能在单个节点上运行，但最终可能会增长到数千个节点。试图在如此之多的节点上进行多数投票将是非常低效的。相反，ZooKeeper 在固定数量的节点（通常是三到五个）上运行，并在这些节点之间执行其多数票，同时支持潜在的大量客户端。因此，ZooKeeper 提供了一种将协调节点（共识，操作排序和故障检测）的一些工作 “外包” 到外部服务的方式。

通常，由 ZooKeeper 管理的数据类型的变化十分缓慢：代表 “分区 7 中的节点运行在 10.1.1.23 上” 的信息可能会在几分钟或几小时的时间内发生变化。它不是用来存储应用的运行时状态的，后者每秒可能会改变数千甚至数百万次。如果应用状态需要从一个节点复制到另一个节点，则可以使用其他工具（如 Apache BookKeeper 【108】）。

服务发现

ZooKeeper、etcd 和 Consul 也经常用于服务发现 —— 也就是找出你需要连接到哪个 IP 地址才能到达特定的服务。在云数据中心环境中，虚拟机来来往往很常见，你通常不会事先知道服务的 IP 地址。相反，你可以配置你的服务，使其在启动时注册服务注册表中的网络端点，然后可以由其他服务找到它们。

但是，服务发现是否需要达成共识还不太清楚。 DNS 是查找服务名称的 IP 地址的传统方式，它使用多层缓存来实现良好的性能和可用性。从 DNS 读取是绝对不线性一致性的，如果 DNS 查询的结果有点陈旧，通常不会有问题【109】。 DNS 的可用性和对网络中断的鲁棒性更重要。

尽管服务发现并不需要共识，但领导者选举却是如此。因此，如果你的共识系统已经知道领导是谁，那么也可以使用这些信息来帮助其他服务发现领导是谁。为此，一些共识系统支持只读缓存副本。这些副本异步接收共识算法所有决策的日志，但不主动参与投票。因此，它们能够提供不需要线性一致性的读取请求。

成员资格服务

ZooKeeper 和它的小伙伴们可以看作是成员资格服务（membership services）研究的悠久历史的一部分，这个历史可以追溯到 20 世纪 80 年代，并且对建立高度可靠的系统（例如空中交通管制）非常重要【110】。

成员资格服务确定哪些节点当前处于活动状态并且是集群的活动成员。正如我们在 第八章 中看到的那样，由于无限的网络延迟，无法可靠地检测到另一个节点是否发生故障。但是，如果你通过共识来进行故障检测，那么节点可以就哪些节点应该被认为是存在或不存在达成一致。

即使它确实存在，仍然可能发生一个节点被共识错误地宣告死亡。但是对于一个系统来说，知道哪些节点构成了当前的成员关系是非常有用的。例如，选择领导者可能意味着简单地选择当前成员中编号最小的成员，但如果不同的节点对现有的成员都有谁有不同意见，则这种方法将不起作用。

本章小结

在本章中，我们从几个不同的角度审视了关于一致性与共识的话题。我们深入研究了线性一致性（一种流行的一致性模型）：其目标是使多副本数据看起来好像只有一个副本一样，并使其上所有操作都原子性地生效。虽然线性一致性因为简单易懂而很吸引人 —— 它使数据库表现的好像单线程程序中的一个变量一样，但它有着速度缓慢的缺点，特别是在网络延迟很大的环境中。

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

但即使捕获到因果顺序（例如使用兰伯特时间戳），我们发现有些事情也不能通过这种方式实现：在 “光有时间戳排序还不够” 一节的例子中，我们需要确保用户名是唯一的，并拒绝同一用户名的其他并发注册。如果一个节点要通过注册，则需要知道其他的节点没有在并发抢注同一用户名的过程中。这个问题引领我们走向 共识。

我们看到，达成共识意味着以这样一种方式决定某件事：所有节点一致同意所做决定，且这一决定不可撤销。通过深入挖掘，结果我们发现很广泛的一系列问题实际上都可以归结为共识问题，并且彼此等价（从这个意义上来讲，如果你有其中之一的解决方案，就可以轻易将它转换为其他问题的解决方案）。这些等价的问题包括：

• 线性一致性的 CAS 寄存器

  寄存器需要基于当前值是否等于操作给出的参数，原子地 决定 是否设置新值。

• 原子事务提交

  数据库必须 决定 是否提交或中止分布式事务。

• 全序广播

  消息系统必须 决定 传递消息的顺序。

• 锁和租约

  当几个客户端争抢锁或租约时，由锁来 决定 哪个客户端成功获得锁。

• 成员 / 协调服务

  给定某种故障检测器（例如超时），系统必须 决定 哪些节点活着，哪些节点因为会话超时需要被宣告死亡。

• 唯一性约束

  当多个事务同时尝试使用相同的键创建冲突记录时，约束必须 决定 哪一个被允许，哪些因为违反约束而失败。

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

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

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

尽管单领导者数据库可以提供线性一致性，且无需对每个写操作都执行共识算法，但共识对于保持及变更领导权仍然是必须的。因此从某种意义上说，使用单个领导者不过是 “缓兵之计”：共识仍然是需要的，只是在另一个地方，而且没那么频繁。好消息是，容错的共识算法与容错的共识系统是存在的，我们在本章中简要地讨论了它们。

像 ZooKeeper 这样的工具为应用提供了 “外包” 的共识、故障检测和成员服务。它们扮演了重要的角色，虽说使用不易，但总比自己去开发一个能经受 第八章 中所有问题考验的算法要好得多。如果你发现自己想要解决的问题可以归结为共识，并且希望它能容错，使用一个类似 ZooKeeper 的东西是明智之举。

尽管如此，并不是所有系统都需要共识：例如，无领导者复制和多领导者复制系统通常不会使用全局的共识。这些系统中出现的冲突（请参阅 “处理写入冲突”）正是不同领导者之间没有达成共识的结果，但这也许并没有关系：也许我们只是需要接受没有线性一致性的事实，并学会更好地与具有分支与合并版本历史的数据打交道。

本章引用了大量关于分布式系统理论的研究。虽然理论论文和证明并不总是容易理解，有时也会做出不切实际的假设，但它们对于指导这一领域的实践有着极其重要的价值：它们帮助我们推理什么可以做，什么不可以做，帮助我们找到反直觉的分布式系统缺陷。如果你有时间，这些参考资料值得探索。

这里已经到了本书 第二部分 的末尾，第二部介绍了复制（第五章）、分区（第六章）、事务（第七章）、分布式系统的故障模型（第八章）以及最后的一致性与共识（第九章）。现在我们已经奠定了扎实的理论基础，我们将在 第三部分 再次转向更实际的系统，并讨论如何使用异构的组件积木块构建强大的应用。

LSM树详解

LSM树详解 - 知乎 (zhihu.com)

Pele

关注

LSM树(Log-Structured-Merge-Tree)的名字往往会给初识者一个错误的印象，事实上，LSM树并不像B+树、红黑树一样是一颗严格的树状数据结构，它其实是一种存储结构，目前HBase,LevelDB,RocksDB这些NoSQL存储都是采用的LSM树。

LSM树的核心特点是利用顺序写来提高写性能，但因为分层(此处分层是指的分为内存和文件两部分)的设计会稍微降低读性能，但是通过牺牲小部分读性能换来高性能写，使得LSM树成为非常流行的存储结构。

什么是LSM

LSM（Log-Structured Merge）是一种用于数据存储和检索的技术，其中数据被写入日志结构，并使用合并树来提高读取性能。

日志结构合并树（Log-Structured Merge Tree，LSM-Tree）是基于LSM的一种具体实现方式。它主要解决了传统B树在写入操作频繁的情况下，由于随机写入导致的性能下降和磁盘碎片问题。

LSM-Tree的工作原理如下：

1. 写入过程：当有新的数据写入时，LSM-Tree首先将这些数据追加到一个顺序写的日志文件中，而不是直接修改原始数据文件。这种方式称为写前日志（Write-Ahead Log, WAL），可以提高写入性能并确保数据持久化。
2. 内存存储：LSM-Tree维护一个内存层级的结构（通常称为MemTable），用于快速写入操作。写入的数据首先被存储在内存中的MemTable中。
3. 合并操作：当内存中的数据量达到一定阈值时，MemTable会被转换为一个磁盘上的结构，通常称为SSTable（Sorted String Table）。SSTable是一个排好序的、不可更改的数据文件。为了减少磁盘空间占用和提高查询性能，LSM-Tree周期性地执行合并操作。合并操作会将多个SSTables合并为一个更大的SSTable，并清除不再需要的数据。
4. 读取操作：为了执行读取操作，LSM-Tree会在多个SSTables上执行查找操作。由于SSTables是有序的，可以使用类似二分查找的算法来快速找到所需的数据。

LSM-Tree通过将写入操作追加到日志文件中，并结合合并操作和有序存储的方式，实现了高吞吐量的写入性能和较快的随机读取性能。它被广泛应用于许多数据库和分布式存储系统，如LevelDB、RocksDB等。

1、LSM树的核心思想

如上图所示，LSM树有以下三个重要组成部分：

1) MemTable

MemTable是在***内存***中的数据结构，用于保存最近更新的数据，会按照Key有序地组织这些数据，LSM树对于具体如何组织有序地组织数据并没有明确的数据结构定义，例如Hbase使跳跃表来保证内存中key的有序。

因为数据暂时保存在内存中，内存并不是可靠存储，如果断电会丢失数据，因此通常会通过WAL(Write-ahead logging，预写式日志)的方式来保证数据的可靠性。

2) Immutable MemTable

当 MemTable达到一定大小后，会转化成Immutable MemTable。Immutable MemTable是将转MemTable变为SSTable的一种中间状态。写操作由新的MemTable处理，在转存过程中不阻塞数据更新操作。

3) SSTable(Sorted String Table)

**有序键值对*集合，是LSM树组在磁盘***中的数据结构。为了加快SSTable的读取，可以通过建立key的索引以及布隆过滤器来加快key的查找。

这里需要关注一个重点，LSM树(Log-Structured-Merge-Tree)正如它的名字一样，LSM树会将所有的数据插入、修改、删除等操作记录(注意是操作记录)保存在内存之中，当此类操作达到一定的数据量后，再批量地顺序写入到磁盘当中。这与B+树不同，B+树数据的更新会直接在原数据所在处修改对应的值，但是LSM数的数据更新是日志式的，当一条数据更新是直接append一条更新记录完成的。这样设计的目的就是为了顺序写，不断地将Immutable MemTable flush到持久化存储即可，而不用去修改之前的SSTable中的key，保证了顺序写。

因此当MemTable达到一定大小flush到持久化存储变成SSTable后，在不同的SSTable中，可能存在相同Key的记录，当然最新的那条记录才是准确的。这样设计的虽然大大提高了写性能，但同时也会带来一些问题：

1）冗余存储，对于某个key，实际上除了最新的那条记录外，其他的记录都是冗余无用的，但是仍然占用了存储空间。因此需要进行Compact操作(合并多个SSTable)来清除冗余的记录。
2）读取时需要从最新的倒着查询，直到找到某个key的记录。最坏情况需要查询完所有的SSTable，这里可以通过前面提到的索引/布隆过滤器来优化查找速度。

2、LSM树的Compact策略

从上面可以看出，Compact操作是十分关键的操作，否则SSTable数量会不断膨胀。在Compact策略上，主要介绍两种基本策略：size-tiered和leveled。

不过在介绍这两种策略之前，先介绍三个比较重要的概念，事实上不同的策略就是围绕这三个概念之间做出权衡和取舍。

1）读放大:读取数据时实际读取的数据量大于真正的数据量。例如在LSM树中需要先在MemTable查看当前key是否存在，不存在继续从SSTable中寻找。
2）写放大:写入数据时实际写入的数据量大于真正的数据量。例如在LSM树中写入时可能触发Compact操作，导致实际写入的数据量远大于该key的数据量。
3）空间放大:数据实际占用的磁盘空间比数据的真正大小更多。上面提到的冗余存储，对于一个key来说，只有最新的那条记录是有效的，而之前的记录都是可以被清理回收的。

1) size-tiered 策略

size-tiered策略保证每层SSTable的大小相近，同时限制每一层SSTable的数量。如上图，每层限制SSTable为N，当每层SSTable达到N后，则触发Compact操作合并这些SSTable，并将合并后的结果写入到下一层成为一个更大的sstable。

由此可以看出，当层数达到一定数量时，最底层的单个SSTable的大小会变得非常大。并且size-tiered策略会导致空间放大比较严重。即使对于同一层的SSTable，每个key的记录是可能存在多份的，只有当该层的SSTable执行compact操作才会消除这些key的冗余记录。

2) leveled策略

每一层的总大小固定，从上到下逐渐变大

leveled策略也是采用分层的思想，每一层限制总文件的大小。

但是跟size-tiered策略不同的是，leveled会将每一层切分成多个大小相近的SSTable。这些SSTable是这一层是全局有序的，意味着一个key在每一层至多只有1条记录，不存在冗余记录。之所以可以保证全局有序，是因为合并策略和size-tiered不同，接下来会详细提到。

每一层的SSTable是全局有序的

假设存在以下这样的场景:

\1) L1的总大小超过L1本身大小限制：

此时L1超过了最大阈值限制

\2) 此时会从L1中选择至少一个文件，然后把它跟L2***有交集的部分(非常关键)***进行合并。生成的文件会放在L2:

如上图所示，此时L1第二SSTable的key的范围覆盖了L2中前三个SSTable，那么就需要将L1中第二个SSTable与L2中前三个SSTable执行Compact操作。

\3) 如果L2合并后的结果仍旧超出L5的阈值大小，需要重复之前的操作 —— 选至少一个文件然后把它合并到下一层:

需要注意的是，***多个不相干的合并是可以并发进行的***：

leveled策略相较于size-tiered策略来说，每层内key是不会重复的，即使是最坏的情况，除开最底层外，其余层都是重复key，按照相邻层大小比例为10来算，冗余占比也很小。因此空间放大问题得到缓解。但是写放大问题会更加突出。举一个最坏场景，如果LevelN层某个SSTable的key的范围跨度非常大，覆盖了LevelN+1层所有key的范围，那么进行Compact时将涉及LevelN+1层的全部数据。

3、总结

LSM树是非常值得了解的知识，理解了LSM树可以很自然地理解Hbase，LevelDb等存储组件的架构设计。ClickHouse中的MergeTree也是LSM树的思想，Log-Structured还可以联想到Kafka的存储方式。

虽然介绍了上面两种策略，但是各个存储都在自己的Compact策略上面做了很多特定的优化，例如Hbase分为Major和Minor两种Compact，这里不再做过多介绍，推荐阅读文末的RocksDb合并策略介绍。

PS:封面是在当时百度搜索lsm树的截图，真实截图，非PS。

参考来源：

文件结构 压缩(compaction) 压缩文件选择 层的目标大小 TTL RocksDB中文网rocksdb.org.cn/doc/Leveled-Compaction.html

LSM Tree-Based存储引擎的compaction策略（feat. RocksDB）www.jianshu.com/p/e89cd503c9ae?utm_campaign=hugo

发布于 2020-08-20 17:33