Design a Distributed Cache

The ask

The request is a shared cache for many app servers. Each app server asks the cache before it asks the database.

The working set is the data read often enough to deserve space in memory. The working set is too large for one machine.

Reads matter far more than writes. New values arrive when the database changes, and reads dominate the traffic.

Stale values are acceptable for a short time. Freshness matters less than speed for this design.

Estimate the scale

Reads reach 1,000,000,000 a day.

1,000,000,000 reads / 86,400 seconds = 11,574 reads per second.

One cached item takes 1 KB. The working set holds 100,000,000 items.

100,000,000 items x 1 KB = 100,000,000 KB = 100 GB of cache.

One cache server holds 50 GB in memory.

100 GB / 50 GB a server = 2 shards by capacity.

API and data

A key is the name a value is stored under. Callers ask for values by key.

Get takes a key and returns the value, or reports a miss. Put takes a key and a value and stores the pair.

A time limit can ride with a put. The entry disappears when its time runs out.

Values stay small and self-contained. Large files belong in storage built for whole files.

High-level design

App servers send each key to one cache shard. A shard is one part of the cache, held in memory on its own servers.

Consistent hashing picks the shard for a key. The same key lands on the same shard every time.

Every shard has three copies on different servers.

2 shards x 3 copies = 6 cache servers.

A read asks a copy that holds the shard. A write updates the copies of that shard.

Choosing what stays

Memory fills, so entries must leave. Eviction is the removal of entries to free space.

The least recently used entries leave first. Hot entries get read again and stay.

A time limit guards against very old values. Even popular entries expire and refresh from the database.

Deep dive: a hot key

A hot key is one key read far more than the rest. A famous post or a sale item can turn hot in minutes.

One shard then carries a crowd of reads. Its server slows while the other servers stay calm.

Copying the hot value to more servers spreads the reads. Each copy answers part of the crowd.

Splitting the key into named variants spreads reads too. Callers pick a variant at random, and each variant holds the same value.

The database stays protected either way. The cache absorbs the crowd instead of passing it through.

Keeping values fresh

A cached value can fall behind the database. A price change in the database may not show in the cache at once.

Short time limits bound the staleness. The next read after expiry fetches the fresh value.

Writers can delete the cached entry on each change. The next read rebuilds it from the database.

Perfect freshness costs the speed the cache exists for. This design buys speed and bounds the delay.

When a server fails

Servers fail, and a shard copy can vanish with its machine. The remaining copies keep answering reads.

Checks that a server answers run often between the servers. A silent server is marked down, and its keys move to its copies.

A replacement copy is built from a surviving copy. Reads continue during the rebuild, at lower safety.

Losing every copy of a shard hurts more. Reads then fall through to the database until the shard refills.

Evaluation and trade-offs

The cache answers 95% of reads. The remaining 5% miss and reach the database.

1,000,000,000 reads x 5% = 50,000,000 reads a day reach the database.

50,000,000 reads / 86,400 seconds = 579 reads per second.

Memory costs more than disk per byte. The design pays that cost only for the working set.

Speed is the win, and bounded staleness is the price. The database sees a small, steady load instead of the full crowd.

The scale in numbers