Distributed cache (Memcached/Redis)

01 · CONTEXT AND REQUIREMENTS

What it is and what it must do

Um cache distributed cache stores key-value pairs in the memory of several networked machines. Unlike the cache of a single node, limited to the resources of one machine, it scales horizontally. The set of nodes partitions and replicates the data so it stays available when a node fails.

The functional requirements are to write, read and delete key-value pairs, configure the expiration of each pair, and evict data by the LRU criterion, which removes whatever was used longest ago.

On the non-functional side, the Hello Interview prompt asks for high availability, accepting eventual consistency, and low latency, under 10 ms on get and set. For scale, the interviewer imagines up to 1 TB of data and a peak of 100 thousand requests per second. Durability, that is, surviving restarts, is out of scope.

02 · ONE NODE FIRST

Hash table, linked list and cache-aside

Before distributing, it helps to understand a single node. Since memory is limited, the primer uses LRU to expire old entries. The implementation combines a doubly linked list, in which new items enter at the head and those about to expire leave through the tail, with a hash table that gives direct access to each node in the list.

1. The client makes a request and the application service receives it.

2. The service checks the cache first. If the key is there, it is a hit: the cache responds and moves the entry to the front of the recently-used list.

3. If the key is not in the cache, it is a miss: the service fetches the value from the source database.

4. The service writes the value to the cache, and the new entry sits at the front of the recently-used list.

5. If the cache is full, the least-used entry, at the end of the list, is discarded to make room for the new one.

The flow in the diagram is what the primer describes as cache-aside: the application looks in the cache and, if it misses, fetches from the source and updates the cache. To avoid serving a stale value forever, the most direct way to refresh is to give each entry a maximum lifetime, the TTL.

03 · SEVERAL MACHINES

Three ways to use a cluster

The primer starts from two assumptions: traffic is not uniform, and popular queries should almost always be in the cache. When one machine is not enough, there are three ways to distribute the data.

To know which machine holds a query, the primer suggests applying a hash function to the key, something like machine equals hash of the query, and indicates that the most likely choice is to use consistent hashing.

04 · DISTRIBUTING THE KEYS

From simple hashing to consistent hashing

Choosing the machine by the remainder of dividing the hash by the number of nodes works until that number changes. When a node is added or removed, most keys start pointing to another machine, and the entire cache becomes a miss at once, which dumps a flood of requests on the source database.

Consistent hashing avoids this by placing nodes and keys in the same circular hash space. Each key belongs to the first node found going around the ring; if a node joins or leaves, only the keys in its neighborhood change owner. To balance the load, each machine usually appears at several points on the ring, the so-called virtual nodes.

1. The application computes the hash of the requested key.

2. The hash falls in node B's range, so only it is queried; the other nodes do not even take part in the request.

3. If node B does not have the key, the application fetches it from the source database and writes the value to B.

4. Node C goes down. Its range's keys become misses and start pressuring the source database.

5. With consistent hashing, C's range passes to its neighbor on the ring; nodes A and B keep the keys they already had.

Redis Cluster solves the same problem with fixed slots: the key space is divided into 16384 slots, each key's slot is the CRC16 of the key modulo 16384, and each master node takes care of a subset of them. Reconfiguring the cluster means moving slots from one node to another.

Redis Cluster also offers hash tags, which force several keys into the same slot and thus enable operations involving more than one key.

05 · WHEN A NODE GOES DOWN

Replicas and the price of asynchronous replication

The high availability requirement asks that a node going down not take the cache down. The answer is to replicate each partition: if the primary fails, a replica takes over. This is what the prompt describes when it says the set of nodes partitions and replicates the data.

1. The application sends the write to the primary of the partition that owns the key.

2. The primary copies the write to the replica without waiting for its acknowledgment, that is, asynchronously.

3. The primary of partition A goes down.

4. The replica is promoted to primary and the application starts talking to it. Partition B stays intact.

5. Recent writes that had not yet been copied are lost. This is the price of asynchronous replication: the cache stays available, with eventual consistency.

Redis Cluster makes this trade-off explicit: it uses asynchronous replication between nodes and, because of that, there is always a window in which writes can be lost during partitions.

06 · HOT KEYS AND LIMITS

When a single key concentrates the traffic

Hello Interview lists, among the case's deep dives, how to ensure a uniform distribution of keys across nodes and what to do with a heavily read hot key and a heavily written one.

Even with well-distributed keys, the load may not be: a single popular key always lands on the same node. For reads, the usual ways out are to replicate the key on several nodes or to keep it briefly in a local cache inside the application. For hot writes, one way out is to split the key into parts and sum the parts on read.