Caching and content delivery: every cache trades freshness for speed

A cache is a promise made before the answer is known: the copy it holds is good enough to serve now, at a lower latency than the truth would cost. Breslau and colleagues (1999) found the request stream at a web proxy skewed enough that a cache pays for itself, and the same bet recurs at every layer of the stack. The claim argued here is narrower. A cache buys latency with staleness, so the design question is where to place the cost of invalidation and who may act on a stale answer. Placement is a topology decision about which tier answers. Permission is a meaning decision about how stale an answer may be, and a surface an attacker can write to. The one is settled by measurement and the other by specification, and the two are more entangled than the literature admits. The four units that follow leave performance for authority, starting with the password.

A cache is a bet on a skewed request stream

Caching only pays if requests repeat. Breslau and colleagues (1999) found page requests follow a Zipf-like distribution whose exponent varies from trace to trace. Correlations between request frequency and document size or rate of change were weak. A simple independent-request model reproduced the observed hit-ratio and locality behaviour, so those properties belong to web access rather than one trace.

Fitzpatrick (2004) gave the bet an operational form. LiveJournal ran 28 memcached instances across ten hosts to hold the most popular 30 gigabytes of a site with 2.5 million accounts, for a hit rate around 92 per cent. The application consulted the cache deliberately, so it owned the decision about what could be stale.

Freshness is a policy, not a property

What a cache may serve is defined by the protocol. Fielding, Nottingham and Reschke (2022) define a stored response as fresh when its age has not exceeded its freshness lifetime. The same specification bounds the promise: a cache must not reuse a response once stale. Freshness is a counting rule about time, not a claim about truth.

A "fresh" response is one whose age has not yet exceeded its freshness lifetime. Conversely, a "stale" response is one where it has. (Fielding, Nottingham and Reschke, 2022)

Nottingham (2010) turned that rule into a declared policy with two directives. Stale-while-revalidate lets a cache serve stale immediately while revalidating in the background. Stale-if-error lets it serve stale when the origin returns an error. Such a cache is otherwise invisible, so Nottingham (2022) defined the Cache-Status header, by which each cache reports whether it stored or reused a response and under what parameters.

That permission is also a surface an attacker can write to. Liang and colleagues (2024) tested the Tranco top thousand domains with a cache-key-aware tool and found more than 1,000 websites across 172 domains, 17 per cent of those measured, vulnerable to poisoning through inputs their cache keys did not cover. The rule that lets a cache answer without asking the origin is the rule that lets a forged answer travel.

What to keep is a policy too

If permission governs what a cache may serve, eviction governs what it can. Rizzo and Vicisano (2000) analysed proxy traces spanning up to five months and proposed LRV, which values a document by recency, frequency and size together rather than by recency alone. Two caches of equal capacity therefore return different hit rates, so the benefit lies in the policy, not the size.

On the UNIPI and DEC proxy traces, covering up to five months, LRV returned a consistently higher byte hit rate than least recently used, least frequently used, a size-based policy and first in first out. The gap was widest for a small cache, which is the regime a designer is usually arguing about and the one a constrained device lives in. The result is a simulation on two traces rather than a deployment, so it establishes a direction rather than a number to plan against.

The cost of caching is invalidation, not lookup

A miss costs a lookup the application would have paid anyway. A stale hit costs correctness. Fitzpatrick (2004) noted that trying the cache, falling back to the database and repopulating leaves race conditions. Nishtala and colleagues (2013) described the memcached tier behind a large social network, processing over a billion requests per second, and the machinery that kept it consistent: leases grant a client a token to write a value back after a miss, so concurrent writers cannot install a stale set, and an invalidation path has a write delete cached data because deletes are idempotent. The authors are candid that the cache may lose data without notice.

Placement decides who answers

Rodriguez, Spanner and Biersack (2001) modelled hierarchical and distributed caching and derived client-perceived latency, bandwidth use and cache load for each. Cooperation helped most where cache populations were small, and an optimal number of caches to cooperate exists at each level, so more caches do not automatically mean lower latency.

Nygren, Sitaraman and Sun (2010) described a delivery platform of more than 61,000 servers across nearly 1,000 networks in 70 countries. Its mapping system assigns each client to a server by measured performance rather than static distance, since proximity is a proxy for speed rather than the thing itself. Krishnan and colleagues (2009) found that redirecting every client to its least-latency server does not suffice: queueing delays often override the benefit of a nearby server.

If the endpoint can choose, the designer's control over placement weakens. Goel, Wittie and Steiner (2015) proposed a client-side process that shares the balance decision with the content network, choosing among resolved servers by last-mile performance. Across five major providers it cut page load time by 29 per cent on average, by 40 per cent where the domain was already resolved, and by up to 43 per cent for individual static objects.

Contested question: does caching still pay, and who should decide?

One position holds that more and closer caching is the answer and that the gains are measured. Goel and colleagues (2015) report a 29 per cent average reduction in page load time from client-assisted selection. Satyanarayanan (2017) argues that cloud offloading fails where latency or bandwidth are tight, so a tier of nearby compute is required.

The opposing position holds that returns diminish and the cost moves. Breslau and colleagues (1999) show a hit ratio improving gradually with capacity. Krishnan and colleagues (2009) show proximity failing to deliver promised latency because queueing dominates, and Rodriguez and colleagues (2001) show an optimal degree of cooperation rather than a monotone gain. Nishtala and colleagues (2013) locate the real cost in invalidation logic and a consistency problem that grows with the tier. Caching still pays, but it shifts a cost rather than removing one.

A third position moves the question from performance to control. Stocker and colleagues (2017) describe a delivery ecosystem far more complex than the caches it grew from, and analyse how location and interconnection shape who reaches whom. The question becomes who owns the path on which the answer travels. The evidence that would settle the dispute is a controlled comparison across one content set and one client population: no cache, an origin-side cache, an edge cache and a client cache, reporting together the user-visible latency, the invalidation traffic each generates, and the share of responses served stale. No study above reports all three for the same workload.

The evidence is uneven across the three positions. The caching-pays position rests on a proxy-trace distribution (Breslau et al., 1999) and a client-assisted measurement (Goel et al., 2015); the diminishing-returns position on a simulation of two traces (Rizzo and Vicisano, 2000) and latency measurement (Krishnan et al., 2009); the control position on an ecosystem survey (Stocker et al., 2017). The designer therefore budgets user-visible latency and invalidation traffic together and states how stale an answer may be served. The strongest objection is that this unit's claim that invalidation is the real cost rests on one operator's description of its own tier (Nishtala et al., 2013), which reports the machinery rather than comparing it against an uncached system.

Where the argument is heading

The direction of travel is that the cache is becoming programmable, observable and consolidated, and the permission question is turning into one of ownership. Satyanarayanan (2017) makes the case for placing compute at the edge for applications such as wearable cognitive assistance. He names the obstacle that matters here: such a tier needs stateless servers, the same displacement of state a cache raises. Stocker and colleagues (2017) describe an ecosystem whose complexity now bears on interconnection markets, so location is also a question about which networks must interconnect to serve a user. Nottingham's (2022) Cache-Status header makes those decisions visible. The invalidation cost will not shrink; it will move towards the tiers that can afford to be wrong, and who may act on a stale answer will be settled increasingly by whoever operates the edge.

The sources this unit rests on

• Breslau, L., Pei Cao, Li Fan, Phillips, G. and Shenker, S. (1999). Web caching and Zipf-like distributions. IEEE INFOCOM '99. doi:10.1109/infcom.1999.749260 Measured proxy traces and found page requests follow a Zipf-like distribution whose exponent varies by trace, with only weak correlations between access frequency and document size, and between frequency and its rate of change. A simple independent-request model reproduced the observed hit-ratio and locality behaviour, the quantitative reason a finite cache works and why its returns are gradual.
• Fitzpatrick, B. (2004). Distributed caching with memcached. Linux Journal. https://www.linuxjournal.com/article/7451 Reported that LiveJournal ran 28 memcached instances across ten hosts to cache the most popular 30 gigabytes of a site with 2.5 million accounts, for a hit rate around 92 per cent. The cache was consulted explicitly by the application, which therefore owned the decision about what could be stale.
• Rizzo, L. and Vicisano, L. (2000). Replacement policies for a proxy cache. IEEE/ACM Transactions on Networking. doi:10.1109/90.842139 Analysed proxy traces spanning up to five months and proposed LRV, valuing a document by recency, frequency and size together. It outperformed least recently used and other policies, most clearly for small caches, so eviction policy sets a cache's benefit as much as capacity does.
• Fielding, R., Nottingham, M. and Reschke, J. (2022). HTTP caching. RFC 9111. https://www.rfc-editor.org/rfc/rfc9111 Defines freshness lifetime, reuse of a stored response while it is fresh, and the rule that a cache must not reuse a response once stale. It is the normative statement of the trade the unit describes.
• Nottingham, M. (2010). HTTP cache-control extensions for stale content. RFC 5861. doi:10.17487/rfc5861 Defines stale-while-revalidate, which serves a stale response immediately while revalidating in the background, and stale-if-error, which serves stale when the origin returns an error. Both make the amount of acceptable staleness a declared policy rather than a binary.
• Nottingham, M. (2022). The Cache-Status HTTP response header field. RFC 9211. doi:10.17487/rfc9211 Defines a header by which each cache reports whether it stored or reused a response and under what parameters. It is the measurement instrument the unit needs, since a cache's behaviour is otherwise invisible from either end.
• Nishtala, R. and colleagues (2013). Scaling memcache at Facebook. USENIX Symposium on Networked Systems Design and Implementation. https://www.usenix.org/conference/nsdi13/technical-sessions/presentation/nishtala Described the memcached tier behind a large social network, processing over a billion requests per second and storing trillions of items, and the mechanisms keeping it consistent, including leases that prevent stale sets and an invalidation path in which writes delete cached data. The authors state the cache may lose data without notice and that invalidation is not transactional.
• Rodriguez, P., Spanner, C. and Biersack, E. W. (2001). Analysis of web caching architectures. IEEE/ACM Transactions on Networking. doi:10.1109/90.944339 Modelled hierarchical and distributed caching and derived client-perceived latency, bandwidth use, cache load and disk use for each. Cooperation helped most where cache populations were small, and the authors found an optimal number of caches to cooperate at each level.
• Nygren, E., Sitaraman, R. K. and Sun, J. (2010). The Akamai network. ACM SIGOPS Operating Systems Review. doi:10.1145/1842733.1842736 Described a delivery platform of more than 61,000 servers across nearly 1,000 networks in 70 countries, and a mapping system that assigns each client to a server by measured performance rather than static geography. It is the canonical account of measurement-based placement.
• Krishnan, R. and colleagues (2009). Moving beyond end-to-end path information to optimise CDN performance. ACM SIGCOMM Internet Measurement Conference. doi:10.1145/1644893.1644917 Measured latencies from a large content distribution network to clients across the internet and found that redirecting every client to its least-latency server does not optimise client latency. Queueing delays often overrode the benefit of a nearby server, so proximity is a proxy rather than the goal.
• Goel, U., Wittie, M. P. and Steiner, M. (2015). Faster web through client-assisted CDN server selection. ICCCN 2015. doi:10.1109/icccn.2015.7288411 Proposed a client-side process that shares server selection with the content network and measured it across five major providers. It reduced page load time by 29 per cent on average, by 40 per cent where the domain was already resolved, and by up to 43 per cent for individual static objects.
• Satyanarayanan, M. (2017). The emergence of edge computing. Computer. doi:10.1109/mc.2017.9 Argues that cloud offloading fails where latency or bandwidth are tight and that a tier of nearby compute is required, illustrating the case with applications such as wearable cognitive assistance and naming the need for stateless servers. It is the application-level case for placing compute and content at the edge.
• Liang, Y., Chen, J., Guo, R., Shen, K., Jiang, H., Hou, M., Yu, Y. and Duan, H. (2024). Internet's Invisible Enemy: Detecting and Measuring Web Cache Poisoning in the Wild. Proceedings of the 2024 ACM SIGSAC Conference on Computer and Communications Security (CCS). doi:10.1145/3658644.3690361 Tested the Tranco top thousand domains and found 17 per cent vulnerable to cache poisoning through inputs the cache key does not cover. The permission a cache grants is an attack surface.
• Stocker, V., Smaragdakis, G., Lehr, W. and Bauer, S. (2017). The growing complexity of content delivery networks. Telecommunications Policy. doi:10.1016/j.telpol.2017.02.004 Surveys the content delivery ecosystem and the forces that drove its evolution, outlines the network architectures and their strengths and weaknesses, and highlights location and the ecosystem's growth in complexity for interconnection markets. It widens the unit from a technical cache to an infrastructure argument about who reaches whom.