Raft 协议学习笔记
好久没有更新博客了，最近研究了Raft 协议，谈谈自己对 Raft 协议的理解。希望这篇文章能够帮助大家理解 Raft 论文。
Raft 是什么
Raft 是一种分布式系统的一致性算法。
在分布式系统中，我们需要让一组机器作为一个整体向外界提供服务。由于在实际的条件下，我们认为每台机器都是不100%可靠的，随时都可能发生宕机。每台机器之间的通信也不是可靠的，可能发生通信的阻塞、丢失、重试。所以需要某些算法来保证在大多数机器都正常的情况下向外提供可靠的服务。
在 Raft提出之前，Paxos 已经被提出，但是 Paxos 相当复杂。Raft 的目标就是提出一种易于理解的分布式一致性算法。
在了解 Raft 之前需要了解一下什么状态机:
论文指出，Raft 是一种用来管理日志复制的一致性算法。所以我们就要先了解一下。什么是日志复制状态机。我们思考一个问题。如果你要与你的小伙伴分享一个很复杂的操作及计算。一般来说你有两种做法：
第一种:你自己负责计算，经过一段时间的计算，算出结果后，直接把计算结果告诉你的小伙伴。
第二种:你把每一个操作的步骤都告诉你的伙伴，告诉他怎么做，由你的伙伴自己计算出结果。
第二种方式，就是复制状态机的工作原理。复制状态机是通过复制日志来实现的。每一台服务器保存着一份日志，日志中包含一系列的命令，状态机会按顺序执行这些命令。因为每一台计算机的状态机都是确定的，所以每个状态机的状态都是相同的，执行的命令是相同的，最后的执行结果也就是一样的了。
在实际中这种有很多类似的应用比如 mysql 的主从同步就是通过 binlog 进行同步。
在现实生活中，如何有效的组织多人进行协助，最自然的想法就是选举一个领导，交由领导极大的权威，就能极大的提升整个团队工作效率。
下面就谈谈我对 Raft 算法的理解。
基本安全保证
为了保证过程正确性，Raft需要保证以下的性质时刻为真：
选举安全原则：
同一届任期内至多只能有一个领导人。领导人只加原则：
领导人的日志只能增加，不能重写或者删除。日志匹配原则：
如果两个日志具有相同的任期和索引，则这两段日志在[0,索引]之间的日志完全相同。领导人完全原则：
如果一条日志被提交，那么后续的任意任期的领导人都会有这条日志。状态机安全原则：
如果一个服务器已经将给定索引位置的日志条目应用到状态机中，则所有其他服务器不会在该索引位置应用不同的条目。
选取领导者
所以 Raft 算法成立的最重要的前提之一就是选举。
- Raft 由多个节点组成。
- 强领导者， 整个 Raft 在同一时间，只有一个领导者，日志有领导者负责分发和同步。
- 领导选举， 领导是由民主选举产生的，集群中多数节点投票通过就能成为主。
对于在集群中的节点。在任意时间中，都有可能处于以下三种状态之一：
- 跟随者
- 候选人
- 领导人
每个领导人都有一个任期限制。每一届任期的开始阶段，都是选举。如果选举出了领导者就由该领导人负责领导集群。如果没有选举出领导，就会进入下一次选举。直到选举出领导者为止。
角色之间的转换：
领导者会周期性的向每台机器发送心跳，确保自己的领导地位。
跟随者在长时间没有收到领导人的心跳，就会发起投票成为候选人，同时任期 + 1，如果获得超过半数的支持，就升任为领导。
如果候选人，在发起投票的时候，发现集群里面有领导人的时候，就会重新成为追随者。
如果候选人，发起投票后，一定时间里面没有收到超过半数的反馈，就会再次发起投票。
如果领导者发现在集群中发现存在下一任期的领导者，就会变为追随者。
日志同步
在选举出领导人以后，就开始处理客户端的日志。
领导者在收到客户端的请求，每个请求包含一个操作的命令。领导者会将命令记录到自己的日志中，并向自己的追随者发起同步的请求，要求自己的追随者复制这个命令。
一旦这个命令被大多数的追随者保存了。领导者就认为这个状态已经处于提交（commited）的状态。同时告知客户端，命令已经被提交。如果这个时候，追随者发生了崩溃或者延时。领导者会一直尝试重试，直到追随者接受命令，并存储到自己的日志中。这个过程一直持续到所有的追随者最终存储了所有的日志条目。
作为 Raft 的节点需要保证如下性质。
- 如果在不同日志中的两个条目有着相同的索引和任期号，则它们所存储的命令是相同的。
- 如果在不同日志中的两个条目有着相同的索引和任期号，则它们之间的所有条目都是完全一样的。
有了如上性质的保证。如果在某些情况下，发生了追随者的日志与领导者不同步的情况。（包括的情况，就可能是丢失日志，或者保存了领导者没有的日志，或者两兼有），在 Raft 算法中，领导人通过强制追随者们复制它的日志来处理日志的不一致。这就意味着，在追随者上的冲突日志会被领导者的日志覆盖。
为了使得追随者的日志同自己的一致，领导人需要找到追随者同它的日志一致的地方，然后删除追随者在该位置之后的条目，然后将自己在该位置之后的条目发送给追随者。
安全分析
需要分析在各种情况下，每个角色发生宕机，数据的安全性。
选举限制
Raft 保证自己的日志，永远由领导者向追随者流动。也就是说领导者永远不会删改自己的日志，只能向上增加日志。为了达成这个限制，Raft 使用投票的方式来阻止没有包含全部日志条目的服务器赢得选举。
当一个候选人发起投票的时候，需要告诉大家，自己最新的日志。其他节点在投票的时候，要保证自己的日志不能比候选人的新，否则就拒绝投票。通过这个限制就保证了获取多数票的领导者的日志，至少比大多数人要新。
任期越大，日志越长，越容易成为领导者。
提交之前任期的日志条目
这个在论文中比较难以理解。我看到这一节的时候也是读了好几遍才理解论文的意思。实际上作者表达的意思是图 （d）是正确的，而（e）是错误的。
因为 2 号日志没有commited，但是由于一系列操作，造成了 2 号日志没有提交，但是高任期的leader 却认为 2 号日志被提交了。
与知乎网友讨论发现这个地方还是理解有误，这个图后来作者换了一个更容易理解的图：
应该是说，如果高term的leader，可以操作低任期的 log 的话，会造成 d 和 e 情况错误。且 d 造成了 2 号日志的丢失。所以加上限制以后，就不会出现这种问题了。
为了解决这个问题。Raft 限制，只有当前任期的 leader 可以决定一条日志是否 commited，而不能由高任期的 leader 通过计算某条日志（例子中的 2号日志）超过半数节点持有，就确定日志被commited。
换句话说，就是 Raft 限制每个leader 只能确定自己任期内的日志是否commited。而不能由高任期的 leader确定。
追随者和候选人崩溃
由于 Raft 是一个强领导的，少数服从多数的系统。上面花了了很多的篇幅讨论 leader 奔溃后 Raft 协议是如何保证准确性和安全性的。如果追随者或者候选人挂了，就比较简单了。
如果候选人崩溃，一段时间以后，某个节点会出发超时，重新发起选举，一切就回复正常了。
如果一个追随者崩溃，会被 leader 感知。 leader 会一直重试，直到追随者恢复，并同步所有日志。
系统的扩容
分布式系统一大优势就是能够快速扩容。
Raft 为了保证扩容的安全性，采用了两段two-phase）方法。
在Cold 和 Cnew 之间存在一个中间态， Cold,new 的状态。防止刚开始扩容的时候，新的一组机器数量大于老集群数量，就有可能在新机器中自发投票选举出一个 leader，造成集群中有两个leader形成脑裂。
- 日志条目被复制给集群中新、老配置的所有服务器。
- 新、老配置的服务器都能成为领导人。
- 需要分别在两种配置上获得大多数的支持才能达成一致（针对选举和提交）
需要解决三个问题：
- 为了不拖慢整个集群相应速度，可以不给新加入的节点投票权。知道日志追齐以后再开放投票权力
- 如果扩容以后，老的 leader 属于被踢出的节点，老 leader 不会立即下线，而是继续工作，直到 Cnew 被提交。这个时候 leader 自己只负责管理集群而自己不追加日志。
- 将要被被删除的节点，不会收到领导的心跳，就会不停的认为自己超时，会不断的成为候选人，并不断的发起投票。造成集群的 leader 不断的退位，然后再次产生 leader。造成集群的响应能力降低。为了避免这个问题，当服务器确认当前领导人存在时，服务器会忽略请求投票。每个服务器在开始一次选举之前，至少等待一个最小选举超时时间。
日志的压缩
日志的压缩比较容易理解，随着集群的使用，日志的数量越来越大，就会降低集群的性能，同时占用大量的存储空间。所以需要定期对日志进行压缩。快照是最简单的压缩方法。在快照系统中，整个系统的状态都以快照的形式写入到稳定的持久化存储中，然后到那个时间点之前的日志全部丢弃。
客户端交互
整个 Raft 协议中，客户端只与 leader 进行交互。
客户端与集群通信的时候，首先随便与集群中的任意一个节点交互，询问 leader 是谁。
是客户端对于每一条指令都赋予一个唯一的序列号。然后，状态机跟踪每条指令最新的序列号和相应的响应。如果接收到一条指令，它的序列号已经被执行了，那么就立即返回结果，而不重新执行指令。这样保证交互的命令是幂等的。如果一条命令被重复提交，并不会造成状态机的错误。
对于读取的命令来说，如领导人已经被废黜，而自己不知道。就容易造成客户端读取到脏数据。最新的数据由别的 leader 维护了。为了避免这个问题：
- 领导人必须拥有最新的数据，这一点是必然的。Raft 天然保证这个特性。
- 领导人在访问数据之前需要发送一次心跳，保证自己的领导地位。