Source: Dev.to

Key‑Value Stores: Design and Architecture

A key‑value store is a non‑relational database that maps unique keys to values (usually a string or an object).
It supports two core operations:

put(key, value)
get(key)

The concept is simple, but serious trade‑offs appear at scale – every design must balance read performance, write performance, and memory usage.

---

1. Single‑node vs. Distributed

---

2. The CAP Theorem

When a network partition occurs you can guarantee at most two of the following three properties:

Ideal scenario: no partition → full consistency and availability.
When a partition occurs you must choose:

• Consistency – block writes until the failed node recovers (e.g., banking).
• Availability – keep serving reads/writes; stale reads may occur.

---

3. Data Partitioning – Consistent Hashing

1. Hash ring – both servers and keys are mapped onto a circular space.
2. Key placement – a key is stored on the first server encountered when moving clockwise from the key’s position.

Problems with naïve consistent hashing

• Uneven key distribution.
• Unequal partition sizes.

Solution – Virtual Nodes
Each physical server occupies multiple positions on the ring, smoothing distribution proportionally to its capacity.

Benefits

• Automatic scaling.
• Higher storage capacity.
• Improved data locality.
• Support for heterogeneous servers.

---

4. Replication & Quorum

Replication stores copies of each key on N distinct nodes (ideally across separate data‑centers).

If a node fails, other replicas can still serve the request.
When many nodes fail simultaneously, operations may block – this is where quorum helps.

4.1 Quorum Basics

Given:

• N – total replicas.
• R – number of replicas that must acknowledge a read.
• W – number of replicas that must acknowledge a write.

Key insight: W + R > N forces every read set and every write set to overlap, guaranteeing at least one node holds the latest data.

4.2 Sloppy Quorum

Instead of requiring acknowledgements from a strict set of N nodes, any available nodes may temporarily handle the request when the designated nodes are down.
The system remains responsive during partial failures and still satisfies W + R > N once the cluster stabilizes.

4.3 Versioning & Conflict Resolution

• Each write increments a version number (or uses a vector clock).
• On a subsequent write, the client first fetches the latest version, increments it, and writes back.
• Readers compare versions and discard stale data.

DynamoDB uses this reconciliation technique on the read path.

---

5. Consistency Models

---

6. Failure Detection – Gossip Protocol

• Each node keeps a membership list with heartbeat counters.
• Nodes periodically increment their counters and gossip them to random peers.
• If a node’s heartbeat stops incrementing beyond a threshold, it is marked offline.

Advantages

• Decentralized, low‑overhead, and scales well.

Handling failures

---

7. Core Design Principles

1. Client API – get(key) and put(key, value).
2. Coordinator node – acts as a proxy between client and cluster.
3. Consistent‑hashing ring – distributes keys across nodes.
4. Full decentralisation – no single point of failure; every node is symmetric.

Write path

1. Append to a commit log (durability).
2. Write to an in‑memory cache (e.g., MemTable).
3. When the cache exceeds a threshold, flush to an SSTable on disk.

Read path

1. Check the in‑memory cache – return immediately on a hit.
2. On a miss:
   • Consult the Bloom filter to identify which SSTables may contain the key.
   • Query the relevant SSTables and return the result.

---

8. Component Overview

---

This cleaned‑up markdown preserves the original structure and content while improving readability and formatting.

Consistent Hashing – Key Concepts