Phase 4: Reads, Writes, Tunable Consistency & Quorum Mathematics¶

Audience: Principal Distributed Systems Architect & High-Throughput Database Engineer
Source References: src/java/org/apache/cassandra/service/StorageProxy.java, src/java/org/apache/cassandra/db/ReadCommand.java

1. Coordinator Routing & The Token-Aware Policy¶

Any node in a Cassandra cluster can act as a Coordinator for any client request. However, routing efficiency depends on client driver policies:

┌────────────────────────────────────────────────────────────────────────┐
│ Client Query: INSERT INTO orders WHERE id = 101                       │
└───────────────────────────────────┬────────────────────────────────────┘
                                    │
    ┌───────────────────────────────┴───────────────────────────────┐
    ▼ (Random / Round-Robin Policy)                                 ▼ (Token-Aware Policy)
[Non-Replica Coordinator Node]                              [Natural Replica Coordinator Node]
Must route network RPCs across ring to Replicas.           Serves write locally; streams RPCs
Adds extra WAN/LAN hop! Latency: +2ms to +10ms.            only to remaining replicas.

1.1 The Dynamic Snitch¶

Cassandra uses a Dynamic Snitch (org.apache.cassandra.locator.DynamicEndpointSnitch) that tracks latencies and error rates for every peer node. When reading, the coordinator automatically directs full data requests to the fastest, least loaded replica.

2. Cellular Read Path: Multi-SSTable Reconciliation¶

A read operation in Cassandra is fundamentally a merge-sort reconciliation across multiple storage tiers:

Read Query Execution across Memory & Disk:
1. Scan Active Memtable in RAM.
2. Scan Flushing Memtables in RAM.
3. Check Key Cache (Maps partition key to exact byte offset in Index.db).
4. Evaluate Bloom Filters (Filter.db) for all on-disk SSTables:
   - Eliminates SSTables that definitely do not hold the partition.
5. Search Index Summary (Summary.db) & Partition Index (Index.db).
6. Decompress and read matching data blocks from Data.db.
7. Merge all retrieved cell versions:
   - Compare timestamps on every individual column cell.
   - Highest timestamp wins!
   - Tombstones with higher timestamps overwrite older data cells.

3. Read Repair & Digest Mismatches¶

To balance network bandwidth and query latency, the coordinator does NOT request full data payloads from all replicas:

Coordinator Read Execution with Quorum:
1. Full Data Request: Sent to the FASTEST replica.
2. Digest Request (SHA-1 Hash): Sent to remaining (R - 1) replicas.
3. Compare Hashes:
   - If Hashes Match: Return data to client immediately.
   - If Hashes Mismatch: Trigger Reconciliation Phase!

Digest Mismatch Reconciliation Protocol:
[Replica 1: Full Data] ──► { user: 1, email: "alice@new.com", ts: 500 }
[Replica 2: Digest]    ──► Hash 0xA1B2 (Digest Mismatch!)
           │
           ▼ (Coordinator requests full data from Replica 2)
[Replica 2: Full Data] ──► { user: 1, email: "alice@old.com", ts: 400 }
           │
           ▼
[Coordinator Reconciliation Engine]
- Cell ts 500 > ts 400 ===> email: "alice@new.com" is returned to client!
- Asynchronously sends a background WRITE to Replica 2:
  "Update user 1 email to 'alice@new.com' with ts 500" (Read Repair).

4. Tunable Consistency Levels & Quorum Mathematics¶

Cassandra enables per-query tunable consistency:

Consistency Level Spectrum:
[ ANY ] ──► [ ONE ] ──► [ LOCAL_QUORUM ] ──► [ QUORUM ] ──► [ ALL ]
(Lowest Latency,                                       (Highest Latency,
 Weakest Consistency)                                   Strictest Durability)

Level	Definition	Failure Tolerance ($N = 3$)
`ONE`	Acknowledged by any single replica.	Can survive 2 dead nodes.
`LOCAL_QUORUM`	Acknowledged by a majority of replicas in the local datacenter.	Can survive 1 dead node in local DC.
`QUORUM`	Acknowledged by a majority across all datacenters.	Can survive $\lfloor N/2 \rfloor$ dead nodes cluster-wide.
`ALL`	Acknowledged by all $N$ replicas.	Zero failure tolerance (1 dead node fails write).
`ANY`	Acknowledged even if only written to a Hinted Handoff buffer.	Writes succeed even if all natural replicas are dead!

5. The Strong Consistency Mathematical Proof¶

The classic distributed systems equation for strong consistency is: $$R + W > N$$ Where: - $R$ = Read Consistency Level (Number of nodes responding) - $W$ = Write Consistency Level (Number of nodes acknowledging) - $N$ = Replication Factor (Total number of replicas)

5.1 Mathematical Pigeonhole Principle Proof¶

Assume $N = 3$ and we configure: - Write Consistency: LOCAL_QUORUM ($W = \lfloor 3/2 \rfloor + 1 = \mathbf{2}$) - Read Consistency: LOCAL_QUORUM ($R = \lfloor 3/2 \rfloor + 1 = \mathbf{2}$)

\[R + W = 2 + 2 = 4$$ $$4 > 3 \quad (R + W > N)\]

By the Pigeonhole Principle, any read set of 2 nodes and any write set of 2 nodes MUST overlap by at least 1 node: $$\{ \text{Node A}, \text{Node B} \} \cap \{ \text{Node B}, \text{Node C} \} = \{ \mathbf{\text{Node B}} \}$$

Node B is guaranteed to have received the write mutation. Because Cassandra reconciles cells by timestamp, the coordinator will observe Node B's newer timestamp and return the strongly consistent value, completely preventing stale reads without distributed locks!