Key - Value Store

A unique key, generated or processed by a hash function, maps to a specific value. The key-value store does not need to understand the internal structure of the value. The value can be a blob, image reference, server name, session object, cart data, configuration, or any other user-defined data.

Values are usually kept small, commonly from KB to MB. If the actual content is large, a better design is to store the large object in blob or object storage and keep only the reference in the key-value store.

Key-value stores are useful for fast lookup scenarios such as user sessions, shopping carts, product metadata, feature flags, cache data, configuration, and many NoSQL database patterns.

Why do we use a key-value store?

Traditional relational databases are powerful, but they can become difficult to scale when we need very high availability, global distribution, and low-latency access at massive request volume.

For example, an ecommerce platform may need to read and update shopping cart data very quickly. The data is usually accessed by a known key, such as cart:user123. In this case, the application does not always need joins, complex queries, or transactions across many tables. It mainly needs this question answered quickly:

What value is stored for this key?

A key-value store fits this access pattern well because it is optimized for simple operations:

• Put a value by key.
• Get a value by key.
• Delete or expire a key.
• Distribute keys across many servers.
• Replicate data for durability and availability.

Common use cases include ecommerce carts, session management, product catalogs, distributed caches, device state, rate limit counters, and user preference storage.

Key - Value System Design:

A key-value system must be designed around scale, failures, and predictable access.

Non-functional requirements:

• Scalability: The system should support growth across many servers and regions. We should be able to add or remove servers with minimal impact on users.
• Fault tolerance: The system should continue operating even when servers, disks, racks, or network links fail.
• Low latency: Reads and writes should be fast because key-value stores are often used on critical request paths.
• High availability: The system should continue accepting reads and writes during partial failures, depending on the chosen consistency model.
• Durability: Once data is written successfully, it should not be lost when one machine fails.

API design:

• get(key): Returns the value associated with the key. In replicated systems, the store decides which replica to read from. With eventual consistency, a read may sometimes return multiple versions if conflicts exist.
• put(key, value): Stores the value for the key. The system decides where the data should live and maintains metadata such as versions, timestamps, or vector clocks.
• delete(key): Removes the value or marks it as deleted. In distributed systems, deletes may need tombstones so replicas can learn about the deletion.

Ensure Scalability and Replication:

The simplest way to distribute keys is normal hashing with modulo.

If we have 4 nodes, we can hash the key and calculate:

node = hash(key) % 4

This roughly spreads keys across the 4 nodes. Ideally, each node receives around 25 percent of the traffic.

The problem appears when the number of nodes changes. If one node is removed and we now calculate:

node = hash(key) % 3

many keys move to different nodes. A key that previously belonged to node 2 may now belong to node 1 or node 0. This causes a large reshuffling of data, cache misses, high network transfer, and increased latency.

For a large distributed system, moving too much data during every scale-up or failure event is expensive. We need a better approach.

Consistent Hashing

Consistent hashing reduces the amount of data movement when nodes are added or removed.

Instead of assigning keys using hash(key) % numberOfNodes, we visualize the hash space as a ring. Each server is placed on the ring by hashing its node ID. Each key is also hashed onto the same ring.

To find the owner of a key, move clockwise from the key position until the first node is found. That node owns the key.

When a new node joins, it only takes over a portion of keys from its next clockwise neighbor. Other nodes are mostly unaffected. When a node leaves, only the keys owned by that node need to move.

The main benefit is simple: adding or removing nodes moves only a smaller subset of keys instead of reshuffling almost everything.

However, consistent hashing has a practical issue. Random node placement may not divide the ring evenly. One server may own a large segment and receive more storage and traffic than others. This creates a hotspot.

Use virtual nodes

To distribute load more evenly, we use virtual nodes.

Instead of mapping one physical server to one position on the ring, we map each physical server to multiple positions. For example, server A can appear as A1, A2, and A3 on the ring. Server B can appear as B1, B2, and B3.

When a key lands on the ring, it still goes to the next clockwise virtual node. That virtual node maps back to a physical server.

Virtual nodes help because:

• Fault tolerance: If a physical node fails, its key ranges are spread across multiple other nodes instead of overloading only one neighbor.
• Better load distribution: Multiple positions on the ring reduce uneven ownership.
• Capacity management: Stronger machines can be assigned more virtual nodes, so they carry more traffic.
• Operational flexibility: Adding or removing capacity becomes smoother because smaller key ranges move around.

Data replication

A production key-value store should not keep only one copy of the data. If the only node holding a key fails, the data becomes unavailable or lost.

To improve durability and availability, data is replicated across multiple nodes. Common approaches include primary-secondary replication and peer-to-peer replication.

Primary-secondary approach

In a primary-secondary architecture, one node is the primary for writes. Secondary nodes replicate from the primary and may serve reads.

This model is simple to reason about, but it has tradeoffs:

• Writes depend on the primary.
• Replication lag can make reads stale.
• If the primary fails, writes may stop until a new primary is elected.
• Failover logic becomes important.

Primary-secondary replication is useful when stronger ordering is needed, but it can reduce write availability during failures.

Peer-to-peer approach

In a peer-to-peer approach, multiple nodes can accept reads and writes. There is no single primary for all writes.

A node that handles a read or write for a key is often called the coordinator. The coordinator is responsible for contacting the right replica nodes.

Usually, we do not replicate every key to every server because that would be too expensive. Instead, we choose a replication factor such as 3 or 5.

If the replication factor is n = 3, the key is stored on 3 nodes. In a consistent hashing design, the coordinator can store the key on the next n suitable nodes clockwise on the ring. This set is often called a preference list.

A good preference list avoids placing multiple replicas on the same physical server, rack, or failure domain where possible.

Data versioning

Distributed systems can temporarily disagree.

Network partitions, retries, and node failures can produce multiple versions of the same object. For example, two clients may update the same shopping cart while different replicas cannot communicate with each other.

If the system blindly accepts only the latest physical timestamp, it can lose valid updates. Physical clocks are not reliable enough for this decision because machines may have clock drift.

A safer approach is to track causality using logical clocks or vector clocks.

A vector clock is a list of (node, counter) pairs attached to a version of an object. It helps the system understand whether one version happened after another version, or whether two versions were created concurrently.

Example:

• Node A writes the first version: [A,1].
• Node A updates it again: [A,2].
• A network partition happens.
• Node B updates one copy: [A,2], [B,1].
• Node C updates another copy: [A,2], [C,1].

When the partition heals, the system sees two concurrent versions. It cannot safely choose one without reconciliation.

Reconciliation can be done by the application, the client, or the database depending on the use case. For a shopping cart, merging items may be acceptable. For bank balances, automatic merging would be dangerous and a stronger consistency model may be required.

Usage of r and w

In replicated key-value stores, we often use three important values:

• n: The number of replicas for each key.
• r: The minimum number of replicas that must respond for a successful read.
• w: The minimum number of replicas that must acknowledge a successful write.

For example, if n = 3, the data is stored on 3 replicas.

If w = 2, a write is considered successful after 2 replicas acknowledge it.

If r = 2, a read asks at least 2 replicas for the value.

A common rule is:

r + w > n

This increases the chance that the read set and write set overlap on at least one replica. That overlap helps the system discover the latest written value.

The tradeoff is important:

• Higher r gives stronger reads but can increase read latency.
• Higher w gives stronger writes but can increase write latency.
• Lower r or w improves availability and speed but may return stale data.

Final thoughts

A key-value store looks simple from the outside: put a value, get a value. But at scale, the design includes many important distributed system ideas.

The core concepts are:

• Hashing distributes keys across nodes.
• Consistent hashing reduces data movement during scaling.
• Virtual nodes improve load balancing.
• Replication improves durability and availability.
• Vector clocks help detect conflicting versions.
• Quorum reads and writes balance consistency, latency, and availability.

Key-value stores are powerful because they keep the data model simple and focus on fast, scalable access by key. That simplicity is why they are widely used in caching, sessions, ecommerce, distributed databases, and cloud-scale systems.