CSE Roadmap

Core tier · about 3 hours · 7 parts

Part 6 of 7 · 4 min read

Sizing and failure of the cache

How many nodes are needed, what to do when the cache is down, and why the system must work without it.

Sizing and failure of the cache

Think of a bridge built to carry trucks. If the bridge is closed for repair, the town must still have a road, even a slow one. A town that has only the bridge is in trouble the day it closes.

Sizing. Three limits decide the number of cache nodes:

  1. Memory. The size of the hot set with overhead (module 3).
  2. Throughput. Requests per second a node can answer.
  3. Network. Bytes per second through a node's network link.

A worked example. The hot set with spare room is 120 GB. A node has 32 GB, of which 80 percent is usable for data, 25.6 GB. Nodes needed for memory: 120 ÷ 25.6 = 4.7, so 5. The traffic is 400,000 reads a second, and a node handles 100,000. Nodes needed for throughput: 4. The network: 400,000 reads of 2 KB = 800 MB a second = 6.4 Gbit/s. A node has a 10 Gbit/s link and should run below about 70 percent, 7 Gbit/s, so spread over 5 nodes each carries 1.3 Gbit/s. The answer is the largest of the three, 5 nodes, and one or two extra so that a failure still leaves enough capacity: 6 or 7 nodes. The book "System Design Interview" recommends over-provisioning memory by some percentage as a buffer.

Failure. The book "Understanding Distributed Systems" asks the question: if the external cache is down, how should the service react? It might seem fine to bypass the cache and go straight to the dependency. But the dependency is usually shielded by the cache, so it may not be ready for the surge, and a cache outage can cause a cascading failure that takes the dependency down too.

Defences from the book:

  • Use an in-process cache in the clients as a defence against the external cache being unavailable.
  • Prepare the dependency for sudden surges. Load shedding is a technique to do this: reject some requests at once so that the rest can be served.

The book also makes a wider point. A cache gives the system a bi-modal behaviour: most of the time the cache works and all is fine, and when it does not, the system has to survive without it. It is a design smell if the system cannot cope at all without its cache. The book "Building Microservices" adds the idea of hiding the origin: a miss raises an event and the origin refills the cache in the background, while the original request fails fast.

A worked example. Traffic is 60,000 reads a second with a 95 percent hit ratio, so the database serves 3,000. The cache dies.

Plan Database load What users get
Bypass the cache 60,000 a second Database fails, all users see errors
In-process caches with 70 percent hits on the 57,000 former hits 3,000 + 17,100 = 20,100 Database still overloaded
In-process + shed to a limit of 6,000 6,000 Local copies serve what they hold, the database gets 6,000 a second, other misses get a fast error
Hide the origin, refill in background Controlled by the refill rate Fast errors for misses, then recovery

The table shows that a bypass is the worst plan, and that the database's own limit must be part of the design.

Interview angle

Answer in your head first, then open it.

In-process or distributed cache?

Name both. In-process is fastest and inconsistent. Shared is consistent between servers and costs a network trip and another service. Combine them: a small local cache with a short TTL in front of a shared one.

How do you spread keys over cache nodes?

Consistent hashing, so adding or removing a node moves a small share of keys, not most of them.

How do you size the cache?

Hot set size with overhead and spare room, requests per second per node, and network. Take the largest and add nodes for failures.

What happens if the cache goes down?

Do not send all traffic to the database. Use local caches, shed load, and refill in the background. The system must survive without the cache.

Memcached or Redis?

Both are in-memory stores. Memcached is for caching only, Redis offers data structures and optional persistence. For caching, treat the contents as disposable.

Check yourself:

  • Why can bypassing a failed cache make things worse?
  • A hot set is 60 GB. A node has 16 GB with 75 percent usable. How many nodes does memory alone need?

Words you will meet

Word Plain meaning
In-process cache A cache in the memory of each application instance
Out-of-process cache A separate cache service shared by all instances
Replicated cache Every unit holds a full copy of the cache
Distributed cache The data lives in a central cache, and units ask it
Near-cache A small front cache in each unit backed by a full distributed cache
Consistent hashing A scheme where adding or removing a node moves few keys
Virtual node One of many positions a node takes on the hash ring
Cold start An instance that starts with an empty cache
Bi-modal behaviour The system acts differently when the cache works and when it fails
Load shedding Rejecting some requests to protect a limited resource
Cascading failure One failure overloads the next part, which fails too