Caching

Caching involves storing frequently accessed data in a temporary storage location to improve performance and reduce the need to access slower storage systems.

Deciding when to evict items from the cache when it reaches capacity is a key challenge. If important items are removed, performance can degrade.

Some common cache eviction strategies are:

1. Least Recently Used (LRU): Removes items accessed the longest time ago.
2. Least Frequently Used (LFU): Removes items that have been accessed the least number of times.
3. First in First Out (FIFO): Removes the items added the longest time ago.

As a real-world example, a library “caches” books at the front that are frequently requested, so that patrons can access them quickly without having to wait for the book to be retrieved from the shelves.

The flowchart below shows an example of three books added to the front at different times, with varying popularity. If more space is needed on the shelf, a cache eviction strategy can help you choose which one to remove.

  graph TD
    Hamlet["Hamlet <br/> Added in 1601"]
    Frankenstein["Frankenstein <br/> Added in 1818"]
    KiteRunner["The Kite Runner <br/> Added in 2003"]
    
    Hamlet --> HamletFreq["Checked out 1000 times"]
    HamletFreq --> HamletLast["Last checked out 2 months ago"]
    
    Frankenstein --> FrankensteinFreq["Checked out 200 times"]
    FrankensteinFreq --> FrankensteinLast["Last checked out 1 month ago"]
    
    KiteRunner --> KiteRunnerFreq["Checked out 500 times"]
    KiteRunnerFreq --> KiteRunnerLast["Last checked out 3 months ago"]
    
    Decision{"Choose a cache<br/> eviction strategy"}
    HamletLast --> Decision
    FrankensteinLast --> Decision
    KiteRunnerLast --> Decision
    
    Decision -- "Least Recently Used" --> EvictKiteRunner["Remove The Kite Runner"]
    Decision -- "Least Frequently Used" --> EvictFrankenstein["Remove Frankenstein"]
    Decision -- "First In First Out" --> EvictHamlet["Remove Hamlet"]

As we can see, in the LRU strategy, The Kite Runner is removed because it was accessed the longest time ago. Maybe interest has waned recently.

In the LFU strategy, Frankenstein is removed because it has been checked out the fewest times, even though it was checked out most recently. Possibly from the new Frankenstein movie hype.

In the FIFO strategy, Hamlet is removed because it was added the longest time ago, even though it was checked out the most.