CSE Roadmap

Core tier · about 3 hours · 6 parts

Part 5 of 6 · 3 min read

Memory limits and sizing

How to work out how many entries fit, and how much spare room to leave.

Memory limits and sizing

Think of a wardrobe with a fixed number of hangers. Count the clothes you wear often, add space for the new ones you buy, and leave a few empty hangers so that you are not forced to throw something out in the middle of a week.

A cache has a memory limit. The size needed comes from three numbers: how many entries, how big each one is, and how much overhead the cache adds per entry.

Size = entries × (value size + overhead per entry)

A worked example, with made-up figures. The hot set is 3,000,000 entries. A value averages 1.5 KB. Each entry has 100 bytes of overhead for the key, pointers and expiry time.

  1. Per entry: 1,500 + 100 = 1,600 bytes.
  2. Total: 3,000,000 × 1,600 = 4,800,000,000 bytes, about 4.8 GB.
  3. The book advises over-provisioning memory by some percentage, as a buffer when use grows. With 25 percent spare: 4.8 × 1.25 = 6 GB.

What happens when the limit is too low? The hit ratio falls and the miss rate climbs, since the cache evicts entries that would have been read again. A way to see the effect is to watch the eviction rate: the number of entries evicted per second. If entries are evicted shortly after being added, the cache is too small. If evictions are near zero and memory is far from full, the cache may be larger than needed.

Signal What it suggests
Hit ratio falling, evictions rising Cache too small for the hot set
Memory full, evictions low, hit ratio high Cache about right
Memory half empty, hit ratio high Cache larger than needed
Hit ratio low, evictions low Poor locality: the cache may not suit this data

Two memory-saving ideas:

  • Store only what is needed. Cache the fields a page uses, not the full row with 40 columns.
  • Compress large values. Text compresses well. This trades CPU time for memory.

Some designs split memory by use, so that one noisy key type cannot evict everything else. A separate cache or a separate limit for each kind of data keeps the product catalogue from being flushed by session data.

Interview angle

Answer in your head first, then open it.

What eviction policy do you use?

LRU as a default, and say why: recent use predicts near-future use. Name the case that breaks it (a scan) and how to guard against it.

How do you pick a TTL?

From the staleness the business allows and the cost of a reload. Add jitter and active invalidation for important changes.

How big should the cache be?

Entries in the hot set × entry size, plus overhead, plus spare room. Show the arithmetic and the hit ratio you aim for.

What if the cache is too small?

Evictions rise, the hit ratio falls and the database takes the load. Watch the eviction rate.

Check yourself:

  • A cache must hold 2,000,000 entries of 800 bytes with 80 bytes of overhead each, plus 20 percent spare. What size?
  • A falling hit ratio and a rising eviction rate point to which problem?

Words you will meet

Word Plain meaning
Eviction Removing an entry because the cache is full
Expiry Removing an entry because it is too old
TTL Time to live: how long an entry may stay
Lazy expiry Checking age only when the entry is read
LRU Evict the least recently used entry
LFU Evict the least frequently used entry
FIFO Evict the oldest arrival
MRU, MFU Keep or evict by most recent or most frequent use, for special cases
Random replacement Evict an entry chosen at random
Jitter A random extra time on a TTL to spread out expiry
Eviction rate Entries evicted per second
Overhead Extra bytes the cache keeps per entry