DDIA Reading Notes - Chapter 9

Feb 24, 2025

Consistency Guarantees

  • Eventual Consistency: Replicas eventually converge but may return stale reads.
  • Stronger Consistency Models:
    • Linearizability: Operations appear instantaneously in a global order.
    • Serializability: Transactions execute in some sequential order.

Linearizability

  • Ensures: Once a write is complete, all subsequent reads must reflect it.
  • Example: Prevents users from seeing outdated sports scores after an update.
  • Compare-and-Set (CAS): Ensures atomic updates to prevent race conditions.

Linearizability vs. Serializability

  • Linearizability: Applies to single objects, ensures real-time recency.
  • Serializability: Ensures correct execution order for transactions but allows reading stale data.
  • Strict Serializability: Combines both guarantees.

When to Rely on Linearizability

  • Leader Election: Ensures only one leader exists at a time.
  • Uniqueness Guarantees: Enforces unique usernames, prevents overselling.
  • Cross-Channel Dependencies: Avoids race conditions in workflows (e.g., image processing pipelines).

Implementing Linearizable Systems

  1. Single-Leader Replication (Linearizable if reads come from the leader).
  2. Consensus Algorithms (Raft, Paxos ensure linearizability).
  3. Multi-Leader Replication (Not linearizable due to conflicting writes).
  4. Leaderless Replication (Eventual consistency, not linearizable).
  5. Quorum Reads/Writes (May still allow stale reads due to network delays).

The Cost of Linearizability

  • Trade-off: Strong consistency vs. performance & availability.
  • CAP Theorem: During network partitions, must choose between consistency and availability.
  • Performance Overhead: Coordination delays increase response time.

Ordering Guarantees

  • Causal Consistency: Ensures that dependent events are processed in the correct order.
  • Total Order vs. Partial Order:
    • Total Order: All operations have a single sequence.
    • Partial Order: Only causally related events are ordered.
  • Capturing Causality: Lamport timestamps, vector clocks track event dependencies.

Sequence Number Ordering

  • Single-Leader Replication: Assigns sequence numbers to ensure order.
  • Lamport Timestamps: Enforce causal order but don’t distinguish concurrent events.
  • Total Order Broadcast: Ensures all nodes receive operations in the same sequence.

Distributed Transactions and Consensus

Two-Phase Commit (2PC)

  • Ensures atomicity across nodes.
  • Problem: Blocking if the coordinator crashes.
  • Alternative: Consensus-based approaches (Raft, Paxos).

Fault-Tolerant Consensus

  • Consensus is required for: Leader election, atomic commits, ensuring uniqueness.
  • FLP Impossibility Theorem: Perfect consensus is impossible in asynchronous systems with failures.
  • Consensus Algorithms:
    • Raft: Simpler than Paxos, widely used in etcd, CockroachDB.
    • Zab: Used in ZooKeeper for distributed coordination.

Membership and Coordination Services

  • ZooKeeper, etcd: Provide atomic operations, leader election, failure detection.
  • Use Cases:
    • Leader Election: Ensures only one active leader.
    • Partition Assignment: Distributes partitions across nodes.
    • Service Discovery: Tracks available services dynamically.
Jiayi Li