Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)

I was very excited when I actually got to implement it on a real world project.

I was writing a scale out job which used ffmpeg to make clips of video files. To speed it up I kept the downloaded files (which could be 150 GB in size) as a local cache. Quite often a clip is made of the same file. When the disk was full (there was a separate disk for download and clip output) selected two of the downloaded files randomly and deleted the older one. Loop till there was enough disk space, or no files.

It's something I thought I would never actually get to implement in the real word, and thus far is working very well, the caching speeds things up and the eviction seems to avoid too many cache misses.

It is a tree algorithm for tracking the approximate last use time.

When the access pattern is random: recently used items are not more likely to be accessed than other items.

Or worse: the access pattern is "anti-recent": items recently accessed are less likely to be accessed again than other items.

This is undergraduate stuff I once had to know for exams in machine architectures and operating systems.

The choice of LRU replacement is favorable when there exists "locality of reference"; that's what it's predicated upon.

All of the replacement policy choices are only substitutes for a "magic oracle": a replacement strategy which can peer into the future and know which items will be accessed soonest. With a magic oracle, we can not only retain those items in the cache in preference to other items, to great advantage, but we can automatically prefetch the correct items that are not yet in the cache but are about to be accessed.

In general, randomized algorithms provide a defense against situations in which things don't work out according to the best case assumptions. For instance, they help defend against tickling worst cases in algorithms (e.g. sorting) that have good average-case behavior.