Web Application Caching Strategies: Generational caching

This is the second in a two part series on caching strategies. The first post provided an introduction and described write-through caching.

In the previous post in this series on caching strategies we described write-through caching. While an excellent strategy, it has a somewhat limited application. To see why that is that case and how generational caching improves upon it, let's start with an example.

Imagine that you are creating a basic blogging application. It is essentially just a single “posts” table with some metadata associated with each post (title, created date, etc). Blogs have two main types of pages that you need to be concerned about, pages for individual posts (e.g. “/posts/3”) and pages with lists of posts (e.g. “/posts/”). The question now becomes, how can you effectively cache this type of data?

Caching pages for individual posts is a straightforward application of the write-through caching strategy I discussed in a previous post. Each post gets mapped to a cache key based on the object type and id (e.g. “Post/3”) and every update to a post is written back to the cache.

The more difficult question is how to handle pages with lists of posts, like the home page or pages for posts in a certain category. In order to ensure the cache is consistent with the data store, it is important that any time a post is updated, all keys that contain the post need to be expired. This can become difficult to track since a post can be in many cache keys at the same time (e.g. latest ten posts, posts in Ruby category, posts favorited by user 15). While you could try to programmtically figure out all keys that contain a given post, that is a cumbersome and error-prone process. A more clean way of accomplishing this is what is called generational caching.

Generational caching maintains a "generation" value for the each type of object. Each time an object is updated, its associated generation value is incremented. Using the post example, any time someone updates a post object, we increment the post generation object as well. Then, any time we read/write a grouped object in the cache, we include the generation value in the key. Here is a sequence of actions and what would occur with the cache when performing those actions:



By including the generation in the cache key, any time a post is updated the subsequent request will miss the cache, and query the database for the data. The result of this strategy is that any time a post object is updated/deleted, all keys containing multiple posts will be implicitly expired. The reason I said implicitly expired is that we never actually have to delete the objects from the cache, by incrementing the generation we ensure that the old keys are simply never accessed again.

Here is some sample code for how this could be implemented (in psuedo-Python):



After implementing this strategy in multiple applications I want to point out a few things about how it works and its performance properties. In general I have found that using this strategy can dramatically improve application performance and lessen database load considerably. It can save tons of expensive table scans from happening in the database. By sparing the database of these requests, other queries that do hit the database can be completed more quickly.

In order to maintain cache consistency this strategy is conservative in nature, this results in keys being expired that don’t necessarily need to be expired. For example if you update a post in a particular category, this strategy will expire all the keys for all the categories. While this may seem somewhat inefficient and ripe for optimization, I’ve often found that most applications are so read-heavy that these types of optimization don’t make a noticeable overall performance difference. Plus, the code to implement those optimizations then become application or model specific, and more difficult to maintain.

I previously mentioned that in this strategy nothing is ever explicitly deleted from the cache. This has some implications with respect to the caching tool and eviction policy that you us. This strategy was designed to be used with caches that employ a Least Recently Used (LRU) eviction policy (like Memcached). An LRU policy will result in keys the with old generations being evicted first, which is precisely what you want. Other eviction policies can be used (e.g. FIFO) although they may not be as effective.

Overall, I’ve found generational caching to be a very elegant, clean, and performant caching strategy that can be applied in a wide variety of applications. So next time you need to do some caching, don’t forget about generations!

Web Application Caching Strategies: Write-through caching

You have probably heard about all of the big websites which heavily rely on caching to scale their infrastructure. Take a look at the Wikipedia entry on Memcached and you will find a veritable who's who of big internet companies. While we know these websites do caching, I have found very little written about how they actually do caching. Unfortunately a lot of caching is so particular to the individual website that it isn't very useful for most developers. There are however a few overarching caching "strategies" which if done correctly will guarantee you will never get stale data from your cache. In this series I'm going to discuss two of these strategies, write-through and generational caching.

The first and simplest strategy is write-through caching. What happens is when you write to the database, you also write the new entry into the cache. That way, on subsequent get requests the value should always be in the cache, and never need to hit the database. The only way a request would miss the cache is because a) the cache filled up and the value was purged or b) server failure. Here is some sample code in Python for how this works. I'm using database.get/put/delete as shorthands for SELECT/INSERT/DELETE in your database of choice.



The strategy itself is really simple to understand and for many workloads can result in dramatic performance improvements and decreased database load.

While a simple and clean caching strategy there are a few things you should be aware of to avoid some common issues when implementing this strategy.

Often times people will cache database objects by using the database id as the key. This can result in conflicts when caching multiple types of objects in the same cache. A simple solution for this is to prepend the type of the object to the front of the cache key (e.g. “User/17”).

Next, for any put/delete operations to the database it is important it check that those operations completed successfully before updating the cache. Without this type of error checking you can end up in situations where the database update failed but the cache update happened anyways, which results in an inconsistent cache.

While this strategy is effective for caching single objects, most applications fetch multiple objects from the database (e.g. get all books owned by "Joe"). For a strategy which handles multiple objects, see the next post in the series about generational caching.