在寻找一种易于理解的一致性算法的研究(In Search of an Understandable Consensus Algorithm-extended version) 论文中, 作者提出 raft 算法主要用来在分布式环境下管理日志的状态复制. 为了解决 paxos 算法的难于理解, raft 算法中给 server 引入了三个角色(状态), 分别为: Leader,follower,cadidate. 并将一致性算法划分成三个子问题来解决: Leader 选举, 日志复制, 安全性. 集群中任何一个 server 在某一时刻只能处于一种角色状态且只能有一个 server 处于 Leader 角色状态. 客户端所有的写请求都发送给 Leader 或由 follower 转发给 leader, 由 Leader 将写请求日志复制到所有 follower 结点来保证结点间数据的一致性. 当 Leader 结点出现故障, 或者 follower 与 Leader 之间的心跳检测中断时, 进行 Leader 的重新选择. 下面将分别从三个方面来详细讨论 raft 算法的处理流程以及在安全性上采取的应对策略.
二, leader 选举
2.1 leader 选举面临的问题
Raft 算法通过选举的方式, 选出一个高贵的领导人来协调多结点数据的一致性. 所有客户端的请求日志条目 (写请求) 都转发到 leader 服务器上, 由 leader 将日志条目复制到其他的服务器上, 从而达到数据的一致性. 这样做大大简化了数据一致性的管理. 通过这种方式需要面临若干问题:
1. 当 leader 宕机后, 如何保证集群继续对外提供服务.(leader 选举)
2. 如何能够尽快选出可用的 leader.(通过大多数者同意能够保证不受少数结点网络延迟的影响, 并行发送 RPC 选举请求进一步提高性能)
3. leader 将请求日志复制到集群中所有机器上时, 性能问题如何解决. 有些结点可能响应很慢或者挂掉.
4. follower 宕机及宕机恢复后, 日志如何同步
针对问题 1. Raft 使用心跳机制来触发领导人选举, 如果一个 follower 在一段时间里没有接收到 leader 的心跳检测消息, 此时他就会认为系统中没有可用的领导者, 并且发起选举以选出新的领导者.
针对问题 2. Raft 采取的策略是大多数者同意的策略. 即得到集群中大多数者的投票同意, 即认为选举成功. 这样做有两个好处, 首先可以保证集群中即使部分结点挂掉, 或者部分结点响应很慢, 不至于影响系统的可用性以及性能, 为了进一步提高发送投票请求的性能, 集群中 server 向其他服务器发送投票请求时通过并行 RPC 的方式来进行发送请求.
其次, 采用大多数者同意策略可以保证在发生网络分区的情况下, 不会产生多个 Leader 结点(即脑裂问题产生), 从而可能导致数据的不一致问题.
2.2 集群中 server 的三种状态
下图为 raft 中, 集群 server 的状态转换图:
初始时, 集群 server 启动, server 状态为 follower.follower 因超时时间未收到 leader 或 candidate 的消息而转变为 candidate, 开始进入 leader 选主过程.
cadidate 状态的 server 由于在当前一轮任期的选主过程中, 未能选出 leader 重新进入下一轮任期 leader 选举.
cadidate 在选举的过程中可能收到 leader 已经选出的消息或当前的自己记录的任期信息已经过期而进入 follower 状态.
cadidate 由于收到大多数者的投票而成为 leader, 成为 leader 后会定期给其他 server 发送心跳信息以维护其领导者的权威. 如果 leader 发现自己的任期号过期了, 则进入 follower 角色状态
raft 算法选举的过程中, 有个很重要的概念, 即任期号 (term) 每个 server 都有一个 term 变量, 该变量自增, 每产生一个新的 leader,term 都会自增, 用于表示, 当前 Leader 是在该任期内产生的.
当 follower 转变成 cadidate 时会自增当前的任期号, 给自己投票, 重置选举超时计时器, 然后通过并行 RPC 调用向其他 server 发送投票请求, 请求过程中
携带 4 个参数: 分别为 term(候选人任期号),cadidateId(请求选票的候选人 ID),LastLogIndex(候选人的最后日志条目的索引值),LastLogTerm(候选人最后日志条目任期号, 即该条日志请求命令是由哪个 leader 同步的). 返回值分别为: term (当前任期号, 以便于候选人去更新自己的任期号),voteGranted(候选人赢得了此张选票时为真, 否则为假)
如果 cadidate 获得大多数者的同意, 就变成 leader, 如果接收到新的 leader 的附加日志 RPC, 转变成 follower. 如果选举过程超时即一段时间后没有任何一个获胜, 再次发起新一轮选举. cadidate 获得其他 cadidate 同意的条件是 term 最大, 当 term 相同时, 比较 cadidate 之间的 LastLogIndex,LastLogIndex 大的获胜.
当集群中所有 candidate 状态的 server 选举超时, 即该 cadidate 即没有赢得选举也没有输, 会进行下一轮的选举, 这种情况可能重复一直发生, 以至于选票总是被瓜分从而没有赢得大多数 server 的支持. raft 算法采用了随机选举超时时间的方式来确保选票瓜分的情况很少发生. 选举超时时间从一个固定区间 (例如 150-300 毫秒) 随机选择, 进而使得每台服务器的超时时间尽量不相同, 最先超时的 cadidate, 会新增 term, 进行新的投票, 赢得投票, 并在其他 server 超时前发送心跳包.
三, 日志复制
3.1 状态机
一致性算法是从复制状态机的背景下提出的. 复制状态机的结构如下图所示.
集群中每台 server 都通过复制状态机来保持各 server 状态的一致性. server 中的一致性模块接收客户端的日志命令请求, 并将其按照顺序写入到日志中, 然后 server 与其他 server 一致性模块通信, 将日志中的指令按照对应的顺序复制到其他 server, 一旦复制完成, 每个服务器的状态机按照日志顺序执行指令, 并最终返回客户端结果 , 因此服务器集群看起来像一个高可靠的状态机
3.2 日志
Leader 处理客户端的请求时, 首先是将请求指令写入到 Entrys 日志中. 日志如下所示:
图中的每一个 Entry 日志项包含了状态机待执行的指令, 以及该指令当前所处的任期. 只有日志条目被应用到状态机中的时候, 才能认为该日志是已提交, 即持久化. 当 Leader 将日志条目
复制到大多数机器的时候, 该日志条目即可被提交, 并且该日志条目之前的所有未提交的日志条目也会被提交(包括其他领导人创建的条目, 这主要是从安全性的角度考虑, 加了这条规则, 会在安全章节探讨), 并且在最终会被可用的状态机执行
Raft 日志复制具有以下特性:
如果在不同的日志中的两个条目拥有相同的索引和任期号, 那么他们存储了相同的指令.
如果在不同的日志中的两个条目拥有相同的索引和任期号, 那么他们之前的所有日志条目也全部相同.
即领导人在该任期内创建的日志条目存放在指定的日志索引处, 且该日志条目的索引位置不会发生改变.
即 Leader 中的索引位置处的日志条目与 follower 中对应索引处的日志条目相同的话, 则其索引之前的日志条目同样相同. 这一点是通过 follower 的一致性检查来保证的.
Leader 在向 follower 发送日志复制请求时, 会把之前日志条目的索引与任期号一同包含在请求里. 如果 follower 未找到包含相同索引位置和任期号的条目, 那么他就会拒绝接收
新的日志条目.
在 Raft 算法中, 领导人处理日志不一致的方式是通过强制跟随者复制自己的日志来解决. 这意味着跟随者发生冲突的日志会被领导者日志所覆盖. 具体的处理方式. 跟随者会根据一致性检查比较
领导者发送上次日志与索引位置是否相等, 不相等, 则会拒绝. 领导者会修改 nextIndex(领导者针对每一个跟随者维护了一个 nextIndex), 将其值减 1. 在向 follower 发送附加日志请求. 直到日志匹配上后, 直接将 follower 冲突的日志覆盖掉.
请求处理流程
client 连接 follower 或 leader , 如果 client 连接 follower, 则 follower 将 client 的 (写) 请求转发到 leader, 读请求 follower 直接处理.
leader 接收到 client 请求, 将该请求转换成 entry, 写入到自己的日志中, 得到在日志中的 index, 然后会将该 entry 发送给所有的 follower(实际上是批量的 entries)
follower 接收到 leader 的 AppendEntries RPC 请求后, 会将 leader 传过来的批量 entires 写入到文件中(通常并没有立即刷新到磁盘), 然后向 leader 回复 OK
leader 收到过半的 follower 的 OK 回复之后, 就可以认为命令可以提交, 然后根据日志条目更新状态机, leader 更新 commitIndex, 更新状态机完成后, 回复客户端.
在下一次 leader 发给 follower 的心跳中, 会将 leader 的 commitIndex 传递给 follower,follower 发现 commitIndex 更新了则也将 commitIndex 之前的日志都进行提交并更新状态机.
四, 安全性
下面通过分析一种情行来看 Raft 是如何保证日志复制的安全性的.
在 a 这个时间点, S1 为 Leader, 进入 b 时间点后, 复制日志索引 2 位置日志到 S2, 这时如果 S1 挂了, S5 被选举为 Leader(通过 S3,S4,S5 的选票). 从客户端接收了不一样的日志条目存放在索引 2 位置, 进入到阶段 C, 这时 S5 挂掉, S1 已经恢复了, S1 重新被选举为 Leader(通过 S1,S2,S3), 并复制任期 2 阶段的日志条目到大多数结点且未提交, 这时 S1 挂了, s5 重新被选举为 leader, 进入阶段 d, 并将自己任期内的日志条目复制到集群中其他结点, 并覆盖了索引 2 处的日志. 反之, 如果在崩溃之前, S1 把自己主导的新任期里产生的日志条目复制到了大多数机器上, 就如 (e) 中那样, 那么在后面任期里面这些新的日志条目就会被提交(因为 S5 就不可能选举成功). 这样在同一时刻就同时保证了, 之前的所有老的日志条目就会被提交.
为了消除上图中描述的情况, Raft 永远不会通过计算副本数目的方式去提交一个之前任期内的日志条目. 只有领导人当前任期里的日志条目通过计算副本数目可以被提交; 一旦当前任期的日志条目以这种方式被提交, 那么由于日志匹配特性, 之前的日志条目也都会被间接的提交. 即在日志复制的过程中, 会从当前领导人当前的任期的日志条目开始复制直到最近一次提交的日志条目处. 这样能够保证旧的任期的日志不会被更新的任期的日志条目所覆盖.
参考: https://ramcloud.atlassian.net/wiki/download/attachments/6586375/raft.pdf
来源: https://www.cnblogs.com/justinli/p/raft.html