raft

1. 特点

• strong leader
  raft是强leader算法,日志只从leader分发,使理解更容易
• leader election
  raft节点随机时间选举leader,可以快速简单的处理冲突
• membership changes
  允许集群在配置更改期间继续正常运行

2. 一致性算法的典型属性

• 永远不返回错误结果
• 只要半数以上节点可用,就可以正常工作
• 它们不依赖于时间来确保日志的一致性:错误的时钟和极端的消息延迟在最坏的情况下会导致可用性问题
• 一般情况下只要超过半数节点通过,就可以成功返回

3 raft概况

同步状态机架构图

image.png

3.1 State

3.1.1 所有节点都会持久化的状态信息

(响应rpc前会先持久化)

• currentTerm
  server的最新term(初始化为0,逐个递增)
• votedFor
  在当前term中,收到的vote的candidateId
• log[]
  log entries
  每个entry包含state machine 的操作命令以及收到entry时的term信息

3.1.2 所有节点都会保存的非持久化信息

• commitIndex
  最新的log entry index 提交编号(初始化为0,单调递增)
• lastApplied
  最新的应用log entry编号(初始化为0,单调递增)

3.1.3 leaders才会保存的非持久化信息

(选举后会重新初始化)

• nextIndex[]
  要发送给各个server的log entry的编号(初始化为leader的 last log index+1)
• matchIndex[]
  每个节点leader已知已经同步的log entry 最大 index (初始化为0,单调递增)

3.2 AppendEntries RPC

(leader同步log entry,以及心跳相关操作)

3.2.1 Arguments

• term
  leader`s term
• leaderId
• prevLogIndex
  紧接在新日志项之前的日志项的索引
• prevLogTerm
  prevLogIndex 对应的term
• entries[]
  需要持久化的log entry(心跳时为空,同步时为了提升效率也可以一次同步多条 log entry)
• leaderCommit
  leader`s commitIndex

3.2.2 Results

• term
  当前的term,方便leader纪录保存
• success
  follower如果已经同步 prevLogIndex and prevLogTerm的log entry则返回true

3.2.3 Receiver implementation

• 如果term < currentTerm 返回 false
• 如果在prevLogIndex对应的log中的term不等于prevLogTerm则返回false
• 如果已经存在的entry中与新的log entry冲突(index相同,但是term不同),则删除已经存在的entry,应用新的log entry
• 如果没有新log对应的index,则直接append新增的entries
• 如果 leaderCommit > commitIndex 则设置 set commitIndex =
  min(leaderCommit, index of last new entry)

3.3 RequestVote RPC

(candidates 获取 选举信息)

3.3.1 arguments

• term
  candidate`s term
• candidateId
  发起选举的candidateId
• lastLogIndex
  candidate的最新的log erntry的 index
• lastLogTerm
  candidate的最新的log entry 的 term

3.3.2 results

• term
  当前的term,方便condidate更新各个节点的term信息
• voteGranted
  如果同意选举 condidate 则返回true

3.3.3 Receiver implementation(返回说明)

• 如果term 小于currentTerm则返回false
• 如果votedFor是null或者candidateId,并且candidate’s log同步情况不晚于receiver的log,则返回true

3.4 Rules for Servers

3.4.1 All Servers

• 如果 commitIndex > lastApplied
  增加lastApplied,并应用log[lastApplied]
• 如果 request or response 包含 term T > currentTerm
  则 set currentTerm = T, convert to follower

3.4.2 Followers

• Respond to RPCs from candidates and leaders
• 如果在election timeout时间内没有收到当前leader发送的AppendEntries RPC调用或者candidate的选举请求,则转为candidate

3.4.3 Candidates

• 关于转变为Candidate角色后发起选举
  • 增加currentTerm
  • 选举自己为leader
  • 重置election timer
  • 向所有节点发送选举请求RPC
• 如果过半节点同意选举请求,则转换为leader角色
• 如果收到新leader的AppendEntries则转为follower角色
• 如果超过 election timeout 则开启新一轮的选举

3.4.4 Leaders

• 选举为leader
  发送初始AppendEntries RPCs (heartbeat) 给所有节点,在整个空闲期都发送,防止有节点没收到heartbeat,发起选举
• 收到客户端命令时
  在本地 append entry log
  等待更新到 state machine后,才返回给客户端
• 如果 last log index ≥ nextIndex for a follower
  发送起始于nextIndex的 AppendEntries RPC with log entries
  • 如果成功,则更新对应follower的nextIndex and matchIndex
  • 如果因为log不一致导致失败,则decrement nextIndex and retry
• 如果大部分节点的matchIndex[i] ≥ N, log[N].term == currentTerm 并且 N > commitIndex 则set commitIndex = N

3.5 raft会保证整个生命周期如下的规则

• election safety
  在同一个term下,最多选举出一个leader
• leader append-only
  leader只会添加log,不会有覆盖或着删除操作
• log matching
  如果两个log具有相同的term和index,则之前的所有log都会相同
• leader completeness
  如果一个log entry在一个term下被提交,则任何leader(如果发生leader选举)在之后的term中都会包含此log entry
• state machine safety
  如果server已经应用某个index下的log entry到state machine,不会有其他的server在相同的index下应用不同的log entry

3.6 server节点角色

image.png

4 raft一致性算法详细介绍

raft算法分为三个独立的部分:

• Leader election
  如果当前的leader fails时,必须要选举出一个leader
• Log replication
  leader接受客户端的命令,并且同步到整个集群,其他节点必须与leader数据保持一致
• Safety
  raft主要确保state machine的可靠性:如果任何一个server应用一条log entry到 state machine,就确保不会在相同的index下应用其他log

以下列出论文中的条目,方便有个全局印象

• 4.1 Raft basics
• 4.2 Leader election
• 4.3 Log replication
• 4.4 Safety
  • 4.4.1 Election restriction
  • 4.4.2 Committing entries from previous terms
  • 4.4.3 Safety argument
• 4.5 Follower and candidate crashes
• 4.6 Timing and availability
  以下分别详细介绍

4.1 Raft basics

一般一个raft集群包含5个节点(可以允许两个节点异常),任何时间点下server只会是 leader,follower或者candidate中的一个角色.正常运行情况下,只会有一个leader,其他节点都为follower. follower只会被动接收leader和candidate的request而不会主动发送请求.leader处理所有客户端的请求(如果client连接flolower,会转接给leader). candidate用于选举leader时的中间状态.
raft会把时间划分到任意长度的term,term是连续递增编号的,最开始的term会先发起选举,如果有candidate赢得选举,则会成为leader,如果选举冲突,则会在下一个term重新选举.raft确保在同一个term下,最多有一个leader
term就是raft里的逻辑时钟,每个server都会保存一个当前term值,term会随着时间递增.current term信息会在集群内不断交换,如果一个server的current term比其他server小,会更新到较大的那个值,如果一个candidate或leader发现自己的term是过期的,则会降级为follower,如果server收到term老旧的request,server会拒绝响应.
raft使用rpc进行通信,基本的raft算法只需要两种rpc服务,RequestVote rpc是在选举期间由候选人发起,Append-Entries RPCs 则是由leader发起的用于replicate log entries 和 heartbeat. raft还有第三种rpc服务(InstallSnapshot RPC),用于在服务器之间传输快照

4.2 Leader election

raft通过heartbeat机制触发选举.server启动时,会作为followers角色,并且只要能够收到来自leader或candidate有效的rpc请求,server会一直保持followers角色,如果超过election timeout没有收到heartbeat, 则会认为当前没有可用的leader节点,并会发起选举.
要发起选举,follower会先增加自己的term并且转变为candidate角色,选举自己为leader,并且并发的向其他节点发起 RequestVote RPCs ,结果会有三种:
1 自己赢得选举成为leader
2 其他节点赢得选举成为leadder
3 没有节点赢得选举
下面分别探讨三种情况

1. 如果大多数server选举的candidate会成为leader,每个server在同一个term下最多给一个server投票(谁先发起RequestVote,选举谁),candidate成为leader后,发送heartbeat给各个节点,防止新的选举发生
2. candidate在等待选举结果时,如果收到leader发送的AppendEntries RPC,并且leader’s term (included in its RPC) 不低于 candidate’s current term,则认为leader是合法的,自己降级为follower,如果leader的term低于自己的current term,则会忽略,继续保持 candidate 状态
3. 如果多个candidate发起选举,并且都没有能赢得大多数的投票,则会等待选举超时后,增加term,发起新一轮的选举.

raft使用随机的 election timeouts 来避免选举冲突,一般为150–300ms范围内的随机值.相同的机制用于处理分裂投票。每个候选人在选举开始时重新启动随机化的选举超时，并在开始下一次选举前等待超时时间的流逝;这减少了在新选举中再次出现分裂投票的可能性。

4.3 Log replication

leader被选举出来后,就可以响应客户端的请求.一个client的请求包含一个replicated state machines要执行的命令.leader会将命令添加到log , 然后并发给每个节点的发起 AppendEntries RPCs,entry被safely复制后,leader应用entry到state machine中,并返回成功给client.如果followers crash或响应慢或者网络有问题,leader会不定期重新发送 Append-Entries RPCs (即使leader 已经responded client),直到followers最终存储所有的log.

log的组织形式如下图:

image.png

每个log entry包含一个state machine命令以及leader接收entry的term编号.log entries中的term可以用来探测不一致.每个log entry还有一个index编号,确认在log里的位置.

leader决定何时应用log entry到state machine,成为一个提交了的log entry. raft确保已经提交的erntry最终会被所有节点应用到可用的state machines.一旦leader将log etnry同步到大多数节点,该条log就被提交.
raft会维护如下属性:

• 如果两个log具有相同的index和term,则它们存储的命令相同

• 如果两个log具有相同的index和term,则它们前面的log都相同
  首先leader在每个term的每个log index下最多创建一个entry,并且此后不会在改变,来确保第一个属性
  其次通过AppendEntries简单的一致性检查来确保第二个属性,leader发送的AppendEntries RPC中,会包含上一条log entry的index and term ,如果follower没有找到相同index,term的log,则会refuse新的entry.一致性检查作为一个归纳步骤:日志的初始空状态满足日志匹配属性，一致性检查在扩展日志时保留日志匹配属性。因此，每当AppendEntries 成功返回时，leader就知道follower的日志与它自己通过新条目的日志是相同的。
  正确情况下,leader和followers是一致的,AppendEntries的一致性检查也不会出错.但是leader可能会导致不一致情况(old leader可能没有将所有的entry复制到所有节点).如下图所示,因为一系列的leader和follower的 crash,导致数据不一致,follower可能相比于leader多或者少数据.

  
  image.png
  

  raft算法中,通过强制follower同步leader的log来处理不一致问题,即follower与leader冲突的log会用leader的log覆盖(下一节会探讨这样做的可行性)
  为了修复不一致数据,leader必须找到最后一个两者都agree的log,删除follower此后的日志,发送leader此后的log到follower(这些都在AppendEntries RPCs中处理).leader 维护了 每个folloer的 nextIndex(要发送的下一条log的index). 一旦选举出leader后,会初始化所有follower的nextIndex为leader的最后一条log index.如果follower与leader不一致, AppendEntries check则会返回错误,leader收到错误信息会减少nextIndex并且重试AppendEntries RPC,最终nextIndex会找到leader和follower一致的点,然后在删除冲突entry并且同步leader的log后,AppendEntries返回成功,并且follower与leader达到一致状态.

4.4 Safety

本节通过添加对哪些服务器可以被选为leader的限制来完成Raft算法。这个限制确保任何给定期限的leader获得在以前期限中提交的所有条目。最后，我们给出了Leader完备性的一个证明图，并展示了它是如何导致复制状态机的正确行为的。

4.4.1 Election restriction

在任何基于领导的协商一致算法中，领导最终必须存储所有提交的日志条目。在一些协商一致的算法中，比如Viewstamped Replication[22]，可以选出一个leader，即使它最初不包含所有提交的条目。这些算法包含额外的机制来识别缺失的条目，并在选举过程中或选举后不久将其发送给新领导人。不幸的是，这导致相当多的额外机械和复杂性。Raft使用了一种更简单的方法，它保证所有来自previousterm的提交条目从每个新领导者当选的那一刻起就存在，而不需要将这些条目传递给领导者。这意味着日志条目只在一个方向上流动，即从leader到follower。
raft通过在选举中添加限制来确保只有包含所有已经提交的log的节点才能选举成功.因为要多数节点选举才能成为leader,至少在其中一个节点包含所有提交的entry,进而,如果candidate比大多数节点的log都up-to-date则可以确保该candidate包含所有已经提交的信息(如果voter比candidate的log更up-to-date则不会选举它)
raft通过比较最后一条entry的index和term来判断哪个更加up-to-date,如果两个log term不相同,则term较大的更up-to-date,如果term相同,则log越长的越up-to-date

4.4.2 Committing entries from previous terms

旧leader crash之后,新的leader会尝试在之前的基础上完成entry的复制,但是即使大部分节点同步了一个entry,也不能确定确认entry已经提交,下图给出了一种大多数节点已经同步log的情况下,依然被新leader覆盖掉的情况(term是基于时间生成的)

image.png

为了避免上面的情况,raft不会根据已经同步的replicas个数来确认是提交.只有leader当前term的提交才会根据是否有大多数节点同步,只要当前term的entry被提交,则所有之前的entry也可以通过 Log Matching Property来间接保证提交.

4.5 Safety argument

以下通过反证法,证明raft能够保证数据完整性.
假设leader(leader_T)提交 term T log,但是term T log没有在新的term的leader(leader_U U>T)中保存,则可以作出如下推测:

• 在 leader_U选举时肯定没有 log T
• leader_T 同步了log T 到大部分机器上, 而leader_U是被大部分节点选举出来,则最少有一个voter(voter_special)包含log T
• voter_special在选举leader_U前,肯定接收到了leader_T的committed entry,否则会
  rejected the AppendEntries request from leader_T
• voter_special在选举leader_U时依然会保存有log T
• voter_special选举了leader_U, 所以 leader_U的log必须不比voter_special旧,因此只会有如下两种情况
  • 1. voter_special和leader_U 最新的term相同, 则leader_U应该不少于voter_special的log,应该包含 log T
  • 2. 如果leader_U的log term 比 voter_special大,则之前leader_U在同步最新的term时会保证包含所有之前term的数据( by the Log Matching Property),即包含 log T

最后,raft要求server按照 log index顺序应用 log entry,与 State Machine Safety Property 相结合,共同确保所有节点的state machines会按照相同的顺序应用log

4.6 Follower and candidate crashes

如果一个follower或者candidate crash,那么后续的RequestVote和AppendEntries RPCs 就会失败,raft会不定期的重试,如果crash的节点重新启动,rpc会成功.如果一个server在完成rpc请求,但是在返回成功前crash,则会在重启后收到一个相同的rpc请求,因为raft的rpc请求是幂等的,所以不用做特殊处理.例如,如果follower收到的AppendEntries请求里的log与当前log包含一样的内容,节点会忽略这些entries

4.7 Timing and availability

raft集群必须要满足如下时间关系,否则无法正常选主,对外提供服务:
broadcastTime ≪ electionTimeout ≪ MTBF
其中:

• broadcastTime 为发送rpc并且收到回应的平均时间
• electionTimeout 选举超时时间
• MTBF 两个节点crash间隔的平均时间
  一般 broadcastTime 为 0.5~20ms
  electionTimeout 因此在10~500ms之间
  MTBF一般为几个月

5 Cluster membership changes

配置变更时,如果只是简单的逐个变更,则可能会有同一个term下,两个主的危险,如下图所示:

image.png

为了避免上面的问题,raft使用两阶段提交来变更配置,首先切换为变更配置状态( joint consensus),joint consensus 提交后,集群使用新的配置,joint consensus combines both the old and new configurations:

• log entry会被同步到新旧配置的所有节点
• 新旧配置中的任何一个节点都可能作为leader

• 选举或着entry的提交需要经过新旧配置所有节点的大多数通过
  joint consensus 允许允许各个服务器在不同的时间在不同的配置之间进行转换，而不会出现安全隐患。此外，允许集群在整个配置更改期间继续为客户端请求提供服务。
  Cluster configurations 的存储和同步使用特殊的一种log entry,下图描述了configuration change process

  
  image.png
  

  leader收到 Cold to Cnew的请求时,会存储configuration 信息为 joint consensus log entry,并且同步到其他节点,一旦server添加了new configuration entry 到log,未来的decision都会使用这个configuration(server总是使用最新的configuration,不管提交与否),这就意味着,leader会使用Cold,new 来判断log entry for Cold,new 是否提交,如果leader crash,新leader的配置可能为 Cold or Cold,new任何情况下Cnew 都无法作出单方面的decisions
  一旦Cold,new提交之后,无论 Cold 或着 Cnew 都无法独立的作出decision,Leader Completeness Property 也确保了只有包含 Cold,new log entry 的节点才会被选举为leader.此时创建一个Cnew的log entry并同步到其他节点是安全可靠的,其他节点同样一同步到Cnew就生效.只要Cnew被提交,Cold就无关紧要,Cnew中没用的节点就可以shutdown,如上图所示,Cnew和Cold没有重叠的时间做decision,因此可以确保安全.
  此外,新增节点没有初始化的数据,可能需要很长时间才能同步数据,无法提交新的log.未了避免这段 availability gaps,raft引入一个额外的阶段( non-voting members, leader只同步log entry到该节点,但是not considered for majorities,直到同步完成).
  第二点,旧配置的leader可能在新配置中被排除,这种情况下只要提交了Cnew,就立刻降级(变为 follower state),这就有一个阶段会是leader管理一个不把自己count到majorities 的时间段.Cnew提交后(这之后new configuration才能够operate independently,之前只有Cold的节点才能选举为leader),才会发生leader的转换.
  第三种情况,可能被删除的节点依然存活,因为不在Cnew中,不会收到heatbeat,因此会不断的发起选举,损耗性能.为了处理这种情况,节点如果确信已经有leader正常运行时会忽略 RequestVote RPCs.此外,如果一个server在minimum election timeout的时间内收到当前leader的 RequestVote RPC也会被忽略,但是这个不会影响正常的选举,因为正常的选举流程至少要等一个minimum election timeout

6 log compaction

raft的log会逐渐增长,需要做压缩清理,Snapshotting是一种最简便的方式,下图展示了snapshots的基本流程.

image.png

每个server独立的获取快照,覆盖已经提交的log,主要的工作就是state machine 将当前状态写入快照.raft快照中还会包含一部分的metadata,主要为最后一条log的index和term信息,主要是用于AppendEntries的一致性检查.此外,为了方便 membership changes, snapshot还会包含最新的configuration信息.一旦server完成了snapshot,就可以把之前的log entry和之前的snapshot都给清理掉.
虽然server会各自做snapshot,但是leader还是会偶尔发送snapshots到有延迟的节点(发生在follower延迟较高,leader把它所需要的next log entry已经清理的情况下,一般发生在新加入节点的情况).
leader会有InstallSnapshot RPC来发送snapshots给followers,如下图所示:

image.png

follower收到InstallSnapshot RPC后必须要决定怎么处理现存的log entry.一般是收到的InstallSnapshot RPC中日志比server的新,则server会将之前的log清理掉,如果是当前的log已经比Snapshot 更新,则将冲突的部分覆盖清理掉,更新的部分则保留.
还有另外两个影响快照的问题。首先，服务器必须决定何时进行快照。如果服务器快照太频繁，就会浪费磁盘带宽和能量;如果快照太不频繁，就有耗尽存储容量的风险，还会增加重新启动时重播日志所需的时间。一个简单的策略是在日志达到固定大小(以字节为单位)时捕获快照。如果将此大小设置为比快照的预期大小大得多，那么用于快照的磁盘带宽开销将很小。
第二个问题是，编写快照可能会花费大量时间，我们不希望这会延迟正常的操作。解决方案是使用即写即拷技术，这样就可以接受新的更新，而不会影响正在写入的快照。例如，使用 functional data structures构建的state machines 自然支持这一点。或者，操作系统的写时复制支持(例如，Linux上的fork)可以用来创建整个状态机的内存快照(我们的实现使用这种方法)。

7 Client interaction

如果client发送请求到raft集群后,raft已经提交,但是leader在返回response给client前crash,则client会任务没有提交成功,则会重新在新的leader上再此执行导致错误.因此client会给每个command一个唯一的编号,state machine在处理请求时也会保存每个client对应的编号,如果收到command的编号已经执行过,则会直接返回,防止再次执行.
在做读操作的时候因为没有写操作,client连接的leader时是无法确认这个leader是否已经被排除,已经选举出来新的leader,因此需要额外工作,确保数据是否为最新.

• 响应请求前,leader会提交一个blank no-op entry log 来开始一个term,确保当前leader是正常的
• raft会先检查是否大多数节点的heartbeta message正常响应,之后才会返回结果

参考

https://raft.github.io/raft.pdf