ReentrantReadWriteLock lock upgrade method

Question

I have a question about lock upgrading.Specifically what bothers me is between readlock.unlock() and following writelock.lock()... I am providing a nearly complete implementation for a sample cache.I just omitted actual loading of cached data from database.

I appreciate if you can review the code and share your thoughts. I tried to express my concern in the java comments . My question is how to correctly synchronize in order to avoid rechecking the cache in load cache.

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.locks.*;




public class JavaRanchSampleCache {

    private ConcurrentHashMap<String, ReentrantReadWriteLock> refreshLocks = new ConcurrentHashMap<String, ReentrantReadWriteLock>();
    private ConcurrentHashMap<String, HashMap<String, String>> cacheData = new ConcurrentHashMap<String, HashMap<String, String>> ();

    public  HashMap<String, String> getCachedData(String cacheKey)
    {
        ReentrantReadWriteLock lock = refreshLocks.get(cacheKey);

        if(lock==null)
        {
            lock=new ReentrantReadWriteLock();      
            ReentrantReadWriteLock previous=refreshLocks.putIfAbsent(cacheKey, lock);
            if(previous!=null)//null means no previous lock object,first time usage
                lock=previous;      
        }

        //we have a safe lock at this point
        try
        {
            lock.readLock().lock();//read the cached item for correspoding cacheKey
            HashMap<String, String> cachedItem=cacheData.get(cacheKey);
            if(cachedItem==null)//it is not cached yet.Load to cache on first request
            {
                cachedItem=loadItemExpensive(cacheKey);
            }

            return cachedItem;//return the cached item.

        }
        finally
        {
            lock.readLock().unlock();   
        }

    }

    private HashMap<String, String> loadItemExpensive(String cahceKey)
    {
        ReentrantReadWriteLock lock = this.refreshLocks.get(cahceKey);
        HashMap<String, String> cachedItem=null;
        try
        {
             /*these two lines are for lock upgrading
             * BUT what happens if another thread interacts between line1 and line2
             * I mean after the readlock is relased,some OTHER thread might gain the writelock
             * before this thread and perform loaddata and update cache operation.
             * So should I check the cache once more to see if some other thread 
             * has updated the cache? I 'feel' that I should,but it is ugly,i need some clever way.
             */
            lock.readLock().unlock();//line1
            lock.writeLock().lock();//line2


            /*omitted load data from some expensive store such as database or remote server*/

            return  cachedItem;
        }
        finally
        {
            lock.readLock().lock();//writelock owner can grant readlock immediately.
            lock.writeLock().unlock();//lock released
        }
    }

}

Answer 1

Your fears are valid. Once you let go of the lock, all bets are off. When you get the write lock, you will need to check if another thread has mutated the cache. Don't think of it as "ugly"; think of it as "correct". Continue to use comments to explain what you're doing and why you're doing it.

In a nutshell, a read/write lock can't support both upgrading and downgrading. Multiple locks must always be acquired in the same order (in this case, write then read), otherwise a deadly embrace can occur. So when going the other way (read then write), you must let go of the lock, at which point any decisions you made based on current state must be reconsidered.

But there are other options, depending on the details of your situation.

One is to always a get a write lock in anticipation of needing to make a modification and downgrading to a read lock if the data's already there. This is probably not what you want, especially if the majority of operations are read-only, as it will lead to lock contention and poor response times under load.

Other options might involve allowing multiple threads to (redundantly) perform the expensive load, and acquiring the write lock just at the moment of insertion to the table. Or it might be appropriate to just blindly overwrite the existing entry (in this last case, all you would really need is ConcurrentHashMap) . It all depends on the scenario what you're willing to tolerate.

Hope this helps.

Answer 2

This is an old question, but here's both a solution to the problem, and some background information.

If you need to safely acquire a write lock without first releasing a read lock, take a look at a different type of lock instead, a read-write-update lock.

I've written a ReentrantReadWrite_Update_Lock, and released it as open source under an Apache 2.0 license here. I also posted details of the approach to the JSR166 concurrency-interest mailing list, and the approach survived some back and forth scrutiny by members on that list.

The approach is pretty simple, and as I mentioned on concurrency-interest, the idea is not entirely new as it was discussed on the Linux kernel mailing list at least as far back as the year 2000. Also the .Net platform's ReaderWriterLockSlim supports lock upgrade also. So effectively this concept had simply not been implemented on Java (AFAICT) until now.

The idea is to provide an update lock in addition to the read lock and the write lock. An update lock is an intermediate type of lock between a read lock and a write lock. Like the write lock, only one thread can acquire an update lock at a time. But like a read lock, it allows read access to the thread which holds it, and concurrently to other threads which hold regular read locks. The key feature is that the update lock can be upgraded from its read-only status, to a write lock, and this is not susceptible to deadlock because only one thread can hold an update lock and be in a position to upgrade at a time.

This supports lock upgrade, and furthermore it is more efficient than a conventional readers-writer lock in applications with read-before-write access patterns, because it blocks reading threads for shorter periods of time.

Example usage is provided on the site. The library has 100% test coverage and is in Maven central.

Note there is a similar question here.