Raft一致性算法

Raft将一致性算法分解成了几个关键模块 - 领导人选举 一个新的领导人需要被选举出来,当现存的领导人宕机的时候 - 日志复制 领导人必须从客户端接收日志然后复制到集群中的其他节点,并且强制要求其他节点的日志保持和自已相同 - 安全性 在Raft中安全性的关键是状态机安全:如果有任何的服务器节点已经应用了一个确定的日志条目到他的状态机中,那么其他服务器节点不能在同一个日志索引位置应用一个不同的指令

Raft一致性算法的浓缩总结

Raft 基础

每个服务器接单都处于这三个状态之一 - 领导人 - 跟随者 - 候选人

>服务器状态。跟随者只响应来自其他服务器的请求。如果跟随者接收不到消息,那么他就会变成候选人并发起一次选举。获得集群中大多数选票的候选人将成为领导者。在一个人任期内,领导人一致都会是领导者直到自已宕机了。

>时间会被划分为一个个的任期,每个任期开始都是一次选举开始,如果一个候选人赢得选举,然后他就在接下来的任期内党领导人得职责。有时候选举会失败,那么这个任期就会没有领导人而结束。
Raft保证了在一个给定得任期内,最多只有一个领导者

领导人选举

Raft使用一种心跳机制来触发领导人选举。领导者周期的向所有跟随者发送心跳包来维持自已的权威。如果一个跟随者在一段时间内没有接收到任何消息,也就是选举超时,那么他就会认为系统中没有可用的领导者,并且发起选举已选出新的领导者。
要开始一次选举过程,跟随者先要增加自已档期内的任期号并且转换到候选人状态。然后他会并行的向集群中的其他服务器节点发送请求投票的RPCS来给自已投票。候选人会继续保持当前状态直到以下三件事之一发生 - 赢得这次选举
当一个候选人从整个集群的大多数服务器节点获得了针对同一个任期号的选票,那么他就赢得了这次选举并且成为领导人。然后他就会向其他的服务器发送心跳消息来建立自已的权威并且组织新的领导人产生 - 其他服务器成为领导者
在等待投票的时候,候选人可能会从其他的服务器接收到声明他是领导人的附加日志项RPC。如果这个领导的任期号(包含在此次的RPC中)不小于候选人当前的任期号,那么候选人会承认他是领导人合法并回到跟随者状态。如果此次RPC中的任期比自已小,那么候选人就会拒绝这次的RPC并且继续保持候选人状态。 - 一段时间内之后没有一个获胜的人
如果有多个跟随者同时成为候选人,那么选票可能会被瓜分以至于没有候选人可以赢得大多数人的支持。当这种情况发生时,每一个候选人都会超时。然后增加当前任期号来开始一轮新的选。然而没有其他的机制的话,选票可能会被无限的重复瓜分。
Raft算法使用随机选举超时时间的方法来确保很少会发生选票瓜分的情况。 为了阻止选票起初就被瓜分,选举超时时间是从一个固定的区间随检选择。这样就可以把服务器都分开以至于在大多数的情况下只有一个服务器会选举超时。

日志复制

客户端的每一个请求都包含一条被复制状态机执行的指令。领导人把这条指令作为一条新的日志条目附加到日志中去,然后并行的发起附加条目RPCs给其他的服务器,让他们复制这条日志条目。当这条日志被安全的复制,领导会应用这条日志到它的状态机中然后把执行的结果返回给客户端。如果跟随者崩溃或者运行缓慢,网络丢包,领导人会不断的重复尝试附加日志条目RPCs(尽管已经回复了客户端)直到所有的跟随者最终存储了所有的日志条目。

>图 6:日志由有序序号标记的条目组成。每个条目都包含创建时的任期号(图中框中的数字),和一个状态机需要执行的指令。一个条目当可以安全的被应用到状态机中去的时候,就认为是可以提交了。

领导者来决定什么时候把日志条目应用到状态机中是安全的;这种日志条目被称为已提交。Raft算法保证所有已提交的日志都是持久化的并且最终会被所有可用的状态机执行。在领导人将创建的日志条目复制到大多数的服务器上的时候,日志条目就会被提交。同时,领导人的日志中之前的所有日志条目也都会被提交,包括由其他领导人创建的条目。

日志匹配特性 - 如果在不同的日志中的两个条目拥有相同的索引和任期号,那么他们存储了相同的指令
领导人最多在一个任期里在指定的一个日志索引位置创建一个日志条目,同时日志条目在日志中的位置也从不不会改变。 - 并且之前的所有日志条目也相同
在发送附加日志RPC的时候,领导人会把新的日志条目紧接着之前的条目的索引位置和任期号包含在里面。如果跟随者在他的日志中找不到包含相同的索引位置和任期好的条目,那么他就会拒绝接收新的日志题目

在Raft算法中,领导人处理不一致是通过强制跟随者直接复制自已的日志解决了。

要使得跟随者的日志和自已一直的状态,领导者必须找到最后两者达成一致的地方,然后删除从那个点之后的所有日志条目,发送自已的日志给跟随者。所有的这些操作都在进行附加日志RPCs的一致性检查时完成。领导者针对每一个跟随者维护了一个nextindex,这表示下一个需要发送给跟随者的条目的索引地址。当一个领导人刚获得权力的时候,他初始化所有的nextindex值为自已最后一条日志的索引+1。如果一个跟随者的日志和领导人不一致,那么在下一次的附加日志RPC时的一致性就会失败。在被跟随者拒绝后,领导人就会减小nextindex值并且重试。最后nextindex会在某个位置使得领导人和跟随者日志达成一致。当这种情况发生,附加日志加就会成功,这时就会把跟随者冲突的日志条目全部删除并且加上领导人的日志。一旦附加日志RPC成功过那么跟随者的日志就会和领导人保持一致,并且在接下来的任期里一直继续保持

安全性

在领导选举的时候增加一些限制来完善Raft算法。这一限制保证了任何的领导者对于给定的任期号,都有了之前任期的所有被提交的日志条目(领导人完成特性)

选举限制

Raft使用投票的方式来阻止一个候选人赢得选举除非这个候选人包含了所有已经提交的日志条目。候选人为了赢得选举必须联系集群中的大部分节点,这意味着每个已经提交的日志在这些服务器即诶单中肯定存在于至少一个节点上。如果候选人的日志至少和大多数的服务器节点一样新,那么他一定持有所有已经提交的日志条目。

原文链接