Distributed Systems

Overview

A distributed system is a collection of independent (autonomous) computers that appears to users as a single coherent system. “Independent” means each machine has its own CPU, memory, disk, operating system, clock, and—crucially—its own ways to fail. “Single coherent system” means that despite being many machines, the system tries to present one service interface with predictable behavior (for example: “put(key, value)” and “get(key)”). The core challenge is that the machines communicate over a network that can delay, drop, duplicate, or reorder messages—so correctness and reliability must be designed in.

The Problem It Solves — what goes wrong without this concept?

If you run everything on one machine, you get simplicity: one clock, one memory space, one failure domain. But you hit hard limits:

• Scale limits: one machine can only handle so many requests per second and store so much data.
• Availability limits: when that machine goes down (hardware failure, kernel panic, deploy gone wrong), your service is down.
• Latency limits: users far away experience high latency if the service is only in one region.

Distributed systems exist to solve these, but they introduce new failure modes:

• Partial failures: one node is down while others are fine. This is harder than a total outage because the system is “half alive” and making inconsistent progress.
• Unreliable communication: the network is not a perfect wire. Timeouts don’t tell you whether the request failed or just got delayed.
• No global clock: you can’t safely assume “the latest timestamp wins” across machines because clocks drift and messages arrive out of order.

A useful analogy is a group chat with flaky internet: messages arrive late, out of order, sometimes duplicated. If you want the chat history to look consistent for everyone, you need ordering rules and conflict handling.

The Core Mental Model: one service, many machines

A distributed system is often built from these building blocks:

1. Partitioning (sharding) to scale out
2. Replication to survive failures and scale reads
3. Membership & failure detection so nodes know who’s alive
4. Routing so requests reach the right shard/replica
5. Ordering & concurrency control because clocks lie
6. Consistency model to define what “correct” means
7. Repair & conflict resolution when replicas diverge
8. Coordination (consensus) when you must agree on one truth

Not every system uses all of these, but most production-grade distributed systems use many.

Partitioning: scaling by splitting work and data

When a dataset or workload outgrows one machine, you partition it across multiple nodes.

• In a key-value store, partitioning answers: which node owns this key?
• In a job system, partitioning answers: which worker should run this task?

Common partitioning strategies:

• Range partitioning: keys in a range go to one shard (great for range queries; risk of hotspots).
• Hash partitioning: hash(key) decides shard (good distribution; range queries harder).
• Consistent hashing: a special hash partitioning approach that minimizes reshuffling when nodes join/leave.

Analogy: consistent hashing is like a circular seating arrangement at a round table. When a person (node) leaves, only the adjacent seats need to be reassigned—not the whole table.

flowchart LR
  C[Client] --> R[Router / Coordinator]
  R --> S1[Shard 1]
  R --> S2[Shard 2]
  R --> S3[Shard 3]

  subgraph Data
    S1 --> D1[(Keys A-F)]
    S2 --> D2[(Keys G-N)]
    S3 --> D3[(Keys O-Z)]
  end

Trade-off: partitioning improves throughput and storage capacity, but makes operations that span partitions (joins, transactions, aggregations) more complex.

Replication: surviving failures and scaling reads

Partitioning alone makes failures worse: if shard 2 dies, keys on shard 2 are unavailable. Replication fixes that by keeping multiple copies of data.

Replication patterns:

• Leader–follower (primary–replica): one leader accepts writes; followers replicate (common in MySQL and PostgreSQL streaming replication).
• Multi-leader: multiple leaders accept writes (more available; conflict resolution required).
• Leaderless / quorum-based: clients write to multiple replicas and use quorums to decide success (Dynamo-style; Cassandra-style).

flowchart TB
  C[Client] --> L[Leader]
  L --> F1[Follower 1]
  L --> F2[Follower 2]
  L --> F3[Follower 3]

  L --- WAL[(Write-ahead log)]

Why replicate?

• Fault tolerance: if one node dies, another has the data.
• Read scaling: serve reads from replicas.
• Maintenance: do rolling upgrades without full downtime.

Trade-off: replication forces you to answer: when is a write “committed”? and what should reads return if replicas disagree?

Membership and failure detection: who’s in the cluster?

Nodes must continuously answer:

• Who are the current members?
• Which nodes are healthy?
• Where did partitions move after scaling or failures?

A common approach is gossip-based membership (used by Cassandra-style systems). Gossip works like rumor spreading: each node periodically shares what it knows with a few others, and the cluster converges.

Analogy: a workplace rumor spreads quickly without a single coordinator, but it may take a short time for everyone to hear the latest update.

Trade-off: gossip is scalable and robust, but not instantly consistent. For critical metadata (like “who is the leader?”), systems often rely on consensus instead.

Request routing: getting to the right shard and replica

Once data is partitioned and replicated, a request must be routed correctly.

Common routing designs:

• Client-side routing: the client library knows the partition map (fast, but clients must update when topology changes).
• Coordinator node: client hits any node; that node routes internally (simpler clients, but adds an extra hop).
• Load balancer + service discovery: common for stateless microservices.

sequenceDiagram
  participant Client
  participant LB as Load Balancer
  participant Coord as Coordinator
  participant ReplicaA as Replica A
  participant ReplicaB as Replica B

  Client->>LB: GET key=K
  LB->>Coord: forward request
  Coord->>ReplicaA: read K
  ReplicaA-->>Coord: value
  Coord-->>Client: value

Trade-off: routing must adapt to rebalancing and failures. Stale routing info causes retries, redirects, or “wrong shard” errors.

Time, ordering, and concurrency: because clocks lie

In a single machine, “time” is mostly consistent. In a distributed system:

• clocks drift
• NTP can step time backward/forward
• messages arrive out of order

So distributed systems rely on logical ordering rather than wall-clock time.

Lamport’s key idea is happens-before: if event A could have influenced event B (e.g., A sends a message that B receives), then A happens-before B. This creates a partial order—some events are incomparable.

Why you care:

• Without ordering rules, you can get anomalies like “a read returns older data than a previous read” or “two writes overwrite each other incorrectly.”

Analogy: two people editing a shared document while offline. When they reconnect, you need a merge strategy—timestamps alone aren’t trustworthy.

Consistency models and CAP: defining “correct” under failure

A consistency model defines what results reads are allowed to return.

Two important ends of the spectrum:

• Strong consistency / linearizability: once a write completes, all future reads see it.
• Eventual consistency: replicas converge over time; reads may be stale.

The CAP theorem (in its practical interpretation) says: when a network partition happens, a system must choose between:

• Consistency (C): act like a single up-to-date copy
• Availability (A): respond to requests (even if some nodes can’t communicate)

Partition tolerance (P) isn’t optional in real distributed systems; partitions can happen. So during partitions, systems often degrade:

• CP-ish behavior: reject/timeout writes to preserve a single truth
• AP-ish behavior: accept writes on both sides and reconcile later

Important nuance: CAP is not “pick two forever.” Many systems shift behavior based on which endpoints are partitioned and which operations are being performed.

Quorums and “tunable consistency”: a practical middle ground

Dynamo-style systems popularized quorum reads/writes.

Let:

• N = replication factor (number of replicas)
• W = number of replicas that must acknowledge a write
• R = number of replicas consulted for a read

A common rule of thumb: if R + W > N, then reads and writes overlap on at least one replica, which helps avoid stale reads in many cases.

What it buys you:

• Better odds that a read sees the latest write (especially if replicas are healthy)

What it does not guarantee by itself:

• True linearizability in the presence of clock skew, concurrent writes, or sloppy quorums
• Safety if the system can acknowledge writes without ensuring a single global order

This is why “tunable consistency” (like Cassandra’s consistency levels) is powerful but requires careful application-level thinking.

Conflict resolution and repair: making replicas converge

If you accept writes in multiple places (or allow writes during partitions), replicas can diverge.

Common repair/conflict tools:

• Versioning (e.g., vector clocks in classic Dynamo) to detect concurrent writes
• Read repair: when a read notices replicas disagree, it triggers an update to fix stale replicas
• Anti-entropy: background reconciliation (e.g., Merkle-tree-based comparisons)
• Hinted handoff (Cassandra): if a replica is down, a coordinator stores a “hint” and replays it when the replica returns

Analogy: warehouse inventory replicated across locations. If one warehouse is temporarily offline, you might keep selling (availability) and later reconcile counts (repair). But you risk overselling unless your conflict rules are correct.

Trade-off: repair makes the system eventually converge, but it can increase background load and can surface tricky application conflicts (“which update wins?”).

Coordination and consensus: when you must agree

Some problems require one agreed-upon order of operations:

• leader election
• cluster membership changes
• distributed locks
• critical metadata (like “which node owns shard X?”)

This is where consensus comes in, often implemented as a replicated log (e.g., Raft).

At a high level, Raft:

• elects a leader
• leader appends commands to a log
• replicates log entries to followers
• once a majority acknowledges, the entry is committed and applied

sequenceDiagram
  participant L as Leader
  participant F1 as Follower 1
  participant F2 as Follower 2

  L->>F1: AppendEntries(log idx=10)
  L->>F2: AppendEntries(log idx=10)
  F1-->>L: ACK
  F2-->>L: ACK
  L-->>L: Commit idx=10 (majority)

Production grounding: etcd (used by Kubernetes) uses Raft. Its latency is strongly tied to network latency (for quorum acknowledgements) and disk latency (for durable log writes).

Trade-off: consensus gives strong guarantees, but it costs latency and reduces availability during partitions (because you need a majority).

Reliability patterns: surviving the network you actually have

Even “simple” request/response becomes tricky when messages can be lost and timeouts are ambiguous.

Common patterns you’ll see everywhere:

• Timeouts (always bounded waits)
• Retries with exponential backoff + jitter (avoid retry storms)
• Idempotency keys (so retries don’t double-charge a credit card)
• Circuit breakers (stop calling a failing dependency; prevent cascading failure)
• Bulkheads (resource isolation: separate thread pools/queues per dependency)

These aren’t optional polish—they’re often the difference between a small incident and a full outage.

When to Use / When Not to Use

Use distributed systems when you have clear needs like:

• Scale: one machine can’t meet throughput/storage requirements.
• High availability: downtime is expensive; you need redundancy.
• Geo latency: you need data/services closer to users.
• Operational resilience: rolling upgrades, fault isolation, and capacity elasticity.

Avoid (or delay) distributed designs when:

• Your workload comfortably fits on one machine or one database instance.
• You need simple correctness and the team can’t afford the operational complexity.
• Your primary bottleneck is not compute/storage but product iteration speed.

A practical rule: start with the simplest architecture that meets requirements, and distribute only the parts that truly need it (often read paths, caching, or asynchronous pipelines first).

Real-World Examples

Mapping the concept to production systems:

• DynamoDB / Dynamo-style systems: popularized partitioning (consistent hashing), replication, quorum-style reads/writes, and conflict/repair mechanisms to stay highly available.
• Cassandra: Dynamo-inspired design with consistent hashing, gossip membership, multi-master replication, and tunable consistency.
• Akamai CDN: a globally distributed system that reduces latency by serving content from many edge locations (distribution + replication).
• Memcached (ketama): uses consistent hashing to distribute cache keys across nodes with minimal reshuffling.
• etcd (Raft): a strongly consistent coordination/config store used by Kubernetes; consensus is central to correctness.

Common Misconceptions

• “The network is reliable enough.” It isn’t. Design for loss, delay, duplication, and reordering.
• “CAP means pick two.” CAP is about an impossibility during partitions; real systems often degrade selectively.
• “Eventual consistency means eventually correct no matter what.” Only if you have repair and a resolvable conflict strategy.
• “Consensus solves distributed systems.” It solves agreement, not idempotency, backpressure, hotspots, or data modeling.
• “Retries are safe.” Retries can duplicate side effects and amplify load unless you design for them.

Interview Connection

This topic shows up in:

• System design interviews (designing scalable, reliable services)
• Distributed systems interviews (consistency, replication, consensus, failure models)
• General CS interviews (concurrency, ordering, reasoning about correctness)

Sample interview questions:

1. Define a distributed system. What does “appears as a single coherent system” mean in practice?
2. You have replication factor N=3. Compare R=1, W=1 vs R=2, W=2. What failures can each tolerate, and what anomalies can still happen?
3. Design a globally available key-value store. Where do you need consensus, and where can you accept eventual consistency? Explain what happens during a network partition.

If your goal is specifically “patterns of distributed systems” for interviews, a good next path is: sharding → consistent hashing → replication → quorums → CAP/consistency models → consensus (Raft) → reliability patterns (timeouts/retries/idempotency/circuit breakers).