Caching & Eviction: Overview
Caching & Eviction: The Backpack of Speed
The Physics of Memory
Imagine you are a carpenter working at a bench. You have a Tool Belt (Cache) around your waist, and a Tool Shed (Hard Drive) in the backyard.
- The Tool Belt: Itâs small. It holds only 5 tools. But you can grab a hammer in 1 second.
- The Tool Shed: Itâs infinite. It holds everything you own. But walking there to fetch a drill takes 10 minutes.
The goal of Caching is simple: Keep the tools you need right now in your belt. But the belt is small. When you need a 6th tool, you must make a hard choice: Which tool do I take out of my belt to make room?
This decisionâthe âEviction Policyââis what separates a fast system from a slow one.
The Strategy of Survival
In this section, we explore the different philosophies of âWho deserves to stay?â:
| Policy | The Soul / Metaphor | Representative | Best For⊠|
|---|---|---|---|
| Recency | The Pragmatist âIf you havenât been useful lately, youâre out.â | LRU (Least Recently Used) | General Purpose Most real-world access patterns (e.g., browsing history). |
| Frequency | The Historian âI donât care about lately; I care about loyalty.â | LFU (Least Frequently Used) | Static Popularity Things that are always popular (e.g., the Google Logo). |
| Fairness | The Bureaucrat âFirst come, first served. No exceptions.â | FIFO (First In, First Out) | Simplicity Buffers and message queues. |
| Balance | The Grand Strategist Dynamically balances Recency and Frequency. | ARC (Adaptive Replacement Cache) | Complex Workloads Databases and file systems (ZFS). |
The Three Laws of Caching
- Locality of Reference: Programs (and humans) are predictable. If you accessed data X, you will likely access X again soon (Temporal Locality), or access Xâs neighbor (Spatial Locality).
- The Hit Rate: The only metric that matters. If your cache answers 90% of requests, your system is fast. If it answers 10%, your system is slow, no matter how optimized your code is.
- Coherence: There are only two hard things in Computer Science: cache invalidation and naming things. Keeping the âBeltâ updated when the âShedâ changes is the ultimate headache.
Summary
In this section, we will learn how to build memory systems that are smarter than they are large. We will discover that âintelligenceâ is often just the ability to predict the immediate future based on the immediate past.
Letâs start with the most famous algorithm of them all: LRU.