🧠 Achieving Global Consistency in Distributed Databases using Paxos and TrueTime

Making transactions globally visible in distributed systems that require strong consistency is the hard part. Databases like Google Spanner solve this using Paxos-based consensus and TrueTime to maintain precise timestamps and order across replicas.

The following diagram breaks down a write transaction in 3 Paxos phases and shows how replicas agree, commit, and eventually reach global visibility — even when one of the replicas initially rejects the proposal.

📌 Phase-by-Phase Breakdown

🔹 Phase 1: Proposal

• The client initiates a transaction (e.g., write $100).
• The leader replica (A):
  • Fetches time using TrueTime.now() which returns an interval like [100ms, 105ms].
  • Proposes the transaction with a timestamp tc = 105ms to all replicas.

Each replica:

• Validates the proposal:
  • Ensures timestamp monotonicity: tc >= lastCommittedTc
  • Validates that tc is within the returned TrueTime.now() range
  • Checks for:
    • No conflicting locks
    • Sufficient memory/disk
    • Membership in Paxos group
• Writes the proposal to the WAL (Write-Ahead Log)
• Sends acceptance or rejection

ℹ️ Replica C rejects the proposal due to timestamp being earlier than its last committed time.

🔹 Phase 2: Acceptance

• The leader collects responses from replicas.
• Once quorum is achieved (e.g., from Replica B and Replica D), the leader:
  • Marks the transaction as committed
  • Sends commit notifications to all replicas

Each replica:

• Updates its WAL
• Applies the changes

✅ Even Replica C, which initially rejected, receives the commit notification, revalidates, and commits the transaction.

🔹 Phase 3: Commit

• The transaction is now committed and visible across all replicas.
• Replicas apply the transaction even if they originally rejected the proposal.
• Replica C shows this behavior:
  • Initially rejected the proposal
  • Later accepted the commit notification
  • Updated WAL and applied the transaction

🌍 Global Visibility

• Once all replicas wait for a short “commit wait” duration (e.g., 5ms), the transaction becomes globally visible.
• Global visibility is calculated as:

When to Choose Spanner