raft算法
raft是一种维护日志一致性的共识算法.在此,为什么要维护日志的一致性呢?其所依据的结论是,对于起始状态和接受指令都相同的状态机,能够保持状态的一致,而“接受指令”则借助日志来记录.
其所包含的关键环节是:
leader election.log replication.safety.
Introduction
在此之前Paxos是主流的一致性算法,但是其实现和理解难度比较高.raft性能与之差别不大,但是实现和理解的难度比较低.
其中的关键的环节有:leader election,log replication,safety,state space reduction.
其中相比其他的共识算法,raft有几个独特的地方:
Strong leader,始终有一个全局性的leader负责分发log到其他的server.Leader election,在心跳机制上,使用随机计时器来实现的.Membership changes.当集群中的配置(Membership)要进行变化时,使用一种机制能够保证在变化期间正常运行.
Replicated state machines
replicated state machines是这种共识算法应用的基本情景,其用于解决容错问题.
在这里,状态机也会有多个副本,并且在系统运行时,属于副本的状态机也会进行计算和更新.
图中提到,日志中维护了状态机所接受过的指令,在初始状态相同的情况下,接收到相同的指令(按照顺序)就可以得到相同的输出,因此可以借助日志来恢复状态.
其实现方式主要是,对日志进行复制.如上面所说.
因而这个算法的核心目的就是维护日志副本的一致性.每一个server上都会有相应的共识组件,共识组件不仅仅执行写入日志的功能,server之间的共识组件可以进行交互,进而可以确定这些server中的log是接受的请求是相同并且顺序相同的.只要日志的一致性没有问题,即使发生故障,也可以理想地恢复.
实际使用的系统的共识算法需要如下的特性:
- 非拜占庭条件下保证一致性.
- 在多数节点存活时,保持可用性.
- 不依赖于时间,时钟错误和高延迟只会导致可用性问题.
- 在多数节点一致后就返回结果,不会受到个别慢节点的影响。
The Raft consensus algorithm
其实现共识的方式简而言之,首先选举出一个leader,这个leader具有管理日志副本的功能,并且接受来自clients的日志条目,将其复制到其他的server上.并且告诉他们服务器何时可以安全地将日志条目应用于其状态机.当一个leader宕机故障时,采用选举的方式替代之.
进一步地,可以将共识问题分解为三个子问题:
Leader election,一般用于当前leader故障的时候.Log replication,leader必须接收来自clients的日志条目,并且将其复制扩散到集群中.Safety,如果某一个状态机对于某个日志已经接收到某一条,那么其他的所有server上的状态机都得对此日志处于同步(同一条记录)的.
1.Raft basics
总的来说,其设计要求系统能够容忍两种错误,server有三种状态:leader,follower,candidate,一般是一个leader其他都是follower.
对于从者,来说只会对来自leader,condidate的请求作出响应(不处理client的请求).leader会处理所有client的请求.
followers会接受到来自leader的心跳包,则可以怀疑这个leader是否出现问题,如果一段时间没有接收到,就会变成condidate,并且发起竞选并参与竞选,票数占据集群较多的当选为新的leader.
这可以看作是整个系统的逻辑时钟.每一个term开始的时候都会开始一个选举的过程,如果出现选不出来的情况,就接着进入下一个term并判随着新一轮选举的开始.
每个server都会保存当前的term,并随时间增长,这涉及到过期状态的判断:
- 当
server之间的服务器需要交换term,如果一个服务器的term比较小,就更新成大的. - 如果一个
leader,condidate自己的term过期了,就退出成follower. - 如果一个
server接收到的是过期的,就拒绝或忽略请求.
raft中,会通过RPC进行通信,主要有两个:
RequestVote,竞选者发起.AppendEntries,被leader发起用于向其他节点发送追加日志的请求,也用于心跳包的发送.
2. Leader election
心跳机制会触发选举.
一个follower只要及时接收合法的RPC,就会一直保持follower,否则就要成为竞选者了.
leader也是会周期性地向它的follower发送心跳包的(彰显作为领袖的权威).
当要开始进行选举的时候,这个follower就会调用RequestVote,并进入condidate状态.要么当选为leader,要么没有赢家,要么没被选上.(一般情况下,赢得最多选票的condidate会当选).
如果没有赢家,这些竞选者就会递增term,并调用RequestVote,发起新一轮选举.
为了保证这种情况尽可能少发生,采用了随机选举超时机制,每一个condidate在发起选举后,都会随机化一个新的选举超时时间,一旦超时没有完成,就会增加自己的term,并发起新一轮选举.
3. Log replication
当一个节点称为server后,就开始对client的请求开始处理,对于发送请求的客户端,每一个都包含一个命令用于状态机的执行.
当接收到用户的client后,会先在本地生成一个<term,index,cmd>的日志条目并追加到自己的末尾,进而再进行广播.注意这个广播最好是并行的.
当follower接收到该条目之后,就写入自己的日志中,并返回同意.如果leader收到了多数成功的答复,就将此条目执行到自己的状态机中.进而可以这个条目是commited的,然后再被广播到其他节点,进而其他节点在进行commited.
所以,可以说,对于一个命令,leader先自己写日志,然后在广播给follower写,如果没有异常的话,leader在自己commited,然后通知followers进行committed.
此外,需要保证性质:
在两个日志中,如果有两个条目拥有相同的index和term,其cmd也相同,他们前面的条目也相同.由于这些条目是在leader中产生的,所以能够保证cmd的相同,而对于后半句的条件则需要一致性检查来进行.其步骤如下:
leader再通过AppendEntriesRPC和follower通信时,会带上条目的信息,而folloer在接收到会对比自己的日志,如果发现和自己的不符合,就会拒绝.这是leader接收到拒绝的消息后就会和该follower进行细致地比对,找到最大的共识点,利用leader的条目重写folloer的日志.
当在进行比对的时候,leader会从后向前逐个尝试,如果仍然是拒绝,就在向前的条目尝试.直到找到共识点.
因此,每个leader都会为followers维护一个索引表,在当选为leader时,其索引默认为leader自己日志的index+1,每接收到一个节点的拒绝信号,就将对应的nextindex-1.
4.Safety
1)Election restriction
对于leader来说,需要保证其包含最全面最新的日志记录.但是该如何实现呢?
在raft中,不会像其他的共识算法需要将自己缺少的记录从别的节点上传输过来.因为他直接预防存在缺少记录的节点称为leader.
因为被选举出来的leader会和节点中的大部分进行交互,是得到了它们的认可的,这么大比重中,很容易就包含最新最全的节点.
所以在竞选者所使用的RequestVote中,会附带自己的log记录,这样可以是参与选举的节点,和自己的日志进行比对,比对是否比自己的版本更新.对于比对的细节,主要是比对index和term.
2)Committing entries from previous terms
之前说过,在确定大多数follower已经存储好某个条目时,就会将该条目commited,但如果还没有提交就出现故障了呢?
这个时候自然会需要新的leader来代替它,并继续尝试复制这个条目.但是他不能确定这个时候其前任有没有将被认为已经在多数节点存储的条目完成提交.
3)Safety argument
### 5.Follower and candidate crashes
相对于leader的崩溃而言,其处理方式比较简单.
这类崩溃最主要的特点就是后续发送的RPC都会失败,其处理方式就是对RPC进行不断地重试,如果这个时候一个节点崩溃,他所接受的RPC就会没有响应,直到其重启,才可以完成地完成一个RPC.
6.Timing and availability
Cluster membership changes
这一部分主要针对于当我们需要对系统配置作出改变时的处理机制.
需要避免的问题在于,在转换的过程中不能存在任何时间点使得两个leader被选举在同一个任期.我们不可能一次性地直接完成节点的迁移.这毕竟会有一个迁移的过程,因此整个集群存在划分成两个群体的可能.也就是新旧两种集体.
所以采用两阶段的方法,首先在第一阶段停掉旧的配置所以集群就不能处理客户端请求.然后启用新的配置.在raft中,集群先切换到一个过渡的配置,称为共同一致,一旦被提交了就切换到新的配置上.
Log compaction
日志不能无限制地增长,因为当长度过长时,就会占用更多的内存,传播时间也会更长.
快照是一种日志压缩技术.在快照中需要将当前的系统状态写入一个snapshotting中,写入之后,在这个snapshotting之内的日志项会被丢弃.
这张图中展示了有关于快照技术的基本概念,当一个server中的log数目超过一定的数量,就会生成一个新的snapshot将这些条目进行替代.其中在raft中包含了last included index就和last included term是该snapshot所对应的日志中的最后一项的索引和任期.这便于在后来该节点收到addentry的RPC请求时进行比对.
server不仅仅是独立地在本地生成快照并对log进行替换,leader也需要向比较落后的follower发送快照.其中InstallSnapshot是最主要的RPC,这个RPC用于由leader向follower发送快照.对于接受的follower来说需要做什么操作呢?
如果其中包含新的条目,就丢弃整个日志,并被快照所取代.如果是之前所含有的条目(由于乱序或者延迟导致),则只是用快照替换所包含的部分,快照之后的部分将会被保留且仍然有效.
关于快照技术主要考虑的是两种性能问题:
- 生成快照的时机,如果太频繁,将会浪费磁盘空间和带宽,不够频繁的话,就容易导致日志过大进而超出容量,延长处理时间.在此,当日志超过一定的字节数就会生成快照.
- 写快照会造成显著的开销,更不希望会因此对其他操作造成阻塞.所以在实现上采用了写时复制的技术.
Client interaction
这一部分主要讨论的是,client如何找到leader,毕竟只有leader才可以和client进行直接的交互.另一部分讨论的是,Raft如何支持线性语义的.
线性语义是什么?
每个操作似乎在请求和响应之间的某个时间点就完成了.
当一个client启动时,随机连接一个server,如果不是leader将会在RPC的回复中给予一个否定,还会附加一个最近的leader的信息.当leader挂掉时,此时client与它的请求就会超时,这是就会尝试从其他server中寻找新的leader.
关于线性语义的实现上,在Raft运行的过程中,一个command可能会执行多次.比如说一个leader在提交完一个日志记录后宕机,但是还没有为client作出响应,这个时候client就会向其他节点重试.解决方案是为每个command附加一个序列号,response会与之对应,如果接收到一个其序列号之前已经执行过的command,就会不经过重试直接进行响应.
对于只读操作容易出现的问题是:读不到最新的数据.