可以说分布式协议是整个高并发高可用互联网的基石，用户数量稍微上点规模的公司就会用到各种分布式框架：Redis、RabbitMQ、Kafka、Elasticsearch。。。

那么这些优秀的分布式框架为何每天能够支撑亿级的流量呢？它们之间有没有什么共同点？这就要聊到今天的话题，分布式协议Paxos和Raft。

一、为什么需要分布式算法

我们从一个故事说起，这就是著名的拜占庭算法，拜占庭位于如今的土耳其的伊斯坦布尔，是东罗马帝国的首都。由于当时拜占庭罗马帝国国土辽阔，为了达到防御目的，每个军队都分隔很远，将军与将军之间只能靠信差传消息。

为了更简便的说明拜占庭算法，现在我们假设有三个将军，他们都很忠诚，这时候他们可以通过投票确定一致的行动方案。但是假如其中存在一个叛徒时，将可能扰乱正常的作战计划，下图展示了General C（将军C）为叛徒的一种场景，他给General A（将军A）发送了撤退的消息，给General B（将军B）发送了进攻的消息，在这种场景下General A通过投票得到（进攻:撤退=1:2），最终将作出撤退的行动计划；General B通过投票得到（进攻:撤退=2:1），最终将作出进攻的行动计划，结果只有General B发起了进攻并战败。

拜占庭将军问题最终想解决的是互联网交易、合作过程中的四个问题：

• • （1）信息发送的身份追溯 。

• • （2）信息的私密性 。

• • （3）不可伪造的签名。

• • （4）发送信息的规则 。

近几年火热的区块链轻而易举地解决了这一问题，它为信息发送加入了成本，降低了信息传递的速率，而且加入了一个随机元素使得在一定时间内只有一个将军可以广播信息。这里所说的成本就是区块链系统中基于随机哈希算法的“工作量证明”。哈希算法所做的事情就是计算获得的输入，得到一串64位的随机数字和字母的字符串。

拜占庭将军问题其实是由 Paxos 算法作者莱斯利·兰伯特提出的点对点通信中的基本问题，该问题要说明的含义是，在不可靠信道上试图通过消息传递的方式达到一致性是不可能的。

二、Paxos算法

所以，Paxos 算法的前提是不存在拜占庭将军问题，即信道是安全的、可靠的，集群节点间传递的消息是不会被篡改的。比如三将军问题中，不能有叛徒出现。

一般情况下，分布式系统中各个节点间采用两种通讯模型：共享内存（Shared Memory）、消息传递（Messages Passing），而 Paxos 是基于消息传递通讯模型的。

Paxis算法中有三种角色：Proposer（提案者）、 Acceptor（表决者）、Learner: 同步者

Paxos算法的核心内容

Paxos 算法的一致性主要体现在以下几点：

• • 1）每个提案者在提出提案时都会首先获取到一个具有全局唯一性的、递增的提案编号 N， 即在整个集群中是唯一的编号 N，然后将该编号赋予其要提出的提案。

• • 2）每个表决者在 accept 某提案后，会将该提案的编号 N 记录在本地，这样每个表决者中保存的已经被 accept 的提案中会存在一个编号最大的提案，其编号假设为 maxN。每个表决者仅会 accept 编号大于自己本地 maxN 的提案。

• • 3）在众多提案中最终只能有一个提案被选定。

• • 4）一旦一个提案被选定，则其它服务器会主动同步(Learn)该提案到本地。

• • 5）没有提案被提出则不会有提案被选定。

所以，Paxos 这样的分布式共识算法的基本思路，就是这样几点： 日志追加写入的时候，只要能够半数的服务器完成同步复制就算写入成功了。 在有节点挂掉的时候，因为我们有多个服务器，所以系统可以自动切换恢复，而不是必须修复某一台服务器才能继续运行。系统的数据需要有“一致性”，也就是不能因为网络延时、硬件故障，导致数据错乱，写入的数据读出来变了或者读不出来。

三、Raft算法

Raft和Paxos的目标一样，即如何在不稳定的分布式环境下使各个主机实例达成一致共识。

但是Raft算法更加容易理解，并不是说Paxos算法本身有问题，而是Raft算法直接就从状态复制问题出发，将算法问题拆解成一个个的独立的子问题：Leader 选举（Leader Election）、日志复制（Log Replication）、安全（Safety）和成员变化（Membership Changes）。

要解决以上几个独立子问题，Raft算法给每个节点分为三种状态：

• • Leader：领导者，负责日志的同步处理，处理来自客户端的请求。

• • Follower：追随者，接收Leader同步的日志，然后把日志在本地复制一份。

• • Candidate：候选者，Follower想要参与选举先要转换为Candidate角色，通常是集群刚启动或者Leader宕机之后。

Leader选举：

• • 1）集群刚启动时，所有节点的状态都是Follower。

• • 2）由于没有Leader，无法保持Leader和Follower之间的心跳，Follower会触发选主机制，将自己的状态转换为Candidate。

• • 3）然后Candidate将发起选举，它首先给自己投一票，然后请求其他的Follower也给自己投一票。

• • 4）其他Follower接收到选举请求后，首先会比对自己本地持有的变量term（任期）和请求中携带的变量term谁更大，如果请求中的term更大就投这个Candidate一票，否则拒绝投票。

• • 5）在一个任期里面，一个Follower最多给一个Candidate投票，投票的过程是谁先让我投我就投给谁。

• • 6）如果有超过半数的Follower都给某一Candidate投票，那么它就是新的Leader；

• • 7）没有被选举为Leader的Candidate就会收到一个比自己本地任期term更大的任期term，这个时候就知道自己选举失败了。

• • 8）如果过了一段时间没有人嬴得选举，那么到了超时时间，就会发起一轮新的选举。

• • 9）如果Candidate过多，导致无法获得半数以上的票数，那么就会给每个Candidate设置一个随机超时时间，那个最先超时的服务器大概率会先拿得半数以上选票，成为新Leader。

日志复制：

日志包含的内容：
日志索引：随着数据写入不断自增的字段。
日志内容：具体的需要写入的数据。
Leader任期：这一次数据写入，来自 Leader 的哪一个任期。

• • 1）Leader选举出来之后，整个集群就做好了向外界提供服务的准备了，当有数据的写入请求发送到了Follower，最终也会转发给Leader，因为只有Leader能够处理客户端的请求。

• • 2）Leader接收到写请求之后需要将日志同步给Follower，Follower首先会查看接收到的这条来自Leader的日志里面的任期和索引和在自己本地有没有，如果有就会删掉这个索引后面的所有所有日志都删掉，然后追加新日志。

• • 3）如果没有，Follower就会拒绝新追加的日志。然后Leader 就会找到前一条日志，再重新发送给 Follower，一直让Follower找到最后从Leader中同步过来的索引。

安全性：

这个安全性指的是在日志复制的时候，需要保证Leader里面的数据是整个集群里面最新的数据，Raft算法是靠什么方式实现的呢？

• • 1）Leader选举阶段，半数以上的Follower都会比较本地的索引和任期和请求中的索引和任期是否是最新的，比本地新才会投票，这就保证了Leader在半数以上的Follower中是拥有最新的日志数据。

• • 2）Raft本身写入数据的时候就需要半数以上的主机写入成功才会提交成功，这样至少有一个服务器是拥有最新数据的。

• • 3）如果还不好理解可以做个假设，假设一共三台主机，半数以上就是2，意味着有2台主机至少是写入了最新的数据，这样不论投票过程中怎么随机组合成半数以上的主机来投票都能至少保证有一台拥有最新数据。

成员变更

Raft算法下的成员变更（增减服务器实例）采用了一种“过渡共识”的办法，来解决手动修改配置导致出现的多主问题（有可能在服务重启的时候出现多个Leader）。

• • C_old：变更前的服务器配置

• • C_new：变更后的服务器配置

• • C_old,C_new：变更过段阶段的服务器配置

要变更整个Raft集群的配置，需要分为两个阶段，从C_old变为C_old,C_new，再从C_old,C_new变为C_new。

• • 1）C_old变为C_old,C_new：这个阶段外部客户端通过一个写入操作把我们的集群配置从C_old变为C_old,C_new，这个写入操作需要获得半数以上的C_old服务器通过，这个操作成功之后，集群就进入到了“过渡共识”阶段。

• • 2）C_old,C_new变为C_new：在这个阶段，所有的数据写入都要半数以上的C_old服务器和半数以上的C_new服务器通过，即使是选举新Leader也需要。

所以在整个“过渡共识”阶段，我们可以确保所有的日志写入，新老配置下都是可以达成共识的。Raft 的成员变更，本质上是一个“双写”的策略。通过先将配置修改为在新、老两个版本的配置上都能达成共识，Raft 使得服务器的集群变更可以平滑过渡，不需要中断服务。而整个配置策略的变更本身，也是通过一条 Raft 日志，来实现异步在多个服务器上更新并最终达成共识。