6 Caching

Caching is presented as the final data-focused latency optimization, complementing colocation, replication, and partitioning. It accelerates access by keeping temporary copies of hot data closer to where it’s used, trading freshness and some complexity for speed. Caches may live in memory or persist to disk (reducing cold starts but increasing coordination risk), and their effectiveness hinges on cache hits versus misses, captured by the cache hit ratio. Beyond positive results, negative caching avoids repeating expensive lookups for absent items. Because caches are capacity-limited, they must evict entries, and every choice—persistence, eviction, and freshness—balances latency, storage, and consistency needs. Caching is most compelling for simple key-value access patterns, systems that are hard to modify, or environments constrained by compute and storage.

The chapter surveys read and write strategies and their latency-consistency trade-offs. With cache-aside, applications fetch and populate on misses; with read-through, the cache fetches and can add features like refresh-ahead to hide miss costs. For writes, write-through synchronously updates the backing store (higher latency, stronger sync), whereas write-behind acknowledges quickly and flushes asynchronously (lower latency, weaker durability/consistency). Client-side caching minimizes last-mile latency but complicates transactions and increases memory use; distributed caches introduce partitioning, replication, and coherence concerns akin to replicated systems. Maintaining strict coherence across caches is costly, illustrated by CPU MESI-style protocols—many distributed caches therefore tolerate staleness. Crucially, tail latency remains because misses pay full backing-store cost, so geography and miss handling still matter.

Maximizing cache hit ratio is central: average latency trends toward hit latency as hits rise, so shape access patterns and size caches to the working set. Replacement policies should match workload: LRU favors recency/locality, LFU protects long-term popularity, and FIFO variants like SIEVE combine simplicity with selective reinsertion to avoid evicting hot items. TTL provides simple, time-based invalidation to manage freshness when updates bypass the cache, but choosing durations balances hit ratio against staleness and can cause needless churn if the backing data hasn’t changed. Adjacent techniques further reduce latency: materialized views precompute query results (often with incremental, eventually consistent updates), and memoization caches function outputs to avoid repeated computation. A practical in-application cache for a REST API shows broad latency reductions yet retains a heavy tail—underscoring the need to pair the right strategy, sizing, and freshness controls to the workload while working to lower miss costs.

With cache-aside caching, client first looks up a key from the cache. On cache miss, the clients queries the database and updates the cache.

With read-through caching, client looks up a key from the cache. Unlike with cache-aside caching, the cache queries the database and updates itself on cache miss.

With write-through caching, client writes a key-value pair to the cache. The cache immediately updates cache and the database.

With write-behind caching, client writes a key-value pair to the cache. However, unlike with write-through caching, the cache updates cache but defers the database update. Instead, write-behind cache will batch multiple cache updates to a single database update.

Average cache access latency (y-axis) approaches cache hit latency as the cache hit ratio (x-axis) increase towards 100%.

Cache latency distribution when hit ratio is 80% with cache hit latency of 0.1 seconds and cache miss latency of 1.0 seconds.

Least recently used (LRU) replacement policy evicts values from the cache based on when they were last accessed.

Least frequently used (LFU) replacement policy evicts elements based on how frequently they were used.

First-in, first-out (FIFO) replacement policy evicts elements based on when they were added to the cache. The SIEVE algorithm is a variant of FIFO, which keeps track of cached elements that were accessed to avoid evicting hot elements.

REST API latency eCDF comparing PostgreSQL and PostgreSQL with Moka caching.

• Caching is a technique for speeding up data retrieval by storing temporary copies of data closer to where it’s accessed, similar to colocation or replication but with different trade-offs. The primary goal of caching is to reduce the latency and complexity involved in data access.
• Different caching strategies, cache-aside, read-through, write-through, and write-behind caching, vary in how the cache integrates with the backing store. The various strategies have different trade-offs between latency and complexity because of how they deal with reading and writing.
• In many applications, you end up using distributed caching, meaning multiple copies of the cache exist. This indicates that you need to deal with cache coherency in the cache unless your application can cope with cache incoherency.
• Maximizing the hit ratio of your cache is the key to uncovering low-latency access. Different cache replacement policies such as LRU, LFU, and FIFO mandate that entries are evicted from a cache when fully occupied, impacting the hit ratio.
• Time-to-live (TTL) is a way to deal with data freshness in a cache by specifying how long an entry can be considered valid in a cache until it has to be retrieved again from the backing store. However, TTL is often tricky to get right and can result in a low cache hit ratio if TTL is too low or an application reading stale data if TTL is too high.
• Materialized views is a technique to speed up database queries by building a copy of the data, organized in views, which can be queried like database tables when constructed.
• Memoization is a technique to cache the results of computation. Although the term comes from dynamic programming, an everyday use of memoization is to cache the results of REST API calls, which often combine computation and data access.

FAQ