Leader election and consensus in plain words

A design says: "One server is the leader." The interviewer asks: "What if the network breaks and two servers both think they lead?"

A weak answer names a tool and stops. A strong answer says that the choice needs a majority, why an old leader cannot do damage, and what it costs.

A class chooses one monitor by votes. A student needs votes from more than half of the class, and each student votes once per round. Two such groups share a student, so two monitors cannot win.

Consensus means that servers agree on one value, such as "B is the leader", even when some servers fail. It is safe because of lesson 48: any two majorities share a server.

Raft is a consensus method made to be easy to follow.

1. Each server is a follower, a candidate or the leader.
2. A term is a number that rises with each election. A leader that sees a bigger term steps down.
3. The leader sends a heartbeat, a short "I am alive" message, on a timer. A follower that hears nothing for a random time, the election timeout, becomes a candidate. Random times keep servers from starting together.
4. A candidate adds 1 to the term, votes for itself and asks for votes. A server votes once per term. A candidate with a majority becomes the leader. So a term has at most one leader.
5. A change is committed when a majority has stored it. Only then does the client hear "saved". A server votes only for a candidate that is not missing a change that the server has. So the new leader keeps every committed change.

With 3, 5 or 7 servers, a majority (lesson 48) is 2, 3 or 4. The cluster, a group of servers that work together, survives 1, 2 or 3 failures.

When to use a ZooKeeper-style tool

A coordination service is a small cluster of 3 or 5 servers that runs consensus for you. ZooKeeper and etcd are examples. Do not write consensus yourself. It is hard to get right.

Use it for small facts that all servers must agree on: the leader, a lock and settings. It numbers each change with a number that only rises, which you can use as the fencing token of lesson 51. Do not use it for large data or every user request, because each write waits for a majority.

SwadKart keeps its leader in a cluster of 5 servers, S1 to S5. S1 leads in term 7.

Assumptions (made up to teach with): round trips from S1 to S2, S3, S4 and S5 take 1, 2, 30 and 31 ms. The election timeout is random from 150 to 300 ms, a range the Raft paper calls typical. After the cut, the shortest timer of S3, S4 and S5 is 187 ms, and it belongs to S4.

Step 1. A majority is 3: the leader and 2 followers. A write waits for the second-fastest follower, S3: 2 ms.

Step 2. The network cuts S1 and S2 from S3, S4 and S5. S1 and S2 are 2 servers, less than 3, so nothing they accept is committed. On the other side the heartbeats stop. The timer of S4 ends first, at 187 ms. It moves to term 8, votes for itself, and gets votes from S3 and S5. That is 3 votes, so S4 leads. This answers the predict box: no, and yes.

Step 3. Writes pause only for the timeout (at most 300 ms) and one vote round trip. When the network heals, S1 hears term 8, steps down and drops what it never committed. It thought it led until then, but it saved nothing.

Consensus solves two leaders and lost agreed changes. It costs a majority wait on every write, and writes stop without a majority. I would use it only for small facts.

"Four servers are safer than three." Both survive 1 failure, and four has one more server that can fail. Use an odd number.

"The old leader knows at once that it lost." It does not. It may answer a read with old data until it hears the new term, but it cannot commit a write.

1. Name the three roles in Raft. What is a term?
2. A cluster has 7 servers. Round trips to the six followers are 1, 2, 3, 20, 25 and 40 ms. (a) What is the majority? How many failures can it survive? (b) How long does a write take?
3. A team plans to keep every order status in etcd, at 20,000 writes per second. What do you say?