Raft共识算法

• 是工程开发首选的共识算法
  • Etcd, Consul
• 是在Multi-Paxos思想上，做了简化和限制。
  • 要求日志必须连续的
    • 只要看最后一个log谁更新，O(1)就能证明谁更完整； 若日志不连续，有中间的空格，那就得全量比较，O(n)了； 所以，日志必须连续；用数据结构的维护成本，来降低算法成本，是空间换时间的例子。
  • 只有领导者，追随者，候选人三种状态
• 本质：强领导者模型，一切以领导者为准，实现一系列值的共识，各个节点日志的一致。
• 状态机
• 日志结构
  • 列表：{索引，{任期编号Term，指令}}
• 选举过程
  • 随机心跳超时，任期编号
  • 任期投票，一个节点只能投一票。
    • 投给日志完整度比自己高的（这会导致领导者的日志完整度不比半数节点低）
    • 先来先得
  • 大多数选票
• 日志复制的一阶段提交

旁@Tung: 为什么要引入日志。

如何保证同一时间只有一个领导者？

3 种状态：领导者（Leader）、跟随者（Follower）和候选人（Candidate）

2中RPC消息：RequestVote投票，AppendEntries复制日志和心跳信息

• 候选人或者领导者，发现自己的任期编号比其他节点小，那么它会立即恢复成跟随者状态

在集群中进行成员变更的最大风险是，可能会同时出现 2 个领导者。

疑问

• 由于leader与follower是一阶段提交，leader commit并响应client写入成功，但再发送下一波心跳前宕机，导致followers没有commit log，这会有问题吗
  • 选举出来的新leader，会向其它节点复制日志。如果某条uncommitted的log被发现已经成功复制在大多数节点上，则这条log会更新为commit状态，也会通知其他节点commit
• uncommitted的logentry算不算入日志完整度？
  • 算的，不然可能会导致丢失，见上个问题。