Raft和它的三个子问题

这篇文章来源于一个经常有人困惑的问题：Quorum与Paxos，Raft等一致性协议有什么区别，这个问题的答案本身很简单： 一致性协议大多使用了Quorum机制，但仅仅有Quorum(R+W>N)机制是保证不了一致性的 。本文计划延伸这个问题，以Raft为例回答一个完善的一致性协议拥有包括Quorum在内的那些机制，试着说明这些机制的完备以及其中每一项的不可或缺。

要回答这个问题首先需要说明Raft是做什么的，Paxos、Raft被称为一致性协议，顾名思义它们要解决的是多节点的一致性问题，需要注意的是这里所说的一致性并不是要求所有节点在任何时刻状态完全一致。而是要保证：

即使发生网络分区或机器节点异常，整个集群依然能够像单机一样提供一致的服务，即在每次操作时都可以看到其之前的所有成功操作按顺序完成。

这里有两点需要说明：

将每一个对Raft集群的操作称为一个提案，希望Raft集群对外屏蔽内部的网络或节点异常，依次对每一个提案作出相应，提交成功的提案可以在后续操作中持续可见。这里的提案需要是幂等的，即重复执行不会导致集群状态不同。

接下来我们就看Raft是如何实现这种一致性保证的。Raft将一致性问题拆分为三个子问题，各个击破，从而使得其实现简单易懂。本文将首先简单介绍其三个子问题的内容以及达成方式；之后证明三个子问题是实现一致性的充分条件；最后尝试说明这三个子问题的保证缺一不可。

组成一个Raft集群至少需要三台机器，而Raft限制每一时刻最多只能有一个节点可以发起提案，这个限制极大的简化了一致性的实现，这个可以发起提案的节点称为Leader。因此所要解决的第一个 问题 便是：

如上图所示：

从上面对Raft状态转换的讨论中可以看到，任何非Leader的节点都有可能在未来成为Leader，为了能保证后续Leader节点变化后依然能够使得整个集群对外保持一致，需要通过Log Replication机制来解决如下两个问题：

上图描述了一个Raft提案的执行过程：

Follower在接受AppendEntry时会检查其前一条的Log是否与Leader相同，利用数学归纳法可以很简单的证明Leader和Follower上的Log一致。另外，由于只需要过半数的节点成功即可返回，也就在保证一致性的前提下竟可能的提高了集群的可用性。

这里需要注意， Leader Commit过的提案会向用户返回成功，因此Raft集群需要保证这些提案永远存在 。

通过上述的两个子问题已经解决了大部分的难题，除了下面两个细节：

通过上述的三个子问题的解决，我们得到了一个完善的一致性算法，论文中给出了详细严谨的证明，其首先假设Commit过的提案会在后续丢失，之后推导出矛盾进而反证成功，这里不再赘述。该证明的关键点在于：Leader Election中要求新Leader获得超过半数的节点投票，Log Replication中每个Commit都有超过半数的节点同意，因此这两个大多数中至少存在一个公共节点，这个节点既同意了某个提案的Commit又投票给了新的Leader。

上面讨论了三个子问题对一致性的充分性，接下来要讨论的是在Raft的框架下，任何一个子问题的缺失都会导致严重的不一致后果：

通过上面的讨论，可以看出一个完整的一致性协议做了包括Quorum在内的诸多努力。Raft划分了三个子问题来使得整个一致性算法的实现简单易懂，我们也基于Raft实现了自己的一致性库 Floyd 来满足诸如 Zeppelin 元信息集群及 Pika 跨机房功能中对一致性的需求。

In Search of an Understandable Consensus Algorithm

Qihoo360 Floyd

一致性算法（Paxos、Raft、ZAB)

什么是一致性

1、弱一致性

a、最终一致性

i、DNS（Domain Name System）

j、Gossip（Cassandra的通信协议）

以DNS为例：

2、强一致性

a、同步

b、Paxos

c、(multi-paxos)

d、ZAB(multi-paxos)

DNS 就是一种最终一致性，比如 上图中 增加一条记录： www.hyb.small.com , 我们从其他DNS服务器一时会读取不到，但是过一会就会读取得到了。

数据不能存在单点上。

分布式系统对fault tolerence的一般解决方案是state machine replication 。

准确的来说应该是 state machine replication 的共识（consensus）算法。

paxos其实是一个共识算法，系统的最终一致性，不仅需要达成共识，还会取决于client的行为

主从同步复制

1、Master 接受写请求

2、Master 复制日志到slave

3、Master 等待，直到所有从库返回

问题：

任何一个节点失败，哪怕是从节点（Slave）同步失败，都会导致整个集群不可用，虽然保证了一致性，但是可用性却大大降低

基本想法：

a、多数派：

每次写都保证写入大于N/2个节点，每次读保证从大于N/2个节点中读。

比如5个节点，每次写大于3个节点才算成功；读也是大于3个节点才算成功。

b、多数派还不够！

在并发环境下，无法保证系统正确性，顺序非常重要。比如下图的 Inc 5; Set 0; 执行顺序乱了，结果就会引发错乱。

Lesile Lamport,Latex的发明者。

为描述Paxos算法，Lamport虚拟了一个叫做Paxos的希腊城邦，这个岛按照议会民主制的政治模式制定法律，但是没有人愿意将自己的全部时间和精力放在这种事上，所以无论是议员、议长或者传递消息的时间。

Paxos

1、Basic Paxos

2、Multi Paxos

3、Fast Paxos

强一致性算法---Basic Paxos

角色介绍：

Client:系统外部角色，请求发起者。像民众

Propser: 接受Client 请求，向集群提出提议(propose)。并在冲突发生时，起到冲突调节的作用。像议员替民众提出议案

Accpetor(Voter): 提议投票和接收者，只有在形成法定人数(Quorum,一般即为majority 多数派)时，提议才会最终接受，像国会。

Learner:提议接受者，backup，备份，对集群一致性没什么影响，像记录员；

步骤、阶段(phases):

1、Phase 1a:Prepare

proposer 提出一个提案，编号为N，此N 大于这个proposer之前提出提案编号，向acceptors请求同意，要求有quorum接受的才行。

2、Phase 1b:Promise

N 必须大于此acceptor之前接受的任何提案编号，才会接受，否则会拒绝。

3、Phase 2a: Accept

如果达到了多数派，proposer会发出accept请求，此请求包含提案编号N ,以及提案内容。

4、Phase 2b:Accepted

如果此acceptor在此期间没有收到任何编号大于N的提案，则接受此提案内容，否则忽略。

流程图如下：

操作步骤如下：

Request;

Prepare(1);

Promise(1,{Va,Vb,Vc});

Accept(1,Vn)

Accepted(1,Vn);

Response;

1、Acceptor部分节点失败，但达到了Quoroms，此时仍然会成功。

如果有一个Acceptor因为各种原因挂掉了，3个Acceptors变成了2个Acceptors，还是满足>n/2 的要求，所以还是会成功。

2、Proposer失败，上一次记录不会被写入Proposer表，然后重新开启一个新的Proposer，来替代上次的Proposer来处理未完成请求，此时编号已经增加为2，也就是Prepare(2)

Basic Paxos when an Proposer fails

如果Proposer 在发送了一条Accept消息之后，但是还没收到Accepted消息之前就挂掉了，只有一个Acceptor接收到了Accept消息。那么整个Paxos协议就没法进行下去了，这时一个新的Leader（Proposer）会被选举出来，重新开始一轮新的共识。

Basic Paxos潜在的问题是：活锁（liveness）或dueling

Basic Paxos很有可能出现这种情况：

1、议员A(proposer A)说我们来讨论提案1，大部分议员说：“好，我们来讨论提案1”；

2、但是此时议员A还没有说内容是什么，这时候又来了一个议员B，又来说：“我们来讨论提案2”；这时候大部分还没有接受提案1，提案2的编号是大于提案1的，这时候大部分还没有接受议案2；

3、这时候议员A以为网络断了，然后把编号改下，内容不变然后提出议案3；然后议案4、议案5....

这样就形成了活锁。

解决活锁的方法是用Random的timeout，当两个冲突的时候用一个随机的等待时间；当自己提议未生效时，再发起提议等待几秒。

Basic-Paxos是一个无限循环的2PC，1条日志的确认至少需要2个RTT + 2次落盘（1次是prepare的广播与回复，1次是accept的广播与回复）。

Basic Paxos when multiple Proposers conflict

最后再描述一个最复杂的情况，即有多个Proposers认为他们是Leaders，并不断的发送Prepare请求。为什么会有多个Leaders呢？ 有可能一个Proposer当了一段时间Leader之后挂掉了，新的Proposer被选为Leader继续新的一轮共识。后面挂掉的Proposer又恢复了，它认为自己还是Leader，所以继续发送Prepare请求。

Basic Paxos的问题

难实现（角色太多）、效率低（2轮RPC）、活锁问题

Multi Paxos:

新概念，Leader;唯一的propser，所有请求都需经过此Leader;

只有一个Proposer，没有第二个Proposer； 这个Proposer就是Leader,没人跟他抢;

再者分布式系统必须串行执行所有提议，否则就会出现前面说的顺序问题。

--------First Request(第一次执行)----------

Request

Prepare(N) //选Leader

Promise(N,I,{Va,Vb,Vc})

Accept!(N,I,Vm)

Accepted(N,I,Vm)

Response;

--------Following Request(第二次或者以后)----------

Request

Accept!(N,I,Vm)

Accepted(N,I,Vm)

Response;

第二次或者以后，就不用再选Leader了 直接执行Request 请求，由Leader 发出议案。

如果Leader 挂了 就选下一个总统Leader(N+1)

减少角色，进一步简化，在Basic-Paxos中我们区分了很多角色，有Clients、Proposers、Acceptors、 Learners，实际上Proposers、Acceptors 、Leanrners可以合并成一个，统称为Server，下面是合并之后的序列图。

Multi-Paxos when roles are collapsed and the leader is steady

同样的，当Leader很稳定的时候，我们可以在接下来的执行中忽略Phase 1. 如下图所示：

Raft

1、划分三个子问题

a、Leader Election

b、Log Replication

c、Safely

2、重定义角色

a、Leader

b、Follower

c、Candidate

原理动画解释： http://thesecretlivesofdata.com/raft

场景测试： https://raft.github.io

Raft 是比 Multi Paxos 还要简单的一个版本

一致性并不代表完全正确性！三个可能结果：成功，失败，unknown

详细内容参考：

https://www.jianshu.com/p/6cd41fe0b8f6

强一致性算法--ZAB

基本与raft相同。在一些名词的叫法上有些区别：如ZAB将某一个leader的周期称为epoch，而raft则称为term。实现上也有些许不同：如raft保证日志连续性，心跳方向为leader至follower，ZAB则相反。

鹏仔微信 15129739599 鹏仔QQ344225443 鹏仔前端 pjxi.com 共享博客 sharedbk.com