Premium Video

This video is available to premium subscribers only

Unlock Full Access

In this chapter, we will learn what a key-value store is, how it works internally, how it scales across many machines, and when it is the right choice for a system.

Suppose we run a web application with millions of logged-in users.

Every time a user makes a request, the application needs to load their session. The session tells us who the user is, what permissions they have, and what is in their shopping cart.

We always look it up the same way, using a session id. We never need to join sessions with other tables or search them by their contents. We just need to fetch one session by its id, as fast as possible, thousands of times per second.

We could store sessions in a relational database. But then each lookup goes through query parsing, planning, and possibly disk reads, all to answer a very simple question.

For this kind of access pattern, we want something simpler and faster. That is where a key-value store comes in.

A key-value store is a database that stores data as pairs of keys and values. It works like a hash map, but as a separate service that many application servers can share.

For example, the key might be session:abc123, and the value might be the session details.

The interface is usually very small:

In Redis, those look like this:

In most key-value stores, the database does not care what is inside the value. It could be a JSON string, a serialized object, an image, or just a number. To the database, it is simply a blob of bytes.

Some stores, like Redis, go further and support structured values such as lists, sets, sorted sets, and hashes, with operations on each. A sorted set, for example, makes a leaderboard easy:

But the core idea is still the same. You access data by its key.

Key-value stores appear in many large-scale systems because they are simple and fast.

Caching

One of the most common use cases is caching. An application can store the result of an expensive database query or API call under a key, then reuse that result on future requests instead of doing the same work again.

This is the cache-aside pattern:

The downside is freshness. A cached value may be older than the database value until it expires or the application removes it.

Sessions and Shopping Carts

Key-value stores are also commonly used for session storage. A session id acts as the key, and the user's session data is stored as the value.

Shopping carts can work in a similar way, with the user id as the key and the cart contents as the value.

Rate Limiting

Rate limiting is another natural fit. The key might combine a user id with a time window, and the value stores a counter that increases with each request.

The increment must be atomic, which means the store performs it as one indivisible step. If the application read the number and then wrote a new number itself, two requests could race and let too many requests through.

Other Uses

Key-value stores are also useful for feature flags, configuration settings, leaderboards, password reset tokens, and one-time codes.

The common pattern is simple: the application already knows exactly which key it wants, and it needs to retrieve or update the value very quickly.

Key-value stores generally fall into two groups.

In-Memory Stores

The first group keeps data in memory. Redis and Memcached are the best-known examples.

Because reads and writes happen in RAM, these stores can often respond in under a millisecond. The trade-off is that memory is more expensive than disk, and it is lost if the server restarts.

Memcached is purely a cache, so if a node restarts, its data is gone.

Redis can optionally persist data to disk:

Persistent Stores

The second group stores data durably on disk. Amazon DynamoDB, RocksDB, and etcd are examples. They are designed to be the permanent home for data, not just a cache in front of another database. They are usually a little slower than in-memory stores, but they keep data safely and scale across many machines.

So one of the first questions to ask is:

Hash Tables

On a single machine, an in-memory key-value store is usually built around a hash table.

When you put a key, the store hashes it to find a slot in the table and stores the value there. When you get a key, it hashes the key again and goes straight to that slot.

This takes constant time on average, no matter how many keys are stored. That is why lookups stay fast even with millions of keys.

LSM Trees and B-Trees

Disk-based key-value stores need a structure that works well with storage.

A useful side effect of these sorted structures is that they can support range scans, such as "all keys that start with user:42:". A pure hash table cannot do that efficiently, because hashing scatters related keys across the table.

In a key-value store, the key is your only way to find data. So key design matters a lot.

Use a Structured Naming Pattern

A common practice is to use a structured naming pattern:

This groups related keys, avoids collisions between different types of data, and makes debugging easier.

Make Keys Predictable

Keys should also be predictable. If the application can build the key from information it already has, like a user id, it can fetch the data in one step.

Composite Keys

Some stores allow composite keys. In DynamoDB, a table has a partition key and an optional sort key.

For example, the partition key might be a user id, and the sort key might be an order date. That lets us fetch all orders for one user, sorted by date, in a single query.

Keep Keys and Values Small

Finally, keys and values should stay reasonably small. Very large values take longer to read, send over the network, and replicate. Keys also take memory, which adds up across hundreds of millions of keys.

Prefer user:42:profile over production:application:customer-service:user-profile-object:42.

Much of the data in a key-value store is temporary. Sessions expire, cached results go stale, and rate limit counters only matter for the current time window.

Time-to-Live (TTL)

So most key-value stores support a time-to-live, or TTL, on each key. When you store a session, you can set it to expire after 30 minutes. After that, the store removes it automatically, and the application does not need to clean it up.

Eviction

In-memory stores also need a plan for when memory runs out. This is called eviction.

A common policy is Least Recently Used, or LRU. When memory is full, the store removes the keys that have not been accessed for the longest time.

Redis also supports other policies:

The right policy depends on whether the store is used as a cache or as a primary data store. For a cache, evicting old keys is fine. For a primary store, silently losing data is not.

Eventually, one machine cannot hold all the keys or handle all the requests.

Key-value stores scale well here, because every key is independent. We can split the keys across many nodes. This is called sharding, or partitioning.

Hash Modulo N

The simplest approach is to hash the key and take the result modulo the number of nodes: node = hash(key) % N.

But that approach has a problem. If we add or remove a node, N changes, most keys map to a different node, and a large amount of data has to move. Going from 4 nodes to 5, for example, moves about 80% of the keys.

Consistent Hashing

So many systems use consistent hashing instead. Nodes and keys are placed on a logical ring, and each key belongs to the next node on the ring, moving clockwise.

Here, user:42 belongs to Node B, session:abc to Node C, and cart:77 to Node A. When a node is added, only the keys in its section of the ring need to move.

Amazon's Dynamo system, which inspired DynamoDB and Cassandra, used this approach.

Hash Slots

Redis Cluster uses a related idea. It divides the key space into 16,384 hash slots and assigns groups of slots to each node. Moving capacity between nodes means moving slots, not rehashing every key.

Keys that must be used together, for example in one multi-key operation, can be forced into the same slot with hash tags. Only the part inside {} is hashed:

Sharding spreads the load, but if a node fails, its keys become unavailable. So each partition is usually replicated to multiple nodes. There are two common models.

Primary-Replica Replication

The first is primary-replica replication. Redis uses this.

Writes go to the primary for a partition, and the primary copies them to its replicas. If the primary fails, a replica can be promoted to primary.

Leaderless Replication

The second is leaderless replication, used in Dynamo-style systems. Here, a write is sent to several replicas at once. The system uses three numbers:

If R + W > N, every read overlaps with at least one replica that has the latest write.

For example, with 3 replicas, writing to 2 and reading from 2 gives that overlap:

The read touches B and C. C is stale, but B has v2, so the newest version wins.

Lower values give faster responses but weaker consistency. With W = 1 and R = 1, a read can easily land on a replica that has not seen the write yet.

Consensus

Other stores take a stricter approach. etcd, which Kubernetes uses to store cluster state, uses the Raft consensus algorithm, so every read can reflect the latest committed write.

The right choice depends on the data. A slightly old product page cache may be fine. A slightly old permission decision or lock owner may be dangerous.

The simplicity of key-value stores is also their main limitation.

Lookups Only by Key

You can only look up data efficiently by its key.

Suppose we store user profiles with the user id as the key. Now we want to find all users in India. The store has no idea what is inside each value, so it cannot answer that without scanning every key.

The common workaround is to maintain a second key yourself. For example, a key country:India whose value is a list of user ids.

But now the application has to keep that index in sync on every write. If a user moves from India to Canada, both index keys must be updated.

No Joins

Key-value stores also have no joins. If you need data from two keys, you fetch both and combine them in the application.

Limited Transactions

And transactions are usually limited:

But they are far less flexible than transactions in a relational database.

Another common production problem is the hot key.

Sharding works well when traffic is spread reasonably evenly across many keys. But in real systems, that is not always the case.

Suppose a celebrity publishes a post and millions of users request the same piece of data at once. Because that data belongs to a single key, all of those requests may be routed to the same node. That node can become overloaded even while the rest of the cluster is mostly idle.

There are several ways to reduce this problem:

The important point is that partitioning spreads traffic across different keys. It does not automatically spread the load of one extremely popular key. Handling hot keys requires an additional strategy.

They share the same basic model, but make very different choices around memory, durability, and consistency.

A note on Redis: its license changed in 2024, and the Linux Foundation started Valkey, a community fork of the last BSD-licensed version. For most cache use cases, Redis and Valkey behave the same and share the same commands.

A key-value store is a good fit when:

It is not a good fit when you need to:

In those cases, a relational or document database is usually a better choice.

In practice, many systems use both. A relational database holds the source of truth, and a key-value store like Redis sits in front of it to serve the hottest data quickly.