Consensus, leader election and distributed locks

Several nodes must agree on one thing (who is the leader, which write comes next, what the config is) even though nodes crash and messages get lost or delayed. Consensus algorithms (Paxos, Raft, ZAB in ZooKeeper) do this with a majority quorum: nothing is decided unless more than half the nodes agree.

• To survive f failures you need 2f + 1 nodes: 3 nodes tolerate 1 failure, 5 tolerate 2.
• Use odd sizes. 4 nodes need 3 for a majority, so they still tolerate only 1 failure, the same as 3, at a higher cost.
• Consensus systems are CP (see CAP): the side of a partition that has no majority stops accepting writes.

1. Every node is a follower, candidate or leader. Time is split into numbered terms; each term has at most one leader.
2. The leader takes all writes, appends them to its log and replicates to followers. An entry is committed once a majority has it; only then is it applied and acknowledged.
3. Followers expect regular heartbeats. If none arrives within a randomized timeout (roughly 150 to 300 ms), a follower becomes a candidate, bumps the term and asks for votes. A node votes once per term, and only for a candidate whose log is at least as up to date as its own, so committed entries are never lost.
4. A leader cut off in a minority cannot commit anything, and it steps down when it sees a higher term.

You almost never implement consensus yourself. You use it through etcd, ZooKeeper, Consul or a database that has it built in.

• Candidates race to create an ephemeral node (ZooKeeper) or acquire a lease with a TTL (etcd). The holder is leader and keeps renewing; if it dies, the session or lease expires and another candidate wins.
• Typical uses: one active scheduler or cron runner, primary database failover, the Kafka controller, the owner of a partition.
• For small systems a row in the database you already run (SELECT ... FOR UPDATE) can be enough, as long as you accept that database as a single point of failure.

A lock with a TTL (Redis SET lock:job id NX PX 30000) has a trap: the holder pauses (a long GC, a network stall) longer than the TTL, the lock expires, a second client gets it, and then the first wakes up still believing it holds the lock. Both write.

A: acquires lock -> token 33 ... stalls (GC pause) ... lock expires
B: acquires lock -> token 34, writes to storage with token 34
A: wakes up, writes with token 33 -> storage rejects it (33 < 34)

• Fencing token: the lock service hands out an increasing number with each grant, and the resource being protected rejects any write carrying a lower number than the highest it has seen.
• A single-node Redis lock is fine as an efficiency lock (occasionally running a job twice is harmless). For correctness use a consensus-based service (etcd, ZooKeeper) with fencing tokens. The multi-node Redis "Redlock" scheme is debated, so do not lean on it for correctness.
• Often the better answer is to avoid the lock: make the operation idempotent, or use a unique constraint or an optimistic version check in the database.

Split brain means two nodes both think they are the leader after a network partition, and both accept writes. Prevent it with quorum (a minority cannot act) and fencing (a stale leader's writes are rejected).