在大数据存储系统中，为了增加系统高可用性，往往会将同一数据存储多份副本，工业界的常规做法是三备份。将数据复制成多份除了增加存储系统高可用性外还可以增加读操作的并发性，但是这样会引入一致性问题。本文会详细介绍。

基本原则与设计理念

首先介绍一下CAP、BASE、ACID基础理论模型。

CAP

  1. 强一致性：即在分布式系统中的同一数据多副本情形下，对于数据的更新操作体现出的效果与只有单份数据是一样的
  2. 可用性：客户端在任何时刻对大规模数据系统的读/写操作都应该保证在限定延时内完成
  3. 分区容忍性：在大规模分布式数据系统中，网络分布现象，即分区间的机器无法进行网络通信的情况是必然会发生的，所以系统应该能够在这种情况下仍然继续工作

在设计具体分布式架构技术方案时，必须再一致性和可用性方面做出取舍，要么选择强一致性减弱服务可用性，要么选择高可用性容忍弱一致性。依然认为，传统的关系数据库在三要素中选择CA两个因素，即强一致性，高可用性，但是可扩展性与容错性差。而NoSQL系统往往更关注AP因素，即高扩展性和高可用性，但是往往以弱一致性作为代价。

ACID

  1. 原子性(Atomicity)
  2. 一致性(Consistency)
  3. 事务独立(Isolation)
  4. 持久性(Durability)

BASE

  1. 基本可用(Basically Available)
  2. 软状态或者柔性状态(Soft State)
  3. 最终一致性(Eventual Consistency)

一致性模型分类

  1. 强一致性：
  2. 最终一致性：
  3. 因果一致性：
  4. 读你所写一致性：
  5. 会话一致性：
  6. 单调读一致性：
  7. 单调写一致性：

一致性协议

两阶段提交协议(Two-Phrase Commit, 2PC)

阶段一： 表决阶段

  1. [协调者视角] 协调者向所有参与这发送一个VOTE-REQUEST消息
  2. [参与者视角] 当参与者接收到VOTE-REQUEST消息，向协调者发送VOTE-COMMIT消息作为回应，告知协调者自己已经做好了提交准备，否则就返回一个VOTE-ABORT消息，告知协调者目前尚无提交事务的可能。

阶段二：提交阶段

  1. [协调者视角] 协调者收集来自各个参与者的表决信息。如果所有参与者一致认为可以提交事务，那么协调者决定事务最终可提交，在此情形下协调者向所有参与者发送一个GLOBAL_COMMIT消息，通知参与者进行本地提交；如果所有参与者中有任意一个返回的消息是VOTE-ABORT，协调者决定取消事务，则向所有参与者多播一条GLOBAL_ABORT消息通知其取消事务。
  2. [参与者视角] 每个提交了表决信息的参与者等候协调者行为，如果参与者接收到一个GLOBAL_COMMIT消息，那么参与者提交本地事务，否则如果接收到GLOBAL_ABORT消息，则参与者于本地取消事务。

协调者的有限状态机

参与者的有限状态机

向量时钟

向量时钟是在分布式环境下生成事件之间偏序关系的算法，偏序关系代表事件发生先后顺序导致的事件因果依赖关系语义，通过将时间戳和事件绑定可以用来判定事件之间的因果相关性。

假设分布式系统里有n个独立进程，每个进程$p_i(1 \le i \le n)$记载初始值都是0的整数向量时钟$VC_i[1\dots n]$，其中第j位数值代表进程$p_i$看到的进程$p_j$的逻辑时钟(Logic Clock)。向量时钟系统通过如下3个规则更新每个进程对应的向量时钟值。

  • 规则1：每当进程$p_i$差生了以下3种事情之一(发送消息、接收消息或者进程内部事件)，其将自己的向量时钟对应位置数值计数加1，即$VC_i[i] = VC_i[i] + 1$
  • 规则2：当进程$p_i$发送消息m时，其将自己的向量时钟和消息m同时发送出去，我们记其向量时钟为m.VC
  • 规则3：当进程$p_i$接收到进程$p_j$发送来的消息m时，按照如下方式更新自己的向量时钟的每一位数值：

RWN协议

先说一下相关定义：

  • N: 在分布式存储系统中，有多少份备份数据。
  • W: 代表一次成功的更新操作要求至少有W份数据写入成功。
  • R: 代表一次成功的读数据操作要求至少有R份数据成功读取。

如果能够满足以下公式，则可称为满足“数据一致性协议”：

这是因为，如果满足上述公式的要求，说明成功写入的备份集合和成功读取的备份集合一定会存在交集。

需要说明的是，在具体实现系统时，仅仅依靠RWN协议还不能完成一致性保证，因为在上述过程中，当读取到多个备份数据时，需要判断哪些数据是最新的，如何判断数据的新旧？这需要向量时钟来配合。

Paxos

前言

学习Paxos算法有两部分：a) 算法的原理/证明；b) 算法的理解/运作。

理解这个算法的运作过程其实基本就可以用于工程实践。而且理解这个过程相对来说也容易得多。

记住以下原则，可以方便的理解算法

  1. Prepare阶段喜新厌旧
  2. Commit阶段后者认同前者
  3. 最终少数服从多数

算法内容

Paxos在原作者的《Paxos Made Simple》中内容是比较精简的：

1
2
3
4
5
6
7
8
9
10
11
Phase 1

(a) A proposer selects a proposal number n and sends a prepare request with number n to a majority of acceptors.

(b) If an acceptor receives a prepare request with number n greater than that of any prepare request to which it has already responded, then it responds to the request with a promise not to accept any more proposals numbered less than n and with the highest-numbered pro-posal (if any) that it has accepted.

Phase 2

(a) If the proposer receives a response to its prepare requests (numbered n) from a majority of acceptors, then it sends an accept request to each of those acceptors for a proposal numbered n with a value v , where v is the value of the highest-numbered proposal among the responses, or is any value if the responses reported no proposals.

(b) If an acceptor receives an accept request for a proposal numbered n, it accepts the proposal unless it has already responded to a prepare request having a number greater than n.

参考下图

实例及详解

Paxos中有三类角色Proposer、Acceptor及Learner，主要交互过程在Proposer和Acceptor之间。

Proposer与Acceptor之间的交互主要有4类消息通信，如下图：

这4类消息对应于paxos算法的两个阶段4个过程：

  • phase 1
    • a) proposer向网络内超过半数的acceptor发送prepare消息
    • b) acceptor正常情况下回复promise消息
  • phase 2
    • a) 在有足够多acceptor回复promise消息时，proposer发送accept消息
    • b) 正常情况下acceptor回复accepted消息

因为在整个过程中可能有其他proposer针对同一件事情发出以上请求，所以在每个过程中都会有些特殊情况处理，这也是为了达成一致性所做的事情。如果在整个过程中没有其他proposer来竞争，那么这个操作的结果就是确定无异议的。但是如果有其他proposer的话，情况就不一样了。

以paxos中文wiki上的例子为例。简单来说该例子以若干个议员提议税收，确定最终通过的法案税收比例。

以下图中基本只画出proposer与一个acceptor的交互。时间标志T2总是在T1后面。propose number简称N。

情况之一如下图：

A3在T1发出accepted给A1，然后在T2收到A5的prepare，在T3的时候A1才通知A5最终结果(税率10%)。这里会有两种情况：

  • A5发来的N5小于A1发出去的N1，那么A3直接拒绝(reject)A5
  • A5发来的N5大于A1发出去的N1，那么A3回复promise，但带上A1的(N1, 10%)

这里可以与paxos流程图对应起来，更好理解。acceptor会记录(MaxN, AcceptN, AcceptV)。

A5在收到promise后，后续的流程可以顺利进行。但是发出accept时，因为收到了(AcceptN, AcceptV)，所以会取最大的AcceptN对应的AcceptV，例子中也就是A1的10%作为AcceptV。如果在收到promise时没有发现有其他已记录的AcceptV，则其值可以由自己决定。

针对以上A1和A5冲突的情况，最终A1和A5都会广播接受的值为10%。

其实4个过程中对于acceptor而言，在回复promise和accepted时由于都可能因为其他proposer的介入而导致特殊处理。所以基本上看在这两个时间点收到其他proposer的请求时就可以了解整个算法了。例如在回复promise时则可能因为proposer发来的N不够大而reject：

如果在发accepted消息时，对其他更大N的proposer发出过promise，那么也会reject该proposer发出的accept，如图：

这个对应于Phase 2 b)：

1
it accepts the proposal unless it has already responded to a prepare request having a number greater than n.

总结

Leslie Lamport没有用数学描述Paxos，但是他用英文阐述得很清晰。将Paxos的两个Phase的内容理解清楚，整个算法过程还是不复杂的。

至于Paxos中一直提到的一个全局唯一且递增的proposer number，其如何实现，引用如下：

1
如何产生唯一的编号呢？在《Paxos made simple》中提到的是让所有的Proposer都从不相交的数据集合中进行选择，例如系统有5个Proposer，则可为每一个Proposer分配一个标识j(0~4)，则每一个proposer每次提出决议的编号可以为5*i + j(i可以用来表示提出议案的次数)

Raft

前言

Raft 将一致性算法分为了几个部分，例如领导选取（leader selection），日志复制（log replication）和安全性（safety），同时它使用了更强的一致性来减少了必须需要考虑的状态。

几个特性

  • 强领导者（Strong Leader）：Raft 使用一种比其他算法更强的领导形式。例如，日志条目只从领导者发送向其他服务器。这样就简化了对日志复制的管理，使得 Raft 更易于理解。
  • 领导选取（Leader Selection）：Raft 使用随机定时器来选取领导者。这种方式仅仅是在所有算法都需要实现的心跳机制上增加了一点变化，它使得在解决冲突时更简单和快速。
  • 成员变化（Membership Change）：Raft 为了调整集群中成员关系使用了新的联合一致性（joint consensus）的方法，这种方法中大多数不同配置的机器在转换关系的时候会交迭（overlap）。这使得在配置改变的时候，集群能够继续操作。

复制状态机

分布式一致性的解决方案就是复制状态机, 在一组服务器的状态机产生同样的状态的副本因此即使有一些服务器崩溃了这组服务器也还能继续执行。但是集群中有一个Leader节点，Leader选举是使用一个单独的复制状态机,并存储配置信息，防止leader崩溃。

从图上我们可以发现共识模块是处理分布式一致性的，Log模块记录操作的记录（这个操作很重要），最后是每台机器的状态机。复制状态机是通过复制日志实现的，每台服务器都保存一份日志，日志中包含一系列的命令，状态机会按照顺序执行这些命令。

应用于实际系统的一致性算法一般有以下特性：

  • 确保安全性（从来不会返回一个错误的结果），即使在所有的非拜占庭（Non-Byzantine）情况下，包括网络延迟、分区、丢包、冗余和乱序的情况下。
  • 高可用性，只要集群中的大部分机器都能运行，可以互相通信并且可以和客户端通信，这个集群就可用。
  • 不依赖时序保证一致性，时钟错误和极端情况下的消息延迟在最坏的情况下才会引起可用性问题。
  • 通常情况下，一条命令能够尽可能快的在大多数节点对一轮远程调用作出相应时完成，一少部分慢的机器不会影响系统的整体性能。

易于理解的设计

设计 Raft 的目标有如下几个（我想任何算法都应该是这样的）：

  • 能提供一个完整的、实际的基础来进行系统构建，减少开发者的工作
  • 在任何情况下都能保证安全可用。
  • 对于常规的操作，必须是高效的。
  • 易于理解（这样才能便于应用）
  • 它必须能让开发者有一个直观的认识，这样才能使系统构建者们去对它进行扩展。（其实我觉得这点有点啰嗦）

Raft使用了两种方式来简化算法的复杂度。

一是问题分解： 尽可能将问题分解成为若干个可解决的、可被理解的小问题。例如，在 Raft 中，我们把问题分解成为了领导选取（leader election）、日志复制（log replication）、安全（safety）和成员变化（membership changes）。

第二个方法是通过减少需要考虑的状态的数量将状态空间简化，这能够使得整个系统更加一致并且尽可能消除不确定性。特别地，日志之间不允许出现空洞，并且 Raft 限制了日志不一致的可能性。尽管在大多数情况下，我们都都在试图消除不确定性，但是有时候有些情况下，不确定性使得算法更易理解。尤其是，随机化方法使得不确定性增加，但是它减少了状态空间。我们使用随机化来简化了 Raft 中的领导选取算法。

Raft 一致性算法

状态

在所有服务器上持久存在的：（在响应远程过程调用 RPC 之前稳定存储的）

名称 描述
currentTerm 服务器最后知道的任期号（从0开始递增）
votedFor 在当前任期内收到选票的候选人 id（如果没有就为 null）
log[] 日志条目；每个条目包含状态机的要执行命令和从领导人处收到时的任期号

在所有服务器上不稳定存在的：

名称 描述
commitIndex 已知的被提交的最大日志条目的索引值（从0开始递增）
lastApplied 被状态机执行的最大日志条目的索引值（从0开始递增）

在领导人服务器上不稳定存在的：（在选举之后初始化的）

名称 描述
nextIndex[] 对于每一个服务器，记录需要发给它的下一个日志条目的索引（初始化为领导人上一条日志的索引值+1）
matchIndex[] 对于每一个服务器，记录已经复制到该服务器的日志的最高索引值（从0开始递增）

这个是每台机器内部的状态量，根据这些信息我们可以查看相应的节点状态，每个节点也可以通过这些状态来检查网络中各节点的状态，最终需要leader节点进行同步。

附加日志远程过程调用 （AppendEntries RPC）

由领导人来调用复制日志（5.3节）；也会用作heartbeat

参数 描述
term 领导人的任期号
leaderId 领导人的 id，为了其他服务器能重定向到客户端
prevLogIndex 最新日志之前的日志的索引值
prevLogTerm 最新日志之前的日志的领导人任期号
entries[] 将要存储的日志条目（表示 heartbeat 时为空，有时会为了效率发送超过一条）
leaderCommit 领导人提交的日志条目索引值
返回值 描述
term 当前的任期号，用于领导人更新自己的任期号
success 如果其它服务器包含能够匹配上 prevLogIndex 和 prevLogTerm 的日志时为真

接受者需要实现：

  1. 如果 term < currentTerm返回 false（5.1节）(这个应该是发现了最新的leader)
  2. 如果在prevLogIndex处的日志的任期号与prevLogTerm不匹配时，返回 false（5.3节）（发现问题，3解决）
  3. 如果一条已经存在的日志与新的冲突（index 相同但是任期号 term 不同），则删除已经存在的日志和它之后所有的日志（5.3节）（解决2中存在的问题，回滚）
  4. 添加任何在已有的日志中不存在的条目（恢复数据）
  5. 如果leaderCommit > commitIndex，将commitIndex设置为leaderCommit和最新日志条目索引号中较小的一个（获取新日志后更新）

这个心跳检测和同步日志消息其实就是检测当前节点与Leader节点异同，如果发现数据异常，根据Leader节点的数据进行回滚，拉取最新的日志，根据日志恢复状态机。如果发现漏了很多日志就同步日志恢复状态机。

投票请求RPC（RequestVote RPC）

由候选人发起收集选票（5.2节）

参数 描述
term 候选人的任期号
candidateId 请求投票的候选人 id
lastLogIndex 候选人最新日志条目的索引值
lastLogTerm 候选人最新日志条目对应的任期号
返回值 描述
term 目前的任期号，用于候选人更新自己
voteGranted 如果候选人收到选票为 true

接受者需要实现：

  1. 如果term < currentTerm返回 false（5.1节）(可能是旧的Leader，但现在有新的了，忽略)
  2. 如果votedFor为空或者与candidateId相同，并且候选人的日志和自己的日志一样新，则给该候选人投票（5.2节 和 5.4节）

服务器需要遵守的规则：

所有服务器：

  1. 如果commitIndex > lastApplied，lastApplied自增，将log[lastApplied]应用到状态机（5.3节）
  2. 如果 RPC 的请求或者响应中包含一个 term T 大于 currentTerm，则currentTerm赋值为 T，并切换状态为追随者（Follower）（5.1节）

追随者（followers）: 5.2节

  1. 响应来自候选人和领导人的 RPC
  2. 如果在超过选取领导人时间之前没有收到来自当前领导人的AppendEntries RPC或者没有收到候选人的投票请求，则自己转换状态为候选人

候选人：5.2节

  1. 转变为选举人之后开始选举：
    • currentTerm自增
    • 给自己投票
    • 重置选举计时器
    • 向其他服务器发送RequestVote RPC
  2. 如果收到了来自大多数服务器的投票：成为领导人
  3. 如果收到了来自新领导人的AppendEntries RPC（heartbeat）：转换状态为追随者
  4. 如果选举超时：开始新一轮的选举

领导人：

  1. 一旦成为领导人：向其他所有服务器发送空的AppendEntries RPC（heartbeat）;在空闲时间重复发送以防止选举超时（5.2节）
  2. 如果收到来自客户端的请求：向本地日志增加条目，在该条目应用到状态机后响应客户端（5.3节）
  3. 对于一个追随者来说，如果上一次收到的日志索引大于将要收到的日志索引（nextIndex）：通过AppendEntries RPC将 nextIndex 之后的所有日志条目发送出去
  4. 如果发送成功：将该追随者的 nextIndex和matchIndex更新
  5. 如果由于日志不一致导致AppendEntries RPC失败：nextIndex递减并且重新发送（5.3节）
  6. 如果存在一个满足N > commitIndex和matchIndex[i] >= N并且log[N].term == currentTerm的 N，则将commitIndex赋值为 N
Raft 一致性算法的特性

Raft 算法保证这些特性任何时刻都成立

性质 描述
选举安全原则（Election Safety） 一个任期（term）内最多允许有一个领导人被选上（5.2节）
领导人只增加原则（Leader Append-Only） 领导人永远不会覆盖或者删除自己的日志，它只会增加条目
日志匹配原则（Log Matching） 如果两个日志在相同的索引位置上的日志条目的任期号相同，那么我们就认为这个日志从头到这个索引位置之间的条目完全相同（5.3 节）
领导人完全原则（Leader Completeness) 如果一个日志条目在一个给定任期内被提交，那么这个条目一定会出现在所有任期号更大的领导人中
状态机安全原则（State Machine Safety） 如果一个服务器已经将给定索引位置的日志条目应用到状态机中，则所有其他服务器不会在该索引位置应用不同的条目（5.4.3节）

Raft 通过首先选出一个领导人来实现一致性，然后给予领导人完全管理复制日志（replicated log）的责任。领导人接收来自客户端的日志条目，并把它们复制到其他的服务器上，领带人还要告诉服务器们什么时候将日志条目应用到它们的状态机是安全的。通过选出领导人能够简化复制日志的管理工作。例如，领导人能够决定将新的日志条目放到哪，而并不需要和其他的服务器商议，数据流被简化成从领导人流向其他服务器。如果领导人宕机或者和其他服务器失去连接，就可以选取下一个领导人。

通过选出领导人，Raft 将一致性问题分解成为三个相对独立的子问题：

  • 领导人选取（Leader election）： 在一个领导人宕机之后必须要选取一个新的领导人（5.2节）
  • 日志复制（Log replication）： 领导人必须从客户端接收日志然后复制到集群中的其他服务器，并且强制要求其他服务器的日志保持和自己相同
  • 安全性（Safety）： Raft 的关键的安全特性是 表-3 中提到的状态机安全原则（State Machine Safety）:如果一个服务器已经将给定索引位置的日志条目应用到状态机中，则所有其他服务器不会在该索引位置应用不同的条目。5.4节阐述了 Raft 是如何保证这条原则的，解决方案涉及到一个对于选举机制另外的限制，这一部分会在 5.2节 中说明。

在说明了一致性算法之后，本章会讨论有关可用性（availability）的问题和系统中时序（timing）的问题。

总结

raft的Leader选举机制和策略总觉得和redis的集群模式很像，后来查看资料，果然redis内部使用的就是raft协议。也就大概明白raft协议的意思了。这里就不再过多地去说明了。

但是论文的后面还有大量的实现说明，我在讨论了，可以查看论文原文，里面提到了很多细节问题，都是我们不得不考虑的事情。