Key-Value Stores: Design and Architecture

A key-value store is a non-relational database that maps unique keys to values. Keys must be unique, and each key maps directly to a value — typically a string or object.

When a partition occurs, you must choose:

Naive consistent hashing creates two problems: uneven key distribution and unequal partition sizes. Virtual nodes solve this — each physical server occupies multiple positions on the ring, smoothing out distribution proportionally to each server's capacity.

Key benefits of partitioning: automatic scaling, higher storage capacity, improved data locality, and heterogeneous server support.

Data Replication

Partitioning spreads data but doesn't protect it. Replication does — by storing copies of each key across N distinct nodes, ideally across separate data centers to guard against localized failures like power outages.

The key insight behind W + R > N: any read set and any write set must overlap, so at least one node always has the latest data.

Sloppy Quorum

Standard quorum can still return stale data. If a write lands on node s1 but a subsequent read hits s2, the client sees stale data — since reads and writes are load-balanced, you can't control which nodes they hit.

Sloppy quorum addresses this. Rather than requiring acknowledgement from a strict set of N nodes, it allows any available nodes in the cluster to temporarily handle requests when the designated nodes are unavailable. This keeps the system responsive during partial failures while still satisfying the W + R > N invariant once the cluster stabilizes.

For a 3-node cluster with W = R = 2, a majority of nodes must acknowledge every read and write. This guarantees that the read and write sets always overlap — so at least one node in any read quorum will always have the latest data.

Inconsistency Resolution

Even with quorum, replicas can diverge. Versioning handles this: each write increments a version number, and on subsequent writes clients must first fetch the latest version before incrementing and writing. Readers resolve conflicts by comparing versions and discarding stale data.

Each node maintains a membership list with heartbeat counters. Nodes periodically increment their counters and share them with random peers. If a node's heartbeat stops incrementing past a defined threshold, it's marked offline.

Core design principles:

• Clients interact via get(key) and put(key, value)
  


• A coordinator node acts as a proxy between the client and the cluster


• Nodes are distributed on a consistent hashing ring


• The system is fully decentralized — no single point of failure


• Every node is symmetric, handling the same set of responsibilities

1. Write is appended to a commit log (durability)


2. Data is written to an in-memory cache


3. When the cache exceeds a threshold, it flushes to an SSTable on disk

Read Path

1. Check the in-memory cache — on a miss, proceed


2. Consult the Bloom filter to identify which SSTables likely contain the key


3. Query the relevant SSTables and return the result to the client

Summary