最近在学习zk，因而顺道学习一下paxos和raft，没有看英文论文，直接看的书和网上的译文，看的一塌糊涂，paxos算法感觉很多人理解的不对或者描述的不准确，毕竟两阶段到底哪个算批准，而且接受和接收也容易混淆，甚至一些介绍一致性算法的书也表述模糊或表达错误，现在对那些混论坛或者随便出书所谓技术大牛的有点反感，不能盲目相信。
一、Paxos算法
Paxos一般说来有三种角色，proposer，acceptor，learner，learner主要是学习选定的提案，在选定提案的两个阶段中不会出现。
phase 1:
（1）一个proposer选择一个编号n，并发送一个携带该编号的prepare request给一个acceptor集合，这里的acceptor集合指含有大多数的acceptor。
(2) 当一个acceptor接收到一个编号为n的prepare request，如果n大于之前已经回复过的所有请求的编号（包括prepare request和accept request），那么acceptor将回复这个prepare request，同时带上承诺：不再接受编号小于n的请求（包括prepare request和accept request，如果继续接受小于N的prepare request和accept request，那么这次回复的value就有可能不是这个acceptor已知的小于n的最大编号的value，因为phase 1的目的就是proposer获取当前已经批准的value，从而保证一旦批准了某个value，phase2就不会产生其它的value，保证迅速收敛），回复的value可能有两种情况，第一，如果之前这个acceptor已经批准过accept request，那么就把accept request里的value回复给proposer。第二，如果这个是这个acceptor之前没有批准过任何value，那么就回复一个空value。
phase 2:
（1）如果一个proposer收到了来自大多数的acceptor的prepare request的回复，那么它将再次给acceptor集合发送一个accept request，带上编号n和value。这里的value根据acceptor对prepare request的回复消息来决定，如果回复消息中有value，那么就采用其中编号最大的那个value（其实不管编号是多少，批准的value肯定都一样），如果所有的回复中都是空的value，那么这个proposer就可以自己决定value。
（2）如果一个acceptor收到了一个编号为n的accept request，除非在此之前它接收了一个编号比n大的prepare request或者accept request，否则，这个acceptor将批准这个accept request，因为只要有更高的编号n的value到达第二阶段，就表示编号小于n的提案都没有得到大多数acceptor的批准，这里的批准专指第二阶段的批准。
以上的是我的理解，对于paxos算法，如果一个提案在发送prepare request，收到prepare request响应，再发送accept reqeust，这三条消息之间没有更高编号的提案发送（prepare request一定比accept request先发送给大多数acceptor）给大多数acceptor，那么它就会被大多数acceptor批准，从而被选定，而且一旦它被选定，那么编号大于n的提案的value也将通过阶段一保证与它相同，进而保证最终一致性。但是paxos有可能出现多个proposer交替发送prepare request消息给大多数acceptor的情况，这种情况将会导致不能选定出提案，因而应用中一般也会先选出主proposer，统一由它来同步整个paxos的二阶段，避免出现活锁。paxos难于理解，由于缺少很多细节所以更难于实现，因而就有了raft。
二、Raft算法
raft算法的学习主要看中文译文应该就可以了，写的比较清楚，唯一产生疑问的是5.4.2节中产生新的leader后应该如何处理旧任期内未提交的日志，raft的做法直接处理当前任期的请求，因为在复制当前任期的日志时，根据日志匹配的特性，会顺带着复制旧任期的日志，如果新任期的日志复制到了大多数，旧任期的日志也就复制到了大多数。这样做貌似更简单了，不需要对旧日志做同步的操作，为什么反而是更安全了呢？我的理解是选举leader的过程中已经保证了在所有的成员中，leader的日志要么是最新的，要么其它成员有最新的日志，还没有占大多数，所以这个未决的日志先不用考虑，只要把当前任期的日志复制到大多数了，那么leader上的旧任期日志也就复制到了大多数，因为要保证日志匹配特性。还有一点，就是这种情况下，如果复制日志是逐条复制，也会出现图中的问题，所以从c时刻到e时刻，S3上的index2和index3的日志是一次原子复制。
译文5.4.2
最后，这两个算法都够牛逼了。
raft动画：http://thesecretlivesofdata.com/raft/
raft译文：https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md
网友评论