Raft 是一种为了管理日志复制的一致性算法. 它提供了和 Paxos 算法相同的功能和性能, 但是它的算法结构和 Paxos 不同, 使得 Raft 算法更加容易理解并且更容易构建实际的系统. 为了提升可理解性, Raft 将一致性算法分解成几个关键的模块, 例如领导选举, 日志复制和安全性. 同时它通过实施一个更强的一致性来减少需要考虑的状态和数量. 从一个用户研究的结果可以证明, 对于学生而言, Raft 算法比 Paxos 算法更容易学. Raft 算法还包括了新的机制来允许集群成员的动态改变, 让利用重叠的大多数来保证安全性.
Raft 算法概述
Raft 算法是从多副本状态机的角度提出, 用于管理多副本状态机的日志复制, 它一致性分解为多个子问题: 领导选举 (Leader election), 日志复制(Log replication), 安全性(Safety), 日志压缩(Log compaction), 成员变更(Menbership change) 等. 同时, Raft 算法使用了更强的假设来减少需要考虑的状态, 使之变得更加容易理解.
Raft 讲系统中的角色分为领导者 (Leader), 跟从者(Follower) 和候选人(Candidate):
Leader: 接收客户端请求, 并向 Follower 同步请求日志. 当日志同步到大都数节点上后告告诉 Follower 提交日志.
Follower: 接收并持久化 Leader 同步的日志, 在 Leader 告诉它的日志提交之后, 提交日志.
Candidate:Leader 选举过程中的临时角色.
Raft 要求系统在任意时刻最多只有一个 Leader, 正常工作期间 Leader 和 Followers.
Raft 算法角色状态转换如下:
跟随者只响应来自其他服务器的请求. 如果跟随者接收不到消息, 那么它就会变成候选人并发起一次选举. 获得集群中大多数选票的候选人将成为领导者. 在一个任期内, 领导人直到自己宕机了.
Raft 算法时间被划分成为一个个的任期 (Term), 每个任期(Term) 开始都是一次 Leader 选举. 选举成功后, 领导人会管理整个集群直到任期 (Term) 结束. 有时候会选举失败, 那么任期 (Term) 就会没有领导者, 而结束. 任期 (Term) 之间的切换可以在不同的时间不同的服务器上观察到.
Raft 算法中服务器之间节点通信使用远程调用 (RPCs). 而在 etcd 的实现当中 v2 版本用的 http, 而 v3 版本采用的是 grpc(本身是跨平台). 并且基本的一致性算法只是用了两种类型的 Rpcs. 请求投票(RequestVote)RPCs 由候选人发起. 然后附加条目数(AppendEntries) 由 Leader 发起. 用来复制日志和提供一种心跳机制. 为了服务器之间传输快照增加了第三种 RPCs. 当服务器没有及时收到 RPC 的响应时, 会进行重试, 并且它们能够并行发起 RPCs 来获取最佳性能.
复制状态机
一组服务器上的状态机产生相同状态的副本, 并且在一些机器宕掉的情况下也可以继续运行. 复制状态机在分布式系统中被用于解决很多容错的问题. 例如, 大规模的系统中通常都有一个集群领导者, 像 GFS,HDFS 和 RAMCloud, 典型应用就是一个独立的的复制状态机去管理领导选举和存储配置信息并且在领导人宕机的情况下也要存活下来. 比如 Chubby 和 ZooKeeper.
复制状态机的结构. 一致性算法管理着来自客户端指令的复制日志. 状态机从日志中处理相同顺序的相同指令, 所以产生的结果也是相同的.
复制状态机通常都是基于复制日志实现的, 如图 1. 每一个服务器存储一个包含一系列指令的日志, 并且按照日志的顺序进行执行. 每一个日志都按照相同的顺序包含相同的指令, 所以每一个服务器都执行相同的指令序列. 因为每个状态机都是确定的, 每一次执行操作都产生相同的状态和同样的序列.
保证复制日志相同就是一致性算法的工作了. 在一台服务器上, 一致性模块接收客户端发送来的指令然后增加到自己的日志中去. 它和其他服务器上的一致性模块进行通信来保证每一个服务器上的日志最终都以相同的顺序包含相同的请求, 尽管有些服务器会宕机. 一旦指令被正确的复制, 每一个服务器的状态机按照日志顺序处理他们, 然后输出结果被返回给客户端. 因此, 服务器集群看起来形成一个高可靠的状态机.
实际系统中使用的一致性算法通常含有以下特性:
安全性保证(绝对不会返回一个错误的结果): 在非拜占庭错误情况下, 包括网络延迟, 分区, 丢包, 冗余和乱序等错误都可以保证正确.
可用性: 集群中只要有大多数的机器可运行并且能够相互通信, 和客户端通信, 就可以保证可用. 因此, 一个典型的包含 5 个节点的集群可以容忍两个节点的失败. 服务器被停止就认为是失败. 他们当有稳定的存储的时候可以从状态中恢复回来并重新加入集群.
不依赖时序来保证一致性: 物理时钟错误或者极端的消息延迟在可能只有在最坏情况下才会导致可用性问题.
通常情况下, 一条指令可以尽可能快的在集群中大多数节点响应一轮远程过程调用时完成. 小部分比较慢的节点不会影响系统整体的性能.
Leader 选举
Raft 使用心跳 (heartbeat) 触发 Leader 选举. 当服务器启动时, 初始化 Follower.Leader 向所有的 Followers 周期性的发送 heartbeat. 如果 Follower 在选举超时时间内没有收到 Leader 的 heartbeat, 就会等待一段随机时间 (150ms-300ms) 发起一次选举.
Follower 先要增加自己的当前任期号, 也就把当前的任期号加一并且转换到候选人状态. 然后它们会并行的向集群中的其他服务器节点发起请求投票的 RPCs 来给自己投票. 结果会有以下三种情况:
它自己赢得了这次选举
其他的服务器成为了领导者
一段世家之后没有人获取胜利的人.
日志复制
Leader 被选举出来后. 它就开始为客户端提供服务, 客户端每个请求都包含一条被复制状态机执行的命令. 领导人将这条指令作为新的日志条目附加到日志中去. 然后并行的发起附加条目 RPCs 给其他的服务器, 让它们复制这个日志条目, 当这条日志条目被安全的复制. 领导人会应用这条日志条目到它的状态中然后把执行的结果返回客户端. 如果 Follower 崩溃或者运行缓慢, 再或者网络丢包, 领导人会不断的尝试附加日志条目 RPCs(尽管已经回复了客户端)直到所有 Follower 都最终存储了所有条目数.
日志由有序编号 (log index) 的日志组成条目. 每个日志条目包含它被创建的任期号 (term), 和用于状态机执行的命令. 如果一个日志条目被复制到大多数服务器上, 就被认为可以提交了(commit) 了.
Raft 维护着一下特征:
1. 如果在不同的日志中的两个条目拥有相同的索引和任期号, 那么它们存储了相同的指令.
2. 如果在不同的日志中的两个条目拥有相同的索引和任期号, 那么他们的之前的所有日志条目也全部相同.
第一个特新来这样的一个事实, 领导人最多在一个任期里在指定的日志索引位置创建一条日志条目, 同时日志条目在日志中的位置也从来不会改变. 第二个特性由附加日志 RPC 的一个简单一致性检查保证. 在发送附加日志 RPC 的时候, 领导人会把新的日志条目紧接着之前的条目索引位置和任期号包含在里面. 如果跟随者在它的日志中找不到包含相同的日志索引位置和任期号的条目, 那么他就会拒绝接收新的条目日志. 一致性检查就像一个归纳步骤: 一开始空日志状态肯定是满足日志匹配特性的, 然后一致性检查保护了日志匹配特性当日志扩展的时候. 因此, 每当附加日志 RPC 返回成功时, 领导人就知道跟随着的日志时一样的了.
当一个领导人成功当选时, 跟随者可能是任何情况(a-f). 每一个盒子表示是一个日志条目, 里面的数字表示任期号. 跟随者可能缺少一些体制条目(a-b), 可能会有一些未被提交的日志条目(c-d), 或者两种情况都存在的(e-f). 例如, 场景 f 可能会发生, 某些服务器在任期号 2 的时候是领导人, 已附加了一些日志条目到自己的日志中, 但在提交之前就就崩溃了, 很快这个机器就被重启了, 在任期 3 重新被选为领导人, 并且又增加了一些日志条目到自己的日志中, 并且又增加了一些日志条目到自己的日志中, 在任期 2 和任期 3 的日志被提交之前, 这个服务器又宕机了, 并且在接下来的几个任期里一直处于宕机状态.
要使得跟随着的日志进入和自己一致的状态, 领导人必须找到最后两者达成一致的地方, 然后删除那个点之后的所有日志条目, 发送自己的日志给跟随者. 所有的这些日志操作都在进行附加日志 RPCs 的一致性检查时完成. 领导人针对没一个维护者维护了一个 nextIndex, 这表示下一个发送给追随者的日志条目的索引地址. 当一个领导人刚获得领导者的权利的时候, 他初始化所有的 nextIndex 值作为自己的最后一条日志的 index 加 1. 如果一个跟随者的日志和领导人不一致, 那么下一次日志附 RPC 时的一致性检查就会失败. 在被跟随者拒绝之后, 领导人就会减少 nextIndex 值并进行重试. 最终 nextIndex 会在某个位置使得领导人和跟随者的日志达成一致. 当这种情况发生, 附加日志 RPC 就会成功, 这时就会把跟随者冲突的日志条目全部删除并且加上领导人的日志. 一旦附加日志 RPC 成功, 那么跟随者的日志就会和领导人保持一直, 并且在接下来的任期里一直继续保持.
安全性
Raft 增加了如下两条限制以保证安全性:
1 > 拥有最新的已提交的 log entry 的 Follower 才有资格成为 Leader.
这个保证是在 RequestVote RPC 中做的, Candidate 在发送 RequestVote RPC 时. 要带上自己的最后一条日志的 term 和 log Index. 其他节点收到消息时, 如果发现自己的日志请求中携带的更新, 则拒绝投票. 日志比较的原则是: 如果本地的最后一条 log entry 的 term 更大, 则 term 大更新, 如果 term 一样大, 则 log Index 更大的更新.
2.Leader 只能推进 commit Index 来提交当前 term 已经复制最到最大服务器上的日志, 旧 term 日志的日志要等到提交当前的 term 的日志来间接提交(log Index 小于 commit Index 的日志被间接提交)
之所以要这样, 是因为可能会出现已提交的日志被覆盖的情况:
如图的时间序列展示了领导人无法决定对老任期号的日志条目进行提交. 在 (a) 中, S1 是 Leader, 部分的是复制了索引的位置 2 的条目数目.(b)是时期, S1 崩溃了, 然后 S5 在任期 3 里通过 S3,S4 和自己的选票赢得选举, 然后从客户端接收了一条不一样的日志条目放在了索引 2 处. 然后到 (c),S5 崩溃了, S1 重新启动, 选举成功, 开始日志复制. 在这个时候, 来自任期 2 的那条日志已经被复制到了集群的大多数机器上, 但是还没有被提交, 如果 S1 在(d) 时期中又崩溃了. S5 可以重新被选举成功 (通过来自 S2,S3,S4 的选票), 然后覆盖了他门在索引 2 处的日志. 反之, 如果在崩溃之前, S1 把自己主导的任期里产生的日志日条目复制到了大多数机器上, 就如(e) 中那样. 那么在后面任期里面这些新的日志条目会被提交(因为 S5 就不可能选举成功). 这牙膏在同一时刻就同时保证了, 之前的所有老的日志条目就会被提交.
时间和可用性
Raft 的要求之一就是安全性不能依赖时间: 整个系统不能因为某些事件运行的比预期快一点或者慢一点产生了错误的结果. 但是, 可用性 (系统可以及时的响应客户端) 不可避免的要依赖时间. 例如, 如果消息交换比服务器故障间隔时间长, 候选人没有足够长的时间来赢得选举, 没有一个稳定的领导人, Raft 将无法工作.
领导人选举时 Raft 中对时间要求最为关键的方面. Raft 可以选举并维持一个稳定的领导人, 只需要满足下面的时间要求:
广播时间(broadcastTime) <<选举时间(election Timeout) << 平均故障时间(MTBF)
在这个不等式中, 广播时间指的时从一个服务器并行的发送 RPCs 给集群中的其他服务器并接收平均时间, 选举超时时间 (150ms-300ms) 选举超时时间限制, 然后平均故障时间就是对于一台服务器而言, 两次故障之间的平均时间. 广播时间必须比选举超时时间小一个量级, 这样领导人才能发送稳定的心跳消息来阻止跟随者开始进入选举状态, 通过随机化选举超时时间的方法, 整个不等式也使得选票瓜分的情况变成不肯能. 选举选举超时时间要比平局故障时间间隔小上几个数量级, 这样系统才能稳定的运行. 当领导人崩溃后, 整个系统会大约相当于超时时的时间里不可用. 我们希望这种情况在系统中国运行很少出现.
广播时间和平均故障间隔时间是由系统决定的, 但是选举超时时间是我们自己选择的. Raft 的 RPCs 需要接收方将信息持久化的保存到稳定存储中去, 所以广播时间大约是 0.5 毫秒到 20 毫秒, 取决于存储的技术. 因此, 选举超时时间可能需要在 10 毫秒到 500 毫秒之间. 大多数的服务器的平均故障间隔时间都在几个月甚至更长, 很容易满足时间的需求.
成员变更
成员变更是在集群运行过程中副本发生变化, 如增加 / 减少副本数, 节点替换等.
成员变更也是一个分布式一致性的问题, 既所有服务器对成员新成员达成一致. 但是成员变更又有其特殊性, 因为成员变更的一致性达成的过程中, 参与投票的过程会发生变化.
如果将成员变更当成一般的一致性问题, 直接向 Leader 发送成员变更请求, Leader 复制成员变更日志, 达成多数之后提交, 各个服务器提交成员变更日志后从日志成员 (Cold) 切换到最新成员配置(Cnew 的时刻不同.
成员变更不能影响服务的可用性, 但是成员变更过程的某一时刻, 可能出现 Cold 和 Cnew 中同时存在两个不相交的多数派, 进而可能选出两个 Leader, 形成不同的决议, 破坏安全性.
由于成员变更的这一特殊性, 成员变更不能当成一般的一致性问题去解决.
为了解决这一问题. Raft 提出了两段的成员变更方法. 集群先成旧成员配置 Cold 切换到一个过度的配置, 称为共同一致(joint consensus), 共同一致时旧成员配置 Cold 和新成员配置 Cnew 的组合 Cold U Cnew, 一旦共同一致 Cold U Cnew 被提交, 系统在切换到新成员配置 Cnew.
一个配置切换的时间线. 虚线表示已经被创建但是还没有被提交的条目, 实线表示最后被提交的日志条目. 领导人首先创建了 C-old
,new 的配置条目在自己的日志中, 并提交到 C-old,new 中(C-old 的大多数和 c-new 的大多数). 然后他创建 C-new 条目并且提交到 C-new 的大多数. 这样就不存在 C-new 和 C-old 同时做出决定的时间点.
在关于重新配置还有三个问题需要提出, 第一个问题是, 新的服务器额能初始化没有存储任何的日志条目. 当这些服务器以这种状态加入到集群中, 那么它们需要一段时间来更新追赶. 这时还不能提交新的日志条目. 为了避免这种可用性的间隔时间 Raft 在配置更新的时候用了一种额外的阶段, 在这种阶段, 新的服务器以没有投票权的身份加入集群中来(领导人复制日志给它们. 但是不考虑它们是大多数). 一旦新的服务器追赶上了集群中的集群, 重新配置可以向上面描述一样处理.
第二个问题, 集群的领导人可能不是新配置的一员. 在这种情况下, 领导人就会在提交了 C-new 日志后退位(回到追随者状态). 这意味着有这样一段时间, 领导人管理着集群, 但是不包括他自己, 他复制日志但是不把他自己算作大多数之一. 当 C-new 被提交时, 会发生领导人过度. 因为这时时最新的配置可以独立工作时间点(将总是能够在 C-new 配置下选出新的 Leader). 再此之前, 可能只从 C-old 中选出领导人.
第三个问题是: 移除不再 C-new 中的服务器可能会扰乱集群. 这些服务器将不会再接收心跳. 当选举超时时, 它们就会进行新的选举过程. 它们会发送拥有新的任期号的请求投票 RPCs, 这样会导致当前的领导人退回成跟随者状态. 新的领导人最终被选出来, 但是被移除的服务器将会再次超时, 然后这种过程再次重复, 导致整体可用性大幅度下降.
为了避免这个问题, 当服务器确认当前领导人存在时, 服务器会忽略投票 RPCs. 特别的, 当服务器再当前最小选举超时时间内收到一个请求投票的 RPC. 他不会更新当前的任期号和投票号. 这不会影响正常的选举, 每个服务器在开始一次选举之前, 至少等待一个最小选举超时时间. 然后这有利于避免被移除的服务器的扰乱. 如果领导人能够发送心跳给集群, 那么他就不会更大的任期号废黜.
日志压缩
在实际系统中, 不能让日志无限增长, 否则系统重启时需要花很长的时间回放, 从而影响可用性. Raft 采用对整个系统进行 snapshot 来解决, snapshot 之前的日志都可以抛弃.
每个副本独立的对自己系统状态进行 snapshot, 并且只能对已经提交的日志进行 snapshot.
Snapshot 中包含以下内容:
1 > 日志元数据: 最后提交的 log entry 的 log index 和 term. 这两个值在 snapshot 之后的第一条 log entry 的 AppendEntriesRPC 的完整性检查的时候会被用上.
2> 系统当前状态.
当 Leader 要发给某个日志落后太多的 Follower 的 log entry 被丢弃, Leader 会将 snapshot 发给 Follower. 或者新加入一台机器时, 也会发送 snapshot 给它. 发送 snapshot 使用 InstalledSnapshot RPC.
一个服务器用新的快照替换了从 1 到 5 的条目数, 快照存储了当前的状态. 快照中包含了最后的索引位置和任期号
做 snapshot 不要做的太频繁, 否则消耗磁盘带宽, 也不要做的太平凡, 否则一点节点重启要回放大量日志, 影响可用性. 推荐当日组织达到某个固定的大小做一次 snapshot.
做一次 snapshot 可能耗时过长, 会影响正常日志同步. 可以通过使用 copy-on-write 技术避免 snapshot 过程影响正常的日志同步过程.
一个关于 Raft 一致性算法的浓缩总结(不包括成员变换和日志压缩).
参考:
- http://thesecretlivesofdata.com/raft/(Raft 动画)
- https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md(Raft 论文翻译)
来源: https://www.cnblogs.com/WithLin/p/9947631.html