Paxos和Raft快速理解
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共识如何达成。
