7
\$\begingroup\$

I am working on a small project which utilizes a 3rd party API. Many of the queries from the API can take 5-10 seconds so to keep the front end moving a bit faster I decided to cache the responses from these calls. I ended up building my own cache implementation. There are 3 classes in this implementation which are posted below in the following order: Cache, CacheBin, CacheEntry. All classes should be thread safe. I consider myself a novice of concurrency so its very possible I have something not quite right on that end.

  • Cache is simply wrapper for Map<T, CacheBin<E> and I use store each API call seperated into CacheBins.
  • CacheBin is the basic foundation of a cache with one little tweak. Instead of using a generic type or any old string as a key it uses a MD5 to calculate a key. The reason for the MD5 is many of the queries I send to the API are upwards of 1k characters. Also I am using SoftReference<CacheEntry<T>> so that garbage collection can pick up these bins if memory is running low.
  • CacheEntry an actual entry of data from the cache, is immutable and contains an expiration time.

Also, at the bottom, I have included some JUnit tests I made in case you want to run these.

Questions:

  • Is my synchronization in the Cache and CacheBin correct and/or is there a cleaner way to do it?
  • Am I using SoftReference inside CacheBin on the CacheEntry correctly? Will a SoftReference on the CacheEntry be enough or should I do a SoftReference on the data property of CacheEntry. On my JVM they are being cleand up however some reading on the subject says that JVMs do treat SoftReferences differently so a different approach might be necessary,
  • Does the MD5 sum of a JSON request body make sense to use for a HashMap implementation?

A very simple showing of a CacheBin:

long cacheExpiration = 300; // 300 ms for testing
CacheBin<String> bin = new CacheBin<String>(cacheExpiration);
bin.store("hello", "world");
// cache is good
Assert.assertEquals("world", bin.get("hello"));

How I'm using it to cache data from this API:

// shared cache for all api calls
private static final Cache<String, APIResponse> API_CACHE = new Cache<String, APIResponse>(TimeUnit.MINUTES.toMillis(10));

public APIResponse getHistogram() {
    String uri = "analyze/histogram";
    ....
    Gson gson = ServerUtil.createAPIGson();
    Object contentBody = new HistorgramRequest(filter, groupBy);
    String requestBody = gson.toJson(contentBody);

    APIResponse cachedResponse = API_CACHE.get(uri, requestBody);
    if(cachedResponse != null && cachedResponse.isSuccess()) {
        // return a cached response
        return (HistogramResponse) cachedResponse;
    }

    // query the api
    writeConnectionBody(con, requestBody);
    HistogramResponse res = ServerUtil.createGson().fromJson(new InputStreamReader(con.getInputStream()), HistogramResponse.class);
    ...
    API_CACHE.store(uri, requestBody, res);
}

Classes:

Cache

import java.io.Serializable;
import java.util.HashMap;
import java.util.Map;


/**
 * Caches server requests with server responses, I couldnt find a good implementation of this online because most wouldnt allow caching of POST requests.
 * The choice was made to build my own implementation. This version just takes the request body and calculates a MD5 on the body as the key. Caches are seperated
 * by the <T> value, this allows each URI to have its own cache to allow for the same request body to different URLs.
 * 
 * * This implementation does not include request and response header values. It is limited to the body of the request/response. Its exactly what I need for this
 * job and nothing more.
 * @author Ned
 *
 * @param <T> The object which will identify the unique cache bins.
 * @param <E> Type which the responses are stored in. Most primitive type would probably be a String.
 */
public class Cache<T, E> implements Serializable {
    private static final long serialVersionUID = 2L;

    private final Map<T, CacheBin<E>> bins;
    private final long cacheExpiration;

    public Cache(long cacheExpiration) {
        this.cacheExpiration = cacheExpiration;
        this.bins = new HashMap<T, CacheBin<E>>();
    }

    /**
     * Stores a response in the cache, 
     * @param key
     * @param body
     * @param data
     */
    public synchronized void store(T binKey, String key, E data) {
        CacheBin<E> bin = bins.get(binKey);
        if(bin == null) {
            bin = new CacheBin<E>(cacheExpiration);
            bins.put(binKey, bin);
        }

        bin.store(key, data);
    }

    public synchronized E get(T binKey, String key) {
        CacheBin<E> bin = bins.get(binKey);
        if(bin != null) {
            return bin.get(key);
        }
        return null;
    }

    public synchronized void clear() {
        this.bins.clear();
    }
}

CacheBin

import java.io.Serializable;
import java.lang.ref.SoftReference;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

import org.apache.log4j.Logger;


public class CacheBin<T> implements Serializable {
    private static final long serialVersionUID = 1L;
    private Logger logger = Logger.getLogger(CacheBin.class);

    private Object lock = new Object();

    private final long cacheExpiration;
    private final Map<String, SoftReference<CacheEntry<T>>> cache;


    public CacheBin() {
        this(300000); // 5 minutes till expiration
    }

    public CacheBin(long cacheExpiration) {
        this.cacheExpiration = cacheExpiration;
        this.cache = new HashMap<String, SoftReference<CacheEntry<T>>>();
    }

    public int getCacheSize() {
        synchronized (lock) {
            return this.cache.size();
        }
    }

    /**
     * Clears the cache of all elements
     */
    public void clear() {
        synchronized (lock) {
            this.cache.clear();
        }
    }

    /**
     * Cleans up the cache by removing elements that are expired
     */
    public void cleanup() {
        synchronized (lock) {
            for(Iterator<String> it = cache.keySet().iterator(); it.hasNext();) {
                String key = it.next();
                SoftReference<CacheEntry<T>> value = cache.get(key);
                if(value.get() == null) {
                    logger.trace("Cache entry was garbage collected");
                    cache.remove(key);
                } else if(value.get().isExpired()) {
                    logger.trace("Cache expired");
                    cache.remove(key);
                }
            }

        }
    }


    /**
     * find a value in the cache. Returns NULL if no value was found
     * @param body
     * @return
     */
    public T get(String key) {
        synchronized (lock) {
            assert key != null;

            String storeKey = convertToKey(key);
            if(cache.containsKey(storeKey)) {
                SoftReference<CacheEntry<T>> cached = cache.get(storeKey);
                if(cached.get() == null) {
                    logger.trace("Cache entry was garbage collected");
                    cache.remove(storeKey);
                } else if(!cached.get().isExpired()) {
                    logger.trace("Cache hit");
                    return cached.get().getData();
                } else {
                    logger.trace("Cache expired");
                    cache.remove(storeKey);
                }
            } else {
                logger.trace("Cache Miss");
            }
            return null;
        }
    }


    /**
     * Stores a value in the cache
     * @param key
     * @param body
     * @param data
     */
    public void store(String key, T entry) {
        assert key != null;
        synchronized (lock) {
            String storeKey = convertToKey(key);
            cache.put(storeKey, new SoftReference<CacheEntry<T>>(new CacheEntry<T>(entry, cacheExpiration)));
        }
    }



    private String convertToKey(String data) {
        try {
            MessageDigest digest = MessageDigest.getInstance("MD5");
            return new String(digest.digest(data.getBytes()));
        } catch (NoSuchAlgorithmException e) {
            logger.error("Failed to create MD5 digest, using raw data for keys instead. This will likely result in high memory usage.", e);
        }
        return data;
    }
}

CacheEntry

import java.io.Serializable;

class CacheEntry<E> implements Serializable {
    private static final long serialVersionUID = 1L;

    private final long expirationTime;
    private final E data;

    public CacheEntry(E data, long liveTime) {
        this.expirationTime = System.currentTimeMillis() + liveTime;
        this.data = data;
    }
    public long getExpirationTime() {
        return expirationTime;
    }
    public E getData() {
        return data;
    }

    public boolean isExpired() {
        return expirationTime <= System.currentTimeMillis();
    }
}

Heres the JUnit tests I made up while I was building this out. They aren't perfect especially the cacheSoftReference method. I am not necessarily looking for help with these but they might help you quickly run the code if you like.

public class CacheTest {

    @Test
    public void cachePut() {
    long cacheExpiration = 300; // 300 ms for testing
    CacheBin<String> bin = new CacheBin<String>(cacheExpiration);
    bin.store("hello", "world");
    // cache is good
    Assert.assertEquals("world", bin.get("hello"));
    }

    @Test
    public void cacheExpiration() throws InterruptedException {
        long cacheExpiration = 300; // 300 ms for testing
        CacheBin<String> bin = new CacheBin<String>(cacheExpiration);
        bin.store("hello", "world");
        // cache is good
        Assert.assertEquals("world", bin.get("hello"));
        Thread.sleep(cacheExpiration);
        // cache should have expired
        Assert.assertEquals(null, bin.get("hello"));
    }

    @Test
    public void cacheCleanup() throws InterruptedException {
        long cacheExpiration = 300; // 300 ms for testing
        CacheBin<String> bin = new CacheBin<String>(cacheExpiration);
        bin.store("hello", "world");
        // cache is good
        Assert.assertEquals("world", bin.get("hello"));
        Thread.sleep(cacheExpiration);

        bin.cleanup();
        // cache should have expired
        Assert.assertEquals(0, bin.getCacheSize());
    }

    /*
     * Tests the soft reference garbage collection */
    @Test
    public void cacheSoftReference() {

        // the wait time in MS for the garbage collector to pickup.
        final int maximumWaitTime = 5000;


        final CacheBin<char[]> bin = new CacheBin<char[]>(Integer.MAX_VALUE);
        final int arrayLength = (int) (Runtime.getRuntime().freeMemory()/8);
        bin.store("ShouldBeCollected", new char[arrayLength]);

        // lock to notify the unit test that the bin has been collected.
        final Object notificationObject = new Object();
        // allocates large ammounts of data to the heap. Eventually the cache entry we are looking at *should* be garbage collected
        Thread heapAllocationThread = new Thread(new Runnable() {
            @Override
            public void run() {
                int i = 0;
                while(bin.get("ShouldBeCollected") != null) {
                    bin.store(String.valueOf(i++), new char[arrayLength]);
                }
                // notify the thread below that we have completed.
                synchronized (notificationObject) {
                    notificationObject.notify();
                }
            }
        });
        heapAllocationThread.start();

        synchronized (notificationObject) {
            try {
                notificationObject.wait(maximumWaitTime);
                Assert.assertNull("The bin should have been picked up by the garbage collecter, however the result may vary depending on your runtime enviroment.\n"
                        + "Try increasing the wait time on for this test or decreasing heap space when running this test before debugging further.", bin.get("ShouldBeCollected"));
            } catch (InterruptedException e) {
                e.printStackTrace();
            } finally {
                // make sure we stop our loop, otherwise we could have a thread that doesnt stop!
                bin.store("ShouldBeCollected", null);
            }
        }
    }

}
\$\endgroup\$
  • \$\begingroup\$ What's the compelling reason to not use an existing cache implementation, of which there are many? Caches are tricky to get right. \$\endgroup\$ – Eric Stein Feb 22 '15 at 2:37
  • \$\begingroup\$ @EricStein If this were a larger project or for a project with alot of traffic I would definitely use something like Ehcache. However I like to take the opportunity on my side projects to try and build something I havent or do something I dont know how to do. This is just one of those opportunity's. Heck its what keeps programming fun. \$\endgroup\$ – ns47731 Feb 22 '15 at 2:49
  • \$\begingroup\$ Try using Guava cache. It is lightweight and simple to use, so you won't have to invent and support yet another cache implementation. \$\endgroup\$ – harshtuna Feb 22 '15 at 14:28
  • 1
    \$\begingroup\$ The situation needs a design review. \$\endgroup\$ – Peter Rader Feb 23 '15 at 15:49
  • \$\begingroup\$ You're making it too complicated.Keep it short and simple. Use Collections.synchronizedMap and (uri + requestBody) as a key. \$\endgroup\$ – dieter Mar 27 '15 at 13:37
2
\$\begingroup\$

I think you should never implement your own cache for any serious project. This is many times implemented and it is not only a waste of time, but quite error-prone. That said, these are my (subjective) answers to your questions:

Is my synchronization in the Cache and CacheBin correct and/or is there a cleaner way to do it?

How is the correctness of a cache synchronization defined? I mean, what is the worst case scenario of the incorrect cache synchronization? That you compute an entry twice? That's not so bad. In fact, there are (quite common) scenarios where no synchronization gives you faster results (less synchronization overhead), e.g. when using ConcurrentHashMap. That said, I think your Cache synchronization is correct, but very non-optimal. E.g. your methods are starting with a (implicit) synchronized block, which is IMHO not optimal and a double check should be preferred (because of throughput). Imagine the key everybody uses is already cached, and you have 1000 parallel users (threads) wanting to retrieve this key from your cache. They would need to go through your synchronized methods one by one (instead of all at once if you don't start with the synchronized block, but check the cache first). Yet another reason for an optimized solution. Then you are synchronizing the whole cache even if 100 users are working with different keys. One more reason for some done project, like Guava or EhCache, which can do explicit per-key locking.

Am I using SoftReference inside CacheBin on the CacheEntry correctly? Will a SoftReference on the CacheEntry be enough or should I do a SoftReference on the data property of CacheEntry. On my JVM they are being cleand up however some reading on the subject says that JVMs do treat SoftReferences differently so a different approach might be necessary.

My guess is you are using it correctly. That said, Guava and other cache implementation can do it as well and I bet they do it even more correctly ;)

Does the MD5 sum of a JSON request body make sense to use for a HashMap implementation?

I don't see any good reason for the MD5 sum because of how HasMap and hashCode() of the String works. Normally if you use Strings as keys of a HashMap, hashCode is invoked, which goes through the whole String once. Your implementation does the same when you do the MD5 sum, but then you make HashMap go through MD5 sum String, so you add more overhead.

\$\endgroup\$

protected by Malachi Feb 23 '15 at 15:46

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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