Design Patterns for Scaling - The Practice of Cloud System Administration - page 106

5.4.3 Cache Persistence
When a system starts, the cache is usually empty, or cold . The cache hit ratio will be very
lowandperformancewillremainslowuntilenoughquerieshave warmed thecache.Some
caches are persistent, meaning they survive restarts. For example, a cache stored on disk
is persistent across restarts. RAM is not persistent and is lost between restarts. If a system
has a cache that is slow to warm up and is stored in RAM, it may be beneficial to save the
cache to disk before a shutdown and read it back in on startup.
Case Study: Saving a RAM Cache to Disk
Stack Exchange's web sites depend on a database that is heavily cached in RAM
by Redis. If Redis is restarted, its performance will be unacceptably slow for 10
to 15 minutes while the cache warms. Redis has many features that prevent this
problem, including the ability to snapshot the data held in RAM to disk, or to use
a second Redis server to store a copy of the cache.
5.4.4 Cache Replacement Algorithms
When a cache miss is processed, the data gathered by the regular lookup is added to the
cache. If the cache is full some data must be thrown away to make room. There are many
different replacement algorithms available to handle the cache manipulation.
Ingeneral,betteralgorithmskeeptrackofmoreusageinformationtoimprovethecache
hit ratio. Different algorithms work best for different data access patterns.
The Least Recently Used (LRU) algorithm tracks when each cache entry was used and
discards the least recently accessed entry. It works well for access patterns where queries
arerepeatedoftenwithinasmalltimeperiod.Forexample,aDNSservermightusethisal-
gorithm:ifadomainhasnotbeenaccessed inalongtime, chances areitwon'tbeaccessed
again. Typos, for example, rarely repeat and will eventually expire from the cache.
TheLeastFrequentlyUsed(LFU)algorithmcountsthenumberoftimesacacheentryis
accessed and discards the least active entries. It may track total accesses, or keep an hourly
or daily count. This algorithm is a good choice when more popular data tends to be ac-
cessed the most. For example, a video service might cache certain popular videos that are
viewed often while other videos are viewed once and rarely ever rewatched.
New algorithms are being invented all the time. Tom's favorite algorithm, Adaptive
Replacement Cache (ARC), was invented in 2003 ( Megiddo & Modha 2003 ). Most al-
gorithms do not perform well with a sudden influx of otherwise little-used data. For ex-
ample, backing up a database involves reading every record one at a time and leaves the
cache filled with otherwise little-used data. At that point, the cache is cold, so performance