# Design a key-value store

A Key-Value store is just a [hash table](https://en.wikipedia.org/wiki/Hash_table), until it isn't. At scale, keys shard across servers via [consistent hashing](https://blog.danwald.me/consistent-hashing) and [the CAP Theorem](https://en.wikipedia.org/wiki/CAP_theorem) becomes the constraint you design around.

### CAP Theorem

_Consistency_ will always give you the latest version. 
_Availability_ will always get a response. 
_Partition_ tolerance is an operational *system* even when nodes can no longer communicate. 

Since partition tolerance is non-negotiable in distributed systems, the real trade-off is between the other two: CP systems sacrifice availability (some requests fail) and AP systems sacrifice consistency (some requests return stale data). ZooKeeper and HBase are CP; Cassandra and CouchDB are AP.

### Redundancy w/Consistency and Versioning

With consistent hashing, the number of replicas `N` are configured to store duplicated information. `W` and `R` are the quorum of write and read acknowledgments needed for data consistency guarantees. 

_Strong_ consistency guarantees the last read corresponds to the most recent write. `W + R > N` ensures this because an overlapping node will have the latest data, which has to be resolved at the cost of availability.

`W + R <= N` is optimized for writes or reads with only _weak_ consistency guarantees. 

Eventual consistency is a type of weak consistency that's achieved by versioning. Clients need to reconcile data using [Vector clocks](https://en.wikipedia.org/wiki/Vector_clock) Clocks are lists of `(node, counter)` tuples associated with every version of the object. Conflicts siblings occur when two lists aren't greater than or equal to the other. Given that lists can grow large, Amazon's [Dynamo DB](https://www.allthingsdistributed.com/2007/10/amazons_dynamo.html) noted that timely truncation of vectors at the expense of complete lineage knowledge didn't result in service degradation at production workloads.

### Handling Failures

With cloud distributed systems, it's not *if* but *when* a node will fail.

To detect failures, nodes use the [Gossip protocol](https://en.wikipedia.org/wiki/Gossip_protocol) to share heartbeats of other nodes with a subset of others. A failed node is noted if others indicate the node as well.

To maintain durability guarantees during transient node outages, a *sloppy quorum* of the first N healthy nodes over preferred nodes is considered. *Hinted handoff* to a temporary node will propagate the event to the intended node once it's back online, reconciling data for eventual consistency guarantees.

In the event of permanent failures, efficient data inconsistency detection is handled by [Merkle trees](https://en.wikipedia.org/wiki/Merkle_tree) to resolve discrepancies within the quorum.

Resilient applications are configured to run over multiple data centers and even over multiple cloud systems to work in spite of region or provider failures.

### System Design

Our decentralized KV store works through a coordinator node that provides a simple `get(...)` and `put(...)` API.

![](https://cdn.hashnode.com/uploads/covers/60db6f287c7df7644acddc3b/ea55415f-c20d-447f-a228-89685a52bee6.png align="center")

Each node in our hash ring-backed Key-Value store does a lot of things: API, failure detection/repair, conflict resolution, storage engine, and replication. To cope with potentially large amounts of data, an in-memory cache is used and backed with [SSTables](https://www.igvita.com/2012/02/06/sstable-and-log-structured-storage-leveldb/) and [bloom filters](https://en.wikipedia.org/wiki/Bloom_filter) to efficiently serve clients for read and write access patterns.

Happy Hackin'

### References

*   [Hash table](https://en.wikipedia.org/wiki/Hash_table)
*   [The CAP Theorem](https://en.wikipedia.org/wiki/CAP_theorem)
*   [Vector clocks](https://en.wikipedia.org/wiki/Vector_clock)
*   [DynamoDB](https://www.allthingsdistributed.com/2007/10/amazons_dynamo.html)
*   [Gossip protocol](https://en.wikipedia.org/wiki/Gossip_protocol)
*   [Merkle trees](https://en.wikipedia.org/wiki/Merkle_tree)
*   [SST Tables](https://www.igvita.com/2012/02/06/sstable-and-log-structured-storage-leveldb/)
*   [bloom filters](https://en.wikipedia.org/wiki/Bloom_filter)
* * *

> This article is part of the [system design series](https://blog.danwald.me/series/system-design) where I am summarizing chapters from The System Design Interview: [Volume 1](https://www.amazon.ae/Independently-Published-System-Design-Interview/dp/B08CMF2CQF) / [Volume 2](https://www.amazon.ae/System-Design-Interview-Insiders-Guide/dp/1736049119) amongst other related content