The LRU cache idea

Why this matters

A cache keeps the results of recent work close at hand, so you do not repeat the expensive part. A web server caches a page it just built. A database keeps recently read rows in memory. A phone keeps recently opened apps ready to resume. Memory is limited, so a cache holds only a fixed number of items, and when it is full something must leave to make room. The rule that decides what leaves is called the eviction policy.

The least recently used policy, usually shortened to LRU, removes the item that has gone unused for the longest time. It is a good default, because recent use predicts future use in most real workloads. LRU is also a classic interview design problem. It shows why two data structures are often better than one, and it asks you to make two operations fast at the same time. This lesson builds the cache step by step.

The idea: a desk that holds two books

Picture a small desk that can hold two books. Each time you read a book, you put it on the top of the pile. When a third book arrives and the desk is full, you remove the book at the bottom of the pile. That book is the one you read longest ago, and you have not touched it since. The pile is always ordered from most recently used at the top to least recently used at the bottom.

The desk gives you the policy directly. Reading a book moves it to the top. Adding a new book puts it on the top too, and if the desk is full, the bottom book goes out first. Both moves are easy to do with a real pile, because you only touch the top and the bottom.

A cache needs two abilities at the same time. It must find an item quickly by its key, so you can answer "is this key cached, and what is its value?" It must also keep the usage order, so it can move an item to the top on every use and remove the bottom item when space runs out. The desk does both jobs, but a computer needs data structures that do each job fast.

Why one structure is not enough

Try to build the cache with one structure and it fails in one of the two jobs.

A vector keeps the order easily. The front is the most recent item. But finding a key means scanning the vector, which costs O(n). Moving an item to the front means shifting every element in front of it, which costs O(n) too. Each get or put would scan and shift, so the cache slows down as it grows.

A hash map finds a key in O(1) average time. But it has no order, so it cannot say which key is least recently used. You could store a timestamp with each key and scan for the oldest one, but that scan costs O(n) on every eviction.

A doubly linked list can move a node to the front in O(1) time, and it can remove the back node in O(1) time. But finding a node by key means walking the list from the front, which costs O(n).

The answer is to combine two structures. The hash map finds the node for a key in O(1). The linked list keeps the order and moves nodes in O(1), once you already hold a pointer or iterator to the node. The map stores, for each key, an iterator to its node in the list. The list stores the keys and values in usage order. Each operation uses the map to get to the right node, then the list to reorder.

The list in C++

A linked list is a chain of nodes. Each node holds a value and points to the next node. A doubly linked list also points back to the previous node, so you can move in both directions and remove a node from the middle in O(1) time. C++ provides std::list, which is a doubly linked list. Its member function splice moves a node from one position to another without copying the value. Splicing is the operation that makes LRU fast.

An iterator into a list is like a bookmark that points to one node. The iterator stays valid when other nodes are added or removed, as long as its own node is still in the list. That property is what lets the map keep an iterator to each node safely. Lesson 2 described how an unordered_map can invalidate iterators on a rehash. A list never rehashes, so its iterators are stable, and that is one reason the design works.

Your first LRU cache

The next program builds an LRU cache with capacity 2. It stores integers as keys and values. The get function returns the value for a key, or -1 if the key is not cached. The put function stores a key and value, and it evicts the least recently used item when the cache is full.

The list keeps pairs of key and value, with the most recent pair at the front. The map from key to iterator lets get and put find a node quickly. The program runs a short sequence and prints the results.

The output is:

10
-1
30
10

Trace it, one call at a time. After the two puts, the list holds 2 at the front and 1 behind it. The cache is full. The call get(1) finds key 1 through the map, splices its node to the front, and returns 10. The list is now 1, then 2. The call put(3, 30) finds the cache full with two entries. It removes the back node, which is key 2, from the map and from the list. Then it pushes key 3 to the front. The list is now 3, then 1. The call get(2) misses, because key 2 was evicted, so it returns -1. The call get(3) returns 30. The call get(1) returns 10, because key 1 survived the eviction.

The sequence shows the policy at work. Key 1 was used more recently than key 2, so when space was needed, key 2 was the one that went.

Notice the order of operations inside put. The eviction happens before the new node is pushed. If the code pushed first, the list would briefly hold three items in a cache of two, and the size check would be wrong. Also notice that pos.erase uses order.back().first, the key of the node being removed. The key must be read before the node is popped, because after the pop the node no longer exists.

Keeping the order visible

It helps to see the list at each step. The next program adds a small show method that prints the keys and values from most recent to least recent. It runs a longer sequence with capacity 3, so you can watch the eviction happen once.

The output is:

most recent first: 3=300 2=200 1=100
most recent first: 1=100 3=300 2=200
most recent first: 4=400 1=100 3=300
most recent first: 2=222 4=400 1=100
get 3: -1

Study the four lines of order. After the three puts, key 3 is most recent. The call get(1) moves key 1 to the front, and the list becomes 1, 3, 2. The put of key 4 finds the cache full, so it evicts the back key, which is 2, and the list becomes 4, 1, 3. The put of key 2 with value 222 is a fresh insert, because key 2 was evicted. The cache is full again, so it evicts key 3, and the list becomes 2, 4, 1. The final get(3) misses, which is why it prints -1.

The line for key 2 deserves a second look. Key 2 was gone, so the put created a new node rather than updating one. The old value 200 is not recoverable, because an evicted value is simply dropped. A cache is allowed to forget. Its job is to speed up repeated work, not to keep every value forever.

Step through the animation above. Watch the nodes move to the front on each get and put, and watch the last node disappear when the cache is full.

The LRU order after put of key 4: key 4 at the front, then keys 1 and 3, with the map pointing at each node

The picture shows the same state as the output above, with the map drawn as a column of keys. Each key in the map has an arrow to its node in the list. The arrows are what make get fast: the map jumps straight to the node, and the list reorders it without a search.

Driving the cache from input

A cache is most useful when it runs inside a program that receives a stream of requests. The next program reads the capacity from the first line. It then reads commands until the input ends. Each put key value command stores a value, and each get key command prints the value or -1. At the end it prints how many items remain cached.

Type this into the Input box:

2
put 1 10
put 2 20
get 1
put 3 30
get 2
get 3
get 1

The output is:

10
-1
30
10
items cached: 2

The results match the first program, because the commands are the same. The difference is the source of the input. The loop reads one word at a time. If the word is put, it reads a key and a value. If the word is get, it reads a key and prints the result. The cache does not know or care where the commands come from, which is a good design: the cache is separate from the input format.

The final line reports the size, which is 2. After the last get of key 1, the cache holds keys 3 and 1. The key 2 was evicted by the put of key 3.

A hit-rate simulation

Engineers measure a cache by its hit rate, the fraction of requests served from the cache. A hit means the key was cached. A miss means it was not, and the program must do the expensive work and then store the result. The next program simulates a request stream and counts hits and misses. The cache stores only keys here, because the question is about hits.

The program uses the same map and list, but the list holds keys only. A request for a key is a hit if the map has it. On a hit, the key moves to the front. On a miss, the program evicts the back key when the cache is full, then inserts the new key at the front.

Type this into the Input box. The first number is the capacity, and the second is the number of requests. The keys follow on the next line:

3 8
1 2 3 1 4 1 2 5

The output is:

hits: 2
misses: 6

Trace the stream with a capacity of 3. Keys 1, 2 and 3 are misses, and they fill the cache with 3 at the front. Key 1 is a hit, so it moves to the front. Key 4 is a miss. The cache is full, so it evicts 2, the least recently used key, and the cache holds 4, 1, 3. Key 1 is a hit again. Key 2 is a miss, and it evicts 3. Key 5 is a miss, and it evicts 4, leaving 5, 2, 1. The total is 2 hits and 6 misses.

The hit rate is 2 out of 8, or 25 percent. A larger cache would raise it. In a real system, the question "how big should the cache be?" comes down to measuring the hit rate for a sample of real requests.

Notice that the program does not need the full value to count hits. A real cache stores the value next to the key, and the list node holds both. The principle is identical.

The manual version: what the list does for you

std::list hides the pointers. To see what happens underneath, the next program builds the same cache with a hand-written doubly linked list. Each node holds a key, a value, and two pointers, one to the previous node and one to the next. Two sentinel nodes sit at the ends. A sentinel is a placeholder node with no real data, which removes special cases at the edges of the list. The head sentinel is before the most recent node, and the tail sentinel is after the least recent node.

Read this program slowly. It is the same algorithm as the std::list version, written out in full.

The output is:

10
-1
30
10

The function unlink takes a node out of the list by making its neighbours point at each other. The function pushFront inserts a node right after the head sentinel. Together they implement the splice. Each call changes four pointers, and that is a constant amount of work.

The get function unlinks the node and pushes it to the front. The put function does the same for an existing key. For a new key, it checks the size first. When the cache is full, the node just before the tail sentinel is the least recent, so tail->prev is the one to remove. The code removes it from the list, erases its key from the map, and deletes the node. Only then does it create the new node.

The new and delete calls are the price of doing this by hand. Every node is allocated on the heap, and the destructor frees them. The destructor walks from the head to the end and deletes each node, including the two sentinels. If you forgot the destructor, the program would leak memory. The std::list version avoids this work, because the list frees its own nodes. In production code, prefer the library version unless you have a specific reason to write your own.

Worked example: choosing a capacity

Engineers rarely pick a cache size by guessing. They replay a recent request log against several capacities and compare the hit rates. The program below does the replay for one capacity. The first number on the input line is the capacity, so you can run it four times and compare the results.

Type this into the Input box. The first number is the capacity, and the second is the number of requests:

2 8
1 2 3 1 4 1 2 5

With the first number changed to 1, 2, 3 and 4, the four runs print:

capacity 1: hits 0, misses 8
capacity 2: hits 1, misses 7
capacity 3: hits 2, misses 6
capacity 4: hits 3, misses 5

The hit rate rises from 0 to 3 out of 8 as the capacity grows. Trace capacity 2 to see where its single hit comes from. The keys 1, 2 and 3 are misses, and key 3 evicts key 1. Key 1 is a miss again and evicts key 2. Key 4 is a miss and evicts key 3. Key 1 is a hit, because it was still cached, and it moves to the front. Key 2 is a miss and evicts key 4, and key 5 is a miss and evicts key 1.

A bigger cache does not always help. Once it can hold every key that repeats soon, extra space adds nothing. In a real system, you measure the hit rate on a sample of real traffic, and then you compare the gain with the memory the cache costs. That comparison is the design decision, and the replay is how you make it with evidence.

LRU compared with LFU

LFU stands for least frequently used. An LFU cache evicts the key with the fewest uses, instead of the key with the oldest use. The two policies make different choices on the same request stream, and each one fails on a different kind of traffic.

Take the stream a a a a b c with capacity 2. LRU keeps the two most recent keys. After a is used four times and b arrives, the cache holds b and a. When c arrives, LRU evicts a, the least recent key, and the cache holds c and b. LFU counts uses. Key a has four uses, and key b has one. When c arrives, LFU evicts b, the key with the fewest uses, and the cache holds c and a.

Each policy has a typical failure. LRU suffers from a scan. A long sequence of one-time requests, such as a backup job that reads every file once, pushes out every useful key, because each one is newer than the useful keys. LFU suffers from stale popularity. A key that was popular last month can keep a high count and block new keys that are popular now, even after its use has stopped. Many real caches mix the two ideas, using recency with a frequency filter, so a one-time scan does not evict a hot key.

For an interview, you do not need to build an LFU cache from scratch. Be ready to say how it would differ: a map from key to count, a map from count to a list of keys with that count, and a tracked minimum count to know which list to evict from.

Complexity and memory

Each operation does a constant amount of work after the hash lookup. The map finds the node in O(1) average time. The list changes a fixed number of pointers or splices. So get and put are O(1) on average. The worst case for the map is O(n) when many keys collide, as lesson 1 explained, but a good hash keeps the average constant.

The memory is O(capacity). The list holds at most cap nodes, and the map holds at most cap entries. The cache does not grow with the number of requests, only with its capacity. That bound is what makes a cache safe to run for a long time.

Some implementations add a third structure, such as a counter per key, to support other policies. The LRU policy needs only the map and the list.

What happens inside: iterators and eviction

The map stores an iterator to each list node. Two properties make this design safe. First, a list never rehashes, so its iterators are not invalidated when the list changes. Second, erasing one node invalidates only the iterator to that node. When the cache evicts the back node, it erases that node's key from the map first, so no stale iterator survives in the map.

Look at the order in put once more. The eviction code erases the key from the map before it removes the node from the list, in the std::list version, or uses the key before deleting the node, in the manual version. Reversing the order is a classic bug. It leaves the map pointing at a node that no longer exists, and a later get on that key reads freed memory. That is undefined behaviour, and it can produce wrong values or a crash that appears much later.

Common mistakes

Removing from the list but not from the map. After an eviction, the map still points at the removed node. A later get for that key finds the stale iterator and reads memory that is no longer valid. Always erase the key from the map when you evict its node.

Forgetting that get counts as a use. A get must move the node to the front. If it only reads, the cache evicts a key that was just used, and the hit rate falls. The program in this lesson splices on every hit for that reason.

Using a vector for the order. Moving an element of a vector to the front costs O(n) because every element shifts. The list makes the move O(1) once you hold the node. A vector looks simpler, but it loses the speed that the design is for.

Not updating the value on put. When put is called for a key that is already cached, the value must change, and the node must move to the front. A version that only moves the node keeps the old value, and get returns stale data.

Evicting before checking the size. The eviction must happen only when the cache is full and the key is new. Evicting on an update wastes a slot and drops a value the caller did not expect to lose.

Capacity zero. A cache of capacity 0 must refuse every put. The class in this lesson does not check for that case. When cap is 0 and a put arrives, the size check order.size() == cap is true for an empty list, and order.back() is called on an empty list. That is undefined behaviour. The fix is one line at the top of put: if (cap == 0) return;. A reviewer will look for this case, so mention it when you explain your design.

Testing an LRU cache

Test the cache with small cases whose answers you can predict before you run them. Each case below checks one rule from the spec, and a failing case points at a single line of code.

• Capacity 1. Every new key evicts the only key. After put 1, put 2, get 1 must print -1.
• Update does not evict. With capacity 2, put 1, put 2, put 1 11 must leave both keys cached, and get 2 must still return its value.
• Get counts as a use. With capacity 2, put 1, put 2, get 1, put 3 must evict key 2, not key 1.
• Eviction removes the map entry. After an eviction, get on the evicted key must return -1, not a stale value or a crash.
• Repeated key keeps size one. Putting the same key ten times must leave one item cached.

After the small cases, write a random test. Generate a long sequence of random put and get commands on a small key range, such as keys 1 to 5 and capacity 3. Run the same sequence through a slow reference that keeps a plain vector of pairs, searches it, and moves the hit to the front. The slow version is easy to trust, and the fast version must print exactly the same answers on every step. Compare the two outputs with diff, and when they differ, shrink the sequence until the smallest failing case is short enough to trace by hand.

A debugging walkthrough

Suppose your cache returns old values after an update. The symptom is that get returns the first value written to a key, even after a later put. Start by checking the update branch in put. The branch must set the new value on the node, not just move the node. Print the node's value before and after the update to confirm.

Next suppose the cache evicts the wrong key. The usual cause is a get that does not move the node. Trace a short sequence by hand, with capacity 2, a put of 1, a put of 2, a get of 1, and a put of 3. Key 2 should be evicted, because key 1 was used more recently. If your program evicts key 1, the get did not move the node to the front.

Last, suppose the program crashes after many operations. Check the eviction order. The map must lose the key before the node is freed. Add a check that the map size and the list size are equal after every operation. If they ever differ, the eviction code is wrong, and the first operation that breaks the equality shows the bug.

A test with a capacity of 1 catches most of these bugs quickly, because every new put evicts the only node. Run that test first.

Interview angle

LRU cache is a common design question. The interviewer usually asks you to implement get and put in O(1) time. A strong answer names the two structures and says why each one is needed. It explains the map from key to node, the list for order, and the splice that moves a node without a search. It states the complexity and the memory bound.

Expect follow-up questions. An interviewer may ask how you would handle concurrent access. The answer is a lock around both structures, because a lock must cover the map and the list together, or they can disagree. They may ask about a least frequently used policy. The answer is a different structure, often a map from count to a list of keys, with the minimum count tracked. They may ask about time-based expiry, where each entry also has a deadline. The answer adds a check on each access, and possibly a sorted structure for the deadlines.

Real uses

Caches built on this idea run in most systems you use. A web browser caches recently viewed pages. A database keeps a buffer pool of recently read disk pages in memory. A content delivery network keeps popular files on servers near users. An operating system page cache keeps recently read file data in memory. Hardware processors use related schemes for their small, fast caches. The details differ, but the core question is the same: which item to drop when space runs out, and the LRU answer is a strong default.

Module summary

• A hash function maps keys to buckets. Collisions are handled by chaining, or by probing in open addressing.
• unordered_map and unordered_set give average O(1) operations. The bracket operator inserts missing keys, so use find or count to test membership.
• map and set stay sorted with O(log n) operations, and lower_bound and upper_bound answer nearest-value and range questions.
• Two Sum, frequency counting and prefix-sum maps turn O(n squared) searches into O(n).
• An LRU cache combines a hash map for lookup with a doubly linked list for usage order, and both get and put run in O(1) average time.

Practice

1. Add a method size() that returns how many items are cached. Test it after each step of the first trace.

2. Change the cache so put on an existing key does not move the node to the front. Trace a sequence that shows the bug, and explain what changes in the output.

3. Add a method remove(key) that deletes a key from the cache if it is present, and returns true when a key was removed.

4. Trace by hand a sequence of operations on a cache of capacity 3: put 1, put 2, put 3, get 1, put 4, get 2, put 5, get 3, get 4. Write down the list after each step, and then run the program to check.

5. Change the simulation so it counts evictions as well as hits and misses. Predict the eviction count for the input 3 8 and the keys 1 2 3 1 4 1 2 5 before you run it.

6. Write a cache with capacity 1. Trace what happens when two different keys alternate. Explain why the hit rate is 0.

7. Explain in your own words why the eviction must read the key before the node is removed in the manual version.

8. Modify the manual version so the destructor is not needed. Use unique_ptr to own the nodes, and explain what changes in the code.

9. Write a short paragraph that compares a vector-based cache with the list-based cache. Give the cost of get and put in each.

10. Explain how the hit rate changes as the capacity grows, for the same request stream. Predict the hit rate for capacity 4 with the stream from the simulation.

11. The sentinel nodes make the list code shorter. Explain what would go wrong at the front or back of the list without them.

12. Design an LFU cache at a high level: say which two structures it needs, and what it stores for each key.

What you now know

• An LRU cache evicts the least recently used item when it is full, which is a strong default when recent use predicts future use.
• A hash map finds a node in O(1) average time, and a doubly linked list keeps the usage order and moves nodes in O(1).
• Neither structure works alone. A vector shifts and a list searches, so each one is too slow for one of the two jobs.
• get and put both move a node to the front. put on a new key evicts the back node when the cache is full.
• Erase the key from the map before you free or remove its node, or the map keeps a stale iterator.
• Check the capacity-zero case, and make sure updates change the value as well as the position.
• A hit rate measures how well a cache fits its requests, and a simulation shows it before you build the real system.

The module assignment that follows combines the containers and this cache into a single program. Use it to check how much of the module you can apply.