MIT6.824是一个用来学习分布式系统的非常好的资源。其中第二个课程作业就是关于Raft算法。
由于在工作中涉及到分布一致性算法的调研，接触了paxos/raft算法。然后被@neutronest安利了一发，于是开始着手实现这个作业。
本文是我对这个项目的实现总结。希望能在划出重点的同时，不涉及实现细节，避免破坏大家的写代码体验。
本文唯一参考资料：In Search of an Understandable Consensus Algorithm
在官方文档里，整个项目被分成了2A、2B、2C三个部分：
实际上，2C的工作量非常少，我们可以把2B和2C合成一个。然后单独提出几个比较重要的测试用例，划分成子项目。任务分解如下：
虽然在题目中我们把Paxos、Raft和PacificA并列，但是Paxos和Raft在论文中称自己为一种“算法”（algorithm）；而PacificA对自己的定位是一种通用的，强一致的数据同步框架。
在论文中，作者提到现有的可证明的数据同步协议往往过分简化了性能问题，导致看起来很美的理论设计无法转变有实际的系统（注：本篇论文应该早于Raft的论文）。所以作者的目标是将算法理论与实际相结合，进行相应的系统设计。
与Paxos和Raft不同的是，PacificA采用的算法非常简单。所以在这里我不进行太多铺垫，直接进入正题。
PacificA使用了主从同步模型，用户的读写请求都会发往主节点，以保证强一致性。
主节点会对发来的写请求进行编号，使得所有写请求编号唯一且单调递增。这个编号也会同步到从节点。
无论是主节点还是从节点，所有的写请求都写入一个只追加的日志。主从节点都需要维护committed指针，代表在这个指针之前的数据都已经被所有节点所认可，处理“已确认”状态。从节点需要额外维护一个prepared指针，代表在这个指针之前所有的数据都处于“待确认”状态，而在prepared指针之后的数据，都是“待同步”状态。
主从之间的数据同步使用两步提交模型 …
more ...在上一篇文章中，我们提到了Basic Paxos和Multi Paxos的异同。在Paxos Made Simple论文中，作者提到了Multi Paxos的一种实现。这个实现允许我们对一个连续的数据流（也可以称为复制日志，replicated log）达成共识，从而实现节点状态的一致性复制。
我们可以将系统中的每一个节点抽象为一个有着确定性状态机，即给定多个状态一致的状态机，在执行同一个命令之后，其状态仍保持一致。（可以想一想编译原理里面的DFA）
如果系统中存在有多个proposer，那么就很可能会出现多个提案相互干扰的情况。虽然根据证明，最终这些提案都会收敛到一致，但是性能会非常低下。所以我们可以在系统中通过选举，选出一个leader做为主proposer（distinguishied proposer），所有的提案都由leader提出。
这样一来，在绝大多数情况下都不会出现提案相互干扰的情况。只有在leader切换的瞬间，可能会出现相同编号的不同提案，但是我们的算法可以很好的处理这种情况。
类似于TCP协议中序列号，Multi Paxos中的每一个命令都有一个递增的编号。即我们前一个执行的命令是100号，那么下一个执行的命令一定是101号 …
more ...在分布式系统当中，我们往往需要保持节点之间的一致性。在绝大多数情况下，我们需要让系统中的节点相互协调通力合作，有可能的让系统正确的工作。但是，由于分布式系统本身的特性，需要我们在不可靠的硬件上尽可能的构建可靠的系统。所以，看似简单的一致性问题成为了分布式系统领域的一个重要的课题。
Paxos算法是Leslie Lamport于1990年提出的一种一致性算法。也是目前公认解决分布式一致性问题最有效的算法之一。
Paxos算法的目标是在一个不可靠的分布式系统内，只通过网络通信，能够快速且正确地在集群内部对某个数据的值达成一致。并且保证不论发生任何异常，都不会破坏系统的一致性。
某小区的一些居民在抢车位，而车位只有一个。居民们达成协议，只要一个报价获得半数以上居民认可，那么提出这个出价的居民则获得了车位的所有权。
居民之间非常友善，如果知道了车位已经有了买家，就不会继续出价购买，并且会帮忙传播这个信息。
居民们都是遵纪守法的好公民，在整个过程中都只会如实的与其它用户分享信息。信息的分享是在网上，通过一对一的私密聊天进行。但是小区的手机信号非常差，我们不能保证通信的质量，一些信息可能会丢失。但是居民不会掉线。也不会失去记忆，并且通信的内容是完整的，不会被篡改的。
划重点：
没有什么问题是加一千台机器解决不了的，如果有，就再加一千台。
—— 《21天精通分布式系统》
分布式系统在设计之初，是为了解决单机系统的可用性和可扩展性问题的。
举个例子，单机系统就是雇一个小弟替你干活，但是这个小弟不太靠谱，偶尔泡个病号不上班，偶尔工作太多一个人干不过来。
分布式系统就是雇一群小弟帮你干活，偶尔有一两个小弟泡病号，我们会有富裕的人力顶上，工作太多我们可以继续拉新的小弟入伙，美滋滋。
这个比喻很好的描述了单机系统和分布式系统之间的关系。所以一种可能的分布式系统就是这个样子的：
我们将相同功能的服务器组成一个整体，通过一个load balancer对外提供服务。
这样的系统初步解决了我们的问题，在面对可扩展性和可用性的问题时，我们会：
不过单纯的加机器并不能完全满足我们的需要。对于CPU密集型的服务，增加副本数可以有效的均摊计算压力，但是对于存储密集型的服务，我们需要增加分库逻辑才能有效的增加系统的计算能力。
例如我们有100G的数据，但是数据库的容量最多只支持50G。这样无论怎么样增加副本都不能解决问题。如果我们将100G的数据均分，存储在两个50G的分库上，我们就可以支持单机系统容纳不了的数据了。
我们还可以把多个这样的分布式子系统组合起来，就可以组成一个小有规模的分布式系统了。现在我们在使用的一些服务，仍在使用这种模型。
上面分布式模型虽然有效，但是引入了一个严重的问题：因为节点之间是隔离的，并且只能通过消息传递进行通信与协调，所以基本无法完全保证副本之间保持一致的内部状态。
这就是所谓的一致性问题。