Cache invalidation algorithm
I am thinking about caching dynamic content on a web server. My goal is to combine all the processing by returning a cached HTTP response without bothering DB (or Hibernate). This question is not about choosing between existing caching solutions; my current problem is cancellation.
I'm pretty sure the temporary invalidation doesn't make any sense: whenever the user changes something, they expect to see the effect right away, rather than after a few seconds or even minutes. And caching for a split second is useless as there are no repeated requests for the same data for such a short period (since most of the data is user-dependent).
For every data change, I receive an event and can use it to invalidate everything, depending on the data changed. Since the request is running concurrently, there are two timing issues:
- Invalidity can come too late and stale data can be sent even to the client who changed it.
- Upon invalidation, a long request may complete and its stale data may be cached.
The two problems are opposite to each other. I think the former is easily solved by partially serializing requests from the same client using ReadWriteLock
for each client. So forget about it.
The latter is more serious as it basically means lost invalidation and ubiquitous data forever (or too long).
I can think of a solution like retrying the invalidation after every query run before the change happens, but that sounds pretty complicated and time consuming. I wonder if any existing caches support, but I'm mainly interested in how this is done in general.
Clarification
The problem is with a simple race condition:
- Request A executes the request and receives the result
- Query B makes some changes.
- Invalidity due to B occurs
- Request A (which was delayed for whatever reason) ends
- Outdated response for request A is written to the cache
source to share
To resolve a race condition, add a timestamp (or counter) and note that timestamp when setting up a new cache entry. This ensures that a stale response is not cached.
Here's the 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 have 2 requests for the same resource "foo":
- Request A (received at 00: 00: 00.000) executes the request and retrieves the result
- Request B (received at 00: 00: 00.001) makes some changes.
- Invalidation due to B occurs when called
setCache("foo", "00:00:00.001", null)
- Request A completes
- Request calls
setCache("foo", "00:00:00.000", ...)
to write stale response to cache, but fails because existing entry is newer
This is just a basic mechanism, so there is room for improvement.
source to share
I think you do not understand (or do not want to explicitly call) what you are asking about choosing between cache synchronization strategies. There are several well-known strategies: cache to the side, read, write, and write per. for example read here: A Beginner's Guide to Cache Synchronization Strategies . They offer varying levels of cache consistency (invalidation, as you call it).
Your choice should depend on your needs and requirements.
It looks like you have chosen a "write behind" strategy (invalidating queue or deferring cache). But from your problems it sounds like you chose it wrong because you are worried about inconsistent cache reading.
So, you should consider using either side caching or read / write strategies as they provide better cache consistency. They are all different flavors of the same thing - always keep the cache. If you don't care about cache consistency, then okay, stay with "write behind", but then this question becomes irrelevant.
Architecture as a whole, I would never be going to raise events to invalidate the cache, because it seems like you made it part of your business logic, while this is only about the infrastructure. Invalid (or invalid cache) cache is part of read / write operations, not elsewhere. This allows the cache to become one aspect of your infrastructure and not part of everything else.
source to share