CODEWITHSUNDEEP
cachinginvalidation
maaartinus
maaartinus

Reputation: 46492

Cache invalidation algorithm

I'm thinking about caching dynamic content in web server. My goal is to bridge the whole processing by returning a cached HTTP response without bothering the DB (or Hibernate). This question is not about choosing between existing caching solutions; my current concern is the invalidation.

I'm sure, a time-based invalidation makes no sense at all: Whenever a user changes anything, they expect to see to the effect immediately rather than in a few seconds or even minutes. And caching for a fraction of a second is useless as there are no repeated requests for the same data in such a short period (since most of the data is user-specific).

For every data change, I get an event and can use it to invalidate everything depending on the changed data. As request happen concurrently, there are two time-related problems:

The two problems are sort of opposite to each other. I guess, the former is easily solved by partially serializing requests from the same client using a ReadWriteLock per client. So let's forget it.

The latter is more serious as it basically means a lost invalidation and serving the stale data forever (or too long).

I can imagine a solution like repeating the invalidation after every request having started before the change happened, but this sounds rather complicated and time-consuming. I wonder if any existing caches do support this, but I'm mainly interested in how this gets done in general.

Clarification

The problem is a simple race condition:

Upvotes: 4

Views: 2085

Answers (2)

Tengiz
Tengiz

Reputation: 8449

I think you don't realize (or don't want to explicitly call out) that you are asking about a choice between cache synchronization strategies. There are several well known strategies: "cache aside", "read through", "write through", and "write behind". e.g. read here: A beginner’s guide to Cache synchronization strategies. They offer various levels of cache consistency (invalidation as you call it).

Your choice should depend on your needs and requirements.

It sounds like so far you've chosen "write behind" strategy (queue or defer cache invalidation). But from your concerns it sounds like you've chosen it incorrectly, because you are worried about inconsistent cache reads.

So, you should consider using "cache aside" or "read/write through" strategies, because those offer better cache consistency. They all are different flavors of the same thing - always keep cache consistent. If you don't care about cache consistency, then ok, stay with "write behind", but then this question becomes irrelevant.

Architecture wide, I would never go with raising events to invalidate the cache, because it seems like you've made it part of your business logic, while it's just an infrastructure concern. Invalidate (or queue invalidation of) cache as part of read/write operations, and not somewhere else. That allows cache to become just one aspect of your infrastructure, and not part of everything else.

Upvotes: 2

Rei
Rei

Reputation: 6363

To solve the race condition, add a timestamp (or a counter) and check this timestamp when setting a new cache entry. This ensures that obsolete response will not be cached.

Here's a pseudocode:

//set new cache entry if resourceId is not cached
//or if existing entry is stale
function setCache(resourceId, requestTimestamp, responseData) {
    if (cache[resourceId]) {
        if (cache[resourceId].timestamp > requestTimestamp) {
            //existing entry is newer
            return;
        } else
        if (cache[resourceId].timestamp = requestTimestamp) {
            //ensure invalidation
            responseData = null;
        }
    }

    cache[resourceId] = {
        timestamp: requestTimestamp,
        response: responseData
    };
}

Let's say we got 2 requests for the same resource "foo":

  • Request A (received at 00:00:00.000) executes a query and fetches the result
  • Request B (received at 00:00:00.001) does some changes
  • The invalidation due to B happens by calling setCache("foo", "00:00:00.001", null)
  • Request A finishes
  • Request A calls setCache("foo", "00:00:00.000", ...) to write the obsolete response to cache but fails because the existing entry is newer

This is just the basic mechanism, so there is room for improvements.

Upvotes: 3

Related Questions