Part 2 of 6 · 2 min read
Requirements
What a cache promises, and what it costs.
Think of a small desk with room for five books. You keep the ones you use. When a sixth is needed, you put away the book you have not touched for longest. That is the least-recently-used rule, and the desk is the cache.
The "System Design Interview" book describes the eviction problem in the same way: once the cache is full, adding an item may force an existing item out. It names least-recently-used as the most popular policy, with least-frequently-used and first-in first-out as other choices.
Questions and the answers assumed here:
- What does the cache store? Key and value pairs, with a fixed capacity.
- What operations?
get(key)andput(key, value). - What cost? Both in constant time on average, for any capacity.
- What counts as "use"? Both
getandputmake a key the most recently used. - Many threads? Yes.
- Out of scope for now: expiry times, size in bytes, and persistence.
The numbered requirements:
- R1. The cache holds at most
capacityentries, and capacity is at least 1. - R2.
getreturns the value if present, and marks the key as most recently used. - R3.
putstores the value, marks the key as most recently used, and updates the value if the key exists. - R4. When a new key arrives at full capacity, the least recently used key is removed first.
- R5.
getandputrun in constant time. - R6. The cache is safe for many threads.
The nouns are cache, key, value, entry, capacity and order. The central question is how to know the least recently used key quickly.
Eviction
Eviction is removing an entry from a full cache to make room for a new one.
Example: removing the key that has gone unused for longest when a new key is added.
Check yourself:
1. Which two operations count as a "use"?
2. What is the cost target for get and put?
3. What does eviction do?