RAFT与PBFT

图片.png

【一．raft算法】

因为网上已经有大量文章对raft算法进行过详细的介绍，因此这部分只会简单的阐述算法的基本原理和流程。raft算法包含三种角色，分别是：跟随者（follower），候选人（candidate）和领导者（leader）。集群中的一个节点在某一时刻只能是这三种状态的其中一种，这三种角色是可以随着时间和条件的变化而互相转换的。

raft算法主要有两个过程：一个过程是领导者选举，另一个过程是日志复制，其中日志复制过程会分记录日志和提交数据两个阶段。raft算法支持最大的容错故障节点是（N-1）/2，其中N为 集群中总的节点数量。

国外有一个动画介绍raft算法介绍的很透彻，链接地址在这里[1]。这个动画主要包含三部分内容，第一部分介绍简单版的领导者选举和日志复制的过程，第二部分内容介绍详细版的领导者选举和日志复制的过程，第三部分内容介绍的是如果遇到网络分区（脑裂），raft算法是如何恢复网络一致的。有兴趣的朋友可以结合这个动画来更好的理解raft算法。

【二．pbft算法】

pbft算法的提出主要是为了解决拜占庭将军问题。什么是拜占庭将军问题呢？拜占庭位于如今的土耳其的伊斯坦布尔，是古代东罗马帝国的首都。拜占庭罗马帝国国土辽阔，为了达到防御目的，每块封地都驻扎一支由将军统领的军队，每个军队都分隔很远，将军与将军之间只能靠信差传递消息。 在战争的时候，拜占庭军队内所有将军必需达成一致的共识，决定是否有赢的机会才去攻打敌人的阵营。但是，在军队内有可能存有叛徒和敌军的间谍，左右将军们的决定影响将军们达成一致共识。在已知有将军是叛徒的情况下，其余忠诚的将军如何达成一致协议的问题，这就是拜占庭将军问题。

下图列出了raft算法和pbft算法在适用环境，通信复杂度，最大容错节点数和流程上的对比。

image

关于两个算法的适用环境和最大容错节点数，前文已经做过阐述，这里不再细说。而对于算法通信复杂度，为什么raft是o（n），而pbft是o（n^2）呢？这里主要考虑算法的共识过程。

对于raft算法，核心共识过程是日志复制这个过程，这个过程分两个阶段，一个是日志记录，一个是提交数据。两个过程都只需要领导者发送消息给跟随者节点，跟随者节点返回消息给领导者节点即可完成，跟随者节点之间是无需沟通的。所以如果集群总节点数为 n，对于日志记录阶段，通信次数为n-1，对于提交数据阶段，通信次数也为n-1，总通信次数为2n-2，因此raft算法复杂度为O（n）。

对于pbft算法，核心过程有三个阶段，分别是pre-prepare（预准备）阶段，prepare（准备）阶段和commit（提交）阶段。对于pre-prepare阶段，主节点广播pre-prepare消息给其它节点即可，因此通信次数为n-1；对于prepare阶段，每个节点如果同意请求后，都需要向其它节点再 广播parepare消息，所以总的通信次数为n（n-1），即n^2-n；对于commit阶段，每个节点如果达到prepared状态后，都需要向其它节点广播commit消息，所以总的通信次数也为n（n-1），即n^{2-n。所以总通信次数为（n-1）+（n}2-n）+（n^{2-n），即2n}2-n-1，因此pbft算法复杂度为O（n^2）。

流程的对比上，对于leader选举这块，raft算法本质是谁快谁当选，而pbft算法是按编号依次轮流做主节点。对于共识过程和重选leader机制这块，为了更形象的描述这两个算法，接下来会把raft和pbft的共识过程比喻成一个团队是如何执行命令的过程，从这个角度去理解raft算法和pbft的区别。

一个团队一定会有一个老大和普通成员。对于raft算法，共识过程就是：只要老大还没挂，老大说什么，我们（团队普通成员）就做什么，坚决执行。那什么时候重新老大呢？只有当老大挂了才重选老大，不然生是老大的人，死是老大的鬼。

对于pbft算法，共识过程就是：老大向我发送命令时，当我认为老大的命令是有问题时，我会拒绝执行。就算我认为老大的命令是对的，我还会问下团队的其它成员老大的命令是否是对的，只有大多数人（2f+1）都认为老大的命令是对的时候，我才会去执行命令。那什么时候重选老大呢？老大挂了当然要重选，如果大多数人都认为老大不称职或者有问题时，我们也会重新选择老大。