DBMS

Beyond Relational

CAP, Consistency and Sharding

Every read returns the most recent write.

JrCodex·8 min read

Jr Codex DBMS Notes

Level: Advanced Prerequisites: Chapter 2: The NoSQL Families Time to complete: ~20 minutes

Table of Contents

  1. The CAP Theorem, Stated Correctly
  2. What CAP Is Usually Misread As
  3. PACELC — the More Useful Version
  4. Consistency Models
  5. Partitioning Strategies
  6. Quorums
  7. Summary & Next Steps

1. The CAP Theorem, Stated Correctly

The Three Properties
─────────────────────────────────────────
  CONSISTENCY (linearizability)
    Every read returns the most recent write.
    NOT the C in ACID — a different property with
    the same name (Module 1, Chapter 4).

  AVAILABILITY
    Every request to a NON-FAILED node receives a
    non-error response.

  PARTITION TOLERANCE
    The system continues operating despite network
    messages being lost between nodes.
─────────────────────────────────────────

The Theorem
─────────────────────────────────────────
  In the presence of a network PARTITION, a
  distributed system must choose between
  CONSISTENCY and AVAILABILITY.

  That is all it says.
─────────────────────────────────────────

The Choice, Concretely
─────────────────────────────────────────
  Two nodes, A and B, and the network between them
  fails. A client writes to A.

  CHOOSE CONSISTENCY (CP)
    A refuses the write, because it cannot confirm
    B will see it. The system is UNAVAILABLE for
    that write, and correct.

  CHOOSE AVAILABILITY (AP)
    A accepts the write. B does not know about it,
    so a client reading from B gets stale data. The
    system is AVAILABLE, and inconsistent.

  There is no third option. Both nodes accepting
  divergent writes while claiming consistency is
  simply incorrect.
─────────────────────────────────────────

2. What CAP Is Usually Misread As

THE MISREADING
─────────────────────────────────────────
  "Pick two of three."

  This is wrong, and it produces nonsense like
  "we chose CA".

  PARTITIONS ARE NOT A CHOICE. Networks fail.
  Cables are cut, switches reboot, packets are
  dropped (Computer Networks Notes, Module 4).

  You cannot opt out of partition tolerance in a
  distributed system. If you drop P, you are
  describing a SINGLE-NODE system — which is a
  legitimate architecture, and not a point on this
  triangle.
─────────────────────────────────────────

The Second Misreading
─────────────────────────────────────────
  "CAP forces a permanent, system-wide choice."

  It does not. The choice applies ONLY DURING a
  partition, which is rare.

  Many systems are tunable per operation — strong
  consistency for a payment, eventual for a view
  count, in the same database (Section 6).
─────────────────────────────────────────

The Third
─────────────────────────────────────────
  "CP systems are unavailable."

  Only during partitions, and only for the affected
  partition. A CP system with a healthy network is
  fully available.

  Most CP systems have far better real-world uptime
  than the label suggests.
─────────────────────────────────────────

3. PACELC — the More Useful Version

The Extension
─────────────────────────────────────────
  IF there is a Partition (P):
      choose Availability or Consistency (A/C)
  ELSE (E), in normal operation:
      choose Latency or Consistency (L/C)
─────────────────────────────────────────

Why This Matters More
─────────────────────────────────────────
  Partitions are rare. The ELSE branch describes
  your system EVERY DAY.

  Even with a perfect network, keeping replicas
  consistent costs a round trip. So the real,
  continuous trade-off is LATENCY versus
  CONSISTENCY — which is exactly the synchronous-
  versus-asynchronous replication decision from
  Module 8, Chapter 3.

  CAP describes an emergency. PACELC describes
  Tuesday.
─────────────────────────────────────────

Classifying Real Systems
─────────────────────────────────────────
  PostgreSQL (sync replication)   PC / EC
      consistent during partitions, and pays
      latency for it normally

  Cassandra (default)             PA / EL
      available during partitions, low latency
      normally, eventually consistent

  MongoDB (default)               PC / EC
      primary-based, so a partition makes the
      minority side unavailable

  DynamoDB                        tunable
      per-request: eventually or strongly
      consistent reads
─────────────────────────────────────────

4. Consistency Models

Not a binary. A spectrum, from strongest to weakest.

The Ladder
─────────────────────────────────────────
  LINEARIZABLE (strong)
    Every operation appears to happen at a single
    instant, in real-time order. The whole system
    behaves like one machine.
    Most expensive.

  SEQUENTIAL
    All nodes see operations in the SAME order, but
    that order need not match real time.

  CAUSAL
    Causally related operations are seen in order
    everywhere; unrelated ones may differ.
    "You see a reply only after the comment it
    replies to."
    A genuinely good middle point.

  READ-YOUR-WRITES
    A client always sees its own writes. Others may
    lag.
    Fixes the most user-visible staleness bug
    (Module 8, Chapter 3).

  EVENTUAL (weakest)
    Given no new writes, replicas converge
    eventually. No ordering guarantee at all.
─────────────────────────────────────────

Choosing a Rung
─────────────────────────────────────────
  Money, inventory, bookings   ──► LINEARIZABLE
  Comment threads, messaging   ──► CAUSAL
  A user editing their profile ──► READ-YOUR-WRITES
  View counts, feeds, likes    ──► EVENTUAL

  Most applications need DIFFERENT rungs for
  different operations. Choosing one global level
  means paying for the strongest everywhere, or
  being wrong somewhere.
─────────────────────────────────────────

5. Partitioning Strategies

RANGE PARTITIONING
─────────────────────────────────────────
  Split by key ranges: A-F, G-M, N-Z.

  + RANGE QUERIES stay on one node
  - HOTSPOTS: partitioning by timestamp sends
    every new write to the newest partition, so one
    node takes all the write load

HASH PARTITIONING
─────────────────────────────────────────
  node = hash(key) % N

  + EVEN distribution, no hotspots
  - range queries must touch EVERY node
  - changing N remaps ALMOST EVERY KEY, which means
    moving nearly all the data

CONSISTENT HASHING
─────────────────────────────────────────
  Map both keys and nodes onto a ring. A key
  belongs to the next node clockwise.

  Adding or removing a node remaps only the keys
  between it and its neighbour — roughly 1/N of the
  data, rather than all of it.

  VIRTUAL NODES: give each physical node many
  positions on the ring, so load stays even and a
  departing node's share spreads across all
  remaining nodes rather than landing on one.
─────────────────────────────────────────

import hashlib, bisect
 
class ConsistentHash:
    def __init__(self, nodes, vnodes=150):
        self.ring, self.keys = {}, []
        for node in nodes:
            for i in range(vnodes):                    # VIRTUAL NODES spread the load
                h = self._hash(f"{node}:{i}")
                self.ring[h] = node
                bisect.insort(self.keys, h)
 
    def _hash(self, s):
        return int(hashlib.md5(s.encode()).hexdigest(), 16)
 
    def node_for(self, key):
        h = self._hash(key)
        i = bisect.bisect(self.keys, h) % len(self.keys)     # next node CLOCKWISE
        return self.ring[self.keys[i]]
Choosing the Partition Key
─────────────────────────────────────────
  The most consequential decision in a sharded
  system, and the hardest to change later.

  It must:
    - distribute evenly (no hotspot)
    - keep data queried together on ONE partition
    - appear in nearly every query

  Get it wrong and you either have a hot node or
  every query becomes a scatter-gather across all
  of them.
─────────────────────────────────────────

6. Quorums

The Formula
─────────────────────────────────────────
  N = replicas per item
  W = replicas that must acknowledge a WRITE
  R = replicas that must respond to a READ

  IF  R + W > N  then any read set and any write
  set OVERLAP, so a read is guaranteed to see the
  latest write. STRONG consistency.

  IF  R + W ≤ N  they may not overlap. EVENTUAL.
─────────────────────────────────────────

Tuning It
─────────────────────────────────────────
  N=3, W=3, R=1
    Fast reads, slow writes, no write availability
    if any replica is down.
    ── read-heavy, rarely written data

  N=3, W=1, R=3
    Fast writes, slow reads.
    ── write-heavy logging

  N=3, W=2, R=2
    Balanced. Survives one node down for BOTH reads
    and writes. R+W=4 > 3, so still strong.
    ── the sensible default

  N=3, W=1, R=1
    Fastest, EVENTUAL (1+1 ≤ 3).
    ── counters, caches
─────────────────────────────────────────

# Per-operation consistency — the practical point of quorums.
session.execute(
    SimpleStatement("UPDATE accounts SET balance=%s WHERE id=%s",
                    consistency_level=ConsistencyLevel.QUORUM),      # money: strong
    (new_balance, account_id))
 
session.execute(
    SimpleStatement("UPDATE page_views SET count=count+1 WHERE page=%s",
                    consistency_level=ConsistencyLevel.ONE),         # counter: fast
    (page,))
The Takeaway
─────────────────────────────────────────
  Consistency is a DIAL, set per operation, not a
  property of the database.

  This is the same conclusion as isolation levels
  (Module 7, Chapter 2): the system offers a range,
  and choosing correctly per operation is your job.
─────────────────────────────────────────

7. Summary & Next Steps

Key Takeaways

  • CAP says only that during a network partition you must choose consistency or availability; partition tolerance is not optional in a distributed system.
  • PACELC is more useful because it also covers normal operation, where the continuous trade is latency against consistency — the synchronous replication decision.
  • Consistency is a ladder from linearizable to eventual, and most applications need different rungs for different operations rather than one global setting.
  • Consistent hashing with virtual nodes remaps only about 1/N of keys when membership changes, and R + W > N is what makes a quorum read see the latest write.

Concept Check

  1. Why is "we chose CA" a meaningless statement for a distributed system?
  2. Why does PACELC describe your system more often than CAP does?
  3. With N=3, which combinations of R and W give strong consistency while surviving one node being down?

Next Chapter

→ Chapter 4: Choosing a Database

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index | Back to DBMS Index