背景

MIT6.824是一个用来学习分布式系统的非常好的资源。其中第二个课程作业就是关于Raft算法。

由于在工作中涉及到分布一致性算法的调研，接触了paxos/raft算法。然后被@neutronest安利了一发，于是开始着手实现这个作业。

本文是我对这个项目的实现总结。希望能在划出重点的同时，不涉及实现细节，避免破坏大家的写代码体验。

本文唯一参考资料：In Search of an Understandable Consensus Algorithm

任务分解

在官方文档里，整个项目被分成了2A、2B、2C三个部分：

• 2A - 投票与选举
• 2B - 一致性
• 2C - 可持久化

实际上，2C的工作量非常少，我们可以把2B和2C合成一个。然后单独提出几个比较重要的测试用例，划分成子项目。任务分解如下：

• 2A - 投票与选举
• 2B/2C - 一致性和可持久化
• 三个难度比较高的Case
  • Test (2B): leader backs …

书接上文 - Multi Paxos

在上一篇文章中，我们提到了Basic Paxos和Multi Paxos的异同。在Paxos Made Simple论文中，作者提到了Multi Paxos的一种实现。这个实现允许我们对一个连续的数据流（也可以称为复制日志，replicated log）达成共识，从而实现节点状态的一致性复制。

确定性状态机

我们可以将系统中的每一个节点抽象为一个有着确定性状态机，即给定多个状态一致的状态机，在执行同一个命令之后，其状态仍保持一致。（可以想一想编译原理里面的DFA）

Leader - 系统中唯一的proposer

如果系统中存在有多个proposer，那么就很可能会出现多个提案相互干扰的情况。虽然根据证明，最终这些提案都会收敛到一致，但是性能会非常低下。所以我们可以在系统中通过选举，选出一个leader做为主proposer（distinguishied proposer），所有的提案都由leader提出。

这样一来，在绝大多数情况下都不会出现提案相互干扰的情况。只有在leader切换的瞬间，可能会出现相同编号的不同提案，但是我们的算法可以很好的处理这种情况。

分布式系统中的“TCP”

类似于TCP协议中序列号，Multi Paxos中的每一个命令都有一个递增的编号。即我们前一个执行的命令是100号，那么下一个执行的命令一定是101号 …