Cache – access and expiry

August 27, 2006

In my previous post on cache implementation I had talked about where to keep the cache. Now I will talk about how to access the cache and how to expire the same.

Before we go into those topics, it is very important to consider the tolerance of stale data for maximum optimization.
Lets say we cannot tolerate stale data at all – lets say the application is for selling a hotel room in Thai Bhat converted to Sterling. Now, depending on the rate I get from my bank and the date of stay, I get a price.
So every time anyone requests for a room, I have to check the price like
PriceInGBP=PriceInTHB* ( Select ExchangeRate where fromCurrency=THB and ToCurrency=GBP and ValidityFromDate<=12Jan and ValidityToDate >= 12Jan and isLive=True)
– Since I am selling in future so I have to look up rates on that date.
Now if I cannot tolerate stale data, the best I can do is to put a trigger on the exchange rate table to update a ExchangeRateVersionNumber Table. The exchange rate version number is updated on any change on the entire exchange rate table.
Thus my application changes to
If CachedExchangeRateVersionNumber = select * from ExchangeRateVersionNumber , used Cached exchange rate, Else the above query to fetch the exchange rate.
Here we see that the query on the database, hence load on the database is much smaller aiding scalabililty.

However, atleast one query needs to be fired everytime.
Now lets assume that we could tolerate stale data for 1 minute,
we could change the getExchangeRate to
If CacheExchangeRateTimeStamp > = currentDateTime – 1 minute, then use cached , otherwise the above.
This is going to result in a significantly faster execution times as it will save the round trips to the database.

Lets now take the scenario where the exchange rate table is updated by a feed from my bank, instead of being entered manually. Here, If I cache, I have to tolerate stale data – even if that is for a minute. There can be no trigger ( unless supported by my bank) which can help check validity.

Now lets come back to accessing the cache. We want to read from the cache simultaneously via multiple threads, however when the cache is being updated, we need all the threads to stop.
While implementing such lookup – we need to be careful that we are not locking/synchronizing while reading – i.e. we must not force different objects to read in sequence.

In the typical implementation, I would prefer a hashtable as it already provides such thread-safety ( provided there is only one writing thread).

The granularity of this lock should be the same as granularity of cache update.

Now looking at expiry:
We have already discussed that in some cases, we need to have a Garbage collector like daemon clearing the cached items. This will also be required in case of LRU cache.
If the number of items in cache are limited, we dont need such daemon. The expiry checking happens while fetching from it.
In some other cases, we will expire and seed cache at pre-defined times.

Here are some questions which I answered in a recent post on MSDN forums:
1. At what moment of time should we invalidate the cache like at the start of transaction , just before updating the database or any other time
It really depends on what kind of data you are caching. If you are caching flight information as the expedia example above, the transaction is not in your control hence you have no option but to have a slight tolerance for stale data.
Assuming your own system is updating the data in cache and assuming that it is in a common datastore like a SQL database. If I also assume that we are talking about a clustered environment : there are multiple instances of the cache – one in each app-pool x each machine . Hence the component which is updating the data which is eventually cached has no way of reliably marking the cache invalid in all the different instances of the in-memory cache.
This forces all the different caches to have their own “listeners” checking for cache update.If I donot talk patterns here and only talk implementation – If you were having an application which can tolerate stale data, you could have a background thread updating the cache periodically from the database. IF you were having an application which cannot tolerate stale cache, you will have to check the DB status before each read from the cache. Now in DB you could use triggers to populate cache status in a single cell table ( lets say last updated timestamp) which the cache compares with itself and updates the cache if required, This way, the load on the database is much lesser than what it would be if it were to retrieve the entire cache.
So in this case, updating the cache invalid flag as a part of the atomic transaction will help.
2 When should we lock the cache
In either case, we should lock the cache at the time update check or update is happening. Now the granularity of the lock depends on the granularity in which we want to refresh the data.
3. how should we overcome the data retrieval latency issue which ultimately lead to stale data for some time in cache
For an externally maintained data, it may not be possible. For a self maintained data, sample implementation is discussed above.
4. if a thread is making some changes in a data in database how can we make sure that cache gets refreshed for the other thread to get fresh value .
I think I got your dilemma now – I would say that keep the cache as a static hashtable or equivalent and always get data from it for all your threads ( something like (MyObject)Cache.getFromCache(itemid) ) – lock the getFromCache method when you are checking for updates.
However, if you are looking at a code which is definitely going to be non clustered, you could put data in threads, have events and delegates to trigger cache – have an implementation of observer pattern or state machine. State machine if you have a dependancy like
Thread A has cached data-> Class B depends on that state of class A-> class C depends on state of class B
where you want the change to be propagated all the way to C before you release the locks.
5. Should we update the cache inside the transaction or after completion of transaction (in both scenarios of wanting and not wanting stale data)
It should be a part of the atomic transaction in either case.
6.If one thread is reading or writing a value to cache, how to block other threads to access that cache object.
If we keep the cache in one static class, and implement a lock on the read from cache method **when the update or check for update is happening** ( I am not talking of a synchronous one at a time access). Now you could do an explicit lock of the object/method or you could use a dataset like Hashtable.Synchronized – which already have the implementation – which locks all getters when setters are happening.
I would say for following will fit your purpose best- based on what I think your requirement is ( self maintained data in database, potential clustering, potentially no tolerance for stale data, TTL and not LRU)
1) Chose something like a static synchronized hashtable for your cache
2) For a cluster – you would need to poll to get changes.
3) Poll for changes at a timeout or at every get depending on whether you can tolerate stale data or not
4) Define a coarse granularity of cache expiry (otherwise polling for cache expiry can offset any gains got by having the cache in the first place).
If I were writing a generic cache – I would probably go for three different implementations for – externally maintained items, self maintained items and LRU cache – and Maybe a fourth one for non-clustered applications – like Games.

Do post a comment and I will try to keep up with responses.


2 Responses to “Cache – access and expiry”

  1. I have found using the WebSphere Dynacache to be a very effective and easy way to manage objects in cache. It provides all the flexibility to manage objects and jsp scraps. One can also set a cache expiry timings and the sync across nodes in a cluster is taken care by WebSphere.

  2. Amongst the newbies is The Springfield Diner in just Delco. Enormous menu, and something is delish!

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: