共识算法raft的关键概念

从etcd源码里看raft

raft 算法主要有两个过程：一个过程是领导者选举，另一个过程是日志复制，其中日志复制过程会分记录日志和提交数据两个阶段。raft 算法支持最大的容错故障节点是（N-1）/2，其中 N 为 集群中总的节点数量。

三种状态

raft算法中只有三种状态，etcd的实现中增加了一种状PreCandidate

• Follower（群众）
• Candidate（候选人）
• Leader（领导）

image.png

https://github.com/etcd-io/etcd/blob/master/raft/raft.go#L36,L43

// Possible values for StateType.
const (
    StateFollower StateType = iota
    StateCandidate
    StateLeader
    StatePreCandidate
    numStates
)

两种超时机制

• election timeout（选举超时）
• heart timeout（心跳超时）

https://github.com/etcd-io/etcd/blob/master/raft/raft.go#L619,L653

// tickElection is run by followers and candidates after r.electionTimeout.
func (r *raft) tickElection() {
    r.electionElapsed++

    if r.promotable() && r.pastElectionTimeout() {
        r.electionElapsed = 0
        r.Step(pb.Message{From: r.id, Type: pb.MsgHup})
    }
}

// tickHeartbeat is run by leaders to send a MsgBeat after r.heartbeatTimeout.
func (r *raft) tickHeartbeat() {
    r.heartbeatElapsed++
    r.electionElapsed++

    if r.electionElapsed >= r.electionTimeout {
        r.electionElapsed = 0
        if r.checkQuorum {
            r.Step(pb.Message{From: r.id, Type: pb.MsgCheckQuorum})
        }
        // If current leader cannot transfer leadership in electionTimeout, it becomes leader again.
        if r.state == StateLeader && r.leadTransferee != None {
            r.abortLeaderTransfer()
        }
    }

    if r.state != StateLeader {
        return
    }

    if r.heartbeatElapsed >= r.heartbeatTimeout {
        r.heartbeatElapsed = 0
        r.Step(pb.Message{From: r.id, Type: pb.MsgBeat})
    }
}

任期制

哪个节点做leader是大家投票选举出来的，每个leader工作一段时间，然后选出新的leader继续负责。这跟民主社会的选举很像，每一届新的履职期称之为一届任期，在raft协议中，也是这样的，对应的术语叫term。

image.png