raft论文学习.md
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 没有节点赢得选举
下面分别探讨三种情况
- 如果大多数server选举的candidate会成为leader,每个server在同一个term下最多给一个server投票(谁先发起RequestVote,选举谁),candidate成为leader后,发送heartbeat给各个节点,防止新的选举发生
- candidate在等待选举结果时,如果收到leader发送的AppendEntries RPC,并且leader’s term (included in its RPC) 不低于 candidate’s current term,则认为leader是合法的,自己降级为follower,如果leader的term低于自己的current term,则会忽略,继续保持 candidate 状态
- 如果多个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旧,因此只会有如下两种情况
- voter_special和leader_U 最新的term相同, 则leader_U应该不少于voter_special的log,应该包含 log T
- 如果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正常响应,之后才会返回结果
