摘要：通过muti-paxos的角度来看raft，总结出raft在借鉴multi-paxos的同时于哪些方面进行了取舍，在带来的understandable的同时又失去了什么。
Raft对multi-Paxos的简化
Raft的结构和multi-paxos非常相似，同样是leader-based，然而在multi-Paxos的基础上做了一些改变。
选值思路的简化
Raft的Term如同multi-paxos（以下均指leader-based multi-Paxos）的提议ID，一旦leader选出后，在一个leader lease中所有的消息Term都不变，Term可以被视为一个leader lease的标识。paxos协议要求multi-paxos对于paxos instance的提议ID必须全局唯一，实现通常使用timestamp + ip的形式，为了保证”Only a single value is chosen（不会出现先后不同的值被选中的情况）”的规则。实际对于leader election的场景无需满足如此严苛的要求，而Raft的leader选举就采用了不同的方法，无需保证不同server消息携带的Term全局唯一。
这是由于选择了和paxos策略不同的选值思路，paxos对于两个多数集合交集选值的唯一性保证是通过v2 = v1达成（paxos唯一性保证）。其实对于这个问题还有一种思路，就是选择接受v1后拒绝之后所有的提议，但是问题是极有可能永远达不成一致，那么就改进下，一次达不成一致就再试一次，直到达成一致后，拒绝之后所有的提议，这就是Raft leader election的思路。candidate发送vote给所有server，得到多数集合接受就周期性发送心跳禁止server成为新的candiate，如果不满足多数集合接受，则继续令其自由vote。所以Raft对于唯一性的要求是：在某个Term下，保证最多只有一个leader被选中，如果没选中，那么就通过electionTimeout机制递增Term进行下一轮选举，并且拒绝接受所有Term < currentTerm的提议。如果同时有两个leader被选中，那么至少存在两个多数集合各自接受了两个leader的vote，两个集合必有交集先后选择了两个leader，通过 1.将term实现为logcial clock（先到的vote先更新了currentTime，并设置votedFor），2.server拒绝Term >= currentTerm，且votedFor != null或votedFor != candidateId， 可得，必定拒绝后一个vote。在Raft中，不需要“学习”v1（这个要求导致了basic-paxos的两阶段流程原理难以理解），只需要拒绝，理解起来自然简单多了。
复制流程的简化
multi-paxos由于unknown和乱序commit的问题会产生“空洞”，在提议commit后不能直接apply到state machine，因为之前的提议不一定已经成功commit以及apply，可能和当前paxos instance是并发关系，因此必须等之前所有的提议都apply后才能apply（由于乱序commit的关系，需要使用类似数组的数据结构记录已commit的instance）。Raft通过引入Log Matching Property来保证，在{index, term}已经committed的前提下（不commit的情况，由于server fail等原因会导致不同）：
- 任意两个属于不同log但有相同index和term的entry一定存储着同样的指令
- 任意两个属于不同log但有相同index和term的entry，他们前序的所有entry都一一对应地相同。
因为每个term最多对应一个leader，每个leader在给定index上只会产生一个entry，同时Raft又引入Leader Append-Only原则，确保log不会被改写，因此条件1成立。对于条件2，Raft中的AppendEntries RPC相当于multi-paxos中的Accept消息，用来正式提议， 只要达成Quorum就可以commit。但为了保证条件2，Raft在AppendEntries上实现了前序一致性检查的逻辑，即受到AE后发现如果prevLogIndex对应entry的term不是prevLogTerm，则回复false，让leader递减prevLogIndex并重试，如果前序一致，则将AE携带的entry都append到本地log，使得各个log始终满足Log Matching Property条件。
根据Log Matching Property可得，若{index, term}已commit，前序所有entry都已commit。所以，对于每个server，只需记录一个lastApplied变量记录已apply的index，一个commitIndex变量记录已commit的index，一旦{index, term}被标为committed了，就可以更新commitIndex并直接将[lastApplied+1, index]范围内的所有entry都按顺序apply到state machine，然后通过AE将commitIndex同步给其它server，让他们完成相应的apply工作。
数据不一致的处理方法改进
前文讨论了multi-paxos中对于数据不一致情况的产生以及处理（leader-based multi-paxos数据不一致处理）。raft和leader-based multi-paxos的情况很相似，在正常工作流中并不会出现leader数据不一致的情况（当前log index的前序entry都是committed）。但是在因为故障或其他原因导致的leader transfer后，新leader会有不一致的问题。paxos需要新leader像某多数集合请求最大log index，end index，然后从已commit的位置起，执行single decree，直到到达位置end index，才能开始处理client请求。multi-paxos的问题在于，新leader如果落后较多，需要做single decree的路径较长，会带来较大的延迟。
Raft从两方面对其进行了改进：
- 从“拉”（Pull）数据到“推”（Push）数据
- 选举拥有最新log的server为leader
要减少新leader因为落后太多导致的高延迟，一个可行的方案就是选择最新log的server为leader，这个逻辑被实现在RequestVote RPC的接受逻辑中，只要candidate的log比server本地的log旧，就拒绝。最新committed的log一定存在于多数集合中，那么任何少数集合在选举中一定无法赢得选举（如果某candidate的term很大，但log落后，发送出去的RequestVote会更新其它server的term，但并不会被log更新的server所接受），最终一定是多数集合中的某个server赢得选举（这里也隐含了Leader Completeness Property：如果某个entry的状态是committed，那么该entry一定存在于之后任何term更高的leader的log中）。
另一方面，通过AE实现的“前序一致性检查”，在发送心跳或AE的时候“顺便”解决了follower上的数据不一致问题，化新leader的“拉”数据为当前leader“推”数据到其它server，保证各个server的Log Matching Property，这样当成为新leader时无需“拉”数据了。
细节的处理
Lamport对于multi-paxos的描述缺少了许多细节的处理，包括leader crash的处理、membership的变化管理等等。Raft在这些方面都做了细致的说明。
读写操作
读操作优化
对于读操作来说，操作本身并不改变数据，但是每次读却需要一次entry commit，有没有办法bypass这个commit，直接从本地state machine读?
假设直接从leader的state machine读，需要考虑以下问题：
- leader是不是真leader？
- leader的state machine是不是“足够新”？
只要满足以上2个条件，即可直接从leader本地读。第一个条件，leader必须保证是真的leader才能从state machine读。虽然Raft保证了对于相同的Term最多只有一个leader，但并不排除临时有多个Term互相不同的leader同时存在，这里面只能有一个真正的leader，可以让leader进行一轮heartbeat，收到多数集合回复的即是真leader。第二个条件，leader的state machine“足够新”，leader收到client的读请求后，要满足线性一致性，就需要确保此时能被apply的entry都要被apply后，state machine才“足够新”。而只有当前commitIndex以及之前的entry才符合要求，所以，在leader收到client读请求后，记录下当前的commitIndex，为readIndex。然后当applied更新到readIndex后，可以返回给client。但这里还有一个问题，假设leader刚从失效状态回来，并选举为leader，虽然Leader Completeness Property能保证leader当前有所有commit的entry，但是当前leader可能并不知道实际的commitIndex的值是多少（类似basic paxos，只有proposer知道值有没有被选中，同样，这里只有老leader知道这个commitIndex），leader没法决定apply至哪个index，要重新得到这个真正的commitIndex，需要提交一条新entry，一条标识No-Op的空entry（只需要在leader刚选上时），之后再更新commitIndex到readIndex，等apply至readIndex后返回state machine结果给client。
这样，原来要经过一轮entry commit的读流程现在只需进行一轮heartbeat并等commit到readIndex即可从state machine返回。不用同步写磁盘了。