Dealing with concurrency issues when caching for high-traffic sites

Question

I was asked this question in an interview:

For a high traffic website, there is a method (say getItems()) that gets called frequently. To prevent going to the DB each time, the result is cached. However, thousands of users may be trying to access the cache at the same time, and so locking the resource would not be a good idea, because if the cache has expired, the call is made to the DB, and all the users would have to wait for the DB to respond. What would be a good strategy to deal with this situation so that users don't have to wait?

I figure this is a pretty common scenario for most high-traffic sites these days, but I don't have the experience dealing with these problems--I have experience working with millions of records, but not millions of users.

How can I go about learning the basics used by high-traffic sites so that I can be more confident in future interviews? Normally I would start a side project to learn some new technology, but it's not possible to build out a high-traffic site on the side :)

Answer 1

The problem you were asked on the interview is the so-called Cache miss-storm - a scenario in which a lot of users trigger regeneration of the cache, hitting in this way the DB.

To prevent this, first you have to set soft and hard expiration date. Lets say the hard expiration date is 1 day, and the soft 1 hour. The hard is one actually set in the cache server, the soft is in the cache value itself (or in another key in the cache server). The application reads from cache, sees that the soft time has expired, set the soft time 1 hour ahead and hits the database. In this way the next request will see the already updated time and won't trigger the cache update - it will possibly read stale data, but the data itself will be in the process of regeneration.

Next point is: you should have procedure for cache warm-up, e.g. instead of user triggering cache update, a process in your application to pre-populate the new data.

The worst case scenario is e.g. restarting the cache server, when you don't have any data. In this case you should fill cache as fast as possible and there's where a warm-up procedure may play vital role. Even if you don't have a value in the cache, it would be a good strategy to "lock" the cache (mark it as being updated), allow only one query to the database, and handle in the application by requesting the resource again after a given timeout

Answer 2

You could probably be better of using some distributed cache repository, as memcached, or others depending your access pattern. You could use the Cache implementation of Google's Guava library if you want to store the values inside the application. From the coding point of view, you would need something like

public V get(K key){
    V value = map.get(key);
    if (value == null) {
        synchronized(mutex){
            value = map.get(key);
            if (value == null) {
                value = db.fetch(key);
                map.put(key, value);
            }
        }
    }
    return value;
}

where the map is a ConcurrentMap and the mutex is just

private static Object mutex = new Object();

In this way, you will have just one request to the db per missing key.

Hope it helps! (and don't store null's, you could create a tombstone value instead!)

Answer 3

Cache miss-storm or Cache Stampede Effect, is the burst of requests to the backend when cache invalidates.

All high concurrent websites I've dealt with used some kind of caching front-end. Bein Varnish or Nginx, they all have microcaching and stampede effect suppression.

Just google for Nginx micro-caching, or Varnish stampede effect, you'll find plenty of real world examples and solutions for this sort of problem.

All boils down to whether or not you'll allow requests pass through cache to reach backend when it's in Updating or Expired state.

Usually it's possible to actively refresh cache, holding all requests to the updating entry, and then serve them from cache.

But, there is ALWAYS the question "What kind of data are you supposed to be caching or not", because, you see, if it is just plain text article, which get an edit/update, delaying cache update is not as problematic than if your data should be exactly shown on thousands of displays (real-time gaming, financial services, and so on).

So, the correct answer is, microcache, suppression of stampede effect/cache miss storm, and of course, knowing which data to cache when, how and why.

Answer 4

It is worse to consider particular data type for caching only if data consumers are ready for getting stale date (in reasonable bounds).

In such case you could define invalidation/eviction/update policy to keep you data up-to-date (in business meaning).

On update you just replace data item in cache and all new requests will be responsed with new data

Example: Stocks info system. If you do not need real-time price info it is reasonable to keep in cache stock and update it every X mils/secs with expensive remote call.