Design a Distributed Cache (like Redis)

3. Clarify non-functional requirements

Non-functional requirements describe how well the system must work: how big, how fast, and how reliable.

• Latency: Latency is the time a request takes. The work on a cache server must take under 1 ms for 99 percent of reads and writes (the 99th percentile, or p99), not counting the time on the network.
• Throughput: The cluster must handle 10 million queries per second (QPS) in total. The cluster runs inside one region, because a request to another region takes tens of milliseconds and would miss the latency target by far.
• Availability: 99.9%, often called "three nines". This allows about 8.8 hours of downtime a year. Short failures are acceptable because the database still holds every value, but each one sends extra load to the database.
• Consistency:
  • On the primary: Every key has one primary server, and all reads and writes for that key go to it. In normal operation, a client therefore reads its own write at once. This is called read-your-own-writes consistency. It is not strong consistency, because a failover can still lose writes that had not reached a replica yet.
  • On replicas: A replica may be a few milliseconds behind its primary. This is eventual consistency, meaning the copies agree after a short delay. Clients do not read from replicas, so this delay matters only after a failover.
• Data Size: The cluster must hold about 10 TB of data in RAM.

The latency target is the most important number on this list. Under 1 ms leaves no room for an extra network hop, for waiting on a replica, or for threads waiting on each other.

4. Back of the envelope estimates

These estimates are rough on purpose. Their job is to find which resource limits the size of the cluster.

• Storage Estimates:
  • Target data: 10 TB.
  • Replication factor: 3, meaning each key is stored three times: on one primary and on two replicas.
  • Total RAM needed: 10 TB × 3 = 30 TB.
  • RAM per node: we assume servers with 64 GB of RAM, of which about 50 GB holds cache data. The other 14 GB is left for the operating system, for connection buffers, and for the extra memory a disk snapshot can need (section 10).
  • Total nodes: 30,000 GB ÷ 50 GB = 600 nodes.
  • The 10 TB must include the bookkeeping for each key, such as pointers and the expiry time. At 1 KB per value this is roughly 5 to 10 percent extra, so a real plan would add about 10 percent more nodes.
• Throughput Estimates:
  • Total QPS: 10 million.
  • Each node is the primary for about one third of the data it holds, and a replica for the rest (section 11 explains how). Client traffic therefore spreads over all 600 nodes.
  • QPS per node: 10,000,000 ÷ 600 ≈ 16,700 QPS.
  • Feasibility: One cache process such as Redis can serve roughly 100,000 simple operations per second on one CPU core, and more with pipelining, which means sending many commands without waiting for each reply. Our load per node is a small part of that. The cluster size is set by memory, not by processing power: we are memory bound, not CPU bound.
• Bandwidth Estimates:
  • Average value size: 1 KB.
  • Total bandwidth: 10 million QPS × 1 KB ≈ 10 GB per second.
  • Bandwidth per node: 10 GB per second ÷ 600 ≈ 17 MB per second. A standard 10 Gbps network card moves about 1,250 MB per second, so each node uses less than 2 percent of it.

The conclusion is that we buy servers for their memory. Adding CPU cores or faster network cards would not reduce the number of nodes.

5. API design

The API is the set of requests that applications send to the cache. Real caches use their own compact protocols over TCP connections that stay open. Redis, for example, uses RESP (the Redis serialization protocol), a simple text format that can still carry any bytes. For clarity, we describe the same operations here as REST requests, which are plain HTTP requests on named URLs.

1. Set Value

• Method: PUT /v1/keys/{key}
• Body: {"value": "base64_data", "ttl_seconds": 3600}. The value is encoded in base64, a way of writing raw bytes as plain text.
• Response: 200 OK when the value is stored, or 413 Payload Too Large when the value is over the size limit, for example 1 MB.

2. Get Value

• Method: GET /v1/keys/{key}
• Response:
  • 200 OK: {"value": "base64_data", "ttl": 3590}, where ttl is the number of seconds the key has left.
  • 404 Not Found: the key does not exist or has expired. For the application, both mean the same thing: read the database.

3. Delete Value

• Method: DELETE /v1/keys/{key}
• Response: 204 No Content, whether or not the key existed. Deleting a key twice therefore has the same effect as deleting it once, so a client can safely retry.

6. High level architecture

The usual way to spread requests across many servers is a load balancer, a server that receives every request and forwards it to one of the servers behind it. We do not use one. The work on a cache server takes microseconds, while each extra network hop inside a data center adds about 0.1 to 0.5 ms. A load balancer would therefore cost more time than the cache operation itself. Instead, we use a smart client: the application finds the right cache server by itself and sends the request straight to it.

Components:

1. Smart Client (SDK): A library inside each application server, for example in Service A and Service B. It holds a cluster map, a table that says which cache node owns which range of keys. It uses consistent hashing (section 11) to find the owner of each key. Memcached clients have worked this way for a long time.
2. Cache Nodes: The 600 servers that hold the data in RAM. They share no memory or disk, and they do not coordinate with each other when they answer a request. The only traffic between them is replication: each node copies its writes to the replicas of its keys.
3. Cluster Manager: A small, highly available coordination service, such as ZooKeeper or etcd. It checks that every cache node is alive, decides what happens when one fails, and sends updates of the cluster map to every smart client.

The cluster manager is never on the path of a read or a write. Clients ask it only for the cluster map, so a slow manager delays map updates but does not slow down any cache request.

7. Data model

Because all data lives in memory, the "data model" here means the structures inside each node's RAM. The goal is that every operation takes constant time, written O(1), which means the work does not grow as the number of keys grows. Each node uses two structures over the same entries.

1. Hash Map (The Index)

• Purpose: Finds any key in one step.
• Key: The text key from the client.
• Value: A pointer to the entry in memory. The entry holds the value, the expiry time, and the two links described next.

2. Doubly Linked List (The Eviction Queue)

• Purpose: Keeps the entries in the order they were last used, so the node always knows which one to evict. A doubly linked list is a chain in which each entry points to the entry before it and the entry after it, so any entry can be removed in one step.
• Head: The most recently used (MRU) entry.
• Tail: The least recently used (LRU) entry.
• Mechanism: Every time a key is read or written, its entry moves to the head. When memory is full, the node removes the entry at the tail.

The hash map alone has no order, so it cannot say which key is the oldest. The list alone cannot find a key without walking through it. Together, they give constant time lookup and constant time eviction.

Redis itself does not keep this list, because two extra pointers per key cost a lot of memory across billions of keys. Instead, it samples a few keys (5 by default) and evicts the one used least recently, which comes close to true LRU. Redis also does not evict at all by default: its default policy, noeviction, rejects new writes when memory is full. A cache must set a policy such as allkeys-lru or allkeys-lfu (least frequently used).

8. Core flows end to end

This section follows the three most important journeys through the system: saving a value, reading a value, and handling a missing value. For each step, we describe what happens, why the step is needed, and what it produces.

Every flow begins in the smart client. The client already holds the cluster map, so it knows which server owns a key before it sends anything. No other server takes part in choosing the destination.

Flow 1: Saving Data (The "SET" Request)

Scenario: A user logs in to a website. The backend, Service A, saves the user's session under the key user:123, with the value {"status": "active"} and a TTL of 1 hour.

Step 1: Find the node that owns the key (hashing)

What happens: The smart client runs the key user:123 through a hash function, a formula that turns any text into a number. It then looks up that number in its cluster map. The answer is that Server #42 is the primary for this key.

Why: There are 600 servers. If the client picked one at random, the next read would not know where to look. A hash always gives the same number for the same key, so every client finds the same server.

Outcome: The client knows the owner of the key without asking any other server.

Step 2: Send the request straight to the owner (routing)

What happens: The client sends the write to Server #42 over a TCP connection that it keeps open for many requests (a connection pool). The request goes over the private network inside the data center. It passes through no load balancer or gateway.

Why: Opening a new connection for every request would add a full extra round trip, and a middle server would add a network hop. Either one would cost more time than the cache operation itself.

Outcome: The write arrives at the correct server after a single network hop.

Step 3: Make room if memory is full (eviction)

What happens: Before storing the value, Server #42 checks whether it has reached its memory limit. If it has, it removes the entry at the tail of its linked list, the key that has gone unused the longest. It repeats this until there is enough room. Removing keys to make room is called eviction.

Why: A cache that refuses writes when it is full stops being useful. Removing the least recently used key keeps the keys that applications are actually reading.

Outcome: The node has room for the new value, and the key it evicted can still be read from the database.

Step 4: Store the value in memory

What happens: Server #42 updates its two structures:

• Hash map: It stores the entry for user:123, with the value and an expiry time of now plus 1 hour.
• Linked list: It places the entry at the head of the list, which marks it as the most recently used key.

Why: The hash map lets the next read find the key in one step. The position at the head of the list protects the key from eviction while it is still in use.

Outcome: The value is stored and can be read at once.

Step 5: Reply first, then copy to the replicas (asynchronous replication)

What happens: Server #42 replies "success" to Service A as soon as the value is in its own memory. Right after replying, it sends the write to the key's two replicas, for example Server #43 and Server #87. On a fast local network, this copy usually arrives within about a millisecond. This is called asynchronous replication, because the reply does not wait for the copy.

Why: Waiting for a replica to confirm would add a second network round trip to every write, which roughly doubles the write latency. We give up some durability, meaning the guarantee that an acknowledged write survives a crash, in return for speed.

Outcome: The client has its answer in well under a millisecond. If Server #42 crashes in the short time before the copy arrives, that write is lost. A cache can accept this, because the database still holds the data.

Flow 2: Retrieving Data (The "GET" Request)

Scenario: The user refreshes the page. Service A needs to read user:123.

Step 1: Find the owner again

What happens: The smart client runs user:123 through the same hash function and the same cluster map. It gets the same answer, Server #42, and sends the read there.

Why: Reads must go to the same server that took the write. All reads for a key go to its primary, never to a replica, so the client always sees the newest value the cache holds.

Outcome: The read arrives at the server that holds the key.

Step 2: Look up the key

What happens: Server #42 looks up user:123 in its hash map. If the key is not there, it replies 404 Not Found. If the key is there, the server takes the entry.

Why: The hash map finds the key in one step, however many keys the node holds.

Outcome: The server either has the entry or has already answered that the key is missing.

Step 3: Check the expiry time (lazy deletion)

What happens: The server compares the entry's expiry time with the current time. If the expiry time has passed, the server deletes the entry and replies 404 Not Found. Deleting an expired key only at the moment someone reads it is called lazy deletion. If the key has not expired, the server continues.

Why: Checking expiry during the read costs almost nothing, and it guarantees that a client never receives an expired value.

Outcome: The server holds a value that is still valid, or it has removed an expired one.

Step 4: Mark the key as recently used

What happens: Even though this is a read, the server changes its memory. It moves the entry for user:123 from its current place in the linked list back to the head.

Why: The eviction order must reflect reads as well as writes. Otherwise, a key that is read constantly but rarely written would move to the tail and be evicted. This step also means that every read changes shared data, which matters for the threading choice in section 9.

Outcome: The key is protected from eviction for as long as applications keep reading it.

Step 5: Return the value

What happens: Server #42 sends the value back to Service A.

Why: This completes the request.

Outcome: The work on the server takes a few microseconds. The whole round trip, including the network inside the data center, usually stays under 1 millisecond.