亚马逊网站建设分析,网站建设合同不给版权,欢迎进入18入口1,佛山网站推广建设文章目录一、目的#xff08;与Paxos相同#xff09;二、名字来源三、服务器状态四、基本实现1、任期2、RPC调用3、领导者选举4、日志复制5.领导者更替三、Raft与Paxos的区别1.表现形式2.简单性3.领导选举算法一、目的#xff08;与Paxos相同#xff09;
保证日志完全相同…
文章目录一、目的与Paxos相同二、名字来源三、服务器状态四、基本实现1、任期2、RPC调用3、领导者选举4、日志复制5.领导者更替三、Raft与Paxos的区别1.表现形式2.简单性3.领导选举算法一、目的与Paxos相同
保证日志完全相同地复制到多台服务器上以实现状态机复制的算法。 解决了Paxos的难理解性和工程上的难以实现。
二、名字来源
可靠Reliable、复制Replicated、冗余Redundant、容错Fault-Tolerant—— R{eliable|eplicated|edundant} And Fault-Tolerant 取首字母Raft。
三、服务器状态
1、领导者处理所有的客户端请求和日志复制同一时刻最多只能有一个正常工作的领导者。 2、跟随者 3、候选者领导者与跟随者之间的状态。
四、基本实现
1、任期
是一个逻辑时间用来解决时序问题。 每台服务器维护一个currentTerm变量表示最新任期号持久化存储。
2、RPC调用
Raft算法中服务器通信主要通过两个RPC调用实现 1RequestVoteRPC 领导者选举 2AppendEntriesRPC领导者用来复制日志和发送心跳
3、领导者选举
1领导者需要周期性向跟随者发送心跳包空的AppendEntries消息如果跟随者在选举超时时间electionTimeout一般为100-500ms)没有收到任期更大的RPC请求认为集群中没有领导者开始新选举。
2节点开始竞选流程如下图
3选举过程中需要保证共识算法的两个特性安全性只会有一个领导者被选举出来和活性最终能选出一个领导者。 保证安全性a.每个节点在同一任期只能投一次票给第一个满足条件的RequestVote请求。需要每个节点新增一个投票信息变量votedFor表示当前任期头拍给了哪个候选者为空表示没有投票。votedFor需要持久化存储否则会导致一个节点投票给不同候选者。 b.获得超过半数投票的才能成为领导者。 保证活性如果选举失败使用活锁即节点随机选择超时时间重试。
4、日志复制
1日志格式 每个节点存储自己的日志副本(log[ ]), 日志中的每个日志条目Log Entry)包括 索引该日志条目在整个日志中的位置。 任期号日志条目首次被领导者创建时的任期。 命令应用于状态机的命令。
2Raft算法通过索引和任期号唯一标识一条日志目录。
3日志必须持久化存储 一个节点必须先将日志条目安全写到磁盘中才能向系统中其他节点发送请求或回复请求。
3记录已提交committed) 如果一条日志被存储在超过半数的节点上则认为该记录已提交committed)意味着状态机可以安全的执行该记录。类似Paxos中的已批准chosen)。
4日志复制流程 客户端发送命令——领导者追加该日志并持久化存储——领导者发送AppendEntries消息——a.超过半数响应领导者认为该日志已提交应用apply到自己的状态机向客户端返回响应。注领导者位置LeaderCommit参数一旦提交了一个日志记录会在后续的AppendEntries消息中通知跟随者。该参数代表领导者已提交的最大日志索引跟随者也提交小于该值的日志并应用到自己的状态机。 b.不成功领导者反复尝试发送AppendEntries消息。
5Raft日志特性 a.如果两个节点日志在相同索引位置上任期号相同认为命令相同并且从日志开头到这个索引位置之间的日志也都相同。 b.如果给定的记录已提交那么所有前面的记录也已提交。注这条是Raft算法和Paxos算法的不同之处Paxos算法允许日志不连续地提交但Raft算法的日志必须连续地提交。 一致性检查为了实现日志特性Raft算法通过AppendEntries消息来检测之前的一个日志条目——每个AppendEntries消息请求包含新日志条目之前的一个日志条目的索引(prevLogIndex)和任期(prevLogTerm);跟随者收到请求后会检查自己最后一条日志的索引和任期号是否与请求消息中的prevLogIndex和prevLogTerm相匹配如果匹配则接收该记录否则拒绝。
5.领导者更替
Paxos选举领导者是选id最大的服务器。 Raft选择最有可能包含所有已提交日志的节点即日志最新并且最完整。 方法候选者C在RequestVote消息中包含自己最后一条日志的索引lastIndex和任期lastTerm收到投票请求的服务器V比较谁的日志更完整 lastTermV lastTermC ) || (lastTermV lastTermC) (lastIndexV lastIndexC).表示V更新将拒绝C的投票请求。
三、Raft与Paxos的区别
1.表现形式
Raft提出的目标是可理解性尝试寻找一种比Paxos更容易学习和理解的方式来描述算法。
2.简单性
1Raft按顺序提交日志Paxos允许日志不按顺序提交但需要一个协议来填补可能因此出现的日志漏洞。 2Raft中的所有日志副本都有相同的索引、任期和命令而Paxos中这些任期可能有所不同。
3.领导选举算法
Paxos中选举算法是比较服务器id的大小服务器id较大的节点胜出。
