Motivation
毕业设计的选题是实现一个高可用的 key-value 数据库，其中的共识算法就打算采用 Raft。为了让大家帮我做毕业设计，所以给大家简单谈谈这个算法的一些细节。
What is high availability
首先得简单介绍一下何为高可用。假设我们的数据都存放在一个节点上，如果这个节点意外崩溃了，这个节点将无法提供服务，更加严重的，如果这个节点的存储介质发生了损坏， 数据将会丢失。这些都是我们无法容忍的，我们希望的是整个系统可以容忍一定数量的错误产生，诸如节点崩溃，网络分区的产生等等。这样的系统将出于一个高可用的状态。我们可以通过在不同的节点上存储一个数据的多个副本，来达到这样一个状态。举个例子，原本某瓣将我想看电影的数据存放在广州的节点上。某天，这个机房断电了，我就没有办法查到我想看的电影了。为了让系统实现高可用，现在某瓣搞了一个两地三中心的一个解决方案，这样我的数据将会存三份，即使广州节点出了问题，我还是可以通过别的数据中心拿到我的数据。但是问题来了：
- 如何保证一个集群里边对于一个数据的写入保持共识；也就是所有的节点都会只会写入同一个值，不会产生脑裂的情况。比如集群内部的副本分成两派，都提供正常服务，但是最终他们会产生不一致。
- 客户端有多个数据写入的时候，如何保证写入顺序在所有的节点是否都是一致; 比如我们要写入
x = 3, y = 4, 不会有别的节点先写入 y = 4，后写入 x = 3。
- 当节点发生错误无法继续工作的时候，已经提交成功的数据不会丢失; 比如
x = 3已经提交（成功写入），这个写入不会因为一个在系统容忍范围内的错误而丢失。
这个时候就要引入 Raft，他能给我们解决上边的问题，甚至更多。
What is Raft
Raft 简单的说就是一个保持多个状态机副本状态一致的算法。放到上边的例子，我们可以把数据当作是一个状态机，写入操作看作是状态机的输入。在 Raft 中，我们称状态机的输入为 Command，Command 持久化在所谓的 log entry 中，每个 Raft 节点拥有一个由 log entry 组成的数组，Raft 的目标就是通过解决上边的问题，让不同（大多数）节点的 log 保持一致。接受同样的输入序列，状态机的最终状态必然一致，自然就解决了状态机的一致性问题。
How does Raft work
Raft 将集群中的节点分成三种角色：
- Leader
- Candidate
- Follower
整个集群在任何时刻都只能有一个 leader, 但是允许其他角色存在多个。整个集群正常的工作流程可以分为两个步骤：
- client 向集群发送 commands
- leader 接收到 client 的请求，将 command 顺序持久化（追加）到自己的 log 中，并尝试将这个 entry 提交，如果成功提交，将 command 写入到自己的状态机中，然后返回 OK, 表示成功写入，否则 client 超时重试。
那 leader 怎样才算将 entry 提交了呢。举个例子，比如 client发送了 x = 3这个 command, leader 收到后将会发送给集群中剩下的节点（follower)，如果他确认大多数的节点已经将这个命令持久化到了自己的 log 上，那么他将认为这个命令已经提交了。比如，现在集群里边一共有5个节点，现在如果 5/2 + 1 == 3个节点已经收到了这个命令（包括 leader 他自己），那么这个命令就同步到了大多数的节点，提交成功。（我们暂时认为 entry 的提交是这样的，后边我们会加入一些限制）
还有一个问题，leader 如何产生。leader 通过选举产生，初始状态下，整个集群的节点都是 follower, follower 在一段时间内（election timeout）没有收到来自 leader 的心跳包就会将自己转换成 candidate, 然后发起新一轮的选举，candidate 会向集群中的节点发送拉选票的请求（包括自己投给自己的一票，而且这个选票一定通过）。如果 candidate 收到了集群中大多数approve（自己统计票数），那么他则当选成为 leader。当选之后，为了让 follower 不超时，leader 将会给集群中的节点发送心跳包，收到心跳包的 candidate 会自动会滚成 follower。当然我们这里省略了一些细节，比如选举的标准是什么，如何避免集群中有两个 leader，等等，一切旨在给出算法的一个概貌，后边会讨论更加多的细节。
总的来说，Raft 并不难理解，核心的规则就是将 entry 提交到大多数的节点，这样在新的选举中，少数派无法获得大多数的选票，从而保证拥有更新 log 的节点能够在选举中当选成为 leader。但是本贴只是简介，我们需要更多的约束条件才能保证 Raft 正确性和可用性。
在接下来的贴子中，我们将对以下的几个核心问题展开讨论：
- log 如何同步到别的节点。
- 如何选举。
- 如何确定 entry 已经被提交。