Raft算法

Raft算法用于保证分布式情况下多节点数据的同等性。
原理

Raft算法的主要思想是一个 选主(leader selection) 的算法思想，集群种每个节点都有大概成为三种角色。
三种角色

• leader
  对客户端通信的入口，对内数据同步的发起者，一个集群通常只有一个leader节点。
  
• follower
  非leader节点，被动吸收来自leader的数据请求
  
• candidate
  一种临时角色，只存在于leader推选阶段。
  某个节点想要变为leader，就要发起投票请求(vote)，同时本身变为candidate。
  假如推选乐成，则变为leader,否则退回为follower。
  

数据提交过程

分为三个阶段，分别是日记复制和多数节点确认、提交日记、应用状态机。
日记复制和多数节点确认

leader从客户端吸收到写请求后，会将其封装成日记条目， 然后通过AppendEntriesRPC将日记条目并行发送给所有follower节点。
   

• leader维护了每个follower的nextIndex，表示下一个要发送给改follower日记索引。
  
• leader发送从nextIndex开始的日记条目给follower。
  
• follower收到日记后，会检查‘
  
  
  
  • 前一条日记的Term和Index是否与本地日记匹配(确保一连性)
    
  • 假如匹配，follower将日记追加到本地日记中，并返回乐成
    
  • 若不匹配，则返回失败，leader将nextIndex递减并重试，直到找到同等的位置
    
  
  

  leader需等候 多数节点(包括本身) 确认已乐成复制该条目，才可进行下一步提交。
日记提交(commit)

• leader节点提交并发送给follower节点
  leader确认日记已被大多数节点复制后，会更新本地的commitIndex，leader在后续的AppendEntriesRPC(包括心跳)中，将commitIndex 发送给follower节点。
  
• follower节点提交
  follower节点收到commitIndex后，会将本地日记中所有Index<=commitIndex的日记提交。
  

应用状态机

已提交的日记条目会被应用到状态机。

• leader和follower会按Index次序实验日记中的命令
  
• 实验后更新lastApplied
  leader在应用状态机后，返回效果给客户端。
  

推选过程

candidate的诞生

初始状态下，所有节点都是follower，每个follower都有一个timer，当follower在timer竣事也没有收到其它节点的vote，该follower就会变成candidate，同时向其它节点发送vote。
推选规则

大抵过程

• 每个follower每轮只有一次投给candidate的机会。
  
• follower采用先来先投票策略
  
• 凌驾半数的follower都认为该candidate适合做leader，那么新的leader产生
  
• leader通过心跳联系follower。若在follower的timer期间没有收到leader的心跳，则会认为leader宕机，该follower变为candidate，并开始新的一轮推选。
  

具体推选过程

当candidate节点向本身发送vote后，会根据条件判定是否进行投票(要保证candidate节点的日记条目要新于本身)
follower节点投票规则

• 任期检查
  假如请求中的Term小于自身节点的Term，则认为其日记条目还没有自身新，拒绝投票。
  
• 投票承诺
  每个节点每轮推选，只能投一票(先到先服务)
  
• 日记新旧对比
  
  
  
  • Candidate的最后一条日记的Term必须>=吸收者最后一条日记的Term
    
  • 若Term雷同，Candidate的日记Index必须>=吸收者的日记Index
    
  
  

各消息体

vote
   

• term，自身处于的推选周期
  
• lastLogIndex，log中最新的index值
  
• lastLogTerm，log中近来的index是在哪个term中产生的
  

  每个节点生存的数据信息
   

• currentTerm，节点处于的term号
  
• log[ ]，自身的log集合
  
• commitIndex，log中最后一个被提交的index值
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。