raft算法与paxos算法的差异

raft算法与paxos算法的差异

raft算法和paxos算法都是经典的分布式一致性算法。最初从《redis的设计与实现》这本书中了解到raft算法，当时觉得它十分巧妙的解决了分布式环境下的数据一致性问题。后面又了解到paxos算法，但对paxos算法和raft算法之间的差异却总是无法理解。网上有关两者的差异的总结很多，通常几句话简单概括。最近读到一篇相关博客，总算是解决了我心中的疑惑。博客名为raft算法与paxos算法相比有什么优势，使用场景有什么差异？

这里就不做同这篇文章完全相同的描述了，但读者必须在读上面的博客时对raft算法和paxos算法（主要是说multi-paxos算法）的基本流程有所了解。这里主要做一下对以上博客阅读后的个人认为的关键点总结，在读完上述博客还是无法理解作者要表达什么的话可以看一下总结，方便找到重点。

通篇读完博客，我认为作者最想强调的是raft算法与multi-paxos算法在选举机制上的差异，即raft更加强调选举日志提交的有序性，而multi-paxos算法则是无序的。multi-paxos算法需要专门协调各个节点之间的日志提交。即Raft协议强调日志的连续性，multi-paxos则允许日志有空洞。

raft算法与paxos算法都通过一个版本号确定哪个提案是最新的。需要注意的是提案paxos协议的中叫法，日志是raft协议中的叫法，它们都是指代需要确保一致性的数据。paxos中的版本号被称作proposer-id，raft中的版本号被称作term。此时叫做提案被决定或日志被提交。

实际上raft协议在leader选举阶段，由于老leader可能也还存活，也会存在不只一个leader的情形，只是不存在term一样的两个leader，因为选举算法要求leader得到同一个term的多数派的同意，同时赞同的成员会承诺不接受term更小的任何消息。这样可以根据term大小来区分谁是合法的leader。Multi-paxos的区分leader的合法性策略其实是一样的，谁的proproser-id大谁合法，而proposer-id是唯一的。因此它们其实在同一个时刻，都只会存在一个合法的leader。

Raft协议中日志的commit（提交）也是连续的，一条日志被提交，代表这条日志之前所有的日志都已被提交，一条日志可以被提交，代表之前所有的日志都可以被提交。

而对于multi-paxos来说，日志是有空洞的，每个日志需要单独被确认是否可以commit，也可以单独commit。因此当新leader产生后，它只好重新对每个未提交的日志进行确认，已确定它们是否可以被commit，甚至于新leader可能缺失可以被提交的日志，需要通过Paxos阶段一向其它节点学习到缺失的可以被提交的日志，当然这都可以通过向一个多数派询问完成

总结：raft和multi-paxos最大的区别就是日志提交的有序性。raft有序而multi-paxos无序，全文都在强调这一点。

另外作者也指出为什么paxos比raft更加难以实现：仅仅是因为raft的作者提供了伪代码和部分实现细节，而paxos的作者却仅做了理论阐述。如果想要实现paxos，就需要在实现过程中加上一些自己对算法的理解，这就导致实现出的算法很有可能与他人不同，成为了全新的算法。