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

大多数复制的数据库至少提供了 最终一致性，这意味着如果你停止向数据库写入数据并等待一段不确定的时间，那么最终所有的读取请求都会返回相同的值，中间可能发生短暂的不一致性，但是最终数据都会收敛至相同的值。

1、线性一致性

线性一致性是一个 新鲜度保证（recency guarantee），只要一个客户端成功完成写操作，所有客户端从数据库中读取数据必须能够看到刚刚写入的值。（提供只有一个副本的假象，而不管实际系统拥有多少副本节点数 ）

1.1 怎么使得线性一致性

约束一：当读请求在写请求之前发生时，一定读到数据旧值；当读请求发生在写请求之后，一定读到新值；两者并发进行时读值不确定。

在上述约束下，还不足以完全描述线性一致性：如果与写入同时发生的读取可以返回旧值或新值，那么读者可能会在写入期间看到数值在旧值和新值之间来回翻转，不符合我们的预期。

增加约束二：如果读请求发生在写请求中间，及时写入操作尚未完成，请求也需返回新值。

增加第三种操作：比较设置，cas(X, Vold, Vnew)，来进行读之后的写入操作。

1.2 依赖线性一致性

  • 锁定和领导选举：一个使用单主复制的系统，需要确保领导者真的只有一个，而不是几个（脑裂）。一种选择领导者的方法是使用锁，而不管这个锁是如何实现的，它必须是线性一致的，即所有节点必须就哪个节点拥有锁达成一致，否则就没用了。

  • 约束和唯一性保证：文件存储服务中不能有两个相同的路径名被创建。

1.3 一致性代价

在单主复制的条件下，如果存在网络中断或者分区，则连接到从库的客户端无法联系到主库，因此无法执行任何写入操作，也不能执行任何线性一致的读取。

在非线性一致的情况下，客户端仍能从从库读取，但结果可能是陈旧的。如果应用需要线性一致的读写，那在这种情况下的网络中断将导致这些应用不可用。

  • CAP 定理（在发生网络分区，分布式系统要么保证可用，要么选择一致）

    如果应用需要线性一致性，且某些副本因为网络问题与其他副本断开连接，那么这些副本掉线时不能处理请求。请求必须等到网络问题解决，或直接返回错误（CP，强一致）。

    如果应用不需要线性一致性，那么某个副本即使与其他副本断开连接，也可以独立处理请求。在这种情况下，应用可以在网络问题解决前保持可用，但其行为不是线性一致的（AP，可用，数据可能不一致）。

  • 线性一致性和网络延迟

    更快地线性一致算法不存在，但更弱的一致性模型可以快得多，所以对延迟敏感的系统而言，这类权衡非常重要。

2、分布式事务与共识

共识 是分布式计算中最重要也是最基本的问题之一，节点能达成一致，在很多场景下都非常重要：

  • 领导选举：单主复制中对于哪个节点是主节点的共识很重要，如果出现了多主（脑裂），就会导致数据分歧。

  • 原子提交：所有节点对事务的结果达成一致，要么全部中止 / 回滚（如果出现任何错误），要么它们全部提交（如果没有出错）。

2.1 原子提交

原子性可以防止失败的事务搅乱数据库，避免数据库陷入半成品结果和半更新状态。在实际应用中也是分为两种场景：

一是单节点的原子性，通常由存储引擎去决定。当事务提交时，数据库将使事务的写入持久化（通常在预写式日志中），然后将提交记录追加到磁盘中的日志里。如果数据库在这个过程中间崩溃，当节点重启时，事务会从日志中恢复：如果提交记录在崩溃之前成功地写入磁盘，则认为事务被提交；否则来自该事务的任何写入都被回滚。

二是多节点的原子性，不能仅向每个节点发送请求并靠节点自动完成事务的提交，很容易因为某些节点上成功，而其他节点上失败的问题违反原子性。

2.2 两阶段提交

两阶段提交（two-phase commit） 是一种用于实现跨多个节点的原子事务提交的算法，即确保所有节点提交或所有节点中止。其使用一个通常不会出现在单节点事务中的新组件：协调者（coordinator，也称为事务管理器，即 transaction manager），来管理多个数据库节点上读写数据的操作。

当应用准备提交时，协调者开始阶段①：它发送一个准备（prepare）请求到每个节点，询问它们是否能够提交。然后协调者会跟踪参与者的响应：

  • 如果所有参与者都回答“是”，表示它们已经准备好提交，那么协调者在阶段②发出提交（commit）请求，然后提交真正发生。

  • 如果任意一个参与者回复了“否”，则协调者在阶段②中向所有节点发送中止（abort）请求。

这样一来作为协调者的能力就很重要，一旦发生问题，参与者无法知道是提交还是放弃，只能等待协调者恢复正常。

2.3 三阶段提交

三阶段提交讲究一个原子提交协议变为非阻塞（nonblocking） ，需要一个完美的故障检测器（perfect failure detector）—— 即一个可靠的机制来判断一个节点是否已经崩溃。

2.4 容错共识

共识问题通常形式化如下：一个或多个节点可以提议（propose）某些值，而共识算法决定（decides）采用其中的某个值，算法必须满足下面的性质：

  • 一致同意（Uniform agreement）：没有两个节点的决定不同。

  • 完整性（Integrity）：没有节点决定两次。

  • 有效性（Validity）：如果一个节点决定了值 v ，则 v 由某个节点所提议。

  • 终止（Termination）：由所有未崩溃的节点来最终决定值。

相关共识算法有视图戳复制（VSR, Viewstamped Replication），Paxos，Raft 以及 Zab。

2.5 成员与协调服务

ZooKeeper 模仿了 Google 的 Chubby 锁服务，不仅实现了全序广播（因此也实现了共识），而且还构建了一组有趣的其他特性：

  • 线性一致性的原子操作：如果多个节点同时尝试执行相同的操作，只有一个节点会成功。分布式锁通常以 租约（lease） 的形式实现，租约有一个到期时间，以便在客户端失效的情况下最终能被释放。

  • 操作的全序排序：当某个资源受到锁或租约的保护时，你需要一个防护令牌来防止客户端在进程暂停的情况下彼此冲突。ZooKeeper 通过全序化所有操作来提供这个功能，它为每个操作提供一个单调递增的事务 ID（zxid）和版本号（cversion）。

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

  • 变更通知：客户端不仅可以读取其他客户端创建的锁和值，还可以监听它们的变更。通过订阅通知，客户端不用再通过频繁轮询的方式来找出变更。

3、顺序保证

顺序存在的意义某个重要原因就是能够保证上下文的因果关系，如果一个系统服从因果关系所规定的顺序，我们说它是 因果一致。

3.1 序列号顺序

使用逻辑时钟（生成标识操作的数字序列的算法）生成的时间戳来排序事件，这样避免日历时钟、物理时钟带来的问题。

3.2 全序广播

在单核 CPU 下面实现全序很简单，可以认为就是 CPU 的执行顺序，但是在分布式场景下面，该问题被称为 全序广播，其通常被描述为在节点间交换消息的协议，需要满足两个安全属性：

  • 可靠交付：如果消息被传递到一个节点，则该消息能够传递到所有节点；

  • 全序交付：消息以相同的顺序被发送到每个节点。

全序广播正是数据库复制所需的：如果每个消息都代表一次数据库的写入，且每个副本都按相同的顺序处理相同的写入，那么副本间将相互保持一致（除了临时的复制延迟），这个原理被称为 状态机复制。