Raft
Raft 是一种共识算法，其设计目的是易于理解。它在容错性和性能上与Paxos相当。不同之处在于它被分解为相对独立的子问题，并且它干净地解决了实际系统所需的所有主要部分。我们希望 Raft 能够为更广泛的受众提供共识，并且这些更广泛的受众将能够开发出比目前可用的各种更高质量的基于共识的系统。
Raft算法浓缩总结¶
Raft 一致性算法的浓缩总结图示
Raft算法特性¶
- 选举安全特性：对于一个给定的任期号，最多只会有一个领导人被选举出来。
- 领导人只附加原则：领导人绝对不会删除或者覆盖自己的日志，只会增加。
- 日志匹配原则：如果两个日志在某一相同索引位置日志条目的任期号相同，那么我们就认为这两个日志从头到该索引位置之间的内容完全一致。
- 领导人完全特性：如果某个日志条目在某个任期号中已经被提交，那么这个条目必然出现在更大任期号的所有领导人中。
- 状态机安全特性：如果某一服务器已将给定索引位置的日志条目应用至其状态机中，则其他任何服务器在该索引位置不会应用不同的日志条目。
Raft算法基础¶
一个 Raft 集群包含若干个服务器节点，在任何时刻，每一个服务器节点都处于这三个状态之一：领导人、跟随者或者候选人。在通常情况下，系统中只有一个领导人并且其他的节点全部都是跟随者。 * 领导人：处理所有的客户端请求（如果一个客户端和跟随者联系，那么跟随者会把请求重定向给领导人） * 跟随者：都是被动的：他们不会发送任何请求，只是简单的响应来自领导人或者候选人的请求。 * 候选人：当跟随者没有接收到领导人的heartbeat或者其他候选人的requestvote的时间超过设定的选举超时时间（一般为150-300ms）时给自己投票从而成为 时间被划分成一个个任期，每个任期始于一次选举。在选举成功后，领导人会管理整个集群直到任期结束。有时候选举会失败，那么这个任期就会没有领导人而结束。任期之间的切换可以在不同的时间不同的服务器上观察到。
如果一个候选人或者领导人发现自己的任期号过期了，那么他会立即恢复成跟随者状态。如果一个节点接收到一个包含过期的任期号的请求，那么他会直接拒绝这个请求。 Raft 算法中服务器节点之间通信使用远程过程调用（RPCs），并且基本的一致性算法只需要两种类型的RPCs。请求投票（RequestVote） RPCs 由候选人在选举期间发起，然后附加条目（AppendEntries）RPCs 由领导人发起，用来复制日志和提供一种心跳机制。为了在服务器之间传输快照增加了第三种 RPC。当服务器没有及时的收到 RPC 的响应时，会进行重试， 并且他们能够并行的发起 RPCs 来获得最佳的性能。
领导人选举¶
如果一个跟随者在一段时间里没有接收到任何消息，也就是选举超时，那么他就会认为系统中没有可用的领导人,并且发起选举以选出新的领导人。 跟随者->候选人做以下三件事: * term++ * 向自己投票 * 向其他服务器requestvote 处于候选人状态直到出现下述三种情况: * 赢得选举 * 其他服务器成为了领导人 * 一段时间没有人获胜
日志复制¶
Raft 维护着以下的特性，这些特性共同组成了日志匹配原则： * 如果在不同的日志中的两个条目拥有相同的索引和任期号，那么他们存储了相同的指令。 * 如果在不同的日志中的两个条目拥有相同的索引和任期号，那么他们之前的所有日志条目也全部相同。 当领导者和跟随者发生冲突时,满足领导人只附加原则,领导人是通过强制跟随者直接复制自己的日志来处理不一致问题的。这意味着在跟随者中的冲突的日志条目会被领导人的日志覆盖。通过领导人针对每一个跟随者维护了一个 nextIndex来维持.
安全性¶
选举限制¶
存在问题:一个跟随者可能会进入不可用状态同时领导人已经提交了若干的日志条目，然后这个跟随者可能会被选举为领导人并且覆盖这些日志条目. 解决:请求投票（RequestVote） RPC 实现了这样的限制：RPC 中包含了候选人的日志信息，然后投票人会拒绝掉那些日志没有自己新的投票请求。 通过比较两份日志中最后一条日志条目的索引值和任期号定义谁的日志比较新。
附录¶
Paxos算法问题¶
难以理解¶
第一个缺点是 Paxos 算法特别的难以理解。完整的解释是出了名的不透明。Paxos 首先定义了一个能够达成单一决策一致的协议，比如单条的复制日志项。我们把这一子集叫做单决策 Paxos。然后通过组合多个 Paxos 协议的实例来促进一系列决策的达成。单决策 Paxos 是晦涩微妙的，它被划分成了两种没有简单直观解释和无法独立理解的情景。因此，这导致了很难建立起直观的感受为什么单决策 Paxos 算法能够工作。构成多决策 Paxos 增加了很多错综复杂的规则。
未提供一个构建现实系统的基础¶
Paxos 使用了一种对等的点对点的方式作为它的核心（尽管它最终提议了一种弱领导人的方法来优化性能）。在只有一个决策会被制定的简化世界中是很有意义的，但是很少有现实的系统使用这种方式。如果有一系列的决策需要被制定，首先选择一个领导人，然后让他去协调所有的决议，会更加简单快速。
其他概念¶
拜占庭错误（Byzantine Faults）是分布式系统理论中的一个概念，它指的是在分布式系统中，由于节点（计算机或设备）的故障或恶意行为导致的不可预测的错误。这些错误与简单的硬件故障或网络问题不同，因为它们可能涉及到节点故意发送错误信息或执行错误操作，从而对系统的一致性和可靠性造成严重威胁。