Designing a Key-Value Store

A key-value store is the simplest NoSQL database — perfect for caching, session storage, and configuration management.

Requirements

• put(key, value)
• get(key)
• delete(key)
• High availability, low latency
• Horizontally scalable

Data Distribution

Use consistent hashing to distribute keys across nodes:

hash(key) → Node assignment

Replication

Replicate each key to N nodes (e.g., N=3).

Key → Primary Node
   → Replica 1
   → Replica 2

Consistency: Quorum

N = 3 replicas
W = 2 (write quorum)
R = 2 (read quorum)
W + R > N → Strong consistency

Conflict Resolution

Vector Clocks track causality:

[Node A: 2, Node B: 1] → newer than [Node A: 1, Node B: 1]

When vector clocks diverge, use Last-Write-Wins or ask client.

Failure Detection

Gossip Protocol: Each node periodically shares its view of cluster health with random peers — eventually all nodes converge on consistent view.

Storage Engine

• Memory: For pure cache (Redis-style)
• LSM Tree: For persistent writes (RocksDB)
• B-Tree: For read-heavy (Berkeley DB)

Compaction

LSM tree accumulates SSTables — periodic compaction merges and removes deleted keys.

Conclusion

DynamoDB and Cassandra apply these exact principles: consistent hashing + quorum reads/writes + gossip-based failure detection.