LFU: Counting Instead of Timing

The crawler that empties your cache

Picture the crawler. At three in the morning a job walks your entire catalogue one product at a time, reading each exactly once.

Follow the damage. Every read misses, every miss fills your cache, and every new entry evicts something. By morning you hold a million products nobody wants and none of the two hundred people actually buy.

See why recency cannot defend you. As far as it can tell, those cold products are the most recently used things in the building, and a scan makes recency a lie.

Counting beats timing

Count instead. Keep a hit counter per key and evict the smallest, so a product read four thousand times today outranks one read once at 3am regardless of which was touched more recently.

Watch the crawler lose. It still fills your cache, and its entries leave first, because their counters never move past one.

Understand the cost before you reach for it, because counting has the opposite weakness. A counter is a memory of the past, so something popular last month keeps its high count and squats long after anybody stopped asking for it.

Notice how backwards that gets: yesterday's viral product outranking today's.

Fix it with decay, reducing every counter periodically so old popularity fades. Redis does this, and it also keeps the counter in eight bits with a probabilistic increment rather than counting exactly, because an exact counter per key costs more memory than the saving is worth.

Accept approximate as the right engineering answer here. Knowing that it is approximate is what stops you trusting those numbers for anything else.

# LRU: evict whatever went longest without a read.
maxmemory 4gb
maxmemory-policy allkeys-lru

# LFU: evict the least often read. Survives a scan, and needs
# decay or last month's favourites never leave.
maxmemory-policy allkeys-lfu
lfu-log-factor 10      # how fast counters saturate
lfu-decay-time 1       # minutes before a counter halves

# The counter is 8 bits and increments probabilistically, so it
# is an estimate. Cheap enough to keep per key, and not a number
# to report to anyone.

Worked example

Arjun's cache had a nightly problem he could see in the graphs and not explain. Hit rate sat at 96 percent through the day, then dropped to 60 by 6am and took two hours to climb back. Nobody was awake to cause it.

It was the catalogue export, walking all 180,000 products once. Under LRU it evicted his entire hot set every night, and the morning traffic paid for refilling it.

Switching to allkeys-lfu fixed it without touching the export. The exported products entered with a count of one and left first, while the 214 products that mattered kept counts in the thousands and stayed. The morning dip went from 36 points to four.