Raft和它的三个子问题

发布网友发布时间：2023-04-29 23:43

共1个回答

热心网友时间：2023-11-25 22:49

这篇文章来源于一个经常有人困惑的问题：Quorum与Paxos，Raft等一致性协议有什么区别，这个问题的答案本身很简单：一致性协议大多使用了Quorum机制，但仅仅有Quorum(R+W>N)机制是保证不了一致性的。本文计划延伸这个问题，以Raft为例回答一个完善的一致性协议拥有包括Quorum在内的那些机制，试着说明这些机制的完备以及其中每一项的不可或缺。

要回答这个问题首先需要说明Raft是做什么的，Paxos、Raft被称为一致性协议，顾名思义它们要解决的是多节点的一致性问题，需要注意的是这里所说的一致性并不是要求所有节点在任何时刻状态完全一致。而是要保证：

即使发生网络分区或机器节点异常，整个集群依然能够像单机一样提供一致的服务，即在每次操作时都可以看到其之前的所有成功操作按顺序完成。

这里有两点需要说明：

将每一个对Raft集群的操作称为一个提案，希望Raft集群对外屏蔽内部的网络或节点异常，依次对每一个提案作出相应，提交成功的提案可以在后续操作中持续可见。这里的提案需要是幂等的，即重复执行不会导致集群状态不同。

接下来我们就看Raft是如何实现这种一致性保证的。Raft将一致性问题拆分为三个子问题，各个击破，从而使得其实现简单易懂。本文将首先简单介绍其三个子问题的内容以及达成方式；之后证明三个子问题是实现一致性的充分条件；最后尝试说明这三个子问题的保证缺一不可。

组成一个Raft集群至少需要三台机器，而Raft*每一时刻最多只能有一个节点可以发起提案，这个*极大的简化了一致性的实现，这个可以发起提案的节点称为Leader。因此所要解决的第一个问题便是：

如上图所示：

从上面对Raft状态转换的讨论中可以看到，任何非Leader的节点都有可能在未来成为Leader，为了能保证后续Leader节点变化后依然能够使得整个集群对外保持一致，需要通过Log Replication机制来解决如下两个问题：

上图描述了一个Raft提案的执行过程：

Follower在接受AppendEntry时会检查其前一条的Log是否与Leader相同，利用数学归纳法可以很简单的证明Leader和Follower上的Log一致。另外，由于只需要过半数的节点成功即可返回，也就在保证一致性的前提下竟可能的提高了集群的可用性。

这里需要注意，Leader Commit过的提案会向用户返回成功，因此Raft集群需要保证这些提案永远存在。

通过上述的两个子问题已经解决了大部分的难题，除了下面两个细节：

通过上述的三个子问题的解决，我们得到了一个完善的一致性算法，论文中给出了详细严谨的证明，其首先假设Commit过的提案会在后续丢失，之后推导出矛盾进而反证成功，这里不再赘述。该证明的关键点在于：Leader Election中要求新Leader获得超过半数的节点投票，Log Replication中每个Commit都有超过半数的节点同意，因此这两个大多数中至少存在一个公共节点，这个节点既同意了某个提案的Commit又投票给了新的Leader。

上面讨论了三个子问题对一致性的充分性，接下来要讨论的是在Raft的框架下，任何一个子问题的缺失都会导致严重的不一致后果：

通过上面的讨论，可以看出一个完整的一致性协议做了包括Quorum在内的诸多努力。Raft划分了三个子问题来使得整个一致性算法的实现简单易懂，我们也基于Raft实现了自己的一致性库 Floyd 来满足诸如 Zeppelin 元信息集群及 Pika 跨机房功能中对一致性的需求。

In Search of an Understandable Consensus Algorithm

Qihoo360 Floyd