Skip to content
All articles

Cassandra Internals: Merkle Trees, Paxos & Lightweight Transactions

Dean Jain

Dean Jain

Senior Staff Software Engineer · Enterprise AI, Data & Cloud Architect

· 5 min read

CassandraDistributed SystemsConsistencyNoSQL
---
config:
  theme: neutral
  fontSize: 16
---
flowchart LR
    CL["Client"]:::neutral --> CO["Coordinator<br/>(any node)"]:::gate
    CO --> R1["Replica"]:::server
    CO --> R2["Replica"]:::server
    CO --> R3["Replica"]:::server
    classDef neutral fill:#FFFFFF,stroke:#333333,stroke-width:1px,color:#111111
    classDef gate fill:#F0F0F0,stroke:#333333,stroke-width:1px,color:#111111
    classDef server fill:#DAE8FC,stroke:#333333,stroke-width:1px,color:#111111

Figure 1: No master a client hits any node (the coordinator), which forwards to the replicas. Consistency level decides how many must respond.

Cassandra’s defining architectural choice is that it has no leader. Every node is equal; a client connects to any node, which becomes the coordinator for that query. That’s what gives Cassandra its legendary availability and linear scalability there’s no master to be a bottleneck or single point of failure. But it raises an obvious question: without a coordinator-of-record, how does the data stay consistent? The answer is three mechanisms working together tunable consistency, Merkle-tree repair, and Paxos. Understanding them explains both Cassandra’s power and its sharp edges.

Summary

  • Leaderless by design. Any node can coordinate a query, forwarding reads/writes to the replicas. No master, no single point of failure.
  • Consistency is tunable per query. You choose how many replicas must respond ONE, QUORUM, ALL trading latency for assurance on each read and write.
  • Merkle trees repair drift. Anti-entropy uses hash trees to efficiently compare replicas and fix only the data blocks that differ.
  • Strong consistency isn’t enough for read-then-write. Race conditions need linearizable consistency provided by lightweight transactions (LWT).
  • LWT runs on Paxos and costs four round-trips far pricier than a normal write. Use it sparingly, only where you truly need check-and-set.

1. Leaderless reads and writes, with tunable consistency

When a client connects to a node, that node becomes the coordinator it identifies which nodes are replicas for the data and forwards the query to them. For a write, the coordinator contacts the replicas and considers the write successful once enough of them acknowledge it. For a read, it contacts enough replicas to satisfy the required consistency and returns the data.

“Enough” is the key word, and it’s your choice on every single query via the consistency level:

  • ONE / TWO / THREE only that many replicas must respond. Lowest latency, weakest guarantee.
  • QUORUM a majority must respond. The common balance of consistency and availability.
  • ALL every replica must respond. Strongest guarantee, least available (one slow node stalls the query).

This is Cassandra’s tunable consistency: a higher level means more nodes must agree, giving more assurance the replicas hold the same value at the cost of latency and availability. You make the trade per operation, so a critical write can use QUORUM while a best-effort metric uses ONE. There’s no global “consistency setting” to agonize over; there’s a dial you turn for each query based on what that query actually needs.

2. Merkle trees: repairing drift efficiently

Because writes can succeed at fewer than all replicas (anything below ALL), replicas inevitably drift one node missed a write, another was down. Cassandra fixes this in the background with anti-entropy repair, and the clever part is how it compares replicas without shipping entire datasets around: the Merkle tree (a hash tree).

---
config:
  theme: neutral
  fontSize: 16
---
flowchart TD
    ROOT["Root hash<br/>(summarizes everything)"]:::gov
    ROOT --> H1["hash of left half"]:::gate
    ROOT --> H2["hash of right half"]:::gate
    H1 --> D1["data block"]:::obs
    H1 --> D2["data block"]:::obs
    H2 --> D3["data block"]:::obs
    H2 --> D4["data block"]:::obs
    classDef gov fill:#FFFFFF,stroke:#333333,stroke-width:1px,color:#111111
    classDef gate fill:#F0F0F0,stroke:#333333,stroke-width:1px,color:#111111
    classDef obs fill:#DAE8FC,stroke:#333333,stroke-width:1px,color:#111111

Figure 2: A Merkle tree leaves are data blocks, every parent is a hash of its children. Compare roots; if they match, the data matches.

A Merkle tree is a binary tree where the leaves are data blocks and every parent node is a hash of its child nodes, so the root hash is a tiny summary of a huge dataset. Two replicas compare trees top-down: if the root hashes match, the data is identical done, no transfer needed. If they differ, they walk down only the branches that disagree, pinpointing the exact blocks that drifted and exchanging only those.

The elegance is the efficiency: instead of comparing terabytes row by row, two nodes exchange a few hashes and converge on precisely the data that’s out of sync. (The same structure underpins cryptographic verification and blockchains, for the same reason compact, tamper-evident summaries of large data.) This is how a leaderless cluster heals itself without grinding to a halt.

3. Paxos and lightweight transactions

Tunable consistency gets you strong consistency (read and write at QUORUM and the math works out). But strong consistency still isn’t enough for read-then-write races two clients that both read a value, then both write based on it, can clobber each other. Preventing that needs linearizable consistency: a guarantee that no other client can slip a modification between your read and your write.

Since 2.0, Cassandra provides this through lightweight transactions (LWT) check-and-set operations (IF NOT EXISTS, IF column = value) built on Paxos, a consensus algorithm that lets peer nodes agree on a value without a leader (the natural fit for a leaderless database, and an alternative to two-phase commit). Cassandra’s LWT extends basic Paxos to support read-before-write semantics, running four phases:

---
config:
  theme: neutral
  fontSize: 16
---
flowchart LR
    P1["1 Prepare /<br/>Promise"]:::gate --> P2["2 Read /<br/>Results"]:::obs
    P2 --> P3["3 Propose /<br/>Accept"]:::server
    P3 --> P4["4 Commit /<br/>Ack"]:::good
    classDef gate fill:#FFFFFF,stroke:#333333,stroke-width:1px,color:#111111
    classDef obs fill:#F0F0F0,stroke:#333333,stroke-width:1px,color:#111111
    classDef server fill:#DAE8FC,stroke:#333333,stroke-width:1px,color:#111111
    classDef good fill:#DCDCDC,stroke:#333333,stroke-width:1px,color:#111111

Figure 3: Cassandra's Paxos-based LWT four phases (prepare/promise, read/results, propose/accept, commit/ack), and four round-trips.

A coordinator proposes a value to the replicas; each promises not to accept older proposals, returns any in-progress proposal, and a majority must approve before commit. The catch is the bill: a successful LWT requires four round-trips between coordinator and replicas far more expensive than a normal write. So the guidance is blunt: think carefully before using LWTs. They’re the right tool for genuine check-and-set needs (unique usernames, claiming a resource), and the wrong tool to sprinkle on ordinary writes.

Why it matters: Cassandra’s leaderless design is what makes it scale and survive node failures but “no leader” forces interesting answers to “how do we stay consistent?” Tunable consistency lets you dial the trade-off per query, Merkle trees repair drift cheaply in the background, and Paxos-based LWTs add linearizable guarantees exactly where you need them, at a cost that tells you to use them rarely. Knowing which mechanism is doing the work and what each costs is the difference between using Cassandra well and being surprised by it.

References