Paxos和Raft快速理解

Paxos一致性协议

Paxos问题指分布式系统中存在故障fault，但不存在恶意corrupt节点场景（消息可能丢失但不会造假）下的共识达成（Consensus）问题。

Paxos是第一个被证明的共识算法，原理基于两阶段提交并进行扩展。算法中将节点分为三种类型：

• 倡议者proposer：提交一个提案，等待大家批准为结案，往往是客户端担任。
• 接受者acceptor：负责对提案进行投票，往往服务器担任。提议超过半数的接受者投票及被选中。
• 学习者learner：被告知提案结果，并与之统一，不参与投票过程。客户端和服务端都可担任。

每个节点在协议中可以担任多个角色。

Paxos的特点：

• 一个或多个节点可以提出提议
• 系统针对所有提案中的某个提案必须达成一致
• 最多只能对一个确定的提案达成一致
• 只要超过半数的节点存活且可互相通信，整个系统一定能达成一致状态

两阶段提交图解

假设5个节点构成分布式系统，A和E节点分别有X和Y提案，其他节点没有提案。

image

然后A节点广播它的提案，强假设网络延迟的原因，只有A，B，C节点收到提案，这里的提案哪怕A，E节点的提案同时到某个节点，也必然会有先后顺序的，是不可能真正意义上的同时。

image

A，B，C接收到A的提案后，由于是第一个接收到的提案，acceptedProposal和acceptedValue都为空，诚实返回。

image

由于A节点已经收到超半数的节点相应，且返回的acceptedValue都为空，也就是说可以用X作为提议的值来发生Accept请求，A，B，C节点接收到请求后，将acceptedValue更新为X。

image

A，B，C节点会发生minProposal给A，A检查发现没有大于1的minProposal出现，此时X已经被选中。此时，由于D，E节点的acceptedValue并不是X，系统还没有达成一致共识，Paxos过程还是没有结束。

image

E节点选择Proposal ID为2发送Prepare请求，结果和上面是一样的，因为C节点已经选择接受了A节点的提议，它是很诚实的，就直接告诉E节点他的选择，E节点知道C节点既然选择了A的提案，那自己也选A的提案。于是，E发起Accept请求，使用X作为提议值，至此，整个分布式系统达成了一致，大家都选择了X。

image

总结Paxos两阶段提交

两个阶段分别是准备（prepare）和提交（commit）。准备阶段解决大家对哪个提案进行投票的问题，提交阶段解决确认最终值的问题。

简单来说，提案者发出提案后，收到一些反馈，有两种结果，一种结果是自己的提案被大多数节点接受了，另外一种是没被接受，没被接受就过会再试试。
提案者收到来自大多数的接受反馈，也不能认为这就是最终确认。因为这些接收者并不知道自己刚反馈的提案就是全局的绝对大多数。
所以，引入新的一轮再确认阶段是必须的，提案者在判断这个提案可能被大多数接受的情况下，发起一轮新的确认提案。这就进入了提交阶段。
提交阶段的提案发送出去，其他阶段进行提案值比较，返回最大的，所以提案者收到返回消息不带新的提案，说明锁定成功，如果有新的提案内容，进行提案值最大比较，然后替换更大的值。如果没有收到足够多的回复，则需要再次发出请求。

一旦多数接受了共同的提案值，则形成决议，称为最终确认的提案。

Raft一致性算法

Raft算法是Paxos算法的一种简化实现。

包括三种角色：leader，candidate和follower。

• follow:所有节点都以follower的状态开始，如果没有收到leader消息则会变成candidate状态。
• candidate：会向其他节点拉选票，如果得到大部分的票则成为leader，这个过程是Leader选举。
• leader：所有对系统的修改都会先经过leader。

其有两个基本过程：

• Leader选举：每个candidate随机经过一定时间都会提出选举方案，最近阶段中的票最多者被选为leader。
• 同步log：leader会找到系统中log（各种事件的发生记录）最新的记录，并强制所有的follow来刷新到这个记录。

Raft一致性算法是通过选出一个leader来简化日志副本的管理，例如，，日志项（log entry）只允许从leader流向follower。

下面是动画演示Raft，清晰理解Raft共识如何达成。

http://thesecretlivesofdata.com/raft/