《数据密集型系统设计》记录

本书的电子版本链接：Vonng/ddia: 《Designing Data-Intensive Application》DDIA中文翻译

3. 存储与检索

本章围绕两大类存储引擎：日志结构（log-structured）的存储引擎，以及面向页面（page-oriented）的存储引擎（例如 B 树）。

数据库核心：数据结构

这里所使用的“日志”是一个更一般性的概念：一个支持 append-only 仅追加操作的记录序列。

为了高效查找数据库中特定键的值，需要用到索引。索引是从主要数据中衍生的额外结构，维护它会产生额外开销，特别是写入时。任何类型的索引通常都会减慢写入速度，因为每次写入数据时都需要更新索引。这是存储系统中一个重要的权衡：精心选择的索引加快了读查询的速度，但是每个索引都会拖慢写入速度。因为这个原因，数据库默认并不会索引所有的内容，而需要程序员或数据库管理员（DBA），基于对应用的典型查询模式的了解来手动选择索引。

SSTable

把键值对的序列按照键进行排序，这个格式称为排序字符串表（Sorted String Table, SSTable）。此时再要求每个键值在每个合并的段文件中出现一次。与使用散列索引的日志段相比，SSTable 有几个大的优势：

  • 即使文件大于可用内存，合并段的操作仍然是简单高效：
    • 一开始并排读取多个输入文件，查看每个文件中的第一个键，复制最低的键（根据排序顺序）到输出文件，不断重复此步骤，将产生一个新的合并段文件，而且它也是也按键排序的。
    • 如果在几个输入段中出现相同的键，该怎么办？请记住，每个段都包含在一段时间内写入数据库的所有值。这意味着一个输入段中的所有值一定比另一个段中的所有值都更近（假设我们总是合并相邻的段）。当多个段包含相同的键时，我们可以保留最近段的值，并丢弃旧段中的值。
  • 为了在文件中找到一个特定的键，你不再需要在内存中保存所有键的索引：
    • 假设你正在内存中寻找键 handiwork，但是你不知道这个键在段文件中的确切偏移量。然而，你知道 handbag 和 handsome 的偏移，而且由于排序特性，你知道 handiwork 必须出现在这两者之间。这意味着你可以跳到 handbag 的偏移位置并从那里扫描，直到你找到 handiwork（或没找到，如果该文件中没有该键）。
  • 由于读取请求无论如何都需要扫描所请求范围内的多个键值对，因此可以将这些记录分组为块（block），并在将其写入硬盘之前对其进行压缩。稀疏内存索引中的每个条目都指向压缩块的开始处。除了节省硬盘空间之外，压缩还可以减少对 I/O 带宽的使用。

那么，可以构建 SSTable 了，可以让存储引擎这样工作：

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

这样的索引结构被称为 LSM-Tree（Log-Structured Merge-Tree）。

当查找数据库中不存在的键时，LSM 树算法可能会很慢。为了优化这种访问，存储引擎通常会使用布隆过滤器。还可以使用大小分级和分层压缩。对于大小分级，较新和较小的 SSTables 相继被合并到较旧的和较大的 SSTable 中。对于分层压缩，键的范围被拆分到多个较小的 SSTables，而较旧的数据被移动到单独的层级，这使得压缩能够逐步进行并且使用较少的硬盘空间。

B-Tree

前面看到的日志结构索引将数据库分解为可变大小的段，通常是几兆字节或更大的大小，并且总是按顺序写入段。相比之下，B 树将数据库分解成固定大小的块或分页，传统上大小为 4KB（有时会更大），并且一次只能读取或写入一个页面。这种设计更接近于底层硬件，因为硬盘空间也是按固定大小的块来组织的。

在 B 树的底层中，写操作是用新数据覆写硬盘上的页面，并假定覆写不改变页面的位置。即当页面被覆写时，对该页面的所有引用保持完整。这与日志结构索引（如 LSM 树）形成鲜明对比，后者只追加到文件（并最终删除过时的文件），但从不修改文件中已有的内容。

为了使数据库能处理异常崩溃的场景，B 树实现通常会带有一个额外的硬盘数据结构：预写式日志（WAL，即 write-ahead log，也称为重做日志，即 redo log）。这是一个仅追加的文件，每个 B 树的修改在其能被应用到树本身的页面之前都必须先写入到该文件。当数据库在崩溃后恢复时，这个日志将被用来使 B 树恢复到一致的状态。

两者对比

特性LSM-TreeB-Tree
写入吞吐高（顺序写）中（随机写）
读取延迟高（合并 SSTable）低（直接索引）
空间放大低（压缩合并）中（页碎片）
适用场景写密集、低频更新读密集、高频更新

其他索引结构

  • 将值存储到索引中：

    索引中的键是查询要搜索的内容，而其值可以是以下两种情况之一：它可以是实际的行（文档，顶点），也可以是对存储在别处的行的引用。

    • 后一种情况下，行被存储的地方被称为堆文件，并且存储的数据没有特定的顺序（它可以是仅追加的，或者它可以跟踪被删除的行以便后续可以用新的数据进行覆盖）。堆文件方法很常见，因为它避免了在存在多个次级索引时对数据的复制：每个索引只引用堆文件中的一个位置，实际的数据都保存在一个地方。
    • 从索引到堆文件的额外跳跃对读取来说性能损失太大，因此希望将被索引的行直接存储在索引中，这种方式被称为聚集索引。在聚集索引（在索引中存储所有的行数据）和 非聚集索引（仅在索引中存储对数据的引用）之间的折衷被称为覆盖索引，其在索引内存储表的一部分列，这允许通过单独使用索引来处理一些查询。

  • 多列索引：

    最常见的多列索引被称为连接索引 ，它通过将一列的值追加到另一列后面，简单地将多个字段组合成一个键（索引定义中指定了字段的连接顺序）。

    多维索引是一种查询多个列的更一般的方法，这对于地理空间数据尤为重要。例如，餐厅搜索网站可能有一个数据库，其中包含每个餐厅的经度和纬度。当用户在地图上查看餐馆时，网站需要搜索用户正在查看的矩形地图区域内的所有餐馆。这需要一个二维范围查询，如下所示：

    1
2

    SELECT * FROM restaurants WHERE latitude > 51.4946 AND latitude < 51.5079
                          AND longitude > -0.1162 AND longitude < -0.1004;

    一个标准的 B 树或者 LSM 树索引不能够高效地处理这种查询：它可以返回一个纬度范围内的所有餐馆（但经度可能是任意值），或者返回在同一个经度范围内的所有餐馆（但纬度可能是北极和南极之间的任意地方），但不能同时满足两个条件。

    多维索引不仅可以用于地理位置。例如，在电子商务网站上可以使用建立在（红，绿，蓝）维度上的三维索引来搜索特定颜色范围内的产品，也可以在天气观测数据库中建立（日期，温度）的二维索引，以便有效地搜索 2013 年内的温度在 25 至 30°C 之间的所有观测资料。

事务处理与分析处理

行式存储和列式存储的根本差异：

  • OLTP（联机事务处理）：
    • 特点：频繁的短事务（如订单创建、用户注册）。
    • 存储模型：行存储（Row-Based）。
      • 优势：快速读取单行数据（所有列连续存储）。
      • 劣势：扫描大量数据时需读取冗余列（如仅需统计某列总和）。
  • OLAP（联机分析处理）：
    • 特点：复杂的分析查询（如统计报表）。
    • 存储模型：列存储（Column-Based，如Parquet、ClickHouse）。
      • 优势：
        1. 高压缩率（同列数据类型一致）。
        2. 仅读取所需列，减少I/O。
        3. 适合向量化计算（SIMD优化）。
      • 劣势：随机写入效率低（需批量写入）。

列式存储

列式存储背后的想法很简单：不要将所有来自一行的值存储在一起，而是将来自每一列的所有值存储在一起。如果每个列式存储在一个单独的文件中，查询只需要读取和解析查询中使用的那些列，这可以节省大量的工作。

除了仅从硬盘加载查询所需的列以外，我们还可以通过压缩数据来进一步降低对硬盘吞吐量的需求。通常情况下，一列中不同值的数量与行数相比要小得多（例如，零售商可能有数十亿的销售交易，但只有 100,000 个不同的产品）。现在我们可以拿一个有 $n$ 个不同值的列，并把它转换成 $n$ 个独立的位图：每个不同值对应一个位图，每行对应一个比特位。如果该行具有该值，则该位为 1，否则为 0。这些位图索引非常适合数据仓库中常见的各种查询。

5. 数据复制

主节点与从节点

主从复制的工作原理：

  1. 选定一个节点为主节点。当客户端要向数据库写入时，它必须将请求发送给主节点，主节点将新数据写入其本地存储。
  2. 其他节点为从节点。每当主节点写入了新数据，它也会将数据变更大送给所有的从节点，称之为复制日志。每个从节点拉取复制日志，并相应更新其本地数据库副本。
  3. 客户端可以向任一节点发送查询请求，但只有主节点以及接收写入请求。

同步复制和异步复制

  • 同步复制：在向用户报告写入成功并使结果对其他用户可见之前，主节点需要等待从节点的确认，确保从节点已经收到写入操作。

  • 异步复制：主节点发送消息，但不等待该从节点的响应。

同步复制的优点是，从节点能保证有与主节点一致的最新数据副本。缺点是，如果同步从节点没有响应（比如它已经崩溃，或者出现网络故障，或其它任何原因），主节点就无法处理写入操作。主节点必须阻止所有写入，并等待同步副本再次可用。

因此，将所有从节点都设置为同步的是不切实际的：任何一个节点的中断都会导致整个系统停滞不前。实际上，如果在数据库上启用同步复制，通常意味着其中一个从节点是同步的，而其他的从节点则是异步的。如果该同步从节点变得不可用或缓慢，则将一个异步从节点改为同步运行。这保证你至少在两个节点上拥有最新的数据副本：主节点和同步从节点，这种配置有时也被称为半同步。

通常情况下，基于主节点的复制都配置为完全异步。在这种情况下，如果主节点失效且不可恢复，则任何尚未复制给从节点的写入都会丢失。这意味着即使已经向客户端确认成功，写入也不能保证是持久（Durable） 的。然而，一个完全异步的配置也有优点：即使所有的从节点都落后了，主节点也可以继续处理写入。

设置新从节点

  1. 获取主节点的一致性快照。
  2. 将快照复制到新的从节点。
  3. 从节点连接到主节点，并拉取快照之后发生的所有数据变更。
  4. 当从节点处理完成后，就可以继续及时处理主节点发生的数据变化了。

处理节点宕机

  • 从节点失效：
    • 在其本地磁盘上，每个从节点记录从主节点收到的数据变更。从节点可以从日志中知道在发生故障之前处理的最后一个事务。因此，从节点可以连接到主节点，并请求在从节点断开期间发生的所有数据变更。
  • 主节点失效：
    • 主节点失效就需要将一个从节点提升为主节点，需要重新配置客户端，以将它们的写操作发送给新的主节点，其他从节点需要开始拉取来自新主节点的数据变更。这一过程称为故障切换。
    • 故障切换过程：
      1. 确认主节点失效。如果一个节点在一段时间内（例如 30 秒）没有响应，就认为它挂了。
      2. 选择一个新的主节点。这可以通过选举过程（主节点由剩余副本以多数选举产生）来完成，或者可以由之前选定的控制器节点（controller node）来指定新的主节点。主节点的最佳人选通常是拥有旧主节点最新数据副本的从节点（以最小化数据损失）。让所有的节点同意一个新的领导者，是一个共识问题。
      3. 重新配置系统以启用新的主库。系统需要确保旧主库意识到新主库的存在，并成为一个从库。
    • 在故障切换过程中可能会出现诸多问题：
      • 如果使用异步复制，则新主节点可能没有收到老主节点宕机前最后的写入操作。最常见的解决方案是简单丢弃老主节点未复制的写入。
      • 如果数据库需要和其他外部存储相协调，那么丢弃写入内容是极其危险的操作。
      • 发生某些故障时可能会出现两个节点都以为自己是主节点的情况，这种情况称为脑裂。如果两个主节点都可以接受写操作，却没有冲突解决机制，那么数据就可能丢失或损坏。
      • 在主节点失效的情况下，超时时间越长意味着恢复时间也越长。但是如果超时设置太短，又可能会出现不必要的故障切换。

复制日志的实现

  • 基于语句的复制：在最简单的情况下，主节点记录下它执行的每个写入请求并将该语句日志发送给从节点。对于关系数据库来说，这意味着每个 INSERT、UPDATE 或 DELETE 语句都被转发给每个从节点，每个从节点解析并执行该 SQL 语句。这种方式在语句调用了一些非确定性函数（如 RAND 获取随机数）、使用了自增列等情况下不可用。
  • 传输预写式日志 WAL：对于日志结构存储引擎的 SSTables 和 LSM-trees ，日志是主要的存储方式。对于采用覆盖写磁盘的 Btree，每次修改会预先写入日志。所以可以采用完全相同的 WAL 在另一个节点上构建副本。主要缺点是日志记录的数据非常底层：WAL 包含哪些磁盘块中的哪些字节发生了更改，这使复制与存储引擎紧密耦合。如果数据库将其存储格式从一个版本更改为另一个版本，通常不可能在主节点和从节点上运行不同版本的数据库软件。
  • 基于行的逻辑日志复制：将复制日志从存储引擎的内部实现中解耦出来，这种复制日志被称为逻辑日志，以将其与存储引擎的（物理）数据表示区分开来。关系数据库的逻辑日志通常是以行的粒度来描述对数据库表的写入记录的序列。MySQL 的二进制日志（当配置为使用基于行的复制时）使用了这种方法。对于外部应用程序来说，逻辑日志格式也更容易解析。
  • 基于触发器的复制：触发器允许你将数据更改（写入事务）发生时自动执行的自定义应用程序代码注册在数据库系统中。触发器有机会将更改记录到一个单独的表中，使用外部程序读取这个表，再加上一些必要的业务逻辑，就可以将数据变更复制到另一个系统去。

复制滞后问题

主从复制中，实现完全的同步方案是不现实的、代价巨大的，但是哪怕是半同步方案、完全异步方案依然存在复制延迟问题，下面提到的解决复制延迟的方案都为了保证主从的最终一致性。

读自己的写

许多应用让用户提交一些数据，然后查看他们提交的内容。提交新数据时，必须将其发送给主节点，但是当用户查看数据时，可以通过从节点进行读取。

对于异步复制，如果用户在写入后马上就查看数据，则新数据可能尚未到达副本。对用户而言，看起来好像是刚提交的数据丢失了。在这种情况下，我们需要写后读一致性，如果用户重新加载页面，他们总会看到他们自己提交的任何更新。它不会对其他用户的写入做出承诺，其他用户的更新可能稍等才会看到。

另一种复杂的情况发生在同一位用户从多个设备（例如桌面浏览器和移动 APP）请求服务的时候。这种情况下可能就需要提供跨设备的写后读一致性：如果用户在一个设备上输入了一些信息，然后在另一个设备上查看，则应该看到他们刚输入的信息。

关于写后读一致性的实现，略。

单调读

从异步从节点读取时可能发生的异常的第二个例子是用户可能会遇到时光倒流。如果用户从不同从节点进行多次读取，如首先查询了一个延迟很小的从节点，然后是一个延迟较大的从节点。

单调读可以防止这种异常，单调读仅意味着如果一个用户顺序地进行多次读取，则他们不会看到时间回退，也就是说，如果已经读取到较新的数据，后续的读取不会得到更旧的数据。实现单调读的一种方式是确保每个用户总是从同一个副本进行读取（不同的用户可以从不同的副本读取）。

前缀一致读

第三个复制延迟异常的例子违反了因果律。如果某些分区的复制速度慢于其他分区，那么观察者可能会在看到问题之前先看到答案。前缀一致读可以防止这种异常，即 如果一系列写入按某个顺序发生，那么任何人读取这些写入时，也会看见它们以同样的顺序出现。

如果数据库总是以相同的顺序应用写入，而读取总是看到一致的前缀，那么这种异常不会发生。但是在许多分布式数据库中，不同的分区独立运行，因此不存在全局的写入顺序。

多主节点复制

系统中存在多个主节点，每个主节点均可独立接收写请求，并通过异步方式将数据变更同步到其他主节点及其从节点。

  • 适用场景：

    • 多数据中心：每个数据中心部署一个主节点，用户就近写入本地数据中心，减少跨区域延迟。
    • 离线客户端操作：设备离线时作为本地主节点，联网时与其他节点同步（如协同编辑工具、备忘录同步）。
    • 协作编辑：多个用户同时编辑同一文档时，本地副本异步同步。

  • 优点：

    • 高可用性：单节点失效不影响其他主节点写入。
    • 低延迟：用户就近写入本地数据中心。
    • 容错性：容忍网络分区或数据中心级故障。

  • 缺点：

    • 复杂性高：冲突解决、数据同步和一致性保障增加系统复杂度。
    • 最终一致性：异步复制可能导致临时不一致（需应用层处理）。

无主节点复制

无主节点，所有副本均可直接接收读写请求，客户端并行与多个节点交互。

  • 适用场景：

    • 高可用与容错：节点失效无需切换，客户端直接与其他节点交互。

    • 弱网络环境：宽松Quorum支持临时网络分区下的持续写入。

    • 简单架构：无需主节点选举或复杂同步逻辑（如Dynamo、Cassandra）。

  • 优点：

    • 高可用性：无单点故障，节点失效不影响服务。
    • 灵活一致性：通过调整w/r参数平衡一致性与可用性。

  • 缺点：

    • 并发冲突：需处理多版本合并或数据丢失风险（如LWW策略）。
    • 运维复杂度：反熵和读修复可能增加系统负载。

7. 事务

深入理解事务

ACID的含义

  • 原子性（Atomicity）：能够在错误时中止事务，丢弃该事务进行的所有写入变更的能力。
  • 一致性（Consistency）：对数据的一组特定约束必须始终成立，即不变式。一致性的这种概念取决于应用程序对不变式的理解，应用程序负责正确定义它的事务，并保持一致性。一致性并不是数据库可以保证的事情，如果你写入违反不变式的脏数据，数据库也无法阻止你。原子性、隔离性和持久性是数据库的属性，而一致性（在 ACID 意义上）是应用程序的属性。
  • 隔离性（Isolation）：ACID 意义上的隔离性意味着，同时执行的事务是相互隔离的。这种定义最标准的实现是可串行化，然而实践中很少会使用可串行化这一隔离级别。
  • 持久性（Durability）：一旦事务成功完成，即使发生硬件故障或数据库崩溃，写入的任何数据也不会丢失。

单对象操作和多对象操作的 ACID

对于单对象操作，现代数据库通常保证单对象操作的原子性，关系型数据库在单行更新、插入、删除时默认是原子的。NoSQL 数据库在单个文档、单个键值对操作上通常也能提供原子性。单对象操作的事务通常是隐式的，不需要显式声明 BEGIN TRANSACTION。

而多对象（如多行、多表、多文档）操作不一定具备原子性，关系数据库中可以通过 BEGIN TRANSACTION ... COMMIT 显式的声明来保证原子性，NoSQL 数据库中，通常缺乏对多对象操作的事务支持，或者提供的事务能力较为受限。在分布式环境下，强事务支持（如 ACID）通常会影响性能。NoSQL 数据库为了高可用和可扩展性，通常会弱化事务支持，提供最终一致性或幂等操作来弥补事务缺失。

弱隔离级别

读已提交

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

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

防止脏读的原因：

  • 如果事务需要更新多个对象，脏读取意味着另一个事务可能会只看到一部分更新。
  • 如果事务中止，则所有写入操作都需要回滚。如果数据库允许脏读，那就意味着一个事务可能会看到稍后需要回滚的数据，即从未实际提交给数据库的数据。

数据库通过使用行锁来防止脏写，当事务想要修改特定对象（行或文档）时，它必须首先获得该对象的锁，然后必须持有该锁直到事务被提交或中止。

读锁的办法在实践中效果并不好，因为一个长时间运行的写入事务会迫使许多只读事务等到这个慢写入事务完成。这会影响只读事务的响应时间，并且不利于可操作性。出于这个原因，大多数数据库使用这种方式防止脏读：对于写入的每个对象，数据库都会记住旧的已提交值和由当前持有写入锁的事务设置的新值。当事务正在进行时，任何其他读取对象的事务都会拿到旧值。只有当新值提交后，事务才会切换到读取新值。

快照隔离和可重复读

在一次事务中，先后两次读取同一对象所得到的内容不一致，这个现象就是不可重复读。快照隔离是解决这个问题的常见解决方案，每个事务都从数据库的 一致快照中读取，即使这些数据随后被另一个事务更改，每个事务也只能看到该特定时间点的旧数据。

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

表中的每一行都有一个 created_by 字段，其中包含将该行插入到表中的的事务 ID。此外，每行都有一个 deleted_by 字段，最初是空的。如果某个事务删除了一行，那么该行实际上并未从数据库中删除，而是通过将 deleted_by 字段设置为请求删除的事务的 ID 来标记为删除。在稍后的时间，当确定没有事务可以再访问已删除的数据时，数据库中的垃圾收集过程会将所有带有删除标记的行移除，并释放其空间。

当一个事务从数据库中读取时，事务 ID 用于决定它可以看见哪些对象，看不见哪些对象。通过仔细定义可见性规则，数据库可以向应用程序呈现一致的数据库快照。工作流程如下：

  1. 在每次事务开始时，数据库列出当时所有其他（尚未提交或尚未中止）的事务清单，即使之后提交了，这些事务已执行的任何写入也都会被忽略。
  2. 被中止事务所执行的任何写入都将被忽略。
  3. 由具有较晚事务 ID（即，在当前事务开始之后开始的）的事务所做的任何写入都被忽略，而不管这些事务是否已经提交。
  4. 所有其他写入，对应用都是可见的。

换句话说，如果以下两个条件都成立，则可见一个对象：

  • 读事务开始时，创建该对象的事务已经提交。
  • 对象未被标记为删除，或如果被标记为删除，请求删除的事务在读事务开始时尚未提交。

防止更新丢失

如果应用从数据库中读取一些值，修改它并写回修改的值（读取 - 修改 - 写入序列），则可能会发生丢失更新的问题。如果两个事务同时执行，则其中一个的修改可能会丢失，因为第二个写入的内容并没有包括第一个事务的修改。

许多数据库提供了原子更新操作，从而消除了在应用程序代码中执行读取 - 修改 - 写入序列的需要。原子操作通常通过在读取对象时，获取其上的排它锁来实现，以便更新完成之前没有其他事务可以读取它。

防止丢失更新的另一个选择是让应用程序显式地锁定将要更新的对象。然后应用程序可以执行读取 - 修改 - 写入序列，如果任何其他事务尝试同时读取同一个对象，则强制等待，直到第一个读取 - 修改 - 写入序列完成。FOR UPDATE 子句告诉数据库应该对该查询返回的所有行加锁。

原子操作和锁是通过强制读取 - 修改 - 写入序列按顺序发生，来防止丢失更新的方法。另一种方法是允许它们并行执行，如果事务管理器检测到丢失更新，则中止事务并强制它们重试其读取 - 修改 - 写入序列。这种方法的一个优点是，数据库可以结合快照隔离高效地执行此检查。

在不提供事务的数据库中，有时会发现一种原子操作：比较并设置（CAS, 即 Compare And Set）。此操作的目的是为了避免丢失更新：只有当前值从上次读取时一直未改变，才允许更新发生。如果当前值与先前读取的值不匹配，则更新不起作用，且必须重试读取 - 修改 - 写入序列。

写入偏差和幻读

写入偏差指的是多个事务从同一时间点的快照中读取数据，然后分别对数据进行修改，而这些修改操作彼此之间没有直接的数据冲突（例如，它们操作的是不同的行），因此数据库系统不会检测到冲突，从而允许它们并行提交。但由于事务之间缺乏相互“感知”，最终提交后的数据状态可能会违背业务规则或逻辑约束。

假设有一个医院调度系统，规定“至少必须有一名医生处于值班状态”。假设只有两名医生A和B，各自对应一行数据记录。当两个医生同时决定请假时：

  • 事务1（医生A）读取当前状态，看到医生B仍在值班，于是决定更新自己的状态为“请假”；
  • 同时，事务2（医生B）也读取状态，看到医生A仍在值班，也将自己的状态更新为“请假”。

由于这两个事务分别更新不同的行，它们之间没有直接的写冲突，系统允许它们并行提交。结果就是两位医生都请假，违反了“至少一名医生值班”的业务规则。

写入偏差是由幻读引起的。幻读指的是在同一事务中，连续两次执行相同的查询时，结果集中的数据条目出现了“幻影”——即第二次查询返回了与第一次不同的数据行。其根本原因在于，在第一次查询后，其他并发事务对数据库进行了插入或删除操作，导致满足查询条件的数据集合发生了变化。

为了解决幻读，除了实体化冲突这一“最后手段”，大多数情况下，可串行化这一隔离级别更可行。

串行化

可串行化隔离通常被认为是最强的隔离级别。它保证即使事务可以并行执行，最终的结果也是一样的。因此数据库保证，如果事务在单独运行时正常运行，则它们在并发运行时继续保持正确。下面讨论几种实现可串行化的技术。

2PL

两阶段锁协议（Two-Phase Locking，简称 2PL）是一种经典的数据库并发控制算法，是一种所谓的悲观并发控制机制，它是基于这样的原则：如果有事情可能出错（如另一个事务所持有的锁所表示的），最好等到情况安全后再做任何事情。2PL 用于确保事务调度的冲突可串行化，只要没有写入，就允许多个事务同时读取同一个对象。但对象只要有写入（修改或删除），就需要独占访问权限：

  • 如果事务 A 读取了一个对象，并且事务 B 想要写入该对象，那么 B 必须等到 A 提交或中止才能继续（这确保 B 不能在 A 底下意外地改变对象）。
  • 如果事务 A 写入了一个对象，并且事务 B 想要读取该对象，则 B 必须等到 A 提交或中止才能继续。

读与写的阻塞是通过为数据库中每个对象添加锁来实现的。锁可以处于共享模式或独占模式。锁使用如下：

  • 若事务要读取对象，则须先以共享模式获取锁，同时允许多个事务持有共享锁。但如果另一个事务已经在对象上持有排它锁，则这些事务必须等待。
  • 若事务要写入一个对象，它必须首先以独占模式获取该锁，没有其他事务可以同时持有锁（无论是共享模式还是独占模式），所以如果对象上存在任何锁，该事务必须等待。
  • 如果事务先读取再写入对象，则它可能会将其共享锁升级为独占锁。升级锁的工作与直接获得独占锁相同。
  • 事务获得锁之后，必须继续持有锁直到事务结束（提交或中止）。这就是 “两阶段” 这个名字的来源：第一阶段（当事务正在执行时）获取锁，第二阶段（在事务结束时）释放所有的锁。

谓词锁

在会议室预订的例子中，如果一个事务在某个时间窗口内搜索了一个房间的现有预订，则另一个事务不能同时插入或更新同一时间窗口与同一房间的另一个预订。这一点可以通过谓词锁（predicate lock）实现，它属于所有符合某些搜索条件的对象，如：

1
2
3
4

SELECT * FROM bookings
WHERE room_id = 123 AND
      end_time > '2018-01-01 12:00' AND
      start_time < '2018-01-01 13:00';

谓词锁限制访问，如下所示：

  • 如果事务 A 想要读取匹配某些条件的对象，就像在这个 SELECT 查询中那样，它必须获取查询条件上的 共享谓词锁。如果另一个事务 B 持有任何满足这一查询条件对象的排它锁，那么 A 必须等到 B 释放它的锁之后才允许进行查询。
  • 如果事务 A 想要插入，更新或删除任何对象，则必须首先检查旧值或新值是否与任何现有的谓词锁匹配。如果事务 B 持有匹配的谓词锁，那么 A 必须等到 B 已经提交或中止后才能继续。

临键锁

不过谓词锁性能不佳，如果活跃事务持有很多锁，检查匹配的锁会非常耗时。大多数使用 2PL 的数据库实际上实现了索引范围锁（index-range locking，也称为临键锁 next-key locking），这是一个简化的近似版谓词锁。

在房间预订数据库中，你可能会在 room_id 列上有一个索引，并且 / 或者在 start_time 和 end_time 上有索引：

  • 假设你的索引位于 room_id 上，并且数据库使用此索引查找 123 号房间的现有预订。现在数据库可以简单地将共享锁附加到这个索引项上，指示事务已搜索 123 号房间用于预订。
  • 或者，如果数据库使用基于时间的索引来查找现有预订，那么它可以将共享锁附加到该索引中的一系列值，指示事务已经将 12:00~13:00 时间段标记为用于预定。

无论哪种方式，搜索条件的近似值都附加到其中一个索引上。现在，如果另一个事务想要插入、更新或删除同一个房间和 / 或重叠时间段的预订，则它将不得不更新索引的相同部分。在这样做的过程中，它会遇到共享锁，它将被迫等到锁被释放。

索引范围锁并不像谓词锁那样精确，但是由于它们的开销较低，所以是一个很好的折衷。

可串行化快照隔离

串行化快照隔离是一种乐观并发控制技术。在这种情况下，如果存在潜在的危险也不阻止事务，而是继续执行事务。当一个事务想要提交时，数据库检查是否有什么不好的事情发生，如果是的话，事务将被中止，并且必须重试。只有可串行化的事务才被允许提交。

9. 一致性与共识

一致性保证

分布式一致性主要是针对延迟和故障等问题来协调副本之间的状态。

可线性化

在最终一致的数据库，如果你在同一时刻问两个不同副本相同的问题，可能会得到两个不同的答案。如果数据库可以提供只有一个副本的假象（即只有一个数据副本），那么每个客户端都会有相同的数据视图，且不必担心复制滞后了。这就是线性一致性（原子一致性、强一致性）的思想。在一个线性一致的系统中，只要一个客户端成功完成写操作，所有客户端从数据库中读取数据必须能够看到刚刚写入的值。要维护数据的单个副本的假象，系统应保障读到的值是最近的、最新的，而不是来自陈旧的缓存或副本。

依赖线性一致性

  • 锁定和领导者选举：一个使用单主复制的系统，需要确保领导者真的只有一个，而不是几个（脑裂）。一种选择领导者的方法是使用锁，每个节点在启动时尝试获取锁，成功者成为领导者。不管这个锁是如何实现的，它必须是线性一致的，所有节点必须就哪个节点拥有锁达成一致。而在 ZooKeeper、etcd 之类的协调服务中，线性一致性被用于实现分布式锁和领导者选举，它们使用一致性算法，以容错的方式实现线性一致的操作。
  • 约束和唯一性保证：唯一性约束在数据库中很常见，例如，用户名或电子邮件地址必须唯一标识一个用户，而在文件存储服务中，不能有两个具有相同路径和文件名的文件。如果要在写入数据时强制执行此约束（例如，如果两个人试图同时创建一个具有相同名称的用户或文件，其中一个将返回一个错误），则需要线性一致性。

实现线性化系统

  • 主从复制（部分支持线性化）：如果从主节点或同步更新的从节点上读取，则可以满足线性化。但不是每个数据库都可以通过主从复制实现线性化，主要原因是采用了快照隔离的设计或者实现有 bug 。
  • 共识算法（可线性化）：后面详细介绍。
  • 多主复制（不能线性化）、无主复制（不一定能线性化）。

线性化的代价

线性化会以下代价：

  • 延迟增加：线性化所有操作按全局顺序排列，并满足实时性约束。这通常需要跨节点的协调，导致操作必须等待多数节点确认后才能完成，增加了请求延迟。
  • 可用性牺牲（CAP 理论）：根据CAP定理，网络分区发生时，系统需在一致性（C）和可用性（A）间选择。线性化要求强一致性（CP系统），可能导致部分节点在分区时拒绝服务，降低可用性。
  • 吞吐量受限：严格的操作顺序可能限制并行处理能力。多节点参与的共识过程也需要大量消息交换，消耗网络带宽和CPU资源，限制系统整体吞吐。

CAP 理论目的是探讨分布式系统设计的权衡之道：

  • C（Consistency）：一致性。
  • A（Availability）：可用性。
  • P（Partition tolerance）：分区容错性。

系统只能选择其中两个特性支持。但这种理解存在误导性，网络分区是一种故障，是无法选择或逃避分区的问题。

顺序保证

顺序与因果关系

如果系统服从因果关系所规定的顺序，就称之为因果一致性。如快照隔离提供了因果一致性，当从数据库中读取数据时，如果查询到了某些数据，也一定能看到出发该数据的前序事件。

可线性化一定包含着因果关系，任意可线性化的系统都将正确地保证因果关系。这一结论是线性化系统更加简单易懂。在许多情况下，许多看似需要线性化的系统实际上真正需要的是因果一致性。

序列号排序

跟踪所有的因果关系不切实际，使用序列号或时间戳来排序事件是更好的方法。

可以按照与因果关系一致的顺序来构建序列号，这样的全局排序可以获取所有的因果关系。例如在主从复制数据库中，复制日志定义了与因果关系一致的写操作全序关系。当单一主节点为每个操作递增某个计数器，从而为复制日志中的每个操作复制一个单调递增的序列号，从节点也是一样的序列号。

然而在多主复制数据库中，产生的序列号在每个主节点中都是独立的，因此因果关系无法得到保证。这点可以由兰伯特时间戳解决。

首先每个节点有一个唯一的标识，且都有一个计数器记录自己处理的请求总数。兰伯特时间戳格式如下：（计数器，节点 ID），节点 ID 保证了时间戳的唯一性。兰伯特时间戳与实践的时间不存在直接对应关系，但是可以保证全序：给定某个兰伯特时间戳，计数器大的那个时间戳大；如果计数器相同，则节点 ID 大的时间戳大。因此，兰伯特时间戳解决了多主复制数据库的因果一致性。但是当涉及到分布式系统的并发操作，兰伯特时间戳并不能解决这个一致性问题。

全序关系广播

全序关系广播是指节点之间交换消息的某种协议，它要求满足两个基本安全属性：

  • 可靠发送：没有消息丢失，如果消息发送到了某一节点，则它一定要发送到所有节点。
  • 严格有序：消息总是以相同顺序发送给每个节点。

有了全序关系广播就可以构建线性化的存储系统，比如以追加日志的方式来实现线性化的 CAS 操作：

  1. 在日志中追加一条消息，并指明想要的数据。
  2. 读取日志，将其广播给所有节点，并等待回复。
  3. 检查是否有任何消息声称该数据已被占用，如果第一条这样的回复来自于当前节点，那么成功获得该数据，反之终止操作。

由于日志条目以相同的顺序发送到所有节点，而如果存在多个并发写入，则需要决定哪个请求在先，选择第一个写请求作为获胜者，并终止其他请求。此过程保证了线性化写入，但无法保证线性化读取。

可以证明线性化的 CAS 操作与全序关系广播二者都等价于共识问题，如果能解决其中一个，就可以应用于其他问题。

分布式事务与共识

原子提交与两阶段提交

在分布式事务中，原子性要求事务的所有操作要么全部提交，要么全部中止。

两阶段提交（2PC） 通过协调者（Coordinator）和参与者（Participant）的交互，分两个阶段实现原子提交：

  1. 准备阶段：先向所有参与者发送“准备提交”请求，附带事务数据，然后参与者进行预提交。参与者检查本地是否可提交，若可提交，将事务日志写入磁盘，回复“同意”，若不可提交（如违反约束），回复“中止”。
  2. 提交/中止阶段：
    • 协调者决策：
      • 若收到所有参与者的“同意”，协调者决定提交，持久化提交决定到日志。
      • 若任一参与者回复“中止”或超时未响应，协调者决定中止。
    • 协调者广播决定：向所有参与者发送提交或中止指令。
    • 参与者根据指令提交或中止事务，释放资源，并回复确认（ACK）。协调者收到所有ACK后，事务结束。

2PC 容易遇到以下问题：

  • 协调者单点故障：若协调者在阶段2宕机，参与者可能因未收到最终指令而阻塞（处于“不确定”状态），导致资源长期锁定。
  • 参与者故障：参与者在回复“同意”后宕机，恢复后必须能根据协调者日志完成提交或中止，否则可能违反原子性。
  • 网络分区：若协调者与部分参与者失联，可能导致部分节点提交、部分节点中止，破坏原子性。

可以使用三阶段提交（3PC）或共识算法替代。

支持容错的共识

共识算法必须满足以下性质：

  • 协商一致性：所有的节点都接受相同的决议。
  • 诚实性：所有节点不能反悔。
  • 合法性：如果决定了值，则这个值一定是由某个节点所提议的。
  • 可终止性：节点如果不崩溃则最终一定可以达成协议。

如果不关心容错，那么满足前三个属性很容易。可终止性引入了容错的思想，它强调一个共识算法不能原地空转，即必须取得进展。即使某些节点出现了故障，其他节点也必须最终做出决定。可终止性的前提是，发生崩溃或不可用的节点数必须小于半数。

共识算法有 Paxos、Raft等，它们决定了一系列值，然后采用全序关系广播算法。