Distributed Systems Fundamentals

Distributed Systems Fundamentals

Why Distribution Is Hard

The fallacies of distributed computing: the network is NOT reliable, latency is NOT zero, bandwidth is NOT infinite. Partial failure — some nodes up, some down, messages delayed — is the normal operating condition.

Consensus

FLP Impossibility: in a fully asynchronous system, no deterministic algorithm can guarantee consensus if even one node can fail. Practical algorithms (Raft, Paxos) assume partial synchrony.

Raft (designed to be understandable): three roles — Leader, Follower, Candidate.

Leader election: followers time out waiting for heartbeat → become Candidate → request votes → if majority vote, become Leader → send heartbeats.

Log replication: leader appends entry → sends AppendEntries to all followers → once majority acknowledge, entry is committed → committed entries never overwritten.

Used in: etcd (Kubernetes), CockroachDB, TiKV.

Replication

Primary-replica: one node accepts writes; replicas apply WAL/change log. Synchronous (acknowledged after replica confirms — zero data loss, higher latency) vs Asynchronous (acknowledged immediately — lower latency, possible data loss on primary failure).

Multi-primary: multiple nodes accept writes; requires conflict resolution (CRDTs, last-write-wins). Enables geographic write distribution.

Consistency Models

Linearizability (strongest): every operation appears to take effect at a single point in time. Requires consensus.

Causal consistency: causally related operations seen in the same order by all nodes. Concurrent operations may be seen in different orders.

Eventual consistency: all replicas converge eventually. No guarantees on read staleness. Cassandra, DynamoDB.

Session guarantees: read-your-writes, monotonic reads — practical middle ground.

Distributed Transactions

2PC: Prepare (lock + vote yes/no) → Commit or Abort. Failure mode: coordinator crash after Prepare blocks all participants holding locks.

Sagas: sequence of local transactions; failures trigger compensating transactions (not rollbacks of others' committed state). No distributed locks. Used in microservices.

Clocks and Causality

Physical clocks drift — cannot rely on timestamps for ordering across machines.

Lamport timestamps: increment counter on each event; take max(local, message) + 1 on receive. Captures happened-before.

Vector clocks: per-node counter vector. Enables detecting concurrent updates.

Hybrid Logical Clocks (HLC): physical + logical. Used in CockroachDB, Spanner.

Idempotency Keys

Network requests can fail ambiguously (request reached server but response lost). Retrying without idempotency → double processing.

Idempotency key: client generates UUID per operation; server returns cached result for duplicate keys rather than reprocessing. Used by Stripe for payments — prevents double charges.

At-least-once vs exactly-once: at-least-once = retry freely, consumer deduplicates; exactly-once = idempotent consumer + transactional producer (Kafka transactions) or deduplication at consumer.