Raft Algorithm

Raft

Raft is a consensus algorithm

• etcd中的一致性算法使用了raft

算法流程

leader selection

• 一个节点处于下列三种状态之一
  • leader
    • client与leader进行交互, 并且同一时间只能有一个leader
  • candidate
  • follower
• 每个节点随机一个timeout时间, 当timeout跑完时, follower成为candidata(term+1), 并且向所有节点发送require vote rpc(自己投自己一票)
  • 接收到的节点(每个节点只有一票)根据请求到达顺序、term、log index决定是否投票
• 当candidate获取超过半数选票, 就成为leader
  • leader定期发送heartbeat, 心跳可以抑制timeout和携带指令
• leader如果挂掉, 就重新选举
• 如果同时出现多个candidate, 并且都无法成为leader, 就等再一轮timeout结束, 其他节点成为新candidate(term+1)

log replication

• 系统所有的变更都需要经过leader
  • 如果发给follower, 会重定向到leader节点
• client提交修改(或其他指令), leader追加日志项(append log entry)
  • 并将追加条目发给其他节点(append entry rpc), 其他节点复制entry
• follower节点收到entries后, 可能出现两种情况
  • 成功, 写入log
  • 一致性检查失败, 出现日志不一致现象(term、index不一致), leader会回溯找到最新的一致日志, 并将自己的日志复制给follower(不一致的日志就相当于回滚了)
• leader收到超过半数节点写入log成功, 就将结果返回给client, 并且将日志提交到状态机(state machine)
  • 然后发送commit通知
• follower节点也将日志改为commit状态

safety

• 脑裂(同时出现多个leader)
  • raft算法每个节点只有一票, 并且要获得超过半数选票才能成为leader, 保证同一时间只有一个leader
• log完整性匹配
  • 相同的状态 + 相同的操作 = 相同的结果
  • raft日志同步中日志有相同的term和index, 说明该条日志相同, 并且这条日志之前的日志也都相同