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?”:

The Three Laws of Caching

1. 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).
2. 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.
3. 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.