Raft协议
分布式存储系统通常通过维护多个副本来进行容错，提高系统的可用性。要实现此目标，就必须要解决分布式存储系统的最核心问题：维护多个副本的一致性。而Raft正是为探索一种简单易理解的一致性算法而产生的，Raft是管理日志复制的一致性算法。
Raft 协议所要达成的结果与multi-paxos相同，但是Raft协议的结构与Paxos不同，Raft协议更简单，更容易让人理解。
Raft 将一致性算法分解成四个关键模块
- Leader选举
- 日志复制
- 安全性
- 成员变更
状态机复制 Replicated state machines
一致性算法主要出现在状态机复制中。一组机器之间进行数据同步，当一些机器宕机后，还能继续工作。状态机复制就是用来解决在分布式系统产生的一系列容错问题。状态机制复制使用一个日志复制来实现，每个server都有一个log模块包含一系列的命令，这一系列的命令都有相同的顺序，并被各个server有序执行。
保证日志复制的一致性是一致性算法的职责。Server中的一致性模块接受从客户端传来的命令，将这些命令加入到log中。和其他server中的一致性模块沟通保证每一条log都包含相同的请求，并以相同的顺序执行，即使一些server宕机。
一旦命令被正确复制，每个服务器的状态机按日志顺序处理，并将输出返回给客户端。最终，这些servers形成一个单一的，高度可靠的状态机。
实际系统中一致性算法具有以下特性:
- 保证安全性，在所有拜占庭问题，包括网络延迟，分区和数据包丢失，数据包重复和重新排序问题。
- 只要大多数server可以运行，可以相互通信。因此，一个典型的五台server的集群，可以容忍2台server宕机。server失败恢复也可以重新加入集群。
- 不依赖时间保证日志的一致性：错误的时钟和极端的消息延迟，在最坏的情况下，可能会导致可用性问题。
- 绝大多数服务器处理完命令，即可响应请求返回；少数服务器慢不影响整体系统性能。
Paxos 有什么问题？
paxos主要说的单个决策达成一致的协议，比如一条需要复制的数据。多个实例之间组成的一系列决策称之为multi-Paxos。paxos保证了安全性和可用性，也支持集群关系的变更。
不幸的是，Paxos有两个重要的缺点。第一个缺点是Paxos难以理解。
第二个缺点是paxos没有为构建实际实现提供良好的基础。这其中一个原因是多实例paxos算法并没有广泛认可。Lamport的理论大部分都是说的单个决策Paxos协议，对于多实例paxos只是大致勾勒，很多细节是缺失的。
Paxos的架构难以构建实用的系统。
Paxos 的实现采用弱领导化的设计，但是在实际系统中，会选择一个领导者，然后让领导者协调决策更简单、更快捷。因此，实际系统与 Paxos 几乎没有相似之处。每个实现都从 Paxos 开始，发现实现它的困难，然后开发出截然不同的架构。这是耗时且容易出错的，而且理解 Paxos 的困难加剧了这个问题。 Paxos 的公式对于证明其正确性的定理可能是一个很好的公式，但实际的实现与 Paxos 是如此不同，以至于证明几乎没有价值。
由于这些问题，我们得出结论，Paxos 没有为系统构建或教育提供良好的基础。考虑到共识在大规模软件系统中的重要性，我们决定看看我们是否可以设计出一种性能比 Paxos 更好的替代共识算法。 所以提出了 Raft 协议。
做一个可以理解的设计
在设计Raft协议中，要求以下几点目标:
- 可以构建完整和实用的系统，减少开发者的设计量。
- 在所有条件下是安全的，在典型的操作条件下是可用的。
- 高效的
- 最重要的是可理解性。
采用两种方式做好可理解性。第一种方法是问题分解，将问题拆解为:
leader 选举
日志复制
安全性
成员变更
第二种方式是简化状态变化，减少需要考虑的状态，使系统更加连贯，消除不确定性。
Raft一致性算法
Raft 是一种用于管理复制日志的算法。Raft 先选举一个leader达成共识，然后让leader完全负责管理复制的日志。领导者接受来自客户端的日志条目，将它们复制到其他服务器上，并告诉服务器何时可以安全地将日志条目应用于其状态机。拥有领导者可以简化复制日志的管理。例如，领导者可以在不咨询其他服务器的情况下决定在日志中放置新条目的位置，并且数据以简单的方式从leader流向其他follower。leader可能会失败或与其他服务器断开连接，在这种情况下会选出新的leader。
采用leader 方法，Raft将一致性问题拆解为三个子问题。
- Leader election: 当已有leader宕机，必须选择一个新的leader。
- Log replication: leader 接受客户端提交的日志，并将其复制到集群中其他节点。
- Safety: 如果大多数服务器已将特定的日志条目应用到其状态机，则没有其他服务器可以对相同的日志索引应用不同的命令。
Raft基础概念
一个Raft集群包含多个节点，一般为5个节点，此时可以允许有两个节点宕机。任何时候每个节点都会处于leader，follower，candidate三种角色中的其中一个。一般情况下，是有一个leader节点，其他节点都是follower节点。followers是被动的，他们不会主动请求更多的是响应leader的请求，leader节点负责处理所有客户端的请求（如果一个客户端将请求打到follower节点，follower节点会转发给leader节点）。第三种状态候选人节点，用于选举一个新的leader节点。
Raft 把时间切割为任意长度的任期，每一个任期都有一个任期号，才用连续的整数。每个任期都由一次选举开始，若选举失败则这个任期内没有leader，如果选举了Leader则这个任期内有Leader负责状态管理。