Preface: Just finished 6.824 Lab2A, write an article to sort it out. It is necessary to take a look at section 5.2 of the paper first. It is not easy to understand in English, so you can read the translation. If you haven’t understood the Chinese translation, you can watch the video.
In addition to the paper, you also need to know some Go language, at least have the foundation of other languages. One more thing to know is what is RPC?
This paper is divorced from the background of MIT 6.824 and Raft algorithm, and only describes the implementation of the Leader Election algorithm. If you do not know what the Leader Election can be used for, you need to understand the knowledge related to disaster recovery and active/standby.
The code in this article only lists the trunk, some undefined functions or data members, which you can understand by name or comment.
The code in this article does not represent concurrent synchronization. A simple implementation is to use a larger-grained lock for each function, but you can also use other synchronization mechanisms to achieve better performance concurrent synchronization.
// Current Node
type Server struct {
// Leader | Candidate | Follower
role string
// Logic clock
term int
// Under whose leadership
support int
// All Nodes include current
peers []*rpcClient
// Current peer's ID
me int
}
// Server's main loop
func (srv *Server) ticker(a) {}
// RPC Handler | Follower or Candidate get votes from other nodes
func (srv *Server) Canvass(args *cArgs, reply *cReply) {}
// RPC Handler | Leader declare sovereignty
func (srv *Server) Dominate(args *dArgs, reply *dReply) {}
func main(a) {
srv := MakeServer("Follower")
go srv.ticker()
}
Copy the codeThe code above shows the implementation of a node in a distributed system. For a node, there is only one identity (Leader, Candiate, Follower) at any time, where a Candidate is an intermediate identity from Follower to Leader.
Initially, all nodes are followers. After a period of time (Election Timeout), when they do not feel the rule of the Leader, followers will switch to Candidate and solicit votes from other followers. When the number of votes is enough (more than half), Candidate converts to Leader.
The Election Timeout should be randomly generated to avoid multiple candidates appearing at the same time, as each Candidate may not get enough votes and a new Election is required.
func (srv *Server) ticker(a) {
for srv.alive() {
time.Sleep(1 * time.Millisecond)
if srv.role == "Leader" {
// 10 times per second
if time.Since(srv.lastBroadcastHeartbeat) > srv.broadcastInterval() {
srv.broadcast()
}
} else {
// random election timeout about 300 ~ 400ms
if time.Since(srv.lastReceiveHeartbeat) > srv.electionTimeout() {
srv.elect()
}
}
}
}
func (srv *Server) broadcast(a) {
srv.lastBroadcastHeartbeat = time.Now()
for id, peer := range srv.peers {
if id == srv.me {
continue
}
reply := dReply{}
peer.Call("Server.Dominate", &dArgs{}, &reply)
}
}
func (srv *Server) Dominate(args *dArgs, reply *dReply) {
srv.lastReceiveHeartbeat = time.Now()
}
func (srv *Server) elect(a) {
// reset avoid elect again
srv.lastReceiveHeartbeat = time.Now()
srv.role = "Candidate"
voteCount := 1 // vote for me
for id, peer := range srv.peers {
if id == srv.me {
continue
}
reply := cReply{}
peer.Call("Server.Canvass", &cArgs{CandidateId: srv.me}, &reply)
if reply.VoteGranted {
voteCount++
}
}
if voteCount > len(peers)/2 {
srv.role = "Leader"
srv.lastBroadcastHeartbeat = time.Unix(0.0)}}func (srv *Server) Canvass(args *cArgs, reply *cReply) {
reply.VoteGranted = false
// only have one vote
if srv.support == - 1 {
srv.support = args.CandiateId
reply.VoteGranted = true
srv.lastReceiveHeartbeat = time.Now()
}
}
Copy the codeYou should note that server.term is not used, and I intentionally removed the term related code in order to better understand the basic framework of the Leader Election algorithm.
For the whole system, there should be only one Leader, but there are exceptions. When network isolation occurs in the system, each zone will become its own system, and partitions with more than half of nodes will generate new leaders, while the old Leader will always exist in their own zones. When network isolation disappears, There will be two leaders at the same time.
Tenure solves that problem. The term of office of the new Leader will be longer than that of the old Leader. In this way, after the two leaders meet, the Leader with a shorter term can be converted to followers.
The term is the logical clock, represented by an incrementing integer value. Term increments occur only after the Leader dies, all candidates get a new term (term is generated), and the new term is synchronized to all nodes after taking office (term takes effect).
During the term, that is, during the election phase, each node can only support one Candidate regardless of its role. After the term takes effect, that is, after the Leader takes office, support is set to -1.
func (srv *Server) broadcast(a) {
srv.lastBroadcastHeartbeat = time.Now()
for id, peer := range srv.peers {
if id == srv.me {
continue
}
reply := dReply{}
peer.Call("Server.Dominate", &dArgs{Term: srv.term}, &reply)
if reply.Term > srv.term {
// A new Leader appeared, update self state
srv.role = "Follower"
srv.term = reply.Term
srv.support = - 1}}}func (srv *Server) Dominate(args *dArgs, reply *dReply) {
reply.Term = srv.term
if args.Term < srv.term {
return // ignore old Leader
}
// A new Leader appeared, update self state
if args.Term > srv.term {
srv.term = args.Term
srv.role = "Follower"
srv.support = - 1
}
srv.lastReceiveHeartbeat = time.Now()
}
func (srv *Server) elect(a) {
// Reset avoid elect again
srv.lastReceiveHeartbeat = time.Now()
srv.role = "Candidate"
// Update term when old leader dead
srv.term++
// vote for self
srv.support = srv.me
voteCount := 1
maxTerm := 0
for id, peer := range srv.peers {
if id == srv.me {
continue
}
reply := cReply{}
peer.Call("Server.Canvass", &cArgs{Term: srv.term, CandidateId: srv.me}, &reply)
if reply.VoteGranted {
voteCount++
}
if reply.Term > maxTerm {
maxTerm = reply.Term
}
}
// The role may became Follower during canvass
// That means another Leader appeared
ifsrv.role ! ="Candidate" {
return
}
// A new Leader appeared, update self state
if maxTerm > srv.term {
srv.role = "Follower"
srv.term = maxTerm
srv.support = - 1
return
}
if voteCount > len(peers)/2 {
srv.role = "Leader"
srv.support = - 1
srv.lastBroadcastHeartbeat = time.Unix(0.0)}}func (srv *Server) Canvass(args *cArgs, reply *cReply) {
reply.VoteGranted = false
reply.Term = srv.term
if args.Term < srv.term {
return // ignore old Candidate
}
// A new Leader appeared, update self state
if args.Term > srv.term {
srv.term = args.Term
srv.role = "Follower"
srv.support = - 1
}
// only have one vote
if srv.support == - 1 {
srv.support = args.CandiateId
reply.VoteGranted = true
srv.lastReceiveHeartbeat = time.Now()
}
}
Copy the codeTerm is the core concept of Leader Election. Term and Role always appear at the same time, and the operation of the algorithm as a whole depends on the transition of the two states. I hope this article can be helpful to you.