none
caching optimisation with concurrency handling RRS feed

  • Question

  • I am working on how to implement caching in the best possible manner when we are implementing

     

    1. optimistic concurrency (1st scenario: we can live with stale data. 2nd scenario :we cannot live with stale data)

    2. pessimistic concurrency

     

    Here I also want to cover scenarios like when two thread of the same application accessing the same table in database by using different queries and when both have these query results in different cached objects.So what strategy should I use to make the cache stale ,at what moment of time.

     

    Please share your views on the above.

    Cheers

    Friday, July 21, 2006 11:56 AM

Answers

  • Hi,

    First to clarify on "granularity of the cache ( i.e. are there 2 item types in cache or 100s or unlimited based on user query parameters)."

    What I meant over there was actually the "block sizes" in which you want to expire data.

    Lets say you had an application getting live departure arrival board feeds from different airports, Abardeen, heathrow, luton etc. Now as soon as you get a feed from Heathrow, you would want to expire all cached content for heathrow - rather than expring cache of individual flights. This way you can ensure that cache validity and refresh is "cheap", not offsetting the benefits of cache in the first place.

    Now here, you would want different "cache dirty" flags for each category of news ( sports, england news, scotland news etc.)

    There are some other scenarios (possibly because the amount of data in cache is small) where you would want to refresh the entire cache when anythig goes dirty.

    In the former case, you will need to go for a more elaborate implementation of observer, in the latter, its simpler. In the former case, you would want to have concurrency control at "category" level, while in latter, you can have concurrency control at "fetch from cache" level.

    Now the situation again changes if you were Expedia.co.uk and wanted to cache airline availablility based on user request. Here the user gives - origin, destination, date of outbound travel, date of return travel, number of adults, children and infants etc. Based on all these parameters, there is a unique query. Now if any other user comes in  and asks for exactly the same parameters, you could fetch the data from the cache and give it to the user. Now lets look at cache expiry in this case - There are two scenario in which you want to refresh the cache -1) Based on the age of the cache, 2) on demand - when you know that the cache is wrong as the the booking for a user fails (as the flight is no longer avaialble). Now each cached row has its own life, and each have a seperate trigger.

     

    Let me also explain TTL vs LRU algorithms.

    If you were amazon.co.uk, having millions of products in the catalog, you might want to cache the most frequently used products in the memory and remove the least frequently used - not because they were stale - but because keeping them in memory is not optimal.

    In case of TTL, you basically have infinite resources and everything which people access can live in cache.

    Also talking of cache expiry - you have to worry about clearing cache. If I go to expedia kind of example, you might want to have a housekeeping thread - querying for all items which are past their validity period and removing/ freeing them from memory.

    Now coming to your other questions:

    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 propogated 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.

    Hope this helps.

    Monday, July 24, 2006 3:51 PM

All replies

  • Hi Leo,

    There is no single solution to the problem. The solution will depend on frequency of updates, granularity of the cache ( i.e. are there 2 item types in cache or 100s or unlimited based on user query parameters),  tolerance of stale data, expiry algorithms ( like LRU, TTL etc), whether you want lazy loads, volume of data in cache, and whether you are working in a clustered setup or a single app-pool.

    There are many design patterns on this like the distributed cache pattern, cache management pattern, about observer pattern and state machines

    If you can specify in detail what exactly you are looking at doing, we could recommend something.

    If you are looking to cache lets say computed pages in a CMS, you would treat it slightly differently than caching exchange rates for further computation which would be different than lets say live departure timing of flights as obtained from different airports via different feeds.

     

    Pranshu

    Saturday, July 22, 2006 12:20 PM
  • Hi Pranshu,

    Thanks for your elaborate reply.

    I didn't understaood one small part of your reply which says granularity of the cache ( i.e. are there 2 item types in cache or 100s or unlimited based on user query parameters).

    I am actually doing a study on different caching pattern which can be adopted in different locking scenarios like in optimistic locking ,pessimistic.

    Let me make it more clear.

    I wish to know that if an application is using optimistic concurrency as the base, how should i implement the cache ,if we can't tolerate stale data at all and if we can tolerate stale data but only for some seconds.

    In this case i need to know all the aspects of putting the cache in place like

    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

    2 When should we lock the cache

    3. how should we overcome the data retrieval latency issue which ultimately lead to stale data for some time in cache 

    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 . 

    5. Should we update the cache inside the transaction or after completion of transaction (in both scenarios of wanting and not wanting stale data) 

    6.If one thread is reading or writing a value to cache, how to block other threads to access that cache object. 

    Similarly for pessimistic concurrency

    Hope i am able to clarify my query

    It would indeed take some of your time but i would really appreciate if you can give your inputs on the above

    regards 

    Monday, July 24, 2006 12:59 PM
  • Hi,

    First to clarify on "granularity of the cache ( i.e. are there 2 item types in cache or 100s or unlimited based on user query parameters)."

    What I meant over there was actually the "block sizes" in which you want to expire data.

    Lets say you had an application getting live departure arrival board feeds from different airports, Abardeen, heathrow, luton etc. Now as soon as you get a feed from Heathrow, you would want to expire all cached content for heathrow - rather than expring cache of individual flights. This way you can ensure that cache validity and refresh is "cheap", not offsetting the benefits of cache in the first place.

    Now here, you would want different "cache dirty" flags for each category of news ( sports, england news, scotland news etc.)

    There are some other scenarios (possibly because the amount of data in cache is small) where you would want to refresh the entire cache when anythig goes dirty.

    In the former case, you will need to go for a more elaborate implementation of observer, in the latter, its simpler. In the former case, you would want to have concurrency control at "category" level, while in latter, you can have concurrency control at "fetch from cache" level.

    Now the situation again changes if you were Expedia.co.uk and wanted to cache airline availablility based on user request. Here the user gives - origin, destination, date of outbound travel, date of return travel, number of adults, children and infants etc. Based on all these parameters, there is a unique query. Now if any other user comes in  and asks for exactly the same parameters, you could fetch the data from the cache and give it to the user. Now lets look at cache expiry in this case - There are two scenario in which you want to refresh the cache -1) Based on the age of the cache, 2) on demand - when you know that the cache is wrong as the the booking for a user fails (as the flight is no longer avaialble). Now each cached row has its own life, and each have a seperate trigger.

     

    Let me also explain TTL vs LRU algorithms.

    If you were amazon.co.uk, having millions of products in the catalog, you might want to cache the most frequently used products in the memory and remove the least frequently used - not because they were stale - but because keeping them in memory is not optimal.

    In case of TTL, you basically have infinite resources and everything which people access can live in cache.

    Also talking of cache expiry - you have to worry about clearing cache. If I go to expedia kind of example, you might want to have a housekeeping thread - querying for all items which are past their validity period and removing/ freeing them from memory.

    Now coming to your other questions:

    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 propogated 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.

    Hope this helps.

    Monday, July 24, 2006 3:51 PM
  • Hi Pranshu,

    thank you very much for this excellent reply

    Regards

    leo

    Wednesday, July 26, 2006 8:42 AM