Skip to content
Tutorials Center
My learning

Topics

Lesson 30 of 37 ยท Performance and Sizing

Eviction Policies and Capacity Planning

Compare FIFO, random, LRU and a segmented LRU on skewed traffic with a scan, learn how Memcached picks victims, and plan capacity with TTLs, headroom and growth.

A cache is smaller than the data behind it, so something must be thrown out whenever a new item arrives and memory is full. The rule that picks the victim is the eviction policy. A good policy keeps what will be needed soon and discards what will not. Since nobody knows the future, policies guess from the past, and different guesses win on different workloads.

Memcached's rule is a variant of LRU (least recently used). In this lesson you will compare policies with a simulator, see why plain LRU is vulnerable to one-off scans, understand how Memcached's segmented design copes, and then put it together into a capacity plan.

Policies at a glance

  • FIFO: evict the oldest inserted item, ignoring use. Simple, ignores popularity.
  • Random: evict a random item. Surprisingly decent, no bookkeeping.
  • LRU: evict the item whose last access is oldest. Good for temporal locality.
  • LFU: evict the least frequently used item. Good for stable popularity, slow to adapt when popularity changes.
  • Segmented LRU / 2Q / ARC: keep new and proven items in separate lists so a burst of one-time items cannot flush the proven ones.

A policy simulator

Below, the workload mixes Zipf-popular keys with an occasional scan: a batch job or crawler that reads thousands of keys once each. Scans are the classic enemy of plain LRU, because every scanned key looks "recently used" and pushes out genuinely hot items.

Python FIFO, random, LRU and a segmented LRU

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Expect segmented LRU to come out on top or close to it because scan keys only ever enter the probation segment and never evict proven items. Plain LRU is hurt by the scans, and FIFO and random ignore popularity entirely.

How Memcached evicts

Modern Memcached (since 1.5) uses a segmented LRU inside every slab class, with up to four sub-lists:

  • HOT: newly stored items. Items leave the hot list for the cold list as they age (they are not bumped on every read).
  • WARM: items that were hit while in the cold list are promoted here; they are popular.
  • COLD: the candidates for eviction. Memory is reclaimed from the tail of this list.
  • TEMP: short-TTL items (a few seconds), kept apart so they do not interfere.

A background LRU maintainer thread moves items between the lists, and an LRU crawler scans for items already expired and frees them early, so evictions are mostly reserved for items that are still valid. Reading an item only marks it as active rather than relinking it under a lock on every get, which makes reads cheaper under contention. (Details evolve between versions: consult the documentation for your release.)

Eviction happens per slab class: when class 5 has no free chunk, its own cold tail is evicted, even if class 9 has idle pages (the rebalancing topic of Slab Allocator and Memory Sizing).

If you start the server with -M, it stops evicting and instead returns an "out of memory" error on stores. That is rarely what a cache wants, since a cache is supposed to degrade gracefully.

TTLs and eviction work together

Expiry and eviction both remove items, for different reasons:

  • A short TTL frees space automatically and bounds staleness, but increases misses and rebuild cost.
  • A long TTL gives the best hit ratio but keeps rarely used items around until evicted, and allows stale data to live longer.
  • Items without TTL (or a very long TTL) remain until evicted; a cache full of such items has low turnover and relies completely on the eviction policy.

A good rule: set TTLs by staleness tolerance, set memory by working-set size, and let eviction handle everything between.

A capacity plan, step by step

  1. Baseline: measure the hit ratio, evictions per second and memory use from Hit Ratio and Metrics during a normal peak.
  2. Find the working set: the number of distinct keys requested in one TTL window, times the average item size.
  3. Model the curve: replay a production key log through a simulator like the one above at several sizes and read the hit ratio at each.
  4. Choose headroom: peak traffic, a growth forecast for six to twelve months, and the failure scenario from Node Failure and Failover. If losing one node should not double your database load, size accordingly.
  5. Pick node sizes: several mid-sized nodes beat a few huge ones for resilience; fewer nodes mean fewer connections and a simpler ring.
  6. Re-check regularly: items grow, traffic grows, and features change the mix.

The cheapest capacity gain is usually not more RAM but smaller items: remove unused fields, use a compact serialization format and compress large values (see Serialization and Compression).

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What weakness does plain LRU have against a batch scan?

    A scan fills the recently used end of the list with keys that will never be read again, evicting proven items.
  2. 2. Which Memcached sub-list holds the candidates for eviction?

    Memory is reclaimed from the tail of the COLD list; hit items there are promoted to WARM.
  3. 3. Eviction in Memcached is applied per what?

    Each slab class has its own LRU, so a full class evicts even if another class has spare pages.
  4. 4. How should you choose a TTL?

    TTL bounds how wrong a cached value may be; capacity is a separate decision.

Summary

  • Eviction decides what to drop when memory is full; LRU variants fit most web traffic.
  • Segmented designs protect proven items from one-time scans.
  • Memcached uses HOT, WARM, COLD and TEMP lists per slab class, with background threads that move items and free expired ones.
  • TTLs bound staleness; eviction handles capacity.
  • Plan capacity from the working set, a simulated hit-ratio curve, headroom and failure scenarios.

Next: Memcached vs Redis