CSE Roadmap

Core tier · about 5 hours · 8 parts

Part 7 of 8 · 3 min read

Write and read paths

Inside one node, then what to say.

Write path, read path and wrap-up

The design is decentralised: every node does the same jobs, so there is no single point of failure and nodes can be added or moved automatically. Each node handles the client API, coordinates requests, detects failures, replicates data, resolves conflicts, and stores data.

Write path (as in Cassandra):

  1. The write is first appended to a commit log on disk, so it survives a crash.
  2. The value is put in an in-memory cache.
  3. When the cache is full or reaches a threshold, it is flushed to disk as an SSTable, a sorted list of key-value pairs that is never edited, only replaced by newer files.

Read path:

  1. Look in the memory cache. If the key is there, return it.
  2. If not, use a Bloom filter, a small structure that says "definitely not here" or "maybe here" for each SSTable, so most files can be skipped without a disk read.
  3. Read the likely SSTables, find the newest value, and return it.

A worked example (made up). A key lives in 1 of 12 SSTables. Without the filter, a read might touch up to 12 files. With the filter, the 11 other files answer "not here" from memory, and only 1 or 2 are read. The cost of the filter is a small memory use and occasional false "maybe" answers.

Summary of techniques.

Need Technique
Store big data Consistent hashing across servers
High availability for reads and writes Replication over N nodes and data centres, sloppy quorum
Tunable consistency Quorum values N, W, R
Conflict handling Vector clocks
Failure detection Gossip protocol
Temporary failure Sloppy quorum and hinted handoff
Permanent failure Anti-entropy with Merkle trees
Fast writes Commit log, memory cache, SSTables
Fast reads Memory cache, Bloom filter

Common mistake

Saying "use W + R > N" and stopping. A quorum helps reads see recent writes, but it does not remove conflicts from concurrent writes, and a sloppy quorum weakens the guarantee. Say how conflicts are detected and resolved.

Interview angle

Answer in your head first, then open it.

What is the CAP choice here?

Partition tolerance is required. This design favours availability, with consistency tuned by N, W and R.

How are keys spread?

Consistent hashing with virtual nodes, and the next N distinct nodes clockwise hold the copies.

How do you get strong consistency?

W + R > N, for example N = 3, W = 2, R = 2, at the cost of waiting for slower copies.

How are conflicts found?

Vector clocks, with the client or a rule merging siblings.

How are failures handled?

Gossip for detection, sloppy quorum and hinted handoff for short failures, Merkle trees for repair, multiple data centres for outages.

One follow-up to try. "Add range queries: all keys between two values." A good reply: the hash ring scatters neighbouring keys, so range queries are slow. Either add a second index sorted by key, or choose a range-partitioned design instead (Level 4, page 2) and accept hot spots at busy ranges. This is a real trade, and it explains why some stores offer only point lookups.

Check yourself: 1. Why is a write first put in a commit log? 2. What does a Bloom filter answer? 3. Why are range queries awkward on a hashed ring?

Words you will meet

Word Meaning
Key-value pair A unique key and the value stored under it
CAP theorem In a partition, choose between consistency and availability
Quorum The number of copies that must answer for an operation to count
Coordinator The node that handles a request on behalf of the client
Vector clock Version list that shows ancestry or conflict
Gossip protocol Nodes share membership news with random peers
Hinted handoff A stand-in node holds writes for a down node and returns them later
Merkle tree A tree of hashes that finds differing data quickly
SSTable A sorted, unchanging file of key-value pairs
Bloom filter A compact structure that rules out files that cannot hold a key