Raft实现报告

Raft共识算法

共识算法第一步通过选举leader，给予他责任去管理复制日志系统，leader接受来自clients的日志条目，将他们复制到其他的server上去，然后告诉server们什么时候能安全的将日志条目作用在状态机上，在拥有leader的系统中能简化日志复制的管理。举个例子，leader可以决定放置新日志条目的位置而不同跟其他server沟通，数据流以更简单的方式在leader与server间传递。一个leader可以失败，或者与其他server断连，之后就会开始新的一轮选举。

Raft将共识问题分解成了三个相对独立的子问题，

• leader选举：一个新leader必须被选出来，当现有leader失败之后
• 日志的复制：leader必须接受来自client的日志条目，然后在集群间复制他们，强迫其他日志同意自己的（貌似在做同步）
• 安全性：在安全性中最关键的一条就是保证状态机安全，也就是在server中不会有几位用相同的index来申请不同的日志条目

选举安全：在给定的一个时期内至多一个leader被选举出来

leader仅追加：leader从来不在他的log里重写或删除条目，从来都只追加新条目

日志匹配：如果两个日志个包含了一个条目带有相同index和term，那就说明通过给定的index所指定的所有条目都是相同的。

leader完整性：如果一个日志条目在给定的时期中被确认提交了，那该条目会出现在所有高编号时期的leaders中的log里。

状态机安全：如果一个server通过给定index申请了一条日志到他的状态机中，不会有其他的server用相同的index申请不同的日志条目

Raft必须全程保证这些状态为真。

基本概念

一个Raft集群包含众多服务器，5个服务器就可组成经典raft模型，有两个服务器宕机的容错，在集群运行的时间当中，每一个服务器都会是以下三种状态之一，leader，follower，或candidate，在正常操作下，绝对只有一个leader，其余的节点为follower，follower们是被动的。他们不通过自己处理请求，但会简单的响应来自leader或者candidates的请求，leader处理所有follower的请求（如果一个客户端联系了一个follower，那么follower会将改请求重定向到leader处理），candidate用于选出新的leader。

Raft将时间划分为不定的长度，时刻会被连续的整数编号，每一个时刻由一次选举开始，在这一时刻一个或多个的candidates企图变成leader。如果candidate赢下选举，他将会变成leader服务大家，在一些情况下，选举将会造成分票，在这种情况下，该时期将会结束以没有选举出leader的原因。一个新的时间段，将会带着新的选举一起到来。

raft必须确保一个时间段下，leader最多只有一个。

不同的服务器可能会发现在时刻之间做角色的转变（你无法想象论文中的这句话有多绕，我真服了），换句话说就是，每个服务器都可能在过程中发生身份的变化，可能你在此时为leader，在下一个周期中就变成了follower。在一些特殊情况下，一个server甚至可能根本都观察不到这些状态发生改变，可能断连了。Terms由该文章引入的词汇，被看成是系统进程的逻辑时钟，像是计时器，每一个服务器都存储着当前的term数字，该数字会在过程中持续单调增加。当前的term会在server沟通的时候交换。如果一个服务器中的term小于了其他服务器，那他会更新他当前的term，变成更大的term，如果一个candidate或者leader发现自己的term过期了，他会立刻变成follower状态，如果一个服务器接收到了老的term数字，他会回绝这次请求。

raft服务器通过RPC彼此联系，为什么不是HTTP呢？因为建立连接慢吗？最基础的共识算法只需要两种RPC接口，RequestVote RPC会在candidate做选举时初始化，AppendEntriesRPC会在leader复制日志条目的时候，心跳检测的时候初始化，服务器会重新发送RPC请求如果他们没有收到相应在人为制定的时间内，且为了更加好的性能，他们会并行处理RPC请求。