Dev on break Distributed Computing
episode 1 · arc 1

What Is a
Distributed System?

A cable blinked for 43 seconds. GitHub's service was degraded for 24 hours. What kind of machine can even fail like that?

What this episode covers

  • Version one of the URL shortener: one machine, one process and the three things you get for free (consistency, ordering, fail-as-a-unit).
  • The four pushes that force you off one machine: compute, storage, availability, geography and why geography is pure physics.
  • Two definitions of a distributed system (Tanenbaum & van Steen; Lamport) and the three mechanical properties that actually separate it from a single-machine program.
  • The hidden network hops in an "ordinary" web deployment and why the same logical lookup goes from ~100 ns to ~500 µs.
  • Partial failure: the third outcome (unknown) that single machine code never has, and why a timeout is just a guess.
  • Why more machines does not mean more reliable: 0.999⁵ ≈ 0.995.
  • A reading of the 2018 GitHub incident with the vocabulary from the episode.

Exercises

The coding exercise is the one to prioritize. It walks through configuring a timeout in a real client, which is where the concept actually makes sense.

1 · Written problem

Your team splits the URL shortener into pieces. Create and redirect are handled by a link service running on three machines behind a load balancer. Link data lives in a database on its own machine, with one read replica. A cache sits in front of the database. And on every redirect, the link service fires off a "one more click" message to a separate analytics service and immediately returns the redirect to the user without waiting for a reply.

Answer in a few sentences each:

  1. Identify which parts of this system are distributed systems, using the three-property definition from this episode: independent failure, message passing instead of shared memory, unreliable network. Justify each part you identify.
  2. A user reports that they created a link, saw a success page, and then the link returned "not found." Give two different network-level explanations that do not assume any bug in the application code.
  3. The click counter reads about two percent lower than the load balancer's request logs. Explain why this is the expected behaviour of the design as described, rather than a bug.
Model answer

a) The line is the process/machine boundary, not the boxes on the diagram.

  • Distributed: load balancer, the three link-service machines, cache, database primary, read replica, analytics service, and the primary → replica replication stream. Each a separate failure domain talking only by messages over an unreliable network.
  • Not distributed: anything inside one link-service process (a handler calling a code generator shares memory and a clock with it, so they fail as a unit), and multiple threads or cores on one machine, for the same reason.

b) Two possibilities:

  • The primary acknowledged the write, then failed before that write replicated anywhere else, and a replica that never received the row got promoted. As the write was acknowledged the first call returned a success response.
  • The write hit the primary, but the redirect read from a replica before replication delivered that row.

The two cases end differently: in the first, the row is gone for good. The promoted replica never had it, so there's nothing left to converge to. In the second, the row isn't lost, just not there yet. Replication catches up and the link starts resolving normally on its own.

c) It's at-most-once delivery with no acknowledgement, no retry.

The network can drop the message, a full buffer can drop it, or the analytics service can be restarting, and the link service never waits long enough to find out. Losing a small fraction of events is an undesirable side effect of the design, and the fix costs acknowledgements, retries on timeout, and handling the duplicates those retries produce (that trade is Episode 12).

2 · Coding exercise - timeouts are a guess, make retries safe anyway

~15–20 minutes · JavaScript

The link store below stands in for the URL shortener's database on the other side of a network. db.put(code, longUrl) returns a promise and usually it resolves, but sometimes it rejects with TimeoutError. That rejection can mean two different things: the write never happened, or it happened and only the response got lost. From where you're standing, those look identical. db.get(code) resolves to whatever's stored under code, or undefined

Implement shorten(db, longUrl, maxAttempts = 5) so that it:

  1. Returns a code from randomCode() that actually resolves in the store.
  2. Retries through timeouts instead of giving up on the first one.
  3. Never leaves more than one distinct code in the store for the same call.
  4. Throws TimeoutError if it cannot confirm the write within maxAttempts write attempts.

Three tests run against whatever you type in below. You cannot see or edit the store itself.

Hint, if you're stuck

Ask yourself when the code gets decided - before the first network hop, or after it?

shorten.js

Click "Run tests" to check your implementation.

Reference solution 
async function shorten(db, longUrl, maxAttempts = 5) {
  // Decided once, before the first network hop — retries repeat this same
  // write instead of minting a new one.
  const code = randomCode();
  let lastError;
  for (let i = 0; i < maxAttempts; i++) {
    try {
      await db.put(code, longUrl);
      return code;
    } catch (err) {
      if (!(err instanceof TimeoutError)) throw err;
      lastError = err;
      // A timeout says nothing about whether the write landed, so go look.
      if ((await db.get(code)) === longUrl) return code;
    }
  }
  throw lastError;
}

Deciding the code once and reusing it across retries makes each retry a repeat of the same write rather than a new one. That property is idempotency, and it's the standard answer to timeout ambiguity (Episode 12). The readback after a timeout isn't a fix, it's a second guess. In the real world that read can time out too.

3 · Quiz

  1. Which of the following is a distributed system?
  2. An app server sends a write to the database and receives no response for 10 seconds. What can it conclude?
  3. Five services are each available 99.9% of the time, and a request must touch all five in sequence, failing if any one is unavailable. Roughly what is that request's availability?
  4. Why is a 64-core server not a distributed system?
  5. In the GitHub incident, why could the East Coast databases not simply be promoted back to primary once the network recovered?
Answers
  1. B. The parts fail independently and communicate only by messages over an unreliable network. A, C and D share memory and a clock and fail as one unit.
  2. C. Silence is not evidence. A dropped request, an applied write with a lost reply, a slow database and a slow network all look identical from the caller's side.
  3. B. Components in series multiply their availabilities: 0.999⁵ ≈ 0.995. Adding machines in series makes availability worse, not better.
  4. B. Distribution is concurrency plus independent failure plus an unreliable network. A multi-core machine has the concurrency but neither of the other two.
  5. B. Both copies were honest records of what each site had personally seen, and neither was a superset of the other, so failing back would have discarded real user writes.
← all episodes