《数据密集型应用系统设计》¶

互联网企业最重要的资产就是数据，我们每天编写的代码就是在操作数据。

如今许多新型应用都是数据密集型（data-intensive），而非计算密集型（compute-intensive）。

每个组件高效完成其中一部分功能，多个组件依靠应用层代码驱动有机衔接起来。

• 可靠性：即使发生了某些错误（fault），系统仍可以继续正常工作（not failure）
  • 硬件故障：添加冗余硬件，如磁盘配置 RAID、服务器配置双电源、异地备份等
  • 软件错误：错误的代码耗光系统资源、依赖服务变得缓慢、底层故障被级联放大等。需设计代码时考虑边界条件、充分测试、增强监控报警
  • 人为失误：以最小出错的方式来设计系统，如避免让新手操作生产环境、对新手代码进行审查、解耦易于出错的部分、充分的测试（单元测试、集成测试等）、代码回滚等
• 可扩展性：随着规模的增长，是否可以快速满足新的业务需求（水平扩展与垂直扩展）
• 可维护性：避免系统的单点依赖、让系统设计更为简单、易于迭代

对用户而言，最关注的指标为响应时间，需尽可能控制在 1s 以内。

不同的系统有不同的负载描述方式：如网站为每秒的请求量 rps、聊天室为同时在线人数、数据库为读写比、缓存为命中率。

图状数据模型¶

图由两种对象组成：顶点（也称为结点或实体）和边（也称为关系或弧）。很多数据可以建模为图。典型的例子包括：

• 社交网络：顶点是人，边指示哪些人彼此认识
• Web 图：顶点是网页，边表示与其他页面的 HTML 链接。PageRank 可以计算 Web 图上网页的流行度，从而确定搜索排名
• 公路或铁路网：顶点是交叉路口，边表示他们之间的公路或铁路线。汽车导航系统搜索道路网中任意两点之间的最短路径

存储系统中最重要的权衡设计：适当的索引可以加速读取查询，但每个索引都会减慢写入速度。

Lucene 是 Elasticsearch 和 Solr 等全文搜索系统的索引引擎。

辅助索引都是非聚簇索引

主键索引的叶子节点存的是整行数据，而二级索引叶子节点内容是主键的值。如果二级索引满足查询需求，则直接返回，即为覆盖索引，反之则需要回表去主键索引 (聚簇索引) 查询。主键长度越小，普通索引的叶子节点就越小，二级索引占用的空间也就越小，所以要避免使用过长的字段作为主键

布隆过滤器是内存高效的数据结构，用于近似计算集合的内容。如果数据库中不存在某个键，则可以很快返回结果。布隆过滤器判断存在的值在数据库中则不一定存在。

LevelDB 与 RocksDB 的工作原理：

• 当写入时，将其添加到内存中的平衡树数据结构中 (例如红黑树)。这个内存中的树有时被称为内存表。
• 当内存表大于某个阈值 (通常为几兆字节) 时，将其作为 SSTable（排序字符串表）文件写入磁盘。由于树已经维护了按键排序的 key-value 对，写磁盘可以比较高效。新的 SSTable 文件成为数据库的最新部分。当 SSTable 写磁盘的同时，写入可以继续添加到一个新的内存表实例。
• 为了处理读请求，首先尝试在内存表中查找键，然后是最新的磁盘段文件，接下来是次新的磁盘段文件，以此类推，直到找到目标 (或为空)
• 后台进程周期性地执行段合并与压缩过程，以合并多个段文件，并丢弃那些已被覆盖或删除的值。

LSM（Log-Structured Merge Tree，日志结构的存储引擎）的关键思想是系统地将磁盘上随机访问写入转为顺序写入，由于硬盘驱动器和 SSD 的性能特性，可以实现更高的写入吞吐量。

不同的策略会影响甚至决定 SSTables 压缩和合并时的具体顺序和时机。最常见的方式是大小分级和分层压缩。LevelDB 和 RocksDB 使用分层压缩，HBase 使用大小分级，Cassandra 则同时支持这两种压缩。在大小分级的压缩中，较新的和较小的 SSTables 被连续合并到较旧和较大的 SSTables。在分层压缩中，键的范围分裂成多个更小的 SSTables，旧数据被移动到单独的“层级”，这样压缩可以逐步进行并节省磁盘空间。

日志结构索引将数据库分解为可变大小的段，通常大小为几兆字节或更大，并且始终按顺序写入段。相比之下，B-tree 将数据库分解成固定大小的块或页，传统上大小为 4 KB (有时更大)，页是内部读/写的最小单元。这种设计更接近底层硬件，因为磁盘也是以固定大小的块排列。

B-tree 底层的基本写操作是使用新数据覆盖磁盘上的旧页。LSM-tree 仅追加更新文件 (并最终删除过时的文件)，但不会修改文件。

预写日志 ( write-ahead log, WAL)，也称为重做日志。这是一个仅支持追加修改的文件，每个 B-tree 的修改必须先更新 WAL 然后再修改树本身的页。当数据库在崩溃后需要恢复时，该日志用于将 B-tree 恢复到最近一致的状态。

写放大：一次数据库写入请求导致的多次磁盘写操作。

OLTP 主要有两个流派：

• 日志结构流派：只允许追加式更新文件和删除过时的文件，但不会修改已写入的文件。BitCask、SSTables、LSM-tree、LevelDB、Cassandra、HBase、Lucene 等都属于此类
• 原地更新流派：将磁盘视为可以覆盖的一组固定大小的页。B-tree 是其典型代表

倒排索引

• 正排：一个文档中包含了哪些词汇
• 倒排：一个词汇被哪些文档所包含

数据仓库¶

在线事务处理（online transaction processing, OLTP）

在线分析处理（online analytic processing, OLAP）

大公司可能有几十到上百个系统，由于这些系统至关重要，往往期望它们高度可用，处理事务时延迟足够低，DBA 通常不愿意让业务分析人员在 OLTP 数据库上直接运行临时分析查询，这些查询通常代价很高，要扫描大量的数据，这可能损害并发执行事务的性能。数据仓库则包含了公司各种 OLTP 系统的只读副本，分析人员可以在不影响 OLTP 的情况下尽情使用。

将数据导入数据仓库的过程称为提取 - 转换 - 加载（Extract-Transform-Load, ETL）。

数据仓库的数据模型最常见的是关系型，因为 SQL 通常适合分析查询。

数据仓库包含星型与雪花分析模式。雪花模式比星型模式更规范化，但星型模式通常是首选，主要是因为星型模式对分析人员更简单。

知名的数据仓库软件：

• Apache Hive：构建在 Hadoop 之上的数据仓库工具。将 SQL 转换为 MapReduce 任务，适合超大规模数据的离线批处理。
• Spark：统一的大数据分析及计算引擎。基于内存计算，速度远快于 MapReduce，除批处理外还支持流处理、机器学习和交互式查询（Spark SQL）。
• Presto：Facebook 开发的分布式 SQL 查询引擎。专为低延迟、交互式分析设计，支持跨多个不同数据源（如 HDFS、MySQL 等）进行高效的联邦查询。

数据编码¶

JSON 不像 XML 那么冗长，但与二进制相比，两者仍占用大量空间，因此 Protocol Buffers 等高效压缩的二进制格式应运而生。

人类可读的文本格式包括：

• JSON
• XML
• YAML

二进制格式包括：

• Base64（会使数据大小增加 33%）
• Avro（应用于 Hadoop）。Avro 相比 Protocol Buffers 和 Thrift，其优点是不包含任何标签号，当数据库字段发生变化时，PB 和 Thrift 都需要小心地手动更新字段标签
• BSON（应用于 MongoDB 中）
• Protocol Buffers（由 Google 开发）
• Thrift（由 Facebook 开发）
• MessagePack

面向服务（service-oriented architecture, SOA）/微服务体系结构的一个关键设计目标是，通过使服务可独立部署和演化让应用程序更易于更改和维护。

REST 和 SOAP 是两种流行的 Web 服务方法。

• REST 不是一种协议，而是一个基于 HTTP 原则的设计理念。它强调简单的数据格式，使用 URL 来标识资源，并使用 HTTP 功能进行缓存控制、身份验证和内容类型协商。根据 REST 原则所设计的 API 称为 RESTful。
• SOAP Web 服务的 API 使用被称为 WSDL（Web Services Description Language）。由于 WSDL 的设计目标不是人类可读的，而且 SOAP 消息通常过于复杂，无法手动构建，SOAP 用户严重依赖工具支持、代码生成和 IDE。对于没有 SOAP 供应商支持的编程语言的用户来说，试图与 SOAP 服务集成非常困难。

RPC 经常用于跨组织边界的通信时，服务的兼容性会变得更加困难，服务提供者无法控制客户，也无法强制升级。而 RESTful API 可以在 URL 或 HTTP 头中使用版本号。

与 RPC 相比，消息队列有几个优点：

• 当接收方不可用或过载时，可以充当缓冲区，从而提高系统的可靠性
• 消息发送失败时，可以重新发送消息
• 逻辑上将收发双方分离

消息队列与 RPC 的差异在于，消息通常是单向的：发送方并不期望收到接收方的回复。

知名消息队列软件：Kafka、RabbitMQ、RocketMQ

数据复制¶

数据复制的目的：

• 用户就近访问
• 提供备份以便故障转移
• 提升读的吞吐量

数据复制时的数据同步方式：

• 同步：主库等待所有从库同步完成才确认数据提交，这虽然保证了数据的完整性和准确性，但同时导致：
  • 响应时间变长
  • 任何一个从库无法完成同步（如节点崩溃、网络故障等）导致无法完成确认，进而导致主节点阻塞后续的写入请求
• 半同步：部分从库同步完成即视为数据写入成功
• 异步：保证主节点良好的写入能力，而不受从节点数量影响；缺点则是主节点崩溃并无法恢复会导致尚未同步的数据丢失。异步同步只能保证数据的最终一致性

复制日志的实现方式：

• 基于语句的复制：优缺点参见《高性能 MySQL》笔记相关内容
• 基于行的逻辑日志复制：由于逻辑日志与存储引擎逻辑解耦，因此可以更容易地保持向后兼容，从而使主从节点能够运行不同版本的软件甚至是不同的存储引擎，如 https://github.com/alibaba/canal/
• 基于预写日志（WAL）传输：PostgreSQL、Oracle 等支持这种复制方式。由于 WAL 中包含了哪些磁盘块的哪些字节发生变化等细节，使得复制方案和存储引擎紧密耦合，版本不同就可能导致无法复制
• 基于触发器的复制：该方式通常比其他方式开销更高，也比数据库内置复制更容易出错，但其高度灵活性仍有用武之地。Oracle 的 Databus 和 Postgre 的 Bucardo 就是此技术的典型代表

数据复制的三种方法：

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

新的从节点数据导入步骤：

1. 在某个时间点对主库数据快照
2. 将此快照导入从节点
3. 将从节点连接至主节点并请求快照点之后的变更数据
4. 从节点追赶主节点的变更

处理失效节点：

• 从节点失效：追赶式恢复
• 主节点失效：节点切换
  • 大多数系统采用基于心跳包超时的机制判断节点是否失效
  • 候选节点最好与原主节点的数据差异最小，以最小化数据丢失的风险
  • 若原主节点之后重新上线，可能没有意识到其它节点已经达成共识迫使其下台，此时系统要确保原主节点降级为从节点，并认可新的主节点
  • 如果两个节点同时自认为是主节点，这种情况被称为脑裂。它非常危险：两个主节点都可能接受写请求，并且没有很好的解决冲突的办法，最后数据可能丢失或破坏。作为一种安全应急方案，某些系统会强制关闭其中的一个节点。

由于节点失效是否真的失效仅通过心跳包难以判断，即便系统能够支持自动故障切换，有些运维团队仍然更愿意以手动的方式来控制整个切换过程。

复制滞后问题（正常情况下，主从同步延时可能不足 1 秒）：

多主节点复制

• 场景：
  • 多数据中心。在一个数据中心内使用多主节点意义不大，其复杂性已超过所带来的好处。对于多数据中心，在每个数据中心内，采用常规的主从复制方案；而在数据中心间，由各个数据中心的主节点来负责同其它数据中心的主节点进行数据的交换、更新
  • 离线客户端操作。如 iPhone 的 Notes 应用，允许设备离线时记录笔记，待联网时将本地的写入同步至其它设备。此时，每个设备都有一个充当主节点的本地数据库
  • 在线协作编辑。飞书文档在多人同时编辑同一个单元格时，内容以最后的提交者为准
• 多主节点复制的好处：
  • 性能提升：每个写操作可以在本地数据中心快速响应，然后采用异步同步方式将变化同步至其它数据中心，对应用层有效屏蔽了数据中心间的网络延迟，使得终端用户体验到更好的性能
  • 容忍数据中心失效：每个数据中心独立运行，发生故障的数据中心可以在恢复后更新到最新状态
  • 容忍网络问题：写操作对网络性能和稳定性更加依赖，而广域网的网络质量往往不如本地网络可靠
• 多主节点复制的缺点：
  • 不同数据中心可能会同时修改相同的数据，因而必须解决潜在的写冲突

处理写冲突：

• 所有写入操作路由到同一数据中心，并在该数据中心的主节点上读写
• 为每个写入分配唯一的 ID，如时间戳、足够长的随机数、UUID 或基于键值的哈希，选择最高 ID 的写入作为胜利者，并将其它写入丢弃，但容易丢失数据。
• 为每个副本分配唯一 ID，并制定规则，高序号副本高于低序号副本，该方案同样有数据丢失的问题
• 以每种方式将值合并，如同时分别写入 B 和 C，合并结果为 B/C
• 利用预定义的格式记录并保留冲突的所有信息，然后依靠应用层的逻辑，事后提示用户解决冲突

节点失效时写入数据库

• 当用户并行向 3 个节点写入数据时，其中有两个写入成功，一个无法处理写入请求，此时可认为写入成功。假设在数据读取时，失效节点重新上线，读取请求可能读取到失效节点的数据。为了避免这个问题，可以通过以下方式解决：
  • 并发读取多个副本，通过版本号确定哪个值更新
  • 通过对比主从节点的偏移量，判断从节点的落后程度

检测并发写：

• 最后写入者获胜（last write wins, LWW）：为每个写请求附加一个时间戳，选择最新的时间戳写入，丢弃较早的写入
• 确定请求的前后关系：每次写入分配版本号

第 6 章 数据分区¶

分区的挑战¶

数据分区后的挑战：

• 数据倾斜。倾斜的数据分区会导致效率严重下降，系统瓶颈在最繁忙的那个节点上。
• 访问时确定数据的所在分区

通过哈希分区可以解决数据写入的倾斜问题。虽然哈希可以将数据均匀分布到分区上，但在某些情况下仍无法完全解决倾斜问题，如在社交媒体上，某个拥有百万粉丝的明星用户可能会引发访问风暴，造成数据的倾斜。

通过二级索引可以解决数据读取的问题。二级索引会导致写入速度减缓，当更新文档时，可能需要更新多个二级索引，这导致二级索引维护较为耗时。在实践中，对全局二级索引的更新往往都是异步的。

当通过关键字哈希进行分区，我们就丧失了良好的区间查询特性。即使关键字相邻，但经过哈希之后会分散在不同的分区中，区间查询就失去了原有的有序相邻的特性。

一致性哈希对于数据库实际效果并不是很好，所以目前很少使用。

分区再平衡¶

假设节点出现故障下线，或者数据规模增加而新增节点，此时需要重新平衡分区以使数据分布均匀。再平衡时不能使用取模的方式，这会导致节点数发生变化时，很多关键字需要从现有节点迁移到其它节点上。可以使用：

• 固定数量的分区：假设一个 10 节点的集群，数据库一开始逻辑划分为 1000 个分区，每个节点承担 100 个分区。当新增节点时，新节点可以从当前节点上匀走几个分区，直至分区达到平衡；如果删除节点，则采取相反的均衡措施。
• 动态分区：当分区的数据增长超过一个可配的参数阈值，它就拆分为两个分区，每个承担一半的数据量。相反，如果大量数据被删除，并且分区缩小到某个阈值以下，则将其与相邻分区进行合并。该过程类似于 B 树的分裂操作。

第 7 章 事务¶

事务的 ACID 代表

• 原子性 ( Atomicity)
• 一致性 ( Consistency)
• 隔离性 ( Isolation)
• 持久性 ( Durability)

不符合 ACID 标准的系统有时会被称为 BASE，即：

• 基本可用性 (Basically Available)
• 软状态 (Soft state)
• 最终一致性 (Eventual consistency)

第 8 章 分布式系统的挑战¶

作为开发者，我们的核心任务是构建可靠的系统，即使系统面临各种出错的可能，也需要完成预定工作（确保满足用户期望）。我们需要在不可靠的组件上构建可靠的系统。

在单节点上开发时，通常以一种确定性的方式运行：要么工作，要么出错。而分布式系统中，经常部分功能失效，或者我们无法确认处理结果。

不可靠的网络¶

当一个请求发送之后等待响应的过程中，有很多事情可能出错：

1. 请求可能已经丢失 ( 比如有人拔掉了网线)
2. 请求可能正在某个队列中等待，无法马上发送 (也许网络或接收方已经超负荷)
3. 远程接收节点可能已经失效 (例如崩溃或关机)
4. 远程接收节点可能暂时无法响应 (例如正在运行长时间的垃圾回收)
5. 远程接收节点已经完成了请求处理，但回复却在网络中丢失 (例如网络交换机配置错误)
6. 远程接收节点已经完成了请求处理，但回复却被延迟处理 (例如网络或者发送者的机器超出负荷)

有计划地人为触发网络问题，以测试系统的反应情况

超时时间设置并不是一个不变的常量，而是需要像 TCP 重传那样持续测量响应时间及其抖动，然后根据最新的响应时间分布来自动调整。

网络拥塞与排队：

• 当多个不同节点同时发送数据包到相同的目标节点时，网络交换机会出现排队，然后依次将数据包转发到目标网络。如果数据量太大，交换机队列塞满，之后的数据包则会被丢弃，网络还在运转，但会引发大量数据包重传
• 当数据包到达目标机器后，如果所有 CPU 核都处于繁忙状态，则网络数据包请求会被操作系统排队，直到应用程序能够处理
• 在虚拟化环境下，CPU 核会切换虚拟机，从而导致正在运行的操作系统会突然暂停几十毫秒。在这段时间，客户虚机无法从网络中接收任何数据，入向的包会被虚拟机管理器排队缓冲，进一步增加了网络延迟的不确定性
• TCP 执行流量控制时，节点会主动限制自己的发送速率以避免加重网络链路或接收节点负载。这意味着数据甚至在进入网络之前，已经在发送方开始了排队

电路非常适合音频或视频通话，通话期间只需每秒传送固定数量的数据。但对于访问网页，发送电子邮件或传输文件等无法事先确定带宽需求，我们只是希望它尽快完成。TCP 动态调整传输速率则可以充分利用所有可用的网络容量。

不可靠的时钟¶

分布式系统的时区、时间是否同步？依赖于时间的请求时间是否可信？

某些软件如果在指定时间内无法响应则会导致严重后果，这些运行环境包括：飞机，火箭，机器人，汽车和其他需要对输入传感器快速做出响应的组件等。对于这些系统，软件有一个必须做出响应的上限：如果无法满足，会导致系统级故障。

在很多情况下，系统中只允许有一个实例，多个实例会造成冲突，如下图 GC 暂停了客户端 1 的锁操作，导致文件被损坏。为了解决这样的问题，假设每次锁服务在授予锁或租约时，还会同时返回一个 fencing 令牌，该令牌 (数字) 每授授予一次就会递增 (例如，由锁服务增加) 。然后，要求客户端每次向存储系统发送写请求时，都必须包含所持有的 fencing 令牌。

当使用 ZooKeeper 作为锁服务时，可以用事务标识 zxid 或节点版本 cversion 来充当 fencing 令牌，这两个都可以满足单调递增的要求。

拜占庭故障¶

节点明明没有收到某条消息，但却对外声称收到了。这种行为称为拜占庭故障，在这样不信任的环境中需要达成共识的问题也被称为拜占庭将军问题。

拜占庭将军问题：有 n 位将军需要达成共识，并且其中存在一些叛徒试图阻挠达成共识。大多数的将军都是忠诚的，发出了真实的信息，但是叛徒则试图通过发送虚假或不真实的信息来欺骗和混淆他人 (同时努力隐藏自己)。而且大家事先并不知道叛徒是谁。

如果某个系统中即使发生部分节点故障，甚至不遵从协议，或者恶意攻击、干扰网络，但仍可继续正常运行，那么我们称之为拜占庭式容错系统。这些担忧在某些特定场景是合理的。如航空航天领域，内存或 CPU 中的数据可能受辐射而发生故障，导致严重后果，飞行控制系统必须做到容忍拜占庭故障。还有像比特币和其它区块链的点对点网络就是让互不信任的双方就某项交易达成一致，且不依赖于集中的机制。

我们通常并不使用拜占庭容错协议，而只是全权让服务器决定什么是可接受的客户端行为，什么是不允许的。只有在没有这种中央决策机制的点对点网络中，拜占庭容错才更为必要。

软件中的 bug 可以被认为是拜占庭式故障，但如果将相同的软件部署到所有节点上，那么即使拜占庭式的容错算法也无法解决问题。大多数拜占庭容错算法要求系统超过三分之二的节点即绝大多数要功能正常 (如果有四个节点，则最多允许一台发生故障)。

第 9 章 一致性与共识¶

一致性保证与线性一致性¶

大部分分布式数据库仅提供较弱的最终一致性（仅保证在停止写入后，副本最终会收敛）。为了简化应用层的开发难度，需要更强的一致性模型。

线性一致性¶

• 核心定义：又称强一致性、原子一致性。其目标是让整个系统看起来好像只有一个数据副本，且所有操作都是瞬时（原子）生效的。一旦某个客户端成功完成写入，所有客户端随后的读取必须返回该值或更新的值。
• 线性一致性 vs 序列化：
  • 序列化：针对多对象、多操作的事务隔离级别，保证事务并发执行的结果与某种串行执行结果一致（不要求实时性）。
  • 线性一致性：针对单对象、单个读写操作的最新性（Recency）保证，要求操作顺序与真实时间（物理时间）严格一致。
  • 两者结合即为严格序列化。
• 典型应用场景：
  • 分布式锁与主节点选举：确保任何时刻有且仅有一个节点持有锁或成为 Master（如 Chubby、ZooKeeper）。
  • 唯一性约束：例如用户注册抢占用户名、银行账户防透支等。
  • 跨信道时序依赖：例如用户上传图片（信道 1），接着发消息通知后台裁剪（信道 2）；若后台从一个落后的副本读取，会导致找不到图片。
• CAP 定理与线性一致性：
  • 当发生网络分区（P）时，系统必须在**线性一致性（C）与可用性（A）**之间进行权衡：若选择 C 则必须拒绝另一侧的读写导致不可用；若选择 A 则允许两侧独立读写，但丧失一致性。
  • 注：CAP 中的 C 专指线性一致性，不同于 ACID 中的一致性（状态合法约束）。

因果一致性与逻辑时钟¶

线性一致性由于受到光速和网络延迟的物理限制，且在发生网络分区时不可用，其代价极高。因此，许多系统转而选择提供更弱但性价比更高的因果一致性 (Causal Consistency)：如果操作 A 在因果上先于操作 B 发生，那么系统中的所有节点都必须保证先看到 A，再看到 B（允许并发无因果关系的操作以任意顺序被看到）。

要实现因果一致性，系统必须能够定义并跟踪分布式事件之间的因果依赖关系。然而，由于物理时钟不可靠（存在偏移与漂移），我们无法依赖绝对的物理时间来确定事件的先后。为了在不依赖物理时钟的前提下判定分布式事件的因果顺序，Lamport 提出了逻辑时钟的概念。

Lamport 时钟¶

逻辑时钟指的是分布式系统中用于区分事件的发生顺序的时间机制。具体如下：每个节点以及每个客户端都跟踪迄今为止所见到的最大计数器值，井在每个请求中附带该最大计数器值。当节点收到某个请求 (或者回复) 时，如果发现请求内嵌的最大计数器值大于节点自身的计数器值，则它立即把自己的计数器修改为该最大值。

Lamport 提出逻辑时钟就是为了解决分布式系统中的时序问题，即如何定义 a 在 b 之前发生。但缺点是无法仅凭时间戳大小反推因果关系（即若 \(L(a) < L(b)\)，不能判定 \(a \rightarrow b\)）。

Lamport 时钟被广泛应用于分布式锁（如 Ricart-Agrawala 算法）、生成分布式全局唯一且单调递增的事务/事件 ID。

注：Lamport 也是 LaTeX 和 Paxos 的作者。

向量时钟¶

向量时钟通过每个节点维护一个大小为 \(n\) 的时钟向量，记录所有节点已知的最新版本号，从而判定任意两个事件的因果关系，并精准识别并发冲突。缺点则是空间复杂度为 \(O(n)\)（\(n\) 为副本/节点数），在节点频繁动态增减的集群中管理与扩展极其困难。常见应用场景是高可用去中心化存储（如 Dynamo 的并发购物车合并、Riak 数据库、CouchDB 冲突检测）。

为了说明为什么向量时钟可以判定因果关系，我们假设系统中有两个节点 \(P_1\) 和 \(P_2\)，初始时钟均为 \(0\)。发生了以下四个事件：

• 事件 A：\(P_1\) 上的本地写操作。
• 事件 B：\(P_1\) 向 \(P_2\) 发送消息。
• 事件 C：\(P_2\) 上的本地写操作（与 \(P_1\) 此时的行为相互独立）。
• 事件 D：\(P_2\) 接收到 \(P_1\) 发送的消息。

下面是两种时钟在这些事件上的演进与对比：

P1: (A: L=1) ──► (B: L=2) [Send]
                        \
                        ▼
P2:     (C: L=1) ──► (D: L=3) [Recv]

P1: (A: [1,0]) ──► (B: [2,0]) [Send]
                        \
                            ▼
P2:      (C: [0,1]) ──► (D: [2,2]) [Recv]

工业界常用方案¶

• 物理时钟 + NTP (网络时间协议)：
  • 成本最低，但由于 NTP 偏差（通常在数毫秒至数百毫秒），无法用于强一致性场景。常配合 最后写入者胜 (LWW) 策略作为冲突解决手段，但有覆盖/丢失较新写入的风险。
• TrueTime API (Google Spanner 硬件方案)：
  • 依靠原子钟 + GPS 接收器双重硬件保障。它将全球节点的时钟不确定性误差限制在极小范围内（误差界限 \(\epsilon \le 7\text{ms}\)）。
  • 通过 Commit Wait 机制（写入事务时必须等待 \(\ge 2\epsilon\) 时间），确保了全球分布式事务的外部一致性 (Linearizability)。
• 混合逻辑时钟 (Hybrid Logical Clock, HLC 软件方案)：
  • 结合了物理时钟与 Lamport 逻辑时钟。既能让时钟值保持在接近物理时间的范围内，又能严格满足因果一致性，不需要昂贵的特殊硬件。
  • 典型应用：CockroachDB、YugabyteDB、MongoDB 等现代分布式 NewSQL/NoSQL 数据库。

分布式事务¶

事务提交不可撤销，不能事后再改变主意 (在提交之后再追溯去中止)。这些规则背后的深层原因是，一旦数据提交，就被其他事务可见，继而其他客户端会基于此做出相应的决策。这个原则构成了读 - 提交隔离级别的基础。

原子提交¶

• 两阶段提交
  • 2PC 中引入了协调者，第一阶段协调者询问所有参与者节点是否可以执行操作，收到确认后执行第二阶段的操作，如果所有参与者确认执行成功则 commit，否则 rollback。
  • 2PC 的问题在于，第二阶段参与者没有收到协调者的 commit/rollback 指令 (如 timeout、协调者宕机)，则参与者无法做出正确响应；另一方面，在 2PC 执行过程中间，节点都处于阻塞状态。
• 3PC（三阶段提交）：询问 → 锁定资源 → 执行。实际中使用 2PC 更普遍。

共识算法¶

• Paxos：过半投票、拒绝小于最大版本号的提交
• Raft：Redis 的哨兵 master 节点选举；日志一致性的复制（leader 节点日志显示 uncommitted 状态，在得到大多数节点的确认后，再更新为 committed 状态，然后通知剩余节点更新）。当单个节点超过得到半数以上的节点投票时，即竞选成功；如果有多个竞选者，得票相同则需要重新投票，直到选出唯一胜出者。

由于 Paxos 算法在理论上非常抽象，且在向多决策场景延伸时缺乏公认的工程规范，导致其实际开发难度极大、极易出错。相比之下，Raft 将共识问题拆解为领导者选举、日志复制和安全性三个明确的子问题，极大地提升了算法的可理解性与工程可实现性，同时保证了与 Paxos 相同的性能与容错性。因此，现代开源分布式系统（如 etcd、Consul 等）更普遍采用 Raft。

• Raft 官方互动演示：Raft Consensus Algorithm

其他¶

• DDIA 逐章精读：https://ddia.qtmuniao.com/

评论