Paxos & Raft 算法
在分布式系统中，有很多场景需要对某一个值达成一致。比如：冗余系统的选主（主节点的id就是那个值），分布式日志备份系统（日志中的每条记录就是那个值）等。
Paxos和Raft算法是两种一致性算法（或者说是协议），下面就详细解释一下。
写在前面：这块内容我在网上学习了快两周，感觉零零碎碎还是看论文最直接也最明确。如果有跟我有过同样疑惑的朋友，建议去花时间看看原文，比在网上乱看强多了。
Basic Paxos
Lamport的论文The Part-Time Parliament，简化版Paxos Made Simple
Stanford的一个课件
Paxos算法其实是一个两阶段提交的过程，每个提议只要有超过半数节点通过即最终通过。Paxos中有三种角色：Proposer—提案发起者；Acceptor—提案批准者；Learner—学习提案，这个后面再说。每个节点可以分饰三角，也就是说可以自己投自己。
变量解释：
Proposal number，提案的唯一ID，保证如果两个ID a和b，若a>b，则a比b新且a的优先级高。通常使用timestamp+serverId的形式保证唯一和递增。
minProposal：当前可以接受的最小的ProposalId值。
acceptedProposal：当前已经接受的ProposalId值。
acceptedValue：当前已经接受的提议的值。
两阶段具体内容如下：
第一阶段：Proposer选择一个proposal number n，广播Prepare(n)给所有Acceptor。Acceptor收到prepare(n)后，如果n比任何之前收到的proposal number都大，则该提案当前优先级最高，更新minProposal并返回成功；否则返回当前接受的最大proposal number和value。若Proposer收到了拒绝，则用返回值更新自己的提案。
第二阶段：经过第一阶段之后，无论原始提案被接受还是被其他节点更新，都应该是该节点已知的最高优先级的提案。收到大多数节点的反馈之后，向这些节点发送Accept(n, v)。Acceptor收到accept(n)后，如果该提案是当前最大的，则直接接受；否则返回自己已知的最大提案(n, v)。如果proposer收到(n, v)，则证明有更新的提案，则重新提交提案。
在前面给出的课件链接中讨论了几种情况可以作为一种简单证明。
另外还有一个角色Learner，因为每个节点并不知道自己的提案是不是被大多数接受了，只有proposer才知道。所以learner的作用就是去”学习“，去验证自己是不是那个被接受的提案。网上很多介绍中都不提这个角色，但是这个角色很重要（下一节说）。
但是Basic Paxos的流程中有个缺点，在高并发情况下，可能出现多个提案交替获得多数支持的情况，被称为”活锁“，会严重降低性能。
Multi-Paxos
Multi-Paxos是Paxos的进化版，通过选主来去掉prepare阶段（因为只有一个leader，所以不需要prepare进行一致性确认）。在一个任期内，只有选出的leader可以进行提案，其他节点只被动接受。
选主是一个Paxos过程，参照Basic-Paxos选出一个主机ID。但是刚才提到了，并发情况下可能出现短暂的多主，虽然多主情况是可以接受的，即退化为Basic-Paxos，但是也可以先确认主节点：主节点一旦被选出，就会立即向所有节点群发StartWorking日志。整个系统中只有一个主节点会被大多数节点接受，失败的主节点自动退化成普通节点。
但是Paxos并不要求日志连续，比如说某节点上有连续的ABCDE五条日志，但是CD两条可能并不是那个”大多数“，可能因为没来得及学习或者网络问题，没更新上（如图）
所以被选出的主节点上可能日志并不是完整的。通常工程上的做法是：每个提案被接受之后，leader另外广播一条信息说某个ProposalId被接受了，然后收到这个信息的节点会默默记下这个节点是最终提案的记录（网称Confirm日志），这样在新主启动之后，就知道自己哪些是确定被接受的，哪些可能不是。新主通过询问其他节点”当前能确认的连续最大的ID是多少“，比如上图中”2“就是能确认的最大ID，然后从2之后的所有未确定的log全部执行一次paxos。
性能优化：log可以分组，不用细说了吧……
关于Multi-Paxos这块有很多种不同的实现方案，不必非要固守某一种方法。
Raft
论文：In Search of an Understandable Consensus Algorithm
UIUC课件
Raft之所以出现就是因为Paxos太复杂、太不容易实现（加上Multi-Paxos只是lamport随口一提，实现各异）。Raft强调主节点至高无上，强调日志连续性。Raft可以给出简单的解释和伪代码，容易工程实现。
Raft算法主要有两个部分：选主和备份。其中也就有两种RPC调用：AppendEntryRPC用来插入一条记录，RequestVoteRPC用于请求其他人选主（选自己）。
Raft中有两个角色，Follower和Leader（中间的Candidate角色暂不当做一个独立角色讨论）。Leader会定期向所有Follower发送心跳包（payload为空的AppendEntryRPC包），当某个Follower隔了某段时间没收到心跳包了，他就认为原Leader已经挂了，开始启动选主，此时Follower变身成为Candidate，向所有节点发送RequestVoteRPC。此时有三种情况：
- 收到了大多数支持票——变身Leader
- 收到了AppendEntryRPC请求——变回Follower
- 超时，未满足前两要求，重新选举。
这个时候如果所有Candidate都参选，都投自己，那么选举就失败了，要进行下一轮。Raft的做法是，在下一轮开始前，每个Candidate都会随机地等待一段时间，先被唤醒的节点先发送RequestVoteRPC，那么就更容易当选。
选主是不是随便选的呢？当然不是的。在最开始我们就说到Raft注重的连续性。注意这个AppendEntryRPC的内容：
- term表示的是第几个”任期“，每个节点自己都保存了currentTerm，选主时肯定要选比自己term大的。
- commitIndex表示的是当前已经提交的最大的Index，（每个提案或者每条log都有一个term和一个递增的index），这个东西就像TCP协议中的sequence number一样，在让Follower提交b任务时，一定会把前一个a任务的index带上，从而保证整个任务线是串行的（当然这里也可以让Follower严格按照index递增的顺序提交来实现）。
既然任务是串行的，那选主就容易多了：只选commitIndex最大的节点（我们可以看到在RequestVoteRPC中要把自己的lastLogIndex带上）。这样选出来的主节点一定是当前保存log最多的（此处可以数学归纳法证明，略）。
另外性能上，Raft也可以用batch commit的方式来优化。
不管你信不信，我也是个手写过Raft的人，但是那个时候我还不知道这个叫Raft。。。
最后
无论是Raft还是Paxos，都是eventually consensus，所以一般读写（对外提供服务）都是在Leader上的。
参考资料：
论文、课件（文中链接）
https://zhuanlan.zhihu.com/p/20417442
https://www.zhihu.com/question/36648084