Storage: Hashing and Data Structures

In one line: this lesson answers the two questions that decide a distributed cache's performance: which server holds this key, and how does that server find it in constant time while still supporting eviction?

Hashing, used twice

Hashing is used in two scenarios:

• To identify which cache server should store or retrieve a piece of data.
• To locate a cache entry inside a specific cache server.

Two different problems, both solved by hashing, with different requirements: the first must be stable as servers change, the second must be fast.

Consistent hashing for server selection

For distributing data across servers, consistent hashing is preferred.

With simple hashing — server = hash(key) % N — adding or removing a server forces a remapping of almost all keys, causing a massive cache invalidation event. Consistent hashing minimizes remappings, making it ideal for scalable, fault-tolerant systems.

Why 'massive cache invalidation event' is the exact right phrase

You have met hash % N failing in three chapters now — Databases, Key-Value Store, and Sequencer. Here the consequence has a specific and brutal shape.

When N changes and almost every key remaps, the entries do not move — they are simply looked for in the wrong place. Every one of those lookups is a miss, so the cache hit rate collapses to near zero at the exact moment you were adding capacity, and the full traffic load lands on the database.

That is how adding a cache server takes down the database it was protecting. Consistent hashing avoids it by remapping only a small fraction of keys, so the hit rate dips rather than falls off a cliff.

The Key-Value Store chapter developed consistent hashing and virtual nodes in depth — the ring, the clockwise successor, and the uneven-arc problem. Everything there applies unchanged.

The doubly linked list

We'll use a doubly linked list. The reasons: widespread usage and simplicity, and — more importantly — adding and removing data is a constant-time operation in this design.

Why constant time? Because the operations are only ever:

• Evict a specific entry from the tail, or
• Relocate an entry to the head

Therefore, no iterations are required.

LRU doubly linked list

HEAD                                            TAIL
[Value 1] <-> [Value 2] <-> [Value 3] <-> [Value 4]
 most                                       least
 recently                                   recently
 used                                       used

on access  -> move that node to HEAD    (O(1))
on evict   -> remove the node at TAIL   (O(1))

The pair that makes it work

Neither structure is sufficient alone. Together they are:

Map                        LRU list
Key    | Pointer
Key 1  | ffffx1  ------>   HEAD [Value 1] <-> [Value 2] <-> [Value 3] <-> [Value 4] TAIL
Key 2  | ffffx5  ------------------^
Key 3  | ffffxd  ------------------------------^
Key 4  | ffffxa  ------------------------------------------^

The map stores pointers into the list. A lookup hashes the key, follows the pointer straight to the node, and — because the list is doubly linked — that node can be unlinked and moved to the head without traversing anything.

Bloom filters, for the misses

Bloom filters are an interesting choice for quickly finding if a cache entry doesn't exist. They can tell you an entry is definitely not present, while presence is probabilistic.

That asymmetry is exactly right for a cache: a definite "not here" lets you skip the lookup and go straight to the database, and a false "maybe here" costs only a wasted lookup rather than a wrong answer. Useful in large caching or database systems, particularly where misses are common and lookups are expensive.

What gets stored

The design uses strings for simplicity, but caches can store hash maps, arrays, or sets. That choice turns out to be the main architectural difference between Memcached and Redis — Lesson 11.

Interview signal by level

Next: how the servers are organized, and who talks to them.