Quorum and leader election

Consensus is how several machines agree on one value, such as which of them is the leader, even when some fail or cannot be reached. Without it two machines can both believe they are in charge.

You will learn the idea behind it, the majority vote, and how a group elects a leader.

Suppose a group of five nodes must choose a leader. If each node asked only itself, two nodes could each pick a different leader.

The fix is the majority: a decision counts only if more than half of all the nodes agree. A group of five needs three. This smallest deciding group is the quorum. Two groups can never both hold a majority, because they would share a node.

# Five nodes. Can the nodes that are still up act on their own?
nodes = 5
for up in [5, 4, 3, 2, 1]:
    if up * 2 > nodes:
        print(up, "up: more than half, can go on")
    else:
        print(up, "up: not more than half, must wait")
# Change nodes to 6 and run again. Is 3 up enough?

A network partition cuts the nodes into groups that cannot talk to each other. Each side cannot tell whether the other has crashed or is just cut off.

If both sides chose a leader, the data would split into two versions. This is split brain. With a quorum rule only the side with a majority may act. The smaller side stops and waits.

A write can wait for w nodes to store it, and a read can ask r nodes. Suppose w plus r is more than the number of nodes. Then every read group shares a node with the last write group, so it sees the newest value.

With five nodes, w = 3 and r = 3 always overlap. w = 2 and r = 2 can miss each other.

# A write must reach "w" nodes and a read asks "r" nodes. Do they always share one?
nodes = 5
for pair in [[3, 3], [2, 2], [4, 2], [1, 5]]:
    w = pair[0]
    r = pair[1]
    if w + r > nodes:
        print("write", w, "read", r, ": always share a node")
    else:
        print("write", w, "read", r, ": may miss each other")
# Change nodes to 7 and run again.

v() ( printf '%s\r\n' "$*" | nc -w 1 valkey 6379 )

v CONFIG GET min-replicas-to-write

v CONFIG GET min-replicas-max-lag

Time is split into numbered terms. A node that hears no leader for a while becomes a candidate in a new term and asks for votes. Each node votes once per term.

A candidate with a majority becomes the leader of that term. If nobody gets a majority, because the votes split, that term has no leader and a new one starts.