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

suffers. ARC solves this problem byputting newly cached data inaprobationary state. Ifit
is accessed a second time, it gets out of probation and is put into the main cache. A single
pass through the database flushes the probationary cache, not the main cache.
Many other algorithms exist, but most are variations on the LRU, LFU, and ARC op-
tions.
5.4.5 Cache Entry Invalidation
When data in the primary storage location changes, any related cache entries become ob-
solete. There are many ways to deal with this situation.
One method is to ignore it. If the primary storage does not change, the cache entries do
not become obsolete. In other cases, the cache is very small and obsolete entries will be
eventually be replaced via the cache replacement algorithm. If the system can tolerate oc-
casional outdated information, this may be sufficient. Such situations are rather rare.
Another method is to invalidate the entire cache anytime the database changes. The be-
nefitofthismethodisthatitisverysimpletoimplement.Itleavesthecachecold,however,
and performance suffers until it warms again. This is acceptable in applications where the
cache warms quickly.
The main storage may communicate to the cache the need to invalidate an entry
wheneverthedatainthecachehaschanged.Thismaycreatealotofworkiftherearemany
caches and updates occur frequently. This is also an example of how the CAP Principle,
described in Section 1.5 , comes into play: for perfect consistency, processing of queries in-
volving the updated entry must pause until all caches have been notified.
Some methods eliminate the need for the main storage to communicate directly to the
caches.Thecachecan,forexample,assumeacacheentryisvalidonlyforacertainnumber
of seconds. The cache can record a timestamp on each entry when it is created and expire
entries after a certain amount of time.
Alternatively, the server can help by including how long an entry may be cached when
itanswersaquery.Forexample,supposeaDNSserverrespondstoallquerieswithnotjust
the answer, but also how many seconds each entry in the answer may be cached. This is
calledthetimetolive(TTL)value.Likewise,anHTTPservercanannotatearesponsewith
an expiration date, an indication of how long the item can be cached. If you do not control
theclientsoftware,youcannotbeassuredthatclientswillabidebysuchinstructions.Many
ISPs cache DNS entries for 24 hours at a minimum, much to the frustration of those using
DNSaspartofagloballoadbalancer.Manywebbrowsersareguiltyofignoringexpiration
dates sent by HTTP servers.