Advanced Caching Strategies and Eviction Policies

Hello! Welcome to the next lesson in our module on "Advanced Concurrency & Performance."

In our previous session, we implemented the cache-aside pattern with Spring Boot and Redis. We saw how it effectively reduces read latency by having the application manage fetching data from the database on a cache miss. This pattern is a fantastic workhorse for read-heavy applications.

Today, we're moving beyond application-managed caching to explore more advanced patterns where the cache itself plays a more active role. This lesson is crucial for senior-level interviews, as it tests your ability to weigh architectural trade-offs between consistency, performance, and complexity. We will also dive into the mechanisms that keep caches from growing indefinitely: eviction policies.

Our learning outcome is to describe advanced caching patterns, including write-through, write-behind, and eviction policies.

Recap: Cache-Aside vs. Write-Centric Patterns

Let's quickly recall the cache-aside pattern you implemented:

1. Application asks the cache for data.
2. If it's a miss, the application reads from the database.
3. The application writes the data back into the cache.

In this model, the application code is the "smart" component, orchestrating the cache and the database. The patterns we'll discuss today, write-through and write-behind, shift some of this responsibility, often simplifying the application's write logic.

This diagram provides a great visual summary of several caching strategies. We've already covered "Cache Aside." Today, we'll focus on "Write Through" and "Write Behind."

1. Write-Through Caching

In a write-through cache, the application treats the cache as the primary data store for writes. The cache then takes responsibility for updating the underlying database.

How it works:

1. The application issues a write command directly to the cache.
2. The cache updates its internal store.
3. The cache synchronously writes the same data to the database.
4. The operation is considered complete only after both the cache and the database have been successfully updated.

Trade-offs

• Pro: Strong Consistency. Because the database is updated synchronously, data in the cache is always consistent with the database. Reads from the cache will always return fresh data. This is a significant advantage over cache-aside, where data can become stale until invalidated.
• Pro: Simpler Application Logic. The application only needs to know about the cache for its write operations, not the database.
• Con: Higher Write Latency. The write operation has to wait for two network calls to complete (to the cache and to the database), making it slower than cache-aside or write-behind.
• Con: The "Dual-Write Problem". In a distributed system, what happens if the cache write succeeds but the database write fails? This can lead to an inconsistent state. Handling this requires complex retry logic or distributed transactions, which adds significant complexity.

When to Use It

Use the write-through pattern when you have a read-heavy workload where data freshness is critical, and you can accept slightly higher latency on write operations. A good example is a user profile service where it's vital that any service reading the profile gets the absolute latest information immediately after an update.

To get a clear explanation from an industry expert, please watch the following segment.

Implementation Note: Standard caches like Redis don't natively support this pattern. You would typically rely on a library or framework feature (like Spring Cache or Hazelcast) or write custom application logic that wraps both the cache and database write in a single operation.

Here's a conceptual Java example showing the logic:

// Conceptual interface for a data store
interface DataStore<K, V> {
    void write(K key, V value);
    // ... other methods
}

public class WriteThroughCache<K, V> {
    private Map<K, V> internalCache = new HashMap<>();
    private DataStore<K, V> database;

    public WriteThroughCache(DataStore<K, V> database) {
        this.database = database;
    }

    public void write(K key, V value) {
        // First, write to the database (synchronously)
        database.write(key, value);
        // Then, update the cache
        internalCache.put(key, value);
        // Operation is now complete
    }

    public V read(K key) {
        return internalCache.get(key);
    }
}

2. Write-Behind (or Write-Back) Caching

Write-behind also treats the cache as the primary destination for writes, but it decouples the application from the database write latency.

How it works:

1. The application issues a write command to the cache.
2. The cache updates its internal store and immediately acknowledges the write to the application.
3. The cache then adds the data to a background queue.
4. Later, asynchronously, the cache flushes the data from the queue to the database, often in batches.

Trade-offs

• Pro: Extremely Low Write Latency. Writes are very fast because the application doesn't wait for the database write. This leads to high write throughput.
• Pro: Reduced Database Load. By batching writes, this pattern can significantly reduce the number of write operations sent to the database, which is especially useful during traffic spikes.
• Con: Risk of Data Loss. If the cache server crashes before the data in its queue is persisted to the database, that data is lost permanently.
• Con: Eventual Consistency. There is a delay between the write being acknowledged and it being visible in the database. This means the system is only eventually consistent.

When to Use It

Use write-behind for write-heavy workloads where peak performance and high throughput are more important than strong consistency or a small risk of data loss. Classic examples include:

• Collecting analytics or metrics (e.g., counting video views or 'likes').
• Ingesting logging data at high volume.
• Updating a user's "last seen" timestamp frequently.

Now, watch the next part of the same video for an explanation of write-behind.

Test your understanding!

You are designing two different features:

1. A funds transfer system for a banking application.
2. A system that tracks the number of times an article has been viewed on a news website.

For each feature, would you choose write-through or write-behind caching? Justify your answer based on their trade-offs.

Show answer

1. Funds Transfer System: Use write-through. In a financial transaction, data consistency and durability are non-negotiable. You cannot risk losing a transaction if the cache fails. The higher write latency is an acceptable trade-off for the guarantee that the money transfer is permanently recorded in the database.

2. Article View Counter: Use write-behind. High write throughput is essential to handle thousands of views per second without overwhelming the database. A slight delay in the main database counter being updated is acceptable, and losing a few view counts in the rare event of a cache crash is a minor issue compared to the performance gain.

3. Cache Eviction Policies

Since a cache has limited memory, it needs a strategy to decide what to discard when it's full. This is handled by an eviction policy. Choosing the right policy is key to ensuring your cache remains effective.

For a great introduction to why we need eviction and a deep dive into the most common policies, the following video is an excellent resource.

Let's summarize the key policies discussed in the video:

• First-In, First-Out (FIFO):

  • How it works: Evicts the oldest entry based on insertion time, like a simple queue.
  • Pros: Very simple to implement.
  • Cons: Inefficient. It might evict a very popular item that has been in the cache for a long time.

• Least Recently Used (LRU):

  • How it works: Evicts the item that hasn't been accessed for the longest time. It assumes that if you used something recently, you're likely to use it again soon.
  • Pros: A great general-purpose policy that adapts well to most access patterns. It's the default for many caching systems.
  • Interview Deep-Dive: As the video explained, the classic implementation uses a hash map (for O(1) lookups) and a doubly linked list (to move items to the "most recent" end in O(1) time). Knowing this detail is excellent for impressing interviewers.

• Least Frequently Used (LFU):

  • How it works: Evicts the item that has been accessed the fewest number of times. It keeps a counter for each entry.
  • Pros: Works very well when the popularity of items is stable, and some items are consistently accessed more than others.
  • Cons: More complex to implement. It can be slow to adapt if a rarely used item suddenly becomes popular (this is known as "cache pollution").

• Time To Live (TTL):

  • As we discussed in the last lesson, TTL isn't a size-based eviction policy but an expiration mechanism. It automatically removes an entry after a set duration. It's often used in combination with other policies like LRU to ensure data freshness.

Test your understanding!

Imagine you are caching data for an e-commerce website's product page. This page shows:

1. The product details (name, image, price).
2. A "recommended for you" section, which is personalized for each user.

Which eviction policy, LRU or LFU, would be more suitable for caching the data for each of these sections, and why?

Show answer

1. Product Details: LFU is a strong candidate here. Popular products (like the latest iPhone) will be viewed thousands of times, while obscure products might be viewed rarely. LFU would ensure that the most popular products are kept in the cache, as their access frequency will be very high. LRU could mistakenly evict a popular product if it hasn't been viewed in a little while in favor of several less popular products that were just viewed.

2. "Recommended for you" section: LRU is more suitable here. A user's browsing pattern is dynamic. The items recommended to them are based on their recent activity. What was relevant an hour ago might be less relevant now. LRU excels at keeping the most recently accessed/relevant data in the cache, which aligns perfectly with a user's journey through the site.

Conclusion

Today, we've expanded your caching toolkit significantly. You now understand the critical trade-offs between different write strategies and how to manage your cache's memory with eviction policies. These concepts are at the heart of designing high-performance, scalable systems.

Key Takeaways:

• Write-Through: Prioritizes strong consistency at the cost of higher write latency. Use when data freshness is paramount.
• Write-Behind: Prioritizes high write throughput and low latency, accepting eventual consistency and a small risk of data loss. Use for high-volume, non-critical writes.
• Eviction Policies manage limited cache memory.
  • LRU (Least Recently Used) is the versatile default, great for dynamic access patterns.
  • LFU (Least Frequently Used) is ideal for data with stable, predictable popularity.
  • FIFO is simple but often ineffective.

Next Up

We've covered patterns for a single cache layer. But in truly high-traffic systems, like those at FAANG or major fintech companies, a single cache isn't enough. In our next lesson, we will design a multi-level caching strategy for a high-traffic, read-heavy service. We'll explore how to combine different cache types (e.g., in-process, distributed) to build an even more resilient and performant system.

As a preview, take a look at the diagram below, which shows a multi-level caching architecture. We will break down and design a similar system in our next session.