分布式一致性协议

发表于 | 更新于

背景

在传统的软件系统中，如果想要保证一次业务请求中的多次修改操作结果具有一致性，可以使用事务（Transaction）来控制操作整体的提交（Commit）或回滚（Rollback）。事务为业务操作提供了强一致性保证，其特性可总结为ACID，即：

  • 原子性(Atomicity)：一个事务（transaction）中的所有操作，或者全部完成，或者全部不完成，不会结束在中间某个环节；
  • 一致性(Consistency)：在事务开始之前和事务结束以后，数据库的完整性没有被破坏；
  • 隔离型(Isolation)：数据库允许多个并发事务同时对其数据进行读写和修改的能力，隔离性可以防止多个事务并发执行时由于交叉执行而导致数据的不一致；
  • 持久性(Durability)：事务处理结束后，对数据的修改就是永久的，即便系统故障也不会丢失。

互联网时代，分布式系统的应用越来越普遍，在动辄几百上千的研发团队中，软件系统如果仍然采用单一应用的开发模式，团队的协作成本是非常高的，因此服务化和微服务成为了目前行业的主流。然而，分布式系统带来低耦合，高可扩展性的同时，单个业务可能包含多个应用调用，无法使用传统的事务来为所有应用提供一致性保证。此时，有人提出并证明了CAP定理，即对于一个分布式计算系统来说，不可能同时满足以下三点：

  • 一致性(Consistency)：即更新操作成功并返回客户端完成后，所有节点在同一时间的数据完全一致；
  • 可用性(Availability)：即服务一直可用，而且是正常响应时间；
  • 分区容错性(Partition tolerance)：分布式系统在遇到某节点或网络分区故障的时候，仍然能够对外提供满足一致性和可用性的服务。

由于无法同时满足CAP三个特性，有人又提出了BASE理论，即：

  • 基本可用(Basically Available)：基本可用是指分布式系统在出现故障的时候，允许损失部分可用性，即保证核心可用；
  • 软状态(Soft State)：软状态是指允许系统存在中间状态，而该中间状态不会影响系统整体可用性；
  • 最终一致性(Eventual Consistency)：最终一致性是指系统中的所有数据副本经过一定时间后，最终能够达到一致的状态。

协调者

在分布式系统中，每个应用能够感知各自的事务执行结果，但无法感知其他应用的事务执行结果，于是我们设立了一个协调者的角色来统一指挥分布式系统中的各个应用执行事务，应用在协调者的指挥下执行事务，并把执行结果汇报给协调者，协调者再综合所有应用的执行结果来通知应用最终提交事务还是中断回滚事务。

二阶段提交协议（2PC）

二阶段提交协议将事务执行过程分为两个阶段：准备阶段和执行阶段。

准备阶段

  1. 协调者向各个应用提交事务请求，并等待应用响应；
  2. 应用执行事务；
  3. 如果应用执行事务成功则向协调者响应可以提交事务，否则向协调者响应不能提交事务。

执行阶段

  1. 协调者收集所有应用的响应，后续操作分为两种情况：
    1. 所有应用均响应了可以提交事务，协调者向各个应用发起提交事务请求，并等待应用响应；
    2. 有应用响应了不能提交事务，协调者向各个应用发起中断事务请求，并等待应用响应；
  2. 应用执行提交/中断事务；
  3. 应用反馈提交/中断事务执行结果；
  4. 事务执行完成。

二阶段提交协议的缺点

二阶段提交协议的原理十分简单，实现也方便，但存在几个比较严重的问题。

  1. 同步阻塞问题。执行过程中，所有应用都是事务阻塞型的。当应用占有公共资源时，其他应用访问公共资源都处于阻塞状态。
  2. 协调者单点故障。协调者在整个事务执行过程中起到了指挥的作用，一旦协调者发生故障，正在进行中的事务将持续占用事务资源，无法完成事务操作。即使重新选举新的协调者，也无法继续进行原先未完成的事务。
  3. 数据不一致。在执行阶段，如果由于网络故障，部分应用没有收到提交事务的请求，将导致只有部分应用执行了事务的提交，这样就出现了数据不一致的问题。
  4. 过于保守。如果参与者在与协调者通信期间出现故障，协调者只能靠超时机制来判断是否需要中断事务，这个策略比较保守，需要更为完善的容错机制，任意一个节点的失败都会导致整个事务的失败。

三阶段提交协议（3PC）

由于二阶段提交协议存在着诸如同步阻塞、单点问题、数据不一致等缺陷，所以，人们在二阶段提交协议的基础上提出了三阶段提交协议。
三阶段提交协将事务执行过程分为三个阶段：准备阶段、预提交阶段和提交阶段。

准备阶段

  1. 协调者询问各个应用是否可以开始事务；
  2. 应用根据自身情况响应协调者。

预提交阶段

  1. 协调者收集所有应用的响应，后续操作分为两种情况：
    1. 所有应用均响应了可以开始事务，协调者向各个应用发起事务预提交请求，并等待应用响应；
    2. 有应用响应了不能开始事务，或有应用响应超时，协调者向各个应用发起中断事务请求；
  2. 应用执行事务预提交或中断事务，若中断事务，则本次事务结束；
  3. 应用反馈事务执行结果。

提交阶段

  1. 协调者收集所有应用的响应，后续操作分为两种情况：
    1. 所有应用均响应了可以提交事务，协调者向各个应用发起提交事务请求，并等待应用响应；
    2. 有应用响应了不能提交事务，或有应用响应超时，协调者向各个应用发起中断事务请求，并等待应用响应；
  2. 应用执行提交/中断事务；
  3. 应用反馈提交/中断事务执行结果；
  4. 事务执行完成。

在提交阶段，如果应用由于各种原因没有收到协调者的提交事务或中断事务请求，在等待超时后，将继续进行事务的提交。

三阶段提交协议的缺点

三阶段提交协议相比二阶段提交协议，降低了阻塞的范围，出现协调者单点故障后能够继续完成事务，但如果在预提交阶段出现网络分区问题，仍会出现数据不一致的问题。

Paxos协议

基本思想

Paxos协议为了在可能发生网络异常或服务器故障的分布式系统中能够快速并且正确地对某一数据的值达成一致，在Leader选举或数据修改时，采取了一种类似国会投票的少数服从多数的机制。它能够保证在2F+1个节点的分布式系统中，允许F个节点同时出现故障。

分布式系统中的节点被分为三种角色：

  • Proposer（提案人）：提出一个值，用于投票决议；
  • Acceptor（接受者）：对每个提案进行投票；
  • Learner（观察员）：可获知投票结果，无投票权。

准备阶段

  1. Proposer提出一个提案，并为提案附上一个全局唯一且递增的编号；
  2. Acceptor收到提案，将提案的编号与他已接受的最大提案编号进行比较；
    1. 若新提案的编号小于已接受的最大编号，Acceptor将拒绝新提案，回复提案已被拒绝；
    2. 若新提案的编号大于已接受的最大编号，Acceptor将接受新提案，回复提案已被接受；
      1. 若之前从未接受过同一个事务的其他提案，则仅回复提案已被接受；
      2. 若之前已接受过同一个事务的其他提案，则将已接受的编号和提案内容一并回复给Proposer；

接受阶段

  1. 收到半数以上Acceptor接受提案回复的Proposer可以发起接受请求，请求中同样需要附上提案编号和提案内容；
    1. 若收到的回复都没有附带其他提案编号和内容，则以自己提出的提案内容发起接受请求；
    2. 若收到的回复附带了其他提案编号和内容，则将自己的提案内容修改为回复的提案内容；
  2. Acceptor收到接受请求，将请求中提案的编号与他已接受的最大提案编号进行比较；
    1. 若提案的编号小于已接受的最大编号，Acceptor将拒绝该接受请求，回复接受请求已被拒绝；
    2. 若提案的编号大于已接受的最大编号，Acceptor将接受该接受请求，并提交提案修改的内容，回复接受请求已被接受；
  3. Proposer收到半数以上Acceptor接受的回复，将结果通知所有Learner。

Raft协议

概述

不同于Paxos协议直接从分布式一致性问题出发推导出来，Raft协议则是从多副本状态机的角度提出，用于管理多副本状态机的日志复制。Raft实现了和Paxos相同的功能，它将一致性分解为多个子问题：Leader选举（Leader election）、日志同步（Log replication）、安全性（Safety）、日志压缩（Log compaction）、成员变更（Membership change）等。同时，Raft协议使用了更强的假设来减少了需要考虑的状态，使之变的易于理解和实现。

Raft将系统中的角色分为三种：

  • Leader：接受客户端请求，并向Follower同步请求日志，当日志同步到大多数节点上后告诉Follower提交日志；
  • Follower：接受并持久化Leader同步的日志，在Leader告之日志可以提交之后，提交日志；
  • Candidate：Leader选举过程中的临时角色。

Raft要求系统在任意时刻最多只有一个Leader，正常工作期间只有Leader和Followers。

Raft将时间分为一个个的任期（term），每一个任期的开始都是Leader选举。在成功选举Leader之后，Leader会在整个任期内管理整个集群。

Leader选举

Raft 使用心跳触发Leader选举。当服务器启动时，初始化为Follower。Leader向所有Followers周期性发送心跳。如果Follower在选举超时时间内没有收到Leader的心跳，就会认为Leader挂了，等待一段随机的时间后发起一次Leader选举。

  1. Follower将其任期加一然后在一定超时时间（150ms-300ms随机）后转为Candidate；
  2. Candidate首先给自己投票，并向其他服务器发送投票邀请RequestVote RPCs；
  3. 如果其他服务器还没有投票，那么就给该Candidate投票；
  4. 选举结果分为种情况；
    1. 一个Candidate获得多数投票，则该Candidate成为新的Leader；
    2. 多个Candidate获得的票数相同，则等待选举时间超时后开始新一轮的选举。

日志同步

一旦 Leader 被选了出来，就开始响应客户端的请求。 每一条客户端的请求都包含一条需要被复制状态机执行的命令。

  1. Leader 接收客户端请求；
  2. Leader 将命令作为一个日志条目加到它的日志中去；
  3. Leader 并发的向其他节点发出 AppendEntries RPCs 请求；
  4. 当条目被安全的复制之后，Leader 将条目添加到状态机中， 并向客户端返回结果。

如果 follower 崩溃或者运行的很慢、或者发生了丢包， leader 不停的向 follower 发送AppendEntries RPC， 直到所有的 follower 存储了所有的 AppendEntries。