follow end tps 实现 raft 产生 投票 长时间 什么是
Paxos 自 1990 年提出以后,相当长时间内几乎已成为分布式一致性算法的代名词.但因其难以理解和实现,目前知名实现仅有 Chubby,Zookeeper,libpaxos 几种,其中 Zookeeper 使用的 ZAB 对 Paxos 做了大量改进.为此,2013 年斯坦福的 Diego Ongaro,John Ousterhout,提出了新的更易理解和实现的一致性算法,即 Raft.
Raft 和 Paxos 均只要保证 n/2+1 节点正常,即可服务.相比 Paxos,其优势即为易于理解和实现.Raf 将算法分解为:选择领导者,日志复制,安全性等几个子问题.它的流程即为:开始时在集群中选举出 Leader 负责日志复制的管理,Leader 接收来自客户端的事务请求(日志),并将它们复制给集群中的其他节点,然后通知集群中的其他节点提交日志,Leader 负责保证其他节点与它的日志同步.当 Leader 宕机时,集群其他节点重新发起选举,选出的新的 Leader.
角色
Raft 涉及三种角色:
Leader:即领导者,负责处理来自客户端的请求,管理日志复制,以及与 Follower 保持心跳以维持其领导者地位.
Follower:即追随者,负责响应来自 Leader 的日志复制请求,响应来自 Candidate 的选举请求.初始时所有节点均为 Follower.
Candidate:即候选者,负责发起选举投票,Raft 启动后或 Leader 宕机后,一个节点从 Follower 转为 Candidate,并发起选举,选举成功后,由 Candidate 转为 Leader.
如下为 Raft 角色状态转换图:
Term(任期)
在 Raft 中使用了 Term(任期)的概念,一轮选举即为一个 Term(任期),一个 Term 中仅能产生一个 Leader.Term 使用连续递增的编号表示,初始时所有 Follower 的 Term 均为 1.其中某个 Follower 定时器到期触发选举,其状态转换为 Candidate,此时 Term 加 1 变为 2,然后开始选举,有如下几种可能:
1,如果当前 Term 为 2 的任期内没有选举出 Leader 或出现异常,Term 递增为 3,并开始新一轮选举.
2,此轮 Term 为 2 的任期内选举出 Leader 后,如果 Leader 宕机,此时其他 Follower 转为 Candidate,Term 递增,并发起新的选举.
3,如果 Leader 或 Candidate 发现自己的 Term 比其他 Follower 小时,Leader 或 Candidate 转为 Follower,Term 递增.
4,如果 Follower 发现自己的 Term 比其他 Follower 小时,更新 Term 与其他 Follower 保持一致.
每次 Term 递增都将发生新一轮选举,在 Raft 正常运行过程中,所有节点 Term 均一致.如果节点不发生故障,一个 Term(任期)会一直保持下去,当某节点收到的请求中 Term 比当前 Term 小时拒绝请求.
选举
初始时所有节点均为 Follower,且定时器时间不同.某个节点定时器触发选举后,Term 递增,该节点由 Follower 转换为 Candidate,向其他节点发起投票请求(RequestVote RPC).有如下几种可能:
1,收到过半数节点(n/2+1)投票,由 Candidate 转换为 Leader,向其他节点发送心跳以维持领导者地位.
2,如果收到其他节点发送的 AppendEntries RPC 请求,且该节点 Term 大于当前节点 Term,即发现了新的有效领导者,转换为 Follower,否则保持 Candidate 拒绝该请求.
3,选举超时,Term 递增,重新发起选举.
每轮 Term 期间,每个节点均只能投票 1 次,如果多个 Candidate 均没有接收到过半数投票,则每个 Candidate Term 递增,重启定时器并重新发起选举.因定时器时间随机,因此不会多次出现多个 Candidate 同时发起投票的问题.
日志复制
保证节点的一致性,就要保证所有节点都按顺序执行相同的操作序列,日志复制目的即为此.
1,Leader 接收到客户端事务请求(即日志),先将日志追加到本地 Log 中,并通过 AppendEntries RPC 复制给其他 Follower.
2,Follower 接收到日志后,追加到本地 Log 中,并向 Leader 发送 ACK 消息.
3,Leader 收到过半数 Follower 的 ACK 消息后,将日志置为已提交并正式提交日志,通知客户端,并发送 AppendEntries RPC 请求通知 Follower 提交日志.
安全性
1,每个 Term 期间只能选举一个 Leader.
2,Leader 不会删除或覆盖已有日志条目,只会追加.
3,如果相同索引位置的日志条目 Term 任期号相同,那么认为从头到这个索引位置均相同.
4,如果某个日志条目在某任期内提交,那么这个日志条目必然出现在更大的 Term 任期号的所有领导中.
5,如果 Leader 在某索引位置的日志条目已提交,那么其他节点相同索引位置不会提交不同的日志条目.
RequestVote RPC 和 AppendEntries RPC
Raft 中节点通信使用两种 RPC,即 RequestVote RPC 和 AppendEntries RPC:
RequestVote RPC:即请求投票,由 Candidate 在选举期间发起.
AppendEntries RPC:即附加条目 RPC,由 Leader 发起,用于日志复制和心跳机制.
参考文档
寻找一种易于理解的一致性算法(扩展版)
一致性算法 Raft 详解
Raft 为什么是更易理解的分布式一致性算法
后记
本文总结的 Raft,及之前文章中的 Paxos,2PC,3PC 均为基于非拜占庭容错的分布式一致性算法,即除考虑消息的丢失,超时,乱序,但不考虑消息被篡改.从下个文章起,将总结基于拜占庭容错的分布式一致性算法,该算法在比特币,以太坊,及其他区块链产品中广泛使用.
来源: http://www.bubuko.com/infodetail-2455898.html