LabHub

Blog

The Essential Difficulty of Distributed Systems — CAP, PACELC, Raft/Paxos, Vector Clock, Saga, Event Sourcing (2025)

2026-04-15 · 13 min read · #distributed-systems#cap-theorem#pacelc#raft#paxos#vector-clock#lamport-clock#saga-pattern#event-sourcing#spanner#cockroachdb#consensus

한국어English日本語

Why Distributed Systems Now — In 2026, You Can't Avoid It

Until 2015, "distributed systems were for Netflix and Google." In 2026, even 3-person startups deal with them.

Distributed systems are no longer a choice — they are a condition. Yet it remains the most misunderstood topic in the industry. By the end of this article, you'll see why "we chose CP" is a nearly empty statement.

Part 1 — Why Distribution Is Essentially Hard

The 8 Fallacies of Distributed Computing

Peter Deutsch (Sun, 1994). Still valid 30 years later:

  1. The network is reliable — packets get dropped.
  2. Latency is zero — speed of light is finite (NY-Sydney RTT ~200ms).
  3. Bandwidth is infinite.
  4. The network is secure — MITM, DNS hijacking, BGP hijacking happen.
  5. Topology doesn't change.
  6. There is one administrator.
  7. Transport cost is zero — cloud egress bills prove otherwise.
  8. The network is homogeneous — Ethernet, WiFi, satellite, 5G under one TCP/IP skin.

99% of distributed systems papers address problems caused by these being false.

Two Processes Can't Agree on "Now"

On one machine, now() is clear. On two machines? Fundamentally uncertain.

Hence in distributed systems, event order is determined by logical time, not absolute time — Lamport's 1978 insight.

Part 2 — Rereading the CAP Theorem

Original Definition (Brewer 2000 / Gilbert & Lynch 2002)

"During a network Partition (P), a system can guarantee only one of Consistency (C) or Availability (A)."

Three common misconceptions:

Misconception 1: "Choose CP or AP"

Wrong. Without partitions, both C and A are achievable. CAP speaks only about the trade-off during a partition. Brewer clarified this in 2012's "CAP Twelve Years Later":

"The 'two of three' formulation was always misleading. In reality, the 'choice' is only relevant during partitions."

Misconception 2: "Consistency = C in ACID"

Wrong. CAP's C is Linearizability (a single object, single operation appears atomic). ACID's C means "no constraint violations" — a different concept.

Misconception 3: "Availability = service doesn't die"

Wrong. CAP's A requires every request receives a non-error response — far stricter than 99.99% uptime.

PACELC — What CAP Missed

Daniel Abadi (2010): "During Partition, A vs C; Else, Latency vs Consistency."

SystemOn PartitionNormal
DynamoDB (default)PAEL (low latency, weak consistency)
CassandraPAEL
MongoDBPA/PC (config)EC
HBasePCEC
PostgreSQL (single)N/AEC
SpannerPCEC (TrueTime offsets L)

PACELC matters because normal operation is 99.99% of the user experience. "We're CP" tells you nothing about the other 99.99%.

Consistency Model Spectrum

From strongest to weakest:

  1. Linearizable (Strong) — appears as a single machine to outside observers. Most expensive.
  2. Sequential — all processes see the same order; real-time order not guaranteed.
  3. Causal — causally related events are ordered (Vector Clock).
  4. Read-Your-Writes — I see my own writes immediately.
  5. Monotonic Reads — once seen, never see a staler value.
  6. Eventual — converges given enough time.

Most apps don't need Linearizable. Causal + Read-Your-Writes is usually enough.

Part 3 — Time and Order — Lamport to HLC

Lamport Clock (1978)

Leslie Lamport's "Time, Clocks, and the Ordering of Events in a Distributed System" — the most important distributed computing paper.

1. Each node maintains a monotonic local counter L.
2. Local event: L = L + 1
3. Send: L = L + 1, attach L to message
4. Receive: L = max(L_local, L_message) + 1

Limit: captures Happens-Before only partially. Total order yes, causal order no.

Vector Clock (Fidge, Mattern 1988)

Each node maintains counters for all nodes as a vector.

Node A: [A=3, B=1, C=0]
Node B: [A=2, B=4, C=0]

On send from A to B, attach A's vector.
B updates with element-wise max.

Compare V1, V2:
- V1 <= V2 element-wise: V1 happens-before V2
- Neither: concurrent

Used in early DynamoDB, Riak, Cassandra conflict detection. Downside: vector size grows with node count.

HLC — Hybrid Logical Clock (2014)

Hybrid of physical and logical time. Used by CockroachDB, MongoDB 4.0+, YugabyteDB.

(wall_time, logical_counter)

Safe against NTP drift, human-readable timestamps, preserves causal order.

TrueTime — Google Spanner's Secret Weapon (2012)

Atomic clocks + GPS in every datacenter. API:

TT.now() -> { earliest: t1, latest: t2 }  # uncertainty interval
TT.after(t)  # is t definitely in the past?
TT.before(t) # is t definitely in the future?

Spanner commit:

1. Choose commit timestamp s (after TT.now().latest)
2. Wait until s is definitely past (commit wait) -- usually under 7ms
3. Respond

Commit wait delivers global External Consistency. Only production distributed DB that depends on hardware (atomic clocks). AWS Time Sync (2023, microsecond-precision) now approaches TrueTime without custom hardware.

Part 4 — Consensus — Paxos and Raft

FLP Impossibility (1985)

Fischer, Lynch, Paterson: async network + any process may fail → no deterministic consensus algorithm exists.

How do Paxos/Raft work then? They sidestep via timeouts + randomization. Not 100% deterministic, but converge in practice.

Paxos (Lamport, submitted 1989, published 1998)

"The Part-Time Parliament." The Greek-island parliament metaphor caused reviewers to reject it; publication delayed 9 years. Infamous for being "incomprehensible."

Roles:

Two phases:

Phase 1 (Prepare):
  Proposer -> Acceptors: "Will you accept proposal n?"
  Acceptor -> Proposer: "Yes if n > any prior; returns prior accepted."

Phase 2 (Accept):
  Proposer -> Acceptor: "Accept proposal n with value v"
  (v = most recent accepted value seen, or proposer's choice)
  Acceptor -> Proposer: "Accept/reject"

Majority acceptance = value chosen.

Why notorious:

  1. Too many variants (Multi-Paxos, Fast Paxos, Generalized Paxos).
  2. Paper style not engineer-friendly.
  3. Implementation edge cases not documented.

Used in Google Chubby, early ZooKeeper, Megastore, Spanner.

Raft (Ongaro & Ousterhout, 2014)

Stanford PhD Diego Ongaro created Raft "because Paxos is too hard." Paper title: "In Search of an Understandable Consensus Algorithm."

Decomposed into three sub-problems:

1. Leader Election

2. Log Replication

3. Safety

Systems using Raft: etcd (Kubernetes), Consul, TiKV/TiDB, CockroachDB, NATS JetStream, Redpanda, Cloudflare Durable Objects.

Paxos = proven theory. Raft = practical engineering. 90% of 2020s-era new systems use Raft.

Multi-Paxos, EPaxos, Flexible Paxos

Part 5 — Transactions — 2PC, 3PC, Saga

2PC (Two-Phase Commit)

Simplest and most dangerous transaction protocol.

Phase 1 (Prepare):
  Coordinator -> Participants: "Can commit?"
  Participants -> Coordinator: "Yes / No"

Phase 2 (Commit):
  All Yes -> "Commit!"
  Any No  -> "Abort!"

Fatal flaw: if Coordinator dies right before Phase 2, participants block indefinitely. Only legacy XA setups (DB2, Oracle RAC) use 2PC in production.

3PC — adds a phase to avoid blocking, but still fails under network partition. Rarely used.

Saga Pattern (Garcia-Molina & Salem, 1987)

Decompose a long transaction into local transactions + compensating transactions.

Order -> Payment -> Inventory -> Shipping

On failure, compensate in reverse:
Shipping fail -> restore inventory -> refund payment -> cancel order

Two styles:

2020s mainstream:

Saga's limit: no Isolation. Intermediate state is externally visible; mitigated by "semantic locks."

TCC (Try-Confirm-Cancel)

From Alibaba microservices. Three phases: resource reservation (Try), confirm, cancel.

Part 6 — Event Sourcing + CQRS

Event Sourcing

"Store the sequence of events, not the state."

[current state: balance $100]  -- traditional

[events: +$50, -$20, +$70]  -- Event Sourcing
-> replay to $100

Pros: perfect audit trail, time travel, natural event integration. Cons: needs snapshots, schema evolution is hard, querying current state is expensive (requires CQRS).

CQRS

Physically separate write and read models.

Command -> Write Model (Event Store) -> events
                        -> Read Model (Materialized View)
                        -> Read Model (ElasticSearch)
                        -> Read Model (Redis)
Query   -> Read Models

Powerful but complexity explodes. Don't apply to simple CRUD.

Mainstream: EventStoreDB, Kafka + ksqlDB, Axon Framework (Java), Marten + PostgreSQL JSONB (.NET).

Outbox Pattern — the Exactly-Once Secret

Atomic "DB commit + message publish"?

Naive (wrong):

1. DB commit
2. Kafka publish

Step 2 failure breaks consistency. Reverse order has same problem.

Outbox Pattern:

BEGIN;
  INSERT INTO orders (...);
  INSERT INTO outbox (event_type, payload) VALUES (...);
COMMIT;

-- A separate process polls outbox and publishes to Kafka.
-- On success, delete or mark the outbox row.

Debezium (Kafka Connect CDC) automates this: PostgreSQL WAL -> Kafka stream.

Part 7 — Exactly-Once Semantics — Does It Exist?

Three Meanings of "Exactly Once"

  1. Message transmission ExO: fundamentally impossible (Two Generals Problem).
  2. Message processing ExO: achievable via dedup + idempotency.
  3. End effect ExO: consumer-side idempotency is the key.

At-Least-Once + Idempotency = Effective Exactly-Once

Kafka's official guideline. Assume producer duplicates; design idempotent consumers.

INSERT INTO processed_events (event_id, result)
VALUES ('evt-123', ...)
ON CONFLICT (event_id) DO NOTHING;

Kafka Transactional Producer (2017+)

producer.initTransactions();
producer.beginTransaction();
producer.send(record1);
producer.send(record2);
producer.commitTransaction();

Atomic partition/offset commit + consumer isolation.level=read_committed = Exactly-Once, provided producer/consumer/broker configs align.

Part 8 — Production Distributed DBs — Spanner, CockroachDB, TiDB, YugabyteDB

Google Spanner

CockroachDB (2015)

"Spanner open-sourced." Ex-Google engineers.

Switched to BSL license in 2022, some backlash. Series F $278M in 2024 accelerated adoption.

TiDB (PingCAP, 2016)

Chinese origin.

YugabyteDB (2016)

Ex-Facebook/Nutanix founders.

Part 9 — Streaming Distribution — Kafka, Pulsar, Redpanda

Kafka

Pulsar (Apache, Yahoo 2016)

Redpanda (2019)

Part 10 — Real Failure Cases

1. Roblox 73-hour Outage (Oct 2021)

Cause: Consul's BoltDB writeback contention -> write stalls -> leader election blocked -> total outage. Lesson: background compaction in KV stores affects consensus.

2. GitLab Data Loss (Jan 2017)

Cause: engineer ran rm -rf on primary. All 5 backups failed (misconfigured/empty/stale). Lesson: "we have backups" means nothing without verified restores.

3. Knight Capital $440M in 45 min (2012)

Cause: deploy applied new code to 1 of 8 servers. Old code triggered unlimited buys. Lesson: deploy atomicity failure = distributed inconsistency = economic disaster.

4. Cloudflare 2022 Regex Outage

Cause: one regex pinned CPU at 100% -> all edges down. Lesson: availability equals the atomic blast radius of the weakest link.

5. AWS us-east-1 DynamoDB 2015

Cause: metadata service overload -> table-list failures -> cascading failures. Lesson: "everything as a service" can become a distributed SPOF.

Part 11 — Practical Checklist (12 items)

  1. Speak PACELC, not CAP — steady-state dominates.
  2. Exactly-Once is a myth — design At-Least-Once + idempotency.
  3. Don't trust clocks — use HLC/TrueTime-based DBs or Lamport clocks.
  4. Don't introduce new 2PC — use Saga or Outbox.
  5. For consensus, use Raft — via etcd/Consul/proven libs; don't roll your own.
  6. Systems that depend on leaders must handle "no leader" periods.
  7. Understand quorum sizes — N=3 tolerates only 1 failure.
  8. Retries always need exponential backoff + jitter.
  9. Design cache invalidation upfront — retrofitting is hell.
  10. No distribution without observability — tracing/metrics/logs trio.
  11. Adopt Chaos Engineering — inject partitions deliberately.
  12. Practice data recovery regularly — GitLab can happen again.

Part 12 — 10 Anti-Patterns

  1. Saying "we chose CP" — CAP misunderstood.
  2. Single coordinator — guaranteed SPOF.
  3. Distributed locks for business logic — usually solvable via idempotency.
  4. Local clocks for ordering — NTP drift breeds bugs.
  5. Transactions across microservice boundaries — redesign with Saga/Outbox.
  6. Retries without timeouts — amplify outages.
  7. Distributed monolith — many services, all deployed together.
  8. Testing only locally — distributed bugs live in latency.
  9. Calling single-leader DB with replicas "horizontal scaling."
  10. Hiding every inconsistency behind "eventual consistency" — users don't understand "eventual."

Part 13 — Learning Resources

Closing — Distributed Systems Is Philosophy

Lamport's famous definition:

"A distributed system is one in which the failure of a computer you didn't even know existed can render your own computer unusable."

Distributed systems is the art of producing trustworthy results in an uncontrolled world. There is no perfection — only trade-offs. Make those trade-offs explicitly and consciously, and you can handle near-infinite scale.

In 2026, every engineer writes distributed code. Most just don't realize it.

Coming Next — "Database Internals Fully Dissected" — B-Tree, LSM, WAL, MVCC, Vacuum, Replication, Index Secrets

This series covered distribution "above." Next: distribution "below" — the heart of a single DB: B-Tree vs LSM, WAL, MVCC internals, Vacuum/Compaction, index structures (BRIN, GIN, GiST, HNSW), query planner, replication internals, partitioning strategies. The full answer to "why does a DB get slow?" — next post.

Read the original: https://www.youngju.dev/blog/culture/2026-04-15-distributed-systems-cap-pacelc-raft-paxos-vector-clock-saga-event-sourcing-spanner-deep-dive-guide-2025.en

Comments

No comments yet.

Sign in to leave a comment