Caching

A cache increases retrieval performance by reducing trips to slower storage. It trades capacity for speed, storing a transient subset of data. Caches exploit locality of reference — "recently requested data is likely to be requested again." A cache hit is when data is found in the cache; a cache miss means it must be fetched from the source and written into the cache for next time.

1. Learning Objectives

By the end of this lesson, you will be able to:

• Explain the core concept of caching and its reliance on the locality of reference principle.
• Analyze cache read patterns (Cache-Aside, Read-Through) and write patterns (Write-Through, Write-Around, Write-Back) and identify when to apply each.
• Evaluate eviction policies (LRU, LFU, FIFO, TTL-based) and their implementation trade-offs.
• Compare distributed caching architectures, including client-side caching, CDN caching, reverse proxy caching, and application/distributed caches (e.g., Redis, Memcached).
• Identify failure modes unique to caching (e.g., Cache Stampede, Cache Penetration, Cache Avalanche, Cache Invalidation issues) and design mitigation strategies for them.

2. Prerequisites

To fully comprehend the concepts discussed in this lesson, you should be familiar with:

• Basic client-server communication paradigms (HTTP, TCP/IP).
• Standard relational and non-relational database design concepts (queries, read/write latency).
• Memory hierarchy basics (Register vs. L1/L2/L3 Cache vs. RAM vs. SSD/HDD storage latency profiles).
• Basic data structures (HashMap/Hash Table, Doubly Linked List, Queue).

3. Why This Topic Matters

In modern web-scale systems, data retrieval speed and server capacity are major bottlenecks. Databases, which rely on disk storage or complex index queries, typically respond in milliseconds to tens of milliseconds. Caching allows us to store frequently requested, computationally expensive, or slow-to-retrieve data in high-speed, volatile random-access memory (RAM).

By serving requests from a cache, we can reduce retrieval latency from ~50ms down to sub-millisecond ranges, while offloading up to 90% of the query traffic from our underlying database instances. Without caching, platforms like Netflix, Twitter, or Amazon would collapse under the weight of repetitive database reads, leading to skyrocketing cloud costs and sluggish user experiences.

4. Real-world Analogy

Imagine you are a librarian working in a massive university library. The library has millions of books stored in deep stacks across several floors (analogous to the database on disk). Retrieving a book requested by a student takes 10 to 15 minutes of walking up and down stairs.

To save time, you set up a small desk cart next to your checkout counter. This cart can only hold 20 books (the cache). When a student asks for a textbook, you first check your cart. If it is there (a cache hit), you hand it to them instantly. If it isn't (a cache miss), you must walk into the stacks to retrieve it, hand it to the student, and then place a copy on your cart for the next student. When the cart is full and a new book must be added, you remove the book that has not been read for the longest time (eviction policy).

5. Core Concepts

Understanding caching requires mastering several foundational technical concepts:

• Locality of Reference: The principle that computer programs tend to access the same data or nearby memory locations repeatedly.
  • Temporal Locality: If a resource is accessed once, it is highly likely to be accessed again in the near future (e.g., a trending tweet).
  • Spatial Locality: If a resource is accessed, nearby resources are likely to be accessed soon after (e.g., retrieving page 2 of a list after page 1).
• Cache Hit and Cache Miss:
  • Cache Hit: The system successfully locates the requested data in the cache memory.
  • Cache Miss: The system fails to find the data in the cache, forcing it to fetch the data from the slower primary storage.
• Hit Ratio: The fraction of read requests that are successfully served by the cache. It is calculated as: Hit Ratio = Cache Hits / (Cache Hits + Cache Misses).
• Eviction Policy: The algorithm that determines which item to remove from the cache when it reaches its maximum storage capacity to make room for new data.
• Cache Invalidation: The process of explicitly removing or updating cache entries when the source data changes to prevent serving stale data.

6. Visualization

The diagram below illustrates the standard Cache-Aside pattern workflow, contrasting a cache hit and a cache miss.

Below is a sequence diagram showcasing the flow of data under cache hit versus cache miss conditions:

7. How It Works

To implement caching effectively, we must manage the lifecycle of the data stored inside it. This includes read strategies, write strategies, and eviction mechanisms.

A. Read Strategies

• Cache-Aside (Lazy Loading): The application coordinates both the cache and the database. When reading:
  1. The application checks the cache.
  2. If it's a hit, it returns the data.
  3. If it's a miss, it queries the database, writes the result to the cache, and then returns the data.
• Read-Through: The cache sits in-line with the database. The application talks only to the cache library or service. On a cache miss, the cache itself automatically queries the database, populates itself, and returns the data to the application.

B. Write Strategies

How data is updated in the database and cache simultaneously determines data consistency and write latency:

• Write-Through: Data is written to the cache and the database synchronously.
  • Pros: High consistency; reads are fast because the cache is always up to date.
  • Cons: High write latency because every write requires two network round-trips.
• Write-Around: Data is written directly to the database, completely bypassing the cache.
  • Pros: Prevents cache pollution (loading cache with data that won't be read immediately).
  • Cons: A read immediately after a write results in a cache miss.
• Write-Back (Write-Behind): The application writes data immediately to the cache, which confirms the write instantly. A background worker periodically aggregates these writes and pushes them to the database asynchronously.
  • Pros: Extremely fast writes; reduces database write pressure (write coalescing).
  • Cons: Risk of data loss if the cache node crashes before the dirty data is flushed to the database.

8. Internal Architecture

A distributed caching system (like Redis or Memcached) is structured to operate with minimal latency. Under the hood, it consists of several sub-components, each carrying distinct architectural responsibilities:

Component	Responsibilities	Key Failure Points
Storage Engine (In-Memory Engine)	Manages key-value pairings in RAM; utilizes hash maps or skip lists to achieve O(1) reads and writes.	Out of memory (OOM) errors; fragmentation of memory block allocations.
Eviction Manager	Tracks metadata (e.g., access frequency, modification times) and removes items when capacity thresholds are breached.	CPU spikes under high eviction load; sub-optimal policy selection leading to low cache hit ratios.
TTL Scheduler	Passively or actively deletes keys that have exceeded their designated Time-To-Live (TTL).	Memory leaks if expired keys are not actively pruned (passive eviction only removes keys on read attempts).
Cluster Manager / Hash Ring Coordinator	Routes read/write requests to correct physical shards using techniques like consistent hashing.	Network partitions causing split-brain scenarios; rebalancing latency during node additions/removals.

9. Request Lifecycle

Let's walk through the end-to-end lifecycle of a client request using a Cache-Aside strategy:

1. Request Arrival: Client triggers an API request (e.g., GET /items/55) reaching the Application Gateway/Load Balancer, which routes the request to an application server instance.
2. Hash Calculation: The application server computes the cache key name (e.g., item:55) and determines which distributed cache shard holds this key by applying a consistent hashing function.
3. Cache Query: The server establishes a TCP connection (or reuses a pooled connection) and queries the cache server: GET item:55.
4. Conditional Routing:
   • Branch A (Cache Hit): The cache server retrieves the serialized JSON or binary string from its RAM, updates its internal metadata for LRU tracking, and responds to the application server. The application deserializes the object and returns it to the client. The request is complete.
   • Branch B (Cache Miss): The cache returns a null response. The application server then queries the primary transactional database (SQL/NoSQL) using a disk-based index read.
5. Cache Re-population (upon Cache Miss): The database responds to the application server. The application server spawns an asynchronous job (or performs synchronously) to write the data back into the cache (e.g., SET item:55 <data> EX 3600, setting a 1-hour TTL) so subsequent requests will hit the cache.
6. Response Delivery: The application server serializes the data and responds to the client with a 200 OK status code.

10. Deep Dive

Eviction Policies

When memory is full, the cache must evict items. The choice of eviction policy affects the hit ratio dramatically:

• Least Recently Used (LRU): Discards the least recently accessed items first. It is highly effective for workloads with temporal locality (e.g., news feeds). Implementing LRU typically requires a Hash Map combined with a Doubly Linked List to achieve O(1) lookup and O(1) updates.
• Least Frequently Used (LFU): Discards items that have the lowest access counts. It is ideal for assets that have steady long-term popularity (e.g., search keywords). A drawback of LFU is that historically popular items may stay in the cache forever even if they stop getting requests (frequency accumulation), requiring counter-decay strategies.
• First In, First Out (FIFO): Evicts the oldest items in the cache regardless of how often or recently they were accessed. Easy to implement using a queue, but performs poorly for data with temporal locality.
• Time-to-Live (TTL): Evicts keys based on an expiration time. This can be combined with other policies (e.g., Redis's volatile-lru, which evicts the least recently used keys but only among those that have an expiration set).

Distributed vs. Global Caching

As application scale increases beyond a single server, caching topology must evolve:

• Distributed Cache: The cache state is divided and spread across multiple nodes using consistent hashing. Each node only stores a subset of the data. Scalability is linear; adding nodes increases total cache capacity.
• Global Cache: A single standalone cache layer (possibly replicated for high availability) that all application servers query. Simplifies consistency since there is only one source of cache state, but can become a single bottleneck if not scaled carefully.
• CDN (Content Delivery Network): A geographically distributed network of proxy servers that cache static resources (images, video, JS/CSS) close to users. Reduces network travel distance (speed of light latency).

11. Production Example

Netflix leverages a multi-tier caching hierarchy to serve millions of concurrent viewers globally with minimal latency:

1. EVCache (Distributed In-Memory Cache): Netflix built EVCache, which is a wrapper around Memcached, specifically integrated with AWS. EVCache handles personalization metadata, user viewing history, and recommendation lists. It scales to handle tens of millions of requests per second with sub-millisecond latencies, replication across AWS Availability Zones, and automatic sharding.
2. Open Connect (Edge Content Delivery Network): For actual video file delivery (which represents massive bandwidth), Netflix uses custom CDN appliances called Open Connect Boxes located directly inside Internet Service Provider (ISP) networks. These boxes cache heavy video chunks during off-peak hours (using Write-Around/prefetching), ensuring that during peak streaming hours, the video is fetched directly from the user's ISP local network instead of transit networks.

12. Advantages

• Extremely Low Latency: Reduces retrieval time from milliseconds (disk/network database lookup) to sub-milliseconds (RAM access).
• Database Load Reduction: Offloads read queries from databases, preventing resource saturation (high CPU/IOPS utilization) and allowing the database to prioritize write transactions.
• Cost Optimization: Serving reads from a cache cluster (RAM is relatively cheap when scaled) is far more cost-effective than scaling massive relational database clusters with read replicas.
• Improved System Availability: Under heavy traffic spikes (e.g., flash sales, breaking news), the cache acts as a buffer. Even if the database experiences slowdowns, users can still access cached pages and read-only features.

13. Limitations

• Capacity Constraints: RAM is volatile and far more expensive per gigabyte than SSD or magnetic storage, meaning you can only cache a small percentage of your overall dataset.
• Complexity of Invalidation: Keeping the cache in sync with the database is one of the hardest problems in computer science. Stale data can lead to poor user experiences (e.g., showing incorrect inventory levels).
• Warm-up Overhead: When a cache starts empty (cold start), the initial requests will all miss, causing high latency spikes and database load until the cache is fully populated (warmed up).
• Lack of Durability: Since caches store data in volatile memory (RAM), a server reboot or crash results in data loss if it is not backed up or backed by a persistent store.

14. Trade-offs

When introducing a cache, engineers must balance several conflicting priorities:

• Consistency vs. Latency: Writing data using Write-Through provides strict consistency but increases write latency. Conversely, Write-Back offers ultra-low write latency but sacrifices strong consistency and durability guarantees.
• Memory Size vs. Hit Ratio: Increasing the cache size improves the hit ratio (up to a point of diminishing returns) but raises operational costs. You must find the optimal budget-performance balance.
• Long TTL vs. Short TTL: Long TTLs increase the cache hit ratio and reduce database load, but increase the likelihood that clients will see stale data. Short TTLs keep data fresh but lead to more cache misses and database hits.

15. Performance Considerations

• Serialization Overhead: Storing rich data structures (objects, arrays) requires serialization (e.g., JSON stringify, Protocol Buffers, MessagePack) before writing to the cache, and deserialization on read. For high-throughput systems, this CPU overhead can become the primary bottleneck on application servers.
• Connection Pooling: A high volume of new TCP connections to the cache server can exhaust socket file descriptors. Reusing connections via pooling is essential.
• Single-threaded vs. Multi-threaded Cache Engines: Redis operates on a primarily single-threaded event loop (using non-blocking I/O multiplexing), meaning long-running operations (like KEYS * or large lua scripts) can block the entire cache server. Memcached is multi-threaded, making it better suited for simple, high-throughput key-value operations on multi-core systems.
• Network Bandwidth Saturation: If cache values are very large (e.g., 5MB per key), the network interface cards (NICs) of the cache hosts can easily saturate, even if CPU and RAM utilization are low. Keep cached objects small.

16. Failure Scenarios

1. Cache Avalanche

The Scenario: A large number of cache keys expire at the exact same time, or the cache cluster crashes. This causes all incoming read requests to miss simultaneously, sending a massive tidal wave of queries to the database, knocking it offline.

Mitigation:

• Jitter: Add a small, random deviation to the TTL of every key (e.g., instead of setting all keys to expire in exactly 6 hours, set them to 6 hours +/- a random number of minutes between 1 and 30). This staggers key expirations.
• High Availability Architecture: Deploy a Redis Cluster with master-replica replication and sentinel failover across multiple availability zones.

2. Cache Penetration

The Scenario: A client requests data that exists neither in the cache nor in the database (e.g., querying for a negative user ID: GET /users/-9999). The request misses the cache, hits the database, returns null, and cannot be cached. An attacker can exploit this by sending millions of requests for non-existent IDs, overloading the database.

Mitigation:

• Cache Null Values: Cache the missing key with a short TTL (e.g., 5 minutes) and a value of null or empty.
• Bloom Filter: Place a Bloom Filter in front of the cache. A Bloom Filter is a space-efficient probabilistic data structure that can tell you with 100% certainty if an item does not exist in the dataset. If the Bloom filter says the ID doesn't exist, bypass the cache and database entirely.

3. Cache Stampede (Dogpile Effect)

The Scenario: A highly popular cache key (e.g., a homepage configuration object) expires. Because the key receives thousands of concurrent requests per second, the moment it expires, dozens of application threads concurrently detect the cache miss and trigger identical, heavy queries to the database to rebuild the cache key.

Mitigation:

• Mutex Locking: Use a distributed lock (e.g., Redis Redlock) or local thread locks. Only the first thread that acquires the lock is allowed to query the database and rebuild the cache. Other threads wait or serve stale data until the key is updated.
• Probabilistic Early Expiration (XFetch): Expire the key early probabilistically before its formal TTL expires. The probability increases as the key approaches its actual expiration time. The thread that triggers early expiration rebuilds the key in the background while other requests continue to get the existing cached value.

17. Best Practices

• Always Set a TTL (Time-To-Live): Never write cache entries without a TTL unless you are absolutely sure of the caching topology and have manual eviction hooks. Without a TTL, keys can leak, eventually leading to Out Of Memory (OOM) failures.
• Use Cache Key Namespacing: Structure keys logically using delimiters (colons are standard). E.g., tenant:123:user:456:profile. This prevents key collisions and allows scripts to match and delete related keys.
• Compact Serialized Data: If storing complex data structures, choose efficient serialization formats like Protocol Buffers or MessagePack instead of raw JSON to reduce memory footprint and network load.
• Design for Cache Degradation: Ensure that your application is resilient enough to function even if the caching tier completely fails. Gracefully fallback to the database (possibly with aggressive rate-limiting or degraded responses) rather than crashing the app server.

18. Common Mistakes

• Using Cache as a Source of Truth (Permanent Store): Using a cache like Redis or Memcached as a primary database. Caches are in-memory and volatile; they can lose data on server crashes, reboots, or during eviction.
• Caching Highly Dynamic, Fast-Changing Data: Storing data that changes on every request (e.g., millisecond-level stock tickers or real-time GPS locations). The constant invalidation writes will saturate CPU, and the cache hit ratio will remain near 0%.
• Ignoring Key Sizes: Attempting to cache huge payloads (e.g., 20MB blobs). Cache engines are optimized for small key-value sizes. Large payloads choke network bandwidth and slow down single-threaded engines (like Redis).
• Inconsistent Cache Keys: Constructing different formats for cache keys across different microservices accessing the same database. This leads to duplicate keys holding different copies of the same data, leading to split-brain data states.

19. Implementation

Below is a complete, production-ready implementation of an LRU Cache in TypeScript. It uses a HashMap combined with a Doubly Linked List to achieve O(1) time complexity for both get and put operations.

20. Interview Questions

Easy Questions

Medium Questions

Hard Questions

21. Practice Exercises

22. Challenge Problem

Scenario: You are the lead system architect at a global ticket-selling platform (similar to Ticketmaster) hosting ticket sales for a major pop star. When the sale starts, you expect 500,000 concurrent users accessing the system to buy tickets for a stadium containing only 50,000 seats.

The ticket inventory (how many seats are left) must be displayed to users in real time. If a user tries to reserve a seat that has just been sold, they will be frustrated. However, querying the database (which runs ACID transactions to guarantee a seat is not double-booked) on every page refresh will cause it to crash instantly.

Your Challenge: Design a caching topology and synchronization strategy that allows real-time ticket availability viewing for 500,000 concurrent users while keeping database transactional traffic low enough to prevent outages. Specify:

• The write policy you would use for seat reservations.
• How you would prevent double-booking at the database level while using cached reads.
• The mitigation strategy for Cache Avalanche and Cache Stampede when seats sell out and inventory changes rapidly.

23. Summary

Caching is a powerful technique to optimize system performance by storing transient data in volatile, high-speed memory (RAM). It relies on temporal and spatial locality of reference to intercept reads before they hit slower storage tiers.

While caching improves latency and database load, it introduces challenges around cache invalidation, write synchronization, and system consistency. Common failure modes like Cache Avalanche, Cache Penetration, and Cache Stampedes require careful mitigation, such as random TTL jitter, Bloom filters, and mutex locking.

24. Cheat Sheet

Concept	Key Rule / Definition	Primary Use Case
Cache-Aside	App manages cache directly: read cache -> read DB -> populate cache.	General purpose web applications with varying read/write patterns.
Write-Through	Synchronous write to both cache and DB before returning.	Systems requiring strong consistency (e.g., account settings).
Write-Back	Write to cache instantly; write to DB asynchronously later.	High write volume systems (e.g., log aggregations, IoT sensors).
LRU Eviction	Evict least recently accessed key. Uses HashMap + Doubly Linked List.	Workloads where recently accessed data is likely to be requested again.
Cache Avalanche	Simultaneous expiration of keys overloads the DB. Prevent with TTL jitter.	Mitigating mass outages during scheduled refreshes or failures.
Cache Penetration	Requests for non-existent keys bypass cache. Prevent with Bloom filters.	Defending against malicious queries or random key lookups.

25. Quiz

1. What type of locality is exploited when a cache stores a page of a book because the user just read the previous page?

   • A) Temporal Locality
   • B) Spatial Locality
   • C) Sequential Locality
   • D) Algorithmic Locality

   Explanation: Spatial locality refers to accessing memory locations that are physically close to already accessed locations.

2. Which write policy is best suited for write-heavy applications where losing a small window of updates during a crash is acceptable?

   • A) Write-Through
   • B) Write-Around
   • C) Write-Back (Write-Behind)
   • D) Read-Through

   Explanation: Write-Back writes updates immediately to the cache and delays writing to the database, achieving the highest performance but with a risk of data loss.

3. How does adding "jitter" to a TTL prevent Cache Avalanche?

   • A) It staggers key expirations so they don't expire all at once.
   • B) It encrypts the cache key.
   • C) It automatically replicates the key.
   • D) It dynamically increases cache capacity.

   Explanation: Jitter adds a random time variation to expiration intervals so that keys do not hit their expirations in synchronized waves.

4. What data structures are typically used together to implement an LRU cache with O(1) performance?

   • A) Binary Search Tree + Hash Map
   • B) Doubly Linked List + Hash Map
   • C) Queue + Trie
   • D) Stack + Red-Black Tree

   Explanation: The Hash Map provides O(1) key lookups, and the Doubly Linked List allows O(1) element insertion and removal to track access ordering.

5. What is a false positive in the context of a Bloom Filter used for Cache Penetration?

   • A) The filter incorrectly claims an item does not exist.
   • B) The filter claims an item exists, but it actually does not.
   • C) The filter crashes because of memory allocation.
   • D) The filter rejects a valid write request.

   Explanation: Bloom filters can have false positives (indicating set membership for non-members) but never false negatives.

6. Under the Cache-Aside pattern, what happens during a cache miss?

   • A) The database itself writes the data directly to the cache, bypassing the application.
   • B) The application reads from the DB, writes the data to the cache, and returns it to the client.
   • C) The request fails with an HTTP 404 error.
   • D) The cache queries another cache node to find the value.

   Explanation: In Cache-Aside, the application acts as the coordinator, performing the database lookup and populating the cache afterward.

7. Which eviction policy is most susceptible to retaining obsolete data that had high traffic in the past?

   • A) Least Recently Used (LRU)
   • B) Least Frequently Used (LFU)
   • C) First In First Out (FIFO)
   • D) Random Replacement

   Explanation: LFU tracks access count. If an item was extremely popular in the past, its frequency count remains very high even if its popularity drops to zero, unless decay algorithms are applied.

8. What is a major trade-off of using a single-threaded cache like Redis?

   • A) It cannot handle concurrent network connections.
   • B) It uses more memory than multi-threaded caches.
   • C) A single slow operation (like KEYS *) can block all other operations.
   • D) It cannot support clustering or partitioning.

   Explanation: Because Redis uses a single-threaded event loop for command execution, running O(N) blocking commands will block the event loop, causing timeouts for all other clients.

9. What is a Cache Stampede?

   • A) Multiple cache servers crash at the same time due to hardware issues.
   • B) Multiple requests attempt to read and write a key simultaneously on cache expiration, overloading the DB.
   • C) Hackers spam the cache with random data to deplete memory resources.
   • D) A data corruption bug that cascades across the cluster shards.

   Explanation: A cache stampede occurs when a hot key expires and many concurrent application threads all try to read the database and write to the cache at the same time.

10. Why should you avoid caching highly dynamic, frequently changing data?

    • A) It causes the cache server to exhaust all IP addresses.
    • B) Cache servers do not support rapid updates.
    • C) Constant invalidations lead to a low cache hit ratio and waste CPU resources.
    • D) Caching dynamic data is illegal under privacy laws.

    Explanation: If data is updated on almost every read or changes constantly, it will be invalidated immediately, leading to a hit ratio of near 0% and wasted processing overhead.

26. Further Reading

• Redis Documentation: Deep dive into Redis in-memory data structures, replication, clustering, and persistence models.
• Memcached Official Wiki: Understanding simple, high-throughput, multi-threaded caching architectures.
• "Designing Data-Intensive Applications" by Martin Kleppmann: Section on caching strategies, replication, and split-brain scenarios.
• Analysis of Cache Replacement Algorithms: Academic review of FIFO, LRU, LFU, and random eviction.

27. Next Lesson Preview

Now that you understand how to speed up data reads and reduce database load using caching, we will look at how to scale out the database tier itself. In the next lesson, Database Sharding & Partitioning, we will explore how to divide massive databases into smaller, manageable chunks across different physical servers.