1. 强一致性

1.1. 最终一致数据库通过跨多台机器分区和复制数据集来获得可扩展性，其代价是要跨副本维持强数据一致性以及允许冲突写入

• 1.1.1. 在更新数据对象后，不同的客户端可能会看到该对象的旧值或新值，直到所有副本都收敛到最新值

1.2. 另一类分布式数据库提供一种可替代的模型，即强一致性数据系统，也称为NewSQL或分布式SQL

• 1.2.1. 强一致性系统试图确保所有客户端在数据对象更新后看到相同、一致的值

• 1.2.2. 提供众所周知的ACID（原子性、一致性、隔离性、持久性）数据库事务来处理冲突更新的优势

1.3. 事务和数据一致性，是现有单节点关系数据库中每个人都熟悉的特征，消除了最终一致系统中固有的许多复杂性

1.4. 对于互联网规模的系统，最佳结果当然是提供强一致数据库的好处，同时具备最终一致系统的性能和可用性

1.5. 强一致数据库则旨在提供与单节点系统相同的一致性保证

• 1.5.1. 有了强一致性，你在编写应用程序时便可以确保一旦数据库确认更新，所有客户端的后续读取就会看到新值

1.6. 事务和副本一致性的解决方案由不同的技术社区在不同的时间开发

• 1.6.1. 事务一致性

  • 1.6.1.1. 对于事务一致性，二阶段提交算法起源于Jim Gray（数据库系统先驱之一）1978年的工作

  • 1.6.1.2. 在支持ACID事务的分布式数据库中，你需要一种算法，使得在单个事务中更新来自不同物理数据分区和节点的数据对象时能够保持一致性

• 1.6.2. 副本一致性

  • 1.6.2.1. 强副本一致性意味着在数据对象更新后，无论客户端访问哪个副本，都会看到相同的值

  • 1.6.2.2. 用于实现事务和副本一致性的算法称为共识算法(consensus algorithm)，它们使分布式系统中的节点能够就某些共享状态的值达成共识或协议

1.7. ACID事务

• 1.7.1. 原子性(Atomicity)

  • 1.7.1.1. 对数据库的所有更改都必须像单个操作一样执行，所有更新必须都成功（提交）​，或者必须都失败（回滚）​

• 1.7.2. 一致性(Consistency)

  • 1.7.2.1. 事务将使数据库处于一致状态

• 1.7.3. 隔离性(Isolation)

  • 1.7.3.1. 当事务正在进行时，事务修改的任何数据对其他并发事务是不可见的

• 1.7.4. 持久性(Durability)

  • 1.7.4.1. 如果事务提交，则所做的更改是永久性的，并且在系统出现故障时可以恢复

1.8. 具有一致性保证和支持简易单机编程的可扩展和高可用的分布式数据库是数据管理系统的“必杀技”​

2. 一致性模型

2.1. 最强的一致性模型，也称为严格一致性、严格可串行化或外部一致性的模型，是数据库和分布式系统社区定义的两个最具限制性的一致性模型的组合

2.2. 可串行化

• 2.2.1. 可串行化通常称为事务一致性，即ACID中的“C

• 2.2.2. 事务对多个数据对象执行一次或多次读取和写入

• 2.2.3. 可串行化保证在多个项目上执行一组并发事务时等同于事务按某种顺序执行

2.3. 可线性化

• 2.3.1. 可线性化可线性化与读取和写入单个数据对象有关

• 2.3.2. 可线性化定义了使用挂钟时间(wall clock time)的操作顺序，挂钟时间较近的操作会发生在挂钟时间较远的操作之后

3. 分布式事务

3.1. 从应用程序开发人员的角度来看，将事务视为一种简化分布式系统故障场景的工具是最容易理解的

• 3.1.1. 应用程序只需简单地定义使用ACID属性执行哪些操作，剩下的由数据库完成

• 3.1.2. 事务语义确保两个操作要么都成功要么都失败

• 3.1.3. 锁是确保事务隔离性所必需的

3.2. 二阶段提交

• 3.2.1. 经典的副本一致性算法Paxos于1998年由Leslie Lamport首次提出

• 3.2.2. 二阶段提交(two-Phase Commit，2PC)是经典的分布式事务共识算法

  • 3.2.2.1. 在SQL Server和Oracle等关系数据库以及VoltDB和Cloud Spanner等现代分布式SQL平台中广泛应用

• 3.2.3. 二阶段提交也得到外部中间件平台的支持

  • 3.2.3.1. Java Enterprise Edition中的Java Transaction API(JTA)和Java Transaction Service(JTS)

  • 3.2.3.2. 外部协调器可以使用XA协议驱动跨异构数据库的分布式事务

• 3.2.4. 当数据库客户端启动事务时，选择一个协调器

  • 3.2.4.1. 协调器分配一个全局唯一的tid（事务标识符）并将其返回给客户端

  • 3.2.4.2. tid标识的是由协调器维护的数据结构，称为事务上下文

  • 3.2.4.3. 事务上下文记录了参与事务的数据库分区或参与者，以及它们的通信状态

  • 3.2.4.4. 上下文由协调器保存，持久地维护事务的状态

• 3.2.5. 准备阶段（投票阶段）

  • 3.2.5.1. 协调器向所有参与者发送一条消息，告诉它们准备提交事务

• 3.2.6. 执行阶段

  • 3.2.6.1. 当所有参与者都对准备阶段做出答复时，协调器将检查结果

  • 3.2.6.2. 如果所有参与者都可以提交，则整个事务可以提交，协调器向每个参与者发送提交消息

  • 3.2.6.3. 如果任意参与者决定中止事务，或者在指定的时间段内没有回复协调器，协调器则发送一个中止消息给每个参与者

• 3.2.7. 故障分析

  • 3.2.7.1. 故障可能是由系统崩溃或与应用程序的其他部分分区引起的

  • 3.2.7.2. 参与者故障

    3.2.7.2.1. 若参与者在准备阶段完成之前崩溃，事务将被协调器中止，这是一个简单的故障场景

    3.2.7.2.2. 也可能参与者先回复准备消息，然后出现故障

    3.2.7.2.3. 从本质上讲，参与者故障不会威胁一致性，因为它会达到正确的事务结果

  • 3.2.7.3. 协调器故障

    3.2.7.3.1. 如果协调器在发送准备消息后发生故障，参与者就会进退两难

    3.2.7.3.1.1. 决定投票提交的参与者必须阻塞，直到协调器通知他们事务结果

    3.2.7.3.1.2. 如果协调器在发送提交消息之前或期间崩溃，参与者将无法继续，因为协调器已经失败并且在恢复之前不会发送事务结果

    3.2.7.3.2. 协调器故障没有简单的解决方法

    3.2.7.3.3. 唯一可行的解决方案是让参与者等到协调器恢复后，检查事务日志

    3.2.7.3.4. 事务协调器恢复和事务日志可以完成未完成的事务并确保系统一致性

    3.2.7.3.4.1. 缺点是参与者必须在协调器恢复前阻塞

• 3.2.8. 二阶段提交的弱点就是不能容忍协调器故障

  • 3.2.8.1. 与所有单点故障问题一样，解决此问题的一种可能方法是在参与者之间复制协调器和事务状态

  • 3.2.8.2. 如果协调器失败，参与者可以被提升为协调器并完成事务

4. 分布式共识算法

4.1. 实现副本一致性，使所有客户端都能读取不同数据对象副本的一致数据值，需要副本之间就数据值达成共识或协议

• 4.1.1. 容错共识算法的基础是原子广播、全序广播或复制状态机等一类算法

  • 4.1.1.1. 它们保证一组值或状态以相同的顺序严格一次(exactly once)传递到多个节点

• 4.1.2. 二阶段提交也是一种共识算法

4.2. Leslie Lamport的Paxos（可能是最著名的共识算法）是无领导的

• 4.2.1. 无领导和其他复杂性使其实施起来非常棘手

• 4.2.2. 变体Multi-Paxos

  • 4.2.2.1. Multi-Paxos与Raft等基于领导者的方法有很多共同之处，它们是分布式关系数据库（如Google Cloud Spanner）实现的基础

4.3. 为了容错，共识算法必须在领导者和追随者都出现故障的情况下使应用程序仍能取得进展

• 4.3.1. 当一个领导者失败时，必须选出一个新的领导者，并且所有追随者必须就同一领导者达成一致

4.4. 新的领导者选举方法因算法而异，但它们的核心要求

• 4.4.1. 检测有故障的领导者

• 4.4.2. 一名或多名追随者提名自己为领导者

• 4.4.3. 投票选举新的领导者，可能要进行多轮投票

• 4.4.4. 一个恢复协议，用于确保在选举出新领导者后所有副本都达到一致的状态

4.5. 容错共识算法旨在仅与法定数或大多数参与者一起运行

• 4.5.1. 法定数用于确认原子广播和领导人选举

4.6. Raft

• 4.6.1. Raft是一种基于领导者的原子广播算法

  • 4.6.1.1. 单个领导者接收客户请求，建立订单，并向追随者执行原子广播以确保一致的更新顺序

• 4.6.2. Raft的设计是为了直接应对Paxos算法的复杂性

• 4.6.3. 被称为“一种可理解的共识算法”​，于2013年首次发布

• 4.6.4. 任期编号是一个逻辑时钟，每个有效的任期编号都与一个领导者相关联。

• 4.6.5. 只有大多数追随者需要在日志中提交条目

  • 4.6.5.1. 意味着在不同时间提交的日志条目可能在不同追随者上并不相同

• 4.6.6. 在多个需要共识的生产系统中实现，包括Neo4j和YugabyteDB数据库、etcd键值存储和分布式内存对象存储Hazelcast等

5. 强一致性实践

5.1. VoltDB

• 5.1.1. VoltDB是最初的NewSQL数据库之一

• 5.1.2. 建立在无共享架构之上，关系表使用分区键进行分片并跨节点复制

• 5.1.3. 每个VoltDB表分区都与一个CPU内核关联

• 5.1.4. 存储过程被视为事务单元

• 5.1.5. VoltDB是一个内存数据库，它必须采取额外的措施来提供数据安全性和持久性

  • 5.1.5.1. 每个SPI都将命令日志中的条目写入持久存储

  • 5.1.5.2. 每个分区还定义了一个快照间隔

• 5.1.6. 从版本6.4开始，VoltDB支持可线性化，因此在同一个数据库集群中具有最强的一致性级别

  • 5.1.6.1. VoltDB实现可线性化的原因是，它对所有分区的写入顺序达成了共识，而且事务是按顺序执行的，不会交错

5.2. Google Cloud Spanner

• 5.2.1. 2013年，Google公司发表了Spanner数据库论文

  • 5.2.1.1. Spanner被设计为一个强一致的全球分布式SQL数据库

    5.2.1.1.1. Google将这种强一致性称为外部一致性

  • 5.2.1.2. Cloud Spanner是一个基于云的数据库即服务(DBaaS)平台

• 5.2.2. Cloud Spanner使用Paxos共识算法使副本保持一致

  • 5.2.2.1. 与Raft一样，Paxos使一组副本就一系列更新的顺序达成一致

  • 5.2.2.2. 二阶段提交的实现表现为一个Paxos组

• 5.2.3. Cloud Spanner对开发者隐藏了表分区的细节

  • 5.2.3.1. 随着数据量的增长或收缩，它将跨机器动态地重新分区数据，将数据迁移到新位置来平衡负载

• 5.2.4. Cloud Spanner支持ACID事务

  • 5.2.4.1. 如果事务仅更新单个分片中的数据，则分片的Paxos领导者处理请求

  • 5.2.4.2. 领导者首先获取被修改行上的锁，并将变更传递给每个副本

• 5.2.5. TrueTime服务

  • 5.2.5.1. TrueTime为Google数据中心配备卫星连接的GPS和原子钟，并提供具有已知上限时钟偏差的紧密同步时钟，据报道约为7 ms

• 5.2.6. Cloud Spanner是GCP（谷歌云平台）不可或缺的组件

  • 5.2.6.1. GCP客户群涵盖金融服务、零售和游戏等行业，这些行业都被它强大的一致性保证以及高可用性和全球分布式部署能力所吸引

• 5.2.7. Cloud Spanner启发了基于Spanner架构的开源实现

  • 5.2.7.1. 这些实现不需要定制TrueTime式硬件，当然，代价是较低的一致性保证

  • 5.2.7.2. CockroachDB

  • 5.2.7.3. YugabyteDB