What you are building

A service receives requests from clients and returns responses. One process is a single point of failure, so this project runs several replicas and keeps their committed state consistent. You will handle retries, duplicate requests, leader election, and recovery after a process stops.

Begin with separate processes on one computer, using an injected delay and packet-loss control. Then move a replica to a second computer on the same network. Never expose the test service to the public internet, and authenticate requests before adapting the design for real data.

Teal entries are build checks. The four magenta entries explain a distributed-systems problem and link to the relevant lesson.

Project milestones

Get one byte from one machine to another.
One program waits, another connects to it and sends the number 65. The first one prints 65. A byte is a whole number from 0 to 255, and it is the smallest lump the network moves. A port is a number that says which program on a machine the bytes are meant for. A socket is what your program opens to push bytes at a port. Everything below is that, repeated.
Send a message and get a reply.
The client sends the text add milk. The service keeps a list, puts milk on the end of it, and sends back ok 1. Send list and get the items. One request out, one reply back, and the time for the pair is the round trip.
Retry when the reply does not come.
Put a switch in your client that throws away one reply in three on purpose. Without a retry the client waits for ever for a reply that was binned. Add a timer and a resend, and the list ends up right again.
Make retried requests idempotent.
Nothing was lost that mattered. The request arrived, the service put milk on the list, and the reply is what got thrown away. Your retry sent a perfectly good request that had already been carried out once.

What you need
An operation whose effect is the same whether it happens once or five times is idempotent. Making yours idempotent takes a key on the request. The client invents one per request and keeps the same one across every retry. The service remembers the keys it has already finished, so a repeat is answered from memory instead of being done again.
step 6Idempotence, so a retry is safe
Keep two machines holding the same list.
Run the service twice. The copy the client talks to is the leader, and the other one is a follower. The leader adds the item to its own list, sends the change to the follower, and waits for the follower to say it has written it down. Only then does it answer the client. Ask each of them to print its list and the two match.
Choose and test timeout behaviour.
Wait 50 milliseconds for the follower and the leader gives up and resends every time the follower is a fraction slow. The duplicate count climbs on a network where nothing was lost at all. Wait 30 seconds instead, then unplug the follower, and every single request freezes for half a minute before the client hears anything.

What you need
The wait is a timeout, and no single number is right for every network, so stop picking one. Measure the gap between sending and hearing back, and keep a running average of it. Set the timeout a margin above that average, and make the margin depend on how far the measurements scatter, so a steady link waits barely longer than usual and a jumpy one is given room.
step 4How long to wait
Continue after one replica stops.
Stop the follower: the leader notices, stops waiting for it, and carries on alone. Stop the leader: the client waits out its timeout, connects to the follower instead, and the follower starts accepting items. Pull the plug on either box while you are typing and keep typing.
Prevent two leaders from committing conflicting state.
This time do not stop anything. Block the link between the two machines instead, with a firewall rule or by unplugging one cable. The leader is alive and still taking items from a client that can reach it. The follower hears nothing, decides the leader is dead, and promotes itself. Restore the link and the two lists differ, with no rule anywhere that says which of them is right.

What you need
Two machines each believing they are in charge is split brain. It follows from something you cannot test your way out of: no machine can tell a dead machine from a slow one. The fix is a counting rule instead of a better test. A machine may act as leader only while it can reach more than half the group, which is a majority. Any two majorities of the same group must share at least one machine, so a machine left on its own in a group of three stops itself.
step 7Overlapping on purpose
Elect a leader with a majority quorum.
Add a third copy. Each one runs a countdown, and a machine that hears nothing from a leader before its countdown ends asks the other two for their vote. Two votes out of three makes it leader. Kill any one of the three and the other two carry on within a second. Kill two and the survivor refuses to accept items, which is the right answer rather than a fault.
Reply only after a request is committed.
Both followers go quiet for a moment, and the leader treats them the way it treats a dead one: it stops waiting and carries on alone. It takes add milk, puts it on its own list, answers ok, and dies before either follower has heard of it. One of the survivors wins the next election. It has never heard of milk. Your client holds a reply that says the item was accepted and the item does not exist.

What you need
Write the change down before you carry it out, in an append-only list of changes in the order they happened, which is a log. The leader appends the change, sends it to the followers, and waits until a majority have written it down before applying it to the list and answering the client. That point is where the entry is committed, and the full set of rules for keeping identical logs on machines that keep dying is consensus.
step 7Decide when an entry is safe to act on
Run timed failure and recovery tests.
A small panel that kills one machine at random every twenty seconds, delays some messages, and cuts a link now and then. Leave it running for ten minutes with a client adding numbered items the whole time. Every item the client was told was accepted is in the list afterwards, once each, in the order it was sent. That is the build finished.

Review the service in four passes

Review the same service for request semantics, edge cases, recovery time, and repeated failures.

Make it work

Done, above. Three copies, one leader, and a list that survives a death.

Make it correct

Add fifty numbered items while killing a machine every two seconds. Every number the client was told was accepted appears once, in the order sent, with nothing extra. Then try the case you have not tried: a client that loses its connection before the reply and reconnects to a different machine.

Make it fast

Time a hundred items. Your client sends one request and waits for the reply before sending the next, so the rate is capped at one round trip per item however idle the machines are. Send the hundred without waiting for each reply and compare the two numbers.

Make it survive

Kill a machine and leave it dead. Count how many of your client's later requests still sit out the whole timeout against a machine you already know is not coming back.

Course links for each pass

Each of those three later passes has a step behind it. Take them when you want them and not before.

Getting more than one request into the air at a time.
Make it fast
One request per round trip leaves the link empty almost all the time. Sending several before any of them is answered means keeping a window of unanswered requests and being able to say which reply belongs to which request.
step 5A window of packets in flight
Two requests arriving glued into one.
Make it correct
Send two items quickly and your service reads add milkadd bread in one go. A socket carries a stream of bytes and not a sequence of messages, so it may split them or join them anywhere. What you need is a frame: a length written in front of the bytes, or an agreed marker at the end, so the receiver knows where one message stops.
step 4Where a message starts and stops
Not spending the whole timeout on a machine you know is down.
Make it survive
A circuit breaker counts recent failures against one machine. Once there have been too many, it fails the next requests immediately without sending them. It lets a single one through now and then to find out whether that machine is back.
step 7The circuit breaker

Related projects and courses

An agreed log, an elected leader and a majority rule are what a database cluster, a work queue and a lock service are all made of. They are the reason any of those can be restarted in the middle of a working day. The same three pieces are now running on your own machines.

All builds or read Raft and Consensus straight through. It covers the leader, the log and the majority in order, and ends with a five-machine cluster you try to break. Fault Tolerance is the other half: retries, timeouts, breakers and what a queue should do when it is full.