Caching Trade-offs in Distributed Systems: Strategies, Invalidation and Production Patterns

by
Home » Distributed Systems » Scalability & Performance » Caching Trade-offs in Distributed Systems: Strategies, Invalidation and Production Patterns

Distributed Systems Series — Part 5.5: Scalability & Performance

The Most Powerful and Most Dangerous Scalability Technique

Caching is the highest-leverage performance technique available in distributed systems. A cache hit costs microseconds. A database query costs milliseconds. A cache that absorbs 90% of read traffic reduces database load by 90%, reduces read latency by an order of magnitude, and allows the system to serve ten times the read volume without adding database capacity. No other single technique produces comparable throughput and latency improvement at comparable cost.

Caching is also the technique that produces the most subtle, hardest-to-diagnose production failures. Phil Karlton’s observation — “there are only two hard things in computer science: cache invalidation and naming things” — is cited constantly because it is empirically true. Systems that cache correctly under normal conditions fail in confusing ways when data changes, when cache servers restart, when new nodes join a cluster, or when traffic patterns shift. The failure mode is not an error — it is a user receiving stale data that appears correct.

This post covers the five placement layers where caches live, the read and write strategies that determine consistency behaviour, cache invalidation and why it is genuinely hard, the thundering herd problem and its production solutions, Redis vs Memcached as the two dominant implementations, cache warming as a deployment discipline, and the consistency trade-offs that connect caching to the consistency models established in Post 3.3.

Where Caches Live: Five Placement Layers

The diagram above shows the five layers where caches can be placed in a request path. Each layer intercepts requests before they reach the next layer, protecting the downstream from load. Each layer has different characteristics, different data types it is suited for, and different invalidation complexity.

Client-side cache lives in the browser or mobile application. HTTP cache headers — Cache-Control, Expires, ETag, Last-Modified — instruct clients to store responses and serve them from local storage for subsequent identical requests. A browser that caches a product image for 24 hours serves that image from local storage without making any network request for 24 hours. This eliminates network latency entirely for cached content and reduces origin server load. The cost is staleness — the client serves cached content until the TTL expires, regardless of whether the content has changed. Client-side caching is appropriate for static assets (images, CSS, JavaScript) and slowly-changing public data. It is inappropriate for user-specific or frequently-changing data.

CDN (edge) cache stores responses at geographically distributed edge nodes close to users. When a user in Europe requests content from a US-based origin, the CDN edge node in Europe serves the cached response without the request crossing the Atlantic. This reduces latency from 80-100ms (transatlantic round trip) to 5-10ms (edge to user). CDNs are appropriate for static assets, public API responses, and semi-static content (product catalogs, marketing pages). Cloudflare, Fastly, and AWS CloudFront all implement edge caching. Cache invalidation at CDN scale is non-trivial — purging cached content from hundreds of edge nodes simultaneously requires explicit API calls to each CDN provider.

Application-level cache stores the results of database queries, computed responses, or external API calls in a shared in-memory store — typically Redis or Memcached — accessible to all application instances. This is the most commonly implemented cache layer for dynamic data. It protects the database from read query load. A cache hit returns data in under a millisecond from memory rather than 5-50ms from the database. Application caches require the most careful invalidation logic because the data is dynamic and changes must propagate correctly.

Database buffer pool is the internal cache that every major database engine maintains — PostgreSQL’s shared_buffers, MySQL’s InnoDB buffer pool, the buffer cache in most storage engines. The database automatically caches recently accessed data pages in memory, serving subsequent reads from memory rather than disk. This cache is transparent to the application — the database manages it internally. Tuning the buffer pool size to fit the working set in memory is one of the highest-value database performance optimisations available. A database whose working set fits in the buffer pool serves reads at memory speed. A database whose working set exceeds the buffer pool constantly reads from disk — orders of magnitude slower.

Compute cache memoises expensive computation results within a single application instance — results of CPU-intensive calculations, parsed configuration objects, compiled template objects. This is the simplest form of caching and requires no external infrastructure. Its scope is limited to one instance and its lifetime is bounded by the process restart.

Read Strategies: How Applications Interact With the Cache

Cache-aside (lazy loading) is the most widely deployed read strategy. The application checks the cache first. On a cache hit, it returns the cached value. On a cache miss, it fetches the data from the database, stores it in the cache with a TTL, and returns it to the caller. The cache is populated lazily — only data that is actually requested ends up in the cache.

Cache-aside is the correct default for most application caches. Its advantages are simplicity and flexibility — the application controls exactly what gets cached, with what TTL, and can implement different caching logic for different data types. Its disadvantages are cache miss latency (a cold cache after restart produces database queries for every request) and the thundering herd problem (discussed in detail below).

Cache-aside with Redis requires three operations for a cache miss: a Redis GET (cache miss), a database query, and a Redis SET. These three operations are not atomic. Two concurrent requests for the same cache miss can both see a miss, both query the database, and both write to the cache — producing two identical database queries and two identical cache writes. This is acceptable when database queries are idempotent (which read queries are) but produces doubled database load for popular cache misses.

Read-through cache places the cache as a proxy between the application and the database. The application always reads from the cache. On a miss, the cache itself fetches from the database, populates itself, and returns the result. The application never talks to the database directly for reads. This simplifies application code — the application has one data source to query — but reduces flexibility, as the caching logic is centralised in the cache layer rather than distributed across application code.

Write Strategies: How Writes Propagate to Cache and Database

Write-through writes to the cache and the database synchronously on every write. Both must succeed before the write is acknowledged to the caller. The cache is always consistent with the database — a cache hit always returns the current value. The cost is write latency: every write waits for two storage operations rather than one. For write-heavy workloads, write-through approximately doubles write latency. For read-heavy workloads where write latency is acceptable, write-through is the correct choice for data that must be strongly consistent between cache and database.

Write-back (write-behind) writes to the cache immediately and acknowledges the write to the caller without waiting for the database write. The cache asynchronously persists writes to the database in the background. Write latency is minimal — the caller receives acknowledgement as soon as the cache write completes. Throughput is high — the cache batches writes to the database, reducing write amplification.

The cost is durability. Data written to the cache but not yet persisted to the database is lost if the cache node fails before the async write completes. The recovery point objective (RPO) is the age of the oldest unflushed write — typically seconds to minutes depending on the flush interval. Write-back is appropriate for workloads where some data loss is acceptable (analytics events, log aggregation, social feed updates) and inappropriate for workloads where every write must be durable (financial transactions, inventory decrements, order commits).

Redis’s append-only file (AOF) and RDB snapshot persistence modes mitigate write-back data loss risk. AOF logs every write command to disk before acknowledging — with `fsync always` configuration, this provides the same durability as a database write. The trade-off is the same as write-through: persistence adds latency. `fsync everysecond` (the default) provides durability to within one second of writes at lower latency cost.

Write-around writes directly to the database, bypassing the cache. The cache is populated on the next read miss. This prevents write-heavy data from displacing read-heavy data from the cache — a write-around strategy ensures the cache holds only data that has been read, not data that has only been written. It is appropriate for data that is written frequently but read rarely, where caching write results would evict more valuable read results from limited cache memory.

Cache Invalidation: Why It Is Genuinely Hard

Cache invalidation is hard not because the mechanism is complex — setting a TTL, deleting a key, or publishing an invalidation event are all simple operations. It is hard because the correct invalidation logic depends on distributed state that is difficult to reason about: which keys are cached where, which application instances hold stale data, and whether a cache update and a database update happened in the correct order.

Time-based expiration (TTL) is the simplest invalidation mechanism. Every cached entry has a configured lifetime after which it is considered stale and discarded. The application sets the TTL at cache write time: short TTLs (seconds to minutes) for frequently changing data, long TTLs (hours to days) for slowly changing data.

TTL-based invalidation trades consistency for simplicity. Data remains stale until the TTL expires. For a product price updated in the database, the cached price is incorrect until TTL expiry. The acceptable staleness window — the maximum time a user can see stale data — is the design constraint that drives TTL selection. For most consumer applications, seconds to minutes of staleness are acceptable. For financial data and inventory, zero staleness is required — which means TTL-based invalidation is inappropriate.

Event-based invalidation deletes or updates cached entries immediately when the underlying data changes. A database update triggers a cache delete for the affected key. The next read for that key misses the cache and fetches fresh data from the database. This produces lower staleness than TTL-based invalidation but requires the application to track which cache keys are affected by each data change and to issue invalidation calls consistently.

Event-based invalidation has a race condition that produces stale reads even in correct implementations. The sequence: (1) application reads from cache — miss; (2) application reads from database — returns value V1; (3) another process writes V2 to the database; (4) another process invalidates the cache key; (5) original application writes V1 to the cache. The cache now contains V1, which is stale, and no TTL or invalidation will remove it until the next write to that key. This race condition is rare but real, and it is why cache consistency is analysed using the same framework as distributed database consistency — it is the same problem.

Cache versioning embeds a version number in cache keys rather than invalidating by key deletion. When data changes, the version number increments. New reads use the new version key (cache miss, fresh data). Old version keys expire naturally via TTL. This eliminates the invalidation race condition — there is no deletion that can race with a concurrent read — but leaves stale version keys in the cache until their TTLs expire, consuming memory.

Facebook’s TAO system, which serves the social graph for billions of users, uses a combination of these strategies. TAO caches social graph edges in geographically distributed cache clusters. Write-through propagates updates to the master cache cluster. Asynchronous replication propagates to replica clusters with bounded staleness. This produces eventual consistency between cache replicas with a well-defined staleness bound — the same PACELC trade-off from Post 3.4 applied at cache scale.

The Thundering Herd: The Most Dangerous Cache Failure Mode

The thundering herd (cache stampede) occurs when a popular cache entry expires and many concurrent requests simultaneously experience a cache miss. All concurrent requests proceed to query the database simultaneously. The database, which was protected from this query load by the cache, receives a sudden spike of identical queries. If the database cannot handle this spike — which it frequently cannot, because it was sized assuming cache absorption — the database becomes overloaded, query latency increases, queries begin timing out, and the cascade of failures that Post 4.7’s bulkhead patterns are designed to prevent begins.

The thundering herd is worst for the most popular cache entries — the entries that were absorbing the most traffic. When the entry that was serving 10,000 requests per second expires, all 10,000 simultaneous requesters hit the database. This is precisely backwards from the intuition that popular data is safe — popular data produces the largest thundering herd when it expires.

Probabilistic early expiration (PER) is the production solution that addresses the thundering herd without requiring distributed coordination. The algorithm: when a cache entry is accessed, calculate the probability of recomputing it based on how close its expiry time is and how long the recomputation takes. As the entry approaches expiry, the probability of early recomputation increases. One request triggers early recomputation well before the TTL expires, refreshing the cache entry before the stampede would occur.

The formula: recompute if current_time - (beta * recompute_time * log(random())) is greater than expiry_time, where beta is a tuning parameter (typically 1.0) and random() is a uniform random number between 0 and 1. A request arriving shortly before expiry has an increasing probability of triggering early recomputation. The first request to trigger recomputation refreshes the cache — subsequent requests continue serving the existing cache entry until it is refreshed. No coordination between requesters is required.

Cache locking (mutex-based prevention) uses a distributed lock to ensure only one request recomputes the cache entry on a miss. The sequence: request arrives, cache miss detected, attempt to acquire a lock for this cache key. If the lock is acquired, recompute from the database, populate the cache, release the lock. If the lock is not acquired (another request is recomputing), wait briefly and retry the cache read — the lock holder will have populated the cache by the time the waiter retries.

Redis SETNX (Set if Not Exists) with an expiry implements this pattern — the lock itself has a TTL to prevent deadlocks if the lock holder crashes before releasing. The limitation is that all waiters must pause during recomputation. For expensive recomputations, this produces a latency spike for all concurrent requesters during the lock hold period. PER is preferable for most cases because it eliminates waiting entirely — the cache is refreshed before it expires, so there is no miss for concurrent requesters to wait on.

Cache warming is the deployment practice that prevents the thundering herd after a cache restart or deployment. A cold cache — empty after restart — produces cache misses for every request, sending every request to the database simultaneously. Cache warming pre-populates the cache before routing production traffic to the new cache instance. This can be done by replaying recent request logs against the new cache, by copying the cache contents from a warm peer, or by running a warm-up script that populates the most popular keys from the database before traffic arrives.

Twitter’s migration from Memcached to Redis in 2012 documented cache warming as a critical operational step. Each Redis instance was populated from its corresponding Memcached instance before traffic was migrated, ensuring that the new Redis instances had warm caches and the database was not exposed to cold-cache traffic during the migration window.

Redis vs Memcached: The Production Decision

Redis and Memcached are the two dominant application-level cache implementations. Both are in-memory key-value stores with millisecond response times. The choice between them is not arbitrary — they have meaningfully different capabilities that suit different use cases.

Memcached is a pure key-value cache. It stores strings against string keys. It is multi-threaded, using all available CPU cores efficiently. It is simpler to operate than Redis — there is less configuration surface, fewer failure modes, and lower operational complexity. For workloads that require only simple key-value storage of string data, Memcached often achieves higher throughput per CPU core than Redis due to its multi-threaded architecture.

Memcached’s limitations: no persistence (data is lost on restart), no replication (a Memcached node failure loses all its data with no failover), no data structure support beyond strings (no sorted sets, lists, or hashes), and no pub/sub for cache invalidation events. For pure caching workloads where data loss on cache node failure is acceptable (the cache will simply miss and refetch from the database), Memcached is a valid and performant choice.

Redis supports rich data structures — strings, hashes, lists, sorted sets, sets, bitmaps, HyperLogLogs, and streams. This makes Redis useful for use cases beyond simple caching: sorted sets for leaderboards, lists for queues, pub/sub for event propagation, and streams for event sourcing. Redis supports persistence through RDB snapshots and AOF logging, allowing cache data to survive restarts. Redis Cluster provides horizontal sharding across multiple nodes with automatic failover. Redis Sentinel provides high availability for single-node Redis through automatic leader election.

Redis is single-threaded for command execution (though I/O is multi-threaded in Redis 6+). For CPU-intensive workloads on servers with many cores, this can make Redis less efficient than Memcached per core. In practice, Redis’s single-threaded command execution is rarely the bottleneck — network I/O and memory bandwidth are more commonly limiting factors.

The practical decision: use Redis by default for new systems. Its persistence, replication, cluster mode, and data structure support provide operational flexibility that Memcached cannot match. The performance difference is negligible for most workloads. Use Memcached only when you have specific evidence that Redis’s single-threaded execution is a bottleneck and your use case requires nothing beyond simple key-value string storage.

Cache Consistency and the Consistency Model Connection

Cache consistency is not a binary property — it sits on the same spectrum as database consistency models from Post 3.3. Different caching strategies produce different positions on this spectrum, and the right position depends on the application’s consistency requirements.

Write-through caching with synchronous invalidation produces linearisable cache consistency — reads always return the current value. This is appropriate for financial data, inventory counts, and any value where reading a stale value produces incorrect application behaviour.

TTL-based caching produces eventual consistency with a bounded staleness window equal to the TTL. Reads return the current value eventually — within TTL seconds of the last write. This is appropriate for social feed data, recommendation results, and analytics dashboards where bounded staleness is acceptable.

CDN caching with long TTLs produces eventual consistency with a staleness window of hours. This is appropriate for static assets and marketing content that changes infrequently, and inappropriate for any data that users expect to see updated immediately after a change.

The CAP theorem from Post 3.4 applies to cache clusters as it does to databases. During a network partition between cache nodes, a cache cluster must choose between serving potentially stale data (availability) or refusing to serve reads (consistency). Redis Cluster in the default configuration chooses availability — reads are served from the available nodes even if some writes may be lost during the partition window. Strongly consistent cache reads require either a single Redis node (no partition risk) or accepting the performance cost of coordinating reads across the quorum of nodes.

When Not to Use Caching

Caching is not universally beneficial. Three scenarios where caching adds complexity without value:

Highly dynamic data changes faster than any acceptable TTL. Caching data that changes every second with a one-second TTL provides minimal benefit (each cache entry serves at most one request) while adding cache read latency, write complexity, and invalidation overhead. For data that changes at the same rate as it is requested, caching is counterproductive.

Strict consistency requirements where every read must reflect the most recent write cannot be satisfied by any cache implementation that tolerates staleness. Financial account balances, inventory availability checks before a purchase commitment, and permission checks that must reflect the current access policy all require reads from the authoritative source, not a potentially stale cache. Caching these values produces correctness violations.

Write-heavy workloads where writes significantly outnumber reads produce cache churn — entries are written and invalidated before they accumulate read hits. A cache that is invalidated on every write and reads the database for every miss provides no benefit over direct database reads, at the cost of added cache infrastructure and invalidation complexity. The cache hit rate is the measure: if a cache consistently achieves below 20-30% hit rate, it is probably not beneficial for that data access pattern.

Key Takeaways

  1. Caching is the highest-leverage performance technique in distributed systems — a well-designed cache absorbs 90%+ of read traffic, reducing database load by an order of magnitude and improving read latency from milliseconds to microseconds
  2. Cache placement at five layers (client, CDN, application, database buffer pool, compute) each protects a different downstream resource — the correct layer depends on the data type, change frequency, and audience (public vs user-specific)
  3. Cache invalidation is genuinely hard because it involves distributed state and race conditions — event-based invalidation has a fundamental race between concurrent reads and writes that produces stale cache entries even in correct implementations
  4. The thundering herd (cache stampede) is the most dangerous cache failure mode — probabilistic early expiration prevents it without distributed coordination by refreshing popular entries before they expire, eliminating the concurrent miss that triggers database overload
  5. Write strategy determines the consistency-durability trade-off — write-through provides zero RPO at the cost of higher write latency, write-back provides low write latency at the cost of potential data loss on cache failure, write-around avoids cache pollution for write-heavy data
  6. Use Redis by default over Memcached — persistence, replication, cluster mode, and rich data structures provide operational flexibility that justifies the choice for all but the most throughput-sensitive pure key-value workloads
  7. Cache warming is a mandatory deployment practice — a cold cache after restart sends all traffic to the database simultaneously, producing the same thundering herd that cache expiry produces, and must be pre-populated before production traffic is routed to the new instance

Frequently Asked Questions (FAQ)

What is cache-aside and why is it the most common caching strategy?

Cache-aside (lazy loading) checks the cache first on every read. On a cache miss, it fetches from the database, stores the result in the cache with a TTL, and returns the value. It is the most common strategy because it is simple to implement in application code, flexible (different TTLs and caching logic per data type), and resilient — cache failures degrade gracefully to direct database reads without application errors. Its main disadvantages are cache miss latency (a cold cache produces database queries for every request) and the risk of thundering herd on popular entry expiry.

What is the thundering herd problem and how do I prevent it?

The thundering herd (cache stampede) occurs when a popular cache entry expires and many concurrent requests simultaneously experience a cache miss, all proceeding to query the database simultaneously. The database, sized assuming cache absorption, is overwhelmed by the sudden spike. The standard prevention is probabilistic early expiration (PER): as a cache entry approaches its expiry, each access has an increasing probability of triggering early recomputation. One request refreshes the cache before it expires, preventing the concurrent miss. Redis SETNX-based mutex locking is an alternative — only one request recomputes on a miss while others wait and serve the cached result after recomputation.

What is the difference between Redis and Memcached?

Both are in-memory key-value stores with millisecond response times. Memcached stores only strings, is multi-threaded (higher throughput per CPU core), has no persistence (data lost on restart), and no replication. Redis supports rich data structures (hashes, lists, sorted sets, streams), optional persistence via RDB and AOF, replication with automatic failover (Redis Sentinel), and horizontal clustering (Redis Cluster). For most use cases, Redis is the better default — its operational flexibility justifies the choice. Use Memcached only when you have specific evidence that Redis’s execution model is a bottleneck and your use case requires only simple string key-value storage.

What is write-through caching and when should I use it?

Write-through caching writes to both the cache and the database synchronously on every write — both must succeed before the write is acknowledged. The cache is always consistent with the database. The cost is write latency: every write waits for two storage operations. Write-through is appropriate for data that must be strongly consistent between cache and database — product prices, account balances, permission flags — where a stale cache read would produce incorrect application behaviour. It is inappropriate for write-heavy workloads where the doubled write latency is unacceptable.

How does caching relate to the CAP theorem?

Cache clusters face the same CAP trade-off as distributed databases. During a network partition between cache nodes, the cluster must choose between serving potentially stale data (availability) or refusing reads (consistency). Redis Cluster in its default configuration chooses availability — reads continue from available nodes even if some writes during the partition may be lost. Applications requiring linearisable cache reads must either use a single Redis node (eliminating partition risk at the cost of single-node availability) or accept the latency cost of quorum-based reads across the cluster. The choice maps directly to the PACELC framework from Post 3.4: during normal operation, the latency vs consistency trade-off; during partitions, the availability vs consistency trade-off.

What is cache warming and why is it required after deployments?

Cache warming pre-populates a cache with data before routing production traffic to it. A cold cache — empty after a restart or new deployment — produces cache misses for every request, sending all traffic to the database simultaneously. This is equivalent to a thundering herd at deployment scale: the database receives the full production request volume with no cache absorption. Cache warming prevents this by populating the most frequently accessed keys from the database or from a warm peer cache before traffic is routed to the new instance. Without cache warming, every deployment that restarts cache nodes produces a brief but potentially severe database overload spike.

Continue the Series

Series home: Distributed Systems — Concepts, Design & Real-World Engineering

Part 5 — Scalability & Performance

Previous: ← 5.4 — Load Balancing Strategies in Distributed Systems

Next: 5.6 — Backpressure and Overload Management->

Related posts from earlier in the series:

Discover more from Rahul Suryawanshi

Subscribe now to keep reading and get access to the full archive.

Continue reading