2
\$\begingroup\$

Maybe the title fails to make myself clear, more explanation to the requirements: Implement a thread-safe key-value cache. User of this cache will use an unique key to query for data. If the data is not found in cache, it should call a data provider to load data and then return it.

The provider could take long time to load and return data, so if more than one user (e.g. user A and User B) are querying by using the same key (e.g. key1) at the same time , user B should be blocked until the data is loaded (by user A's query); but if user B is querying a different key (e.g. key2) and the corresponding data is already in the cache, the data should be returned to user B immediately from the cache , while user A is still waiting for data for key1 being loaded.

Please help to review my implementation below (the code can compile and is testable), I wonder

  1. Is this implementation correct ? Is there a scenario that could break it ?
  2. Are there better solutions? I think we can also use Condition, but don't see there's any fundamental difference ...

Cache.java

import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.ConcurrentHashMap;
import java.util.function.Function;    

public class Cache <K,V> {
    private static class Wrapper<V> {
        V value;
    }

    private final Function<K,V>  provider;
    private final ConcurrentMap<K,Wrapper<V>> cache;

    public Cache(Function<K, V> provider) {
        if(provider == null) throw new NullPointerException("Need a valid provider!");
        this.provider = provider;
        this.cache = new ConcurrentHashMap<>();
    }

    public V get(K key){
        Wrapper<V> wrapper = cache.get(key);
        if(wrapper ==null){
            //cache miss
            wrapper = new Wrapper();
            Wrapper<V> savedWrapper = cache.putIfAbsent(key, wrapper);
            if(savedWrapper==null) savedWrapper=wrapper;
            synchronized (savedWrapper){
                if(savedWrapper!=wrapper){
                    //if savedWrapper is not the one created by this thread then another thread has already set the data with the same key
                    //in this case the data is ready as long as we get into the critical section (freed by the other thread that just loaded data)
                    //we don't need to do anything, just exit critical section and return the data
                }
                else{
                    //get data from provider and save it, if there is another thread querying the same key now,
                    //it will get blocked until data is set in this thread
                    savedWrapper.value = provider.apply(key);
                }
            }
            return savedWrapper.value;
        }
        else{
            synchronized (wrapper){ //the other thread might be loading data
                return  wrapper.value;
            }
        }
    }
}
\$\endgroup\$
1
\$\begingroup\$

I'm working on similar thing at the moment. So my thoughts are that you might use most popular EhCache in order to keep something you already have. ehCache.get(key) -> if its there, you return, if it's not there, we call provider. When we call provider - we need to wait for response, so I'm thinking about something like Question about your data provider - can you have parallel calls? Do you have some throttling there? If so, you could have some concurrent map for calls to store responses for keys. Once API is done you might store response in Ehcache so you have that for future. I think EhCache is better than just concurrent map for "caching" because you might define amount of entities, eliminate them, have a disk-backed cache, etc.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.