What to throw out: LRU, LFU and cache size

A cache keeps a copy of the data that people read most. But memory is smaller than the data. A shop may have one million products, and the cache may hold only a small part of them. So an interviewer asks two questions. "The cache is full and a new entry arrives. What do you remove?" And: "How much memory does the cache need?"

A weak answer says "remove the old ones" or "buy a big cache". A strong answer names a rule, and says which reads it protects and which it hurts. It also works out the size from numbers: how many popular items there are, and how big each one is.

At SDE-1 level you should know that a full cache must remove something, and name one rule. At SDE-2 level you should compare two rules and size a cache with arithmetic. At SDE-3 level you should also explain how a rule fails, and how to see that the cache is too small. Some interviewers ask candidates to write the rule that removes the entry unused for the longest time, in code.

Go back to the tea stall (lesson 31). The board near the counter has room for only 10 prices. A new snack arrives, and the board is full. The owner must wipe one line. Which one? She could wipe the line that nobody asked about for the longest time. Or she could wipe the line that was asked about the fewest times. The two choices are different rules.

A cache has a fixed size in memory. When it is full and a new entry must be stored, the cache removes an old entry. This is eviction. The rule that picks the entry to remove is the eviction policy.

Eviction is not the same as expiry (lesson 31). A time to live (TTL) removes an entry because it is old. Eviction removes an entry because memory is full. A cache can use both. If the TTL is short and the cache never fills, nothing is ever evicted.

Five policies

1. No eviction. The cache refuses new entries when it is full. Redis offers this choice and returns an error for writes (see Sources). For a cache this is rarely right, because the cache stops learning.
2. First in, first out (FIFO). Remove the entry that was stored first. It is simple, but it ignores use. A popular entry that was stored first is removed first.
3. Random. Remove any entry. It costs almost nothing. It works fine when all entries are read about equally often.
4. Least recently used (LRU). Remove the entry that was read or written longest ago. The idea: an entry that was used a moment ago will probably be used again soon. This is the most common policy.
5. Least frequently used (LFU). Keep a count of the reads of each entry, and remove the entry with the lowest count. The idea: an entry that was read often in the past will probably be read often again. When two counts are equal, remove the one that was used longer ago.

How LRU works

LRU needs two things. A hash map finds an entry by its key in one step. A list keeps the entries in order of use. On every read, the entry moves to the front of the list. When the cache is full, the entry at the back is removed. Both steps take the same time however many entries there are. The code below does this with Python's OrderedDict, which is a hash map that remembers order.

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.items = OrderedDict()           # the oldest use comes first

    def get(self, key):
        if key not in self.items:
            return None                      # a miss
        self.items.move_to_end(key)          # now the most recently used
        return self.items[key]

    def put(self, key, value):
        self.items[key] = value
        self.items.move_to_end(key)
        if len(self.items) > self.capacity:
            self.items.popitem(last=False)   # remove the least recently used

Keeping the exact order costs extra memory for the list. So Redis does not keep it. It looks at a few random entries and removes the one used longest ago among them (see Sources).

Where each policy fails

• LRU and a scan. A scan is a job that reads many different entries once each, for example a report over all old orders. Every entry in the scan is "recently used", so it pushes out the popular entries, which then must be read from the database again.
• LFU and a change in taste. An entry that was popular last week has a high count. It stays, even if nobody reads it now. A new popular entry starts with a count of 1, so it is the first to be removed. A fix is count decay: lower all counts slowly over time. Redis does this (see Sources).

Choosing the size of a cache

A cache does not need to hold all the data. It needs to hold the working set: the entries that serve most of the reads. Steps:

1. Count how many entries are in the working set.
2. Find the size of one entry, with its key and the extra bytes the cache adds.
3. Multiply. Add some room, so that new entries do not push out popular ones.
4. Check the result against the hit rate (lesson 31) and the load on the database.

Adding memory has less and less effect. After the working set fits, extra memory only holds entries that are read rarely. To see if a cache is too small, watch two numbers: the hit rate goes down, and the number of evictions per second goes up.

A shopping app has a product cache. We look at the policy first, then at the size.

Part 1: LRU and LFU

Assumptions (made up to teach with): the cache holds 4 entries. A, B and C each have been read 10 times, so their LFU count is 10. The cache starts with A, B and C. A was read longest ago, then B, then C. The reads are X1, X2, X3, X4, X5, then A, B, C.

LRU. The list below goes from the least recently used (left) to the most recently used (right).

LRU gets 0 hits in 8 reads. The scan removed the popular products.

LFU. The counts are A 10, B 10, C 10. X1 has a free slot. From X2, the entry with the lowest count is the previous X (count 1), so each X removes the one before it. A, B and C stay. The last three reads are 3 hits. LFU gets 3 hits in 8 reads.

This answers the predict box: LRU 0 of 3, LFU 3 of 3.

LFU fails too. Next week, A, B and C are not read. A new product D becomes popular. D reads 3 times: its count is 3. A new product arrives. The lowest count in the cache is D with 3, so D is removed, and A, B and C stay with their high counts. With count decay, the old counts fall, and D can stay.

Part 2: the size

Assumptions (made up to teach with, not real traffic):

• The shop has 1,000,000 products. One cache entry is 2 KB, with the key and extra bytes. So all products need 1,000,000 x 2 KB = 2,000,000 KB = 2 GB.
• There are 2,000 reads per second.
• 50,000 popular products get 90% of the reads, which is 1,800 per second. The other 950,000 products share 10%, which is 200 per second. Reads are equal inside each group.
• The database can answer 1,000 missed reads per second (4 ms of CPU each, 4 cores, as in lesson 31).
• Entries leave only by eviction, not by TTL. We ignore the first miss of each entry.
• The policy keeps the most-read entries. This is the best case. A real LRU cache does a little worse.

Look at the table.

• 50 MB is too small. Half of the popular products do not fit, and the database has 10% more work than it can do.
• 100 MB holds exactly the working set.
• Doubling to 200 MB adds only 0.5 points of hit rate (90.5 - 90). The extra memory holds products that are read rarely.
• 2 GB is 20 times the memory of 100 MB, for 10 more points.

Choose. Working set = 50,000 entries x 2 KB = 100,000 KB = 100 MB. Add 20% room (our choice, not a rule): 100 x 1.2 = 120 MB.

• A bigger cache solves a low hit rate: 50 MB gave 110% load on the database, and 100 MB gave 20%. It costs memory, and the gain falls fast after the working set fits (200 MB gave 0.5 points). I would grow the cache only while evictions per second are high and the hit rate is rising.
• LRU solves the common case where recent use predicts the next use, and it is simple. It costs a weak spot: a scan can push out the popular entries. I would change when a scan job reads the cache, or keep that job away from the cache.
• LFU solves the scan, and keeps the stable favourites. It costs more memory for counts, and slow reaction to new favourites unless counts decay. I would use LFU when the popular set is stable.

"LFU is better than LRU, because popular entries matter more." It depends on the traffic. In the example, LFU kept A, B and C during the scan, but it removed the new star D and kept the old ones. LRU would have kept D.

"If I double the memory, I double the hit rate." The hit rate is a share, and it cannot pass 100%. In the example, going from 100 MB to 200 MB moved it from 90% to 90.5%. Look for the working set, not for the biggest cache.

"Eviction and TTL do the same job." A TTL removes an entry because it is old. Eviction removes an entry because memory is full. A cache with a long TTL still evicts when it is full. A cache with a short TTL may never be full.

1. What is eviction, and how is it different from a TTL expiring? What does LRU remove, and what does LFU remove?
2. A shop has 500,000 products. One entry is 4 KB. 10,000 popular products get 80% of 1,000 reads per second. The database can take 300 missed reads per second. (a) How much memory holds the 10,000 popular products with 20% room? (b) A cache that holds only 5,000 of them: what share of reads hit, and is the database safe? (c) With all 10,000 held, how busy is the database?
3. A cache with LRU has a hit rate of 92%. Every night a job reads 2 million old orders once each through the cache. In the morning the hit rate is 40%. Why, and what do you do?