Three reasons

There are three categories of reason for deploying a cache:

  • Latency is becoming problematic, and you wish to decrease it.
  • As demand grows, capacity isn't able to scale, so you wish to take load off of a central system.
  • Availability is a concern, so you want to introduce redundancy.

Cache invalidation

Caches are deployed in front of a data source intended to act as a single source of truth. They're not writable, instead having their data updated through synchronisation from their data source.

This presents challenges:

  1. How do we identify stale data?
  2. How do we replace the data? a. Replace synchronously as the source of truth changes, ensuring consistency at the cost of write performance; or b. replace asynchronously, using some form of TTL or eviction strategy.
  3. What is our freshness constraint? What time delay is acceptable?

Some cache replacement policies:

  • First in, first out (FIFO)
  • Last in, first out (LIFO)
  • First in, last out (FILO)
  • Least frequently used (LFU)
  • Time-aware least recently used (TLRU)
  • Most recently used (MRU)
  • Pseudo-LRU (PLRU)
  • Random replacement (RR)
  • Segmented LRU (SLRU)
  • Least recently used (LRU)
  • Least frequent recently used (LFRU)
  • LFU with dynamic ageing (LFUDA)
  • Low inter-reference recency set (LIRS)
  • CLOCK-Pro
  • Adaptive replacement cache (ARC)
  • AdaptiveClimb (AC)
  • Clock with adaptive replacement (CAR)
  • Multi queue (MQ)
  • Pannier