Raft（一）：一致性算法
为什么我们需要分布式系统？
分布式系统是由一组通过网络进行通信、为了完成共同的任务而协调工作的计算机节点组成的系统。
事实上分布式系统的复杂程度通常远远超过单机系统，在单机系统中，我们可能会遇到磁盘故障、并发死锁、系统崩溃等问题，而在分布式系统中，除了这些问题外，我们还可能遇到网络延迟、分区、系统状态不一致等千奇百怪的问题。
但是，分布式系统同样具有一些好处来吸引人们使用它：
分布式系统中存在大量的计算机并行运行，可以获取更高的性能。比如大量的计算的CPU、内存、磁盘可以并行运行。
分布式系统可以提供容错。比如两台计算机运行完全相同的任务，其中一台发生故障，可以切换到另一台。
由于物理原因，有些系统天然在空间上是分布式的。例如银行转账，假设银行在相距很远的地方分别由两台服务器，如果要在这两台服务器之前进行交易转账，那么就需要一种在两者之间进行协调的方法。
实现一些安全目标。比如有一些代码不被信任，但是我们需要和它交互，这些代码不会立即表现出恶意或出现bug。我们可以把代码分散在多处运行，这样不被信任的代码在一台计算机运行，我们的代码在自己的计算机上运行，然后再通过一些特定的网络协议通信。这样就把系统分成了多个计算机，可以限制恶意代码的出错域。
通过复制实现容错
上面提到，人们使用分布式系统的其中一个原因就是容错，而复制是实现容错的一个重要的工具。通过复制，可以让分布式系统中的节点运行相同副本，从在可以在一个节点出现故障的情况下，其他的节点可以继续提供服务。
有两种方法可以实现复制，一种是状态转移（State Transfer），另一种是复制状态机（Replicated State Machine）。
假设我们有一个服务的两个副本，一个是 Primary，另一个是 Backup。我们需要让它们保持同步，在实际上互为副本，这样一旦 Primary 出现故障，因为 Backup 的状态与 Primary 一致，就可以接管整个服务。
状态转移背后的思想是，Primary 将自己完整状态，比如说内存中的内容，拷贝并发送给Backup。Backup 会保存收到的最近一次状态，所以 Backup 会有所有的数据。当 Primary 故障了，Backup 就可以从它所保存的最新状态开始运行。所以，状态转移就是发送 Primary的状态。
复制状态机基于一个事实：我们想要复制的大部分服务都有一些确定的内部操作，而外部输入是不确定的。如果一台计算机没有外部输入，它只是一个接一个的执行指令，这样运行着相同服务的多个计算机的状态就会保持一致。只有当存在外部输入时，才可能会破坏一致性。例如，一台服务器在某个时间收到了一个网络数据包，导致服务器做一些不同的事情。
所以，复制状态机不会在不同的副本之间发送状态，相应的，它只会从 Primary 将这些外部输入发送给 Backup。假设有多台计算机，如果它们从相同的状态启动，并且以相同的顺序执行相同的外部输入，那么它们会一直互为副本，保持一致。
因此，状态转移传输的是可能是内存状态，而复制状态机会将来自客户端的操作或者其他外部输入，从 Primary 传输到 Backup。
Raft 是什么？
上面我们提到复制状态机是复制的一种实现方法，而复制状态机又通常是基于复制日志实现的，如图所示：
每个服务器存储一个包含一系列指令的日志，并且按照日志的顺序执行指令。如果每个日志都按照相同的顺序包含相同的指令，那么每个服务器都将执行相同的指令序列，最终所有的服务其都将保持一致的状态。反过来说，如果服务器上的日志出现了不一致，比如某些服务器上缺失了一条指令，或者指令顺序与其他的服务器不一样，那么每个服务器将会执行不一样的指令序列，导致出现状态不同步的问题。
而 Raft 就是一种一致性算法，其任务是保证复制日志的一致性。服务器上的一致性模块接收客户端发送的指令然后添加到自己的日志中。它和其他服务器上的一致性模块进行通信来保证每一个服务器上的日志最终都以相同的顺序包含相同的请求，即使有些服务器发生故障。一旦指令被正确复制，每一个服务器的状态机按照日志顺序处理他们，然后输出结果被返回给客户端。因此，服务器集群看起来形成了一个高可靠的状态机。