Skip to content

Caching as Space-Time Trade-off

Storing computed or fetched results trades memory for reduced computation/latency; effectiveness depends on the ratio of cache hits to the cost of cache management

Tension Addressed

Memory vs. Computation

Recognizable As

CPU caches, in-memory data stores, CDNs, memoization, lookup tables, precomputed results

Canonical Sources

Denning, "The Working Set Model for Program Behavior" (1968); Smith, "A Survey of CPU Cache Memories" (1982)

Transfers To

Hardware design, database systems, web architecture, any system with repeated access patterns

Sub-concepts: - Cache Hit Ratio: The fundamental metric - percentage of requests served from cache - Temporal Locality: Recently accessed data is likely to be accessed again - Spatial Locality: Data near recently accessed data is likely to be accessed