Skip to content
Tutorials Center
My learning

Topics

Lesson 60 of 77 ยท DevOps, Tools and System Design

Distributed Systems: Consensus, Clocks, Tracing and Consistency

Prepare distributed systems interview answers on consensus (Raft and Paxos), logical clocks, consistency models, fencing tokens, tracing and fault tolerance, with runnable models.

A distributed system is a set of computers that must act like one, while any of them, or the network between them, may fail at any moment. Interviews at this level are less about product names and more about whether you can reason about what can go wrong: messages arrive late, twice or never; clocks disagree; a node looks dead when it is only slow.

Two related topics are covered elsewhere: the CAP theorem, replication and quorums in NoSQL, Scaling and Caching, and sagas and Kafka in Microservices, Kafka and Kubernetes. This lesson adds consensus, time, consistency models, safe leadership and distributed tracing. The real systems (etcd, ZooKeeper, Jaeger) cannot run on the site, so every runnable example is a small Node.js model of the idea.

Why distributed systems are hard

Unreliable network Delay, loss, duplication, reordering.
No shared clock Wall clocks drift and disagree.
Partial failure Some nodes fail while others run.
Uncertainty A slow node looks like a dead one.

Most designs are answers to one of these four problems.

1 / 2

What is consensus, and why is it hard?

Consensus means a group of nodes agrees on a single value (who is the leader, what the next log entry is, whether a transaction commits), even if some nodes crash and messages are delayed. It must satisfy agreement (no two nodes decide differently), validity (the decided value was proposed by someone) and termination (a decision is eventually reached). The FLP impossibility result says no deterministic protocol can guarantee all three in a fully asynchronous network with even one crash; real protocols get around it with timeouts and randomization, which gives up guaranteed liveness in bad moments but never gives up safety.

The universal tool is the majority quorum. With N nodes, a decision needs floor(N/2) + 1 votes. Any two majorities overlap in at least one node, so two conflicting decisions cannot both be accepted. That is why clusters have an odd number of nodes (3 or 5): 3 nodes tolerate 1 failure, 5 tolerate 2, and a 4-node cluster tolerates only 1, the same as 3.

How does Raft work?

Raft is the consensus algorithm designed to be understandable, used by etcd, Consul and many databases. It splits the problem into leader election, log replication and safety.

  • Every node is a follower, candidate or leader. Time is divided into numbered terms, and each term has at most one leader.
  • A follower that hears no heartbeat from a leader for a randomized election timeout becomes a candidate, increments the term, votes for itself and asks the others for votes. A node grants one vote per term. A candidate with votes from a majority becomes leader and starts sending heartbeats. Randomized timeouts make split votes rare and resolve them by retrying with a higher term.
  • Clients send commands to the leader, which appends them to its log, replicates them to followers, and marks an entry committed once a majority has stored it. Committed entries are applied to the state machine and never lost, even if the leader crashes, because a candidate must have an up-to-date log to win votes.
  • A leader cut off in a minority partition cannot commit anything, because it cannot reach a majority. When the partition heals it sees a higher term and steps down.

Paxos solves the same problem (single-value Paxos with prepare/promise then accept/accepted phases; Multi-Paxos for a log). It is harder to teach and implement; in an interview you can say "Raft and Multi-Paxos are equivalent in guarantees, Raft is easier to understand". Other names: ZAB (ZooKeeper) and Viewstamped Replication.

The model below runs elections among five nodes. It is not Raft's full protocol (no logs, no real timing), but it shows the majority rule, one vote per term, and what a partition does.

Node.js Model: majority voting, terms and a network partition

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with node:readline or process.stdin), it gets the next line from this box.

What can go wrong with leaders? Split brain and fencing tokens

Split brain means two nodes both believe they are the leader. It happens when a leader is paused (a long garbage collection, a network stall), the cluster elects a new leader, and the old one wakes up still thinking it is in charge. If both write to shared storage, data is corrupted. A timeout-based lease or lock does not fix it alone: the old holder cannot know its lease expired while it was paused.

The standard defense is a fencing token: every time the lock service grants a lock it hands out a number that only increases. The client includes the token with each write, and the storage rejects any write with a token lower than one it has already seen. The paused old leader's token is now stale, so its late write is refused. Notice where the check must live: in the resource, not in the client.

Node.js Model: a paused leader is stopped by a fencing token

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with node:readline or process.stdin), it gets the next line from this box.

Why can't you trust timestamps? Lamport and vector clocks

Physical clocks on different machines drift (milliseconds to seconds), and NTP adjustments can even move them backwards, so "the event with the later timestamp happened later" is false across machines. What matters for correctness is causality: did event A possibly influence event B?

A Lamport clock is a counter per node. Increment it before each local event or send, attach it to messages, and on receive set it to max(local, received) + 1. If A happened-before B then L(A) < L(B), but the reverse is not true: a smaller number does not prove causality, so you cannot detect concurrent events with it.

A vector clock keeps one counter per node. Compare two vectors: if every entry of one is <= the other (and they differ), one happened before the other; if neither dominates, the events are concurrent, which is a conflict a system such as Dynamo-style storage must resolve. The cost is a vector as large as the number of nodes. Google Spanner takes a different route: TrueTime exposes a clock with a known uncertainty and makes transactions wait out that uncertainty.

Node.js Model: vector clocks detect concurrent updates

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with node:readline or process.stdin), it gets the next line from this box.

What do the consistency models mean?

From strongest to weakest, in the words you should use:

  • Linearizability (strong consistency): the system behaves as if there were one copy of the data and every operation took effect at a single instant between its start and end. Once a write is acknowledged, every later read sees it. It needs coordination (consensus, or a leader plus quorum reads) and costs latency.
  • Sequential consistency: all nodes see operations in the same order, but that order need not match real time.
  • Causal consistency: operations that are causally related are seen in the same order by everyone; unrelated (concurrent) ones may be seen in different orders. A reply is never seen before the post it answers.
  • Session guarantees: read-your-writes, monotonic reads (you never see older data after seeing newer) and monotonic writes. These are cheap and fix most user-visible oddities.
  • Eventual consistency: if updates stop, all replicas eventually converge. It says nothing about what you read in the meantime.

ACID consistency (constraints hold after a transaction) is a different word with the same name; say which one you mean. For tunable systems, quorum settings R + W > N give reads that overlap the latest write (covered in NoSQL, Scaling and Caching), but quorums alone do not give linearizability when failures and concurrent writes interleave.

How do you design for failure?

Failure detection is a guess: you cannot tell a crashed node from a slow one or a partitioned one. Systems use heartbeats with a timeout, or a phi accrual detector that outputs a suspicion level instead of a yes/no. Short timeouts detect failures faster but cause false alarms; long ones slow recovery.

The fault tolerance toolbox: redundancy (replicas across failure domains: machines, racks, zones, regions), timeouts on every remote call, retries with exponential backoff and jitter for idempotent operations, circuit breakers and bulkheads (see the microservices lesson), graceful degradation (serve cached or partial results), load shedding (reject some requests to protect the rest), idempotency keys so retries are safe, and chaos testing to prove it works. Also name the failure kinds: crash-stop, crash-recovery, omission (lost messages) and Byzantine (nodes that lie), where Byzantine fault tolerance needs 3f + 1 nodes and is mostly relevant to blockchains.

Two more definitions: availability measured in "nines" (99.9% is about 8.8 hours of downtime a year, 99.99% about 53 minutes), and the difference between an SLI (a measurement, such as the fraction of requests under 300 ms), an SLO (the target for it) and an SLA (a contract with penalties).

What is distributed tracing?

In a system of dozens of services, one user request touches many of them, and ordinary logs from each service cannot show the path. Distributed tracing records it. A trace represents one request end to end and has a trace ID. It is made of spans: one span per operation (an HTTP handler, a database call), each with its own span ID, a parent span ID, a start time and a duration. The trace ID and the current span ID travel with the request in a header (the W3C traceparent header, OpenTelemetry being the standard instrumentation API). Each service creates child spans and reports them asynchronously to a collector (Jaeger, Tempo, Zipkin), which assembles the tree.

What tracing answers: where did the time go, which dependency is slow, which service caused the error. The three pillars of observability are logs, metrics (aggregated numbers) and traces; connect them by putting the trace ID into every log line (a correlation ID). Practical issues: sampling (keeping every trace is too expensive, so keep a percentage, plus all errors and slow requests) and propagation across queues and async work.

Node.js Model: propagating a trace ID and building the span tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with node:readline or process.stdin), it gets the next line from this box.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why do consensus clusters usually have an odd number of nodes?

    A decision needs a majority. Four nodes need three votes and tolerate one failure, exactly like three nodes, so the fourth node adds no tolerance.
  2. 2. In Raft, why can a leader in a minority partition not commit new entries?

    Commitment requires acknowledgment from a majority. Because any two majorities overlap, a minority-side leader can never commit something that conflicts with the majority side.
  3. 3. What problem do fencing tokens solve?

    Tokens increase with each grant, and the resource refuses any token lower than the highest it has seen, so a stale leader cannot corrupt data.
  4. 4. Two vector clocks are {A:2, B:1} and {A:1, B:2}. What is the relationship between the events?

    Neither vector dominates the other: A is higher in the first, B is higher in the second. Neither event could have seen the other.
  5. 5. In distributed tracing, what links the spans of a single request across services?

    The trace ID travels with the request, usually in the W3C traceparent header, and each span records its parent so the backend can rebuild the tree.

Summary

  • Distributed systems fail partially and unpredictably; most designs answer unreliable networks, unsynchronized clocks and uncertain failure detection.
  • Consensus (Raft, Paxos) rests on majority quorums, so safety holds while a majority is alive; use odd cluster sizes.
  • Raft elects one leader per term by majority vote, replicates a log, and commits an entry once a majority has stored it.
  • Guard against stale leaders with fencing tokens checked by the resource, and do not rely on wall-clock time; use Lamport or vector clocks for causality.
  • Know the consistency spectrum (linearizable, sequential, causal, session guarantees, eventual) and name the failure-handling toolbox.
  • Distributed tracing links spans with a propagated trace ID; combine it with logs and metrics using correlation IDs.

Next: Low-Level Design: Parking Lot, Elevator and Cache.