This is  the first part of series of posts I plan to put-up on effective memory-centric cache implementations.

Well I have been working and going through different cache implementations in Java. Below is a discussion on some of them. The aim is to choose the perfect cache for a respective scenario. Below I have tried to explain the basics of Java dependencies to keep it language independent.

Now in general it is found out that LRU (Least Recently Used) is preferable for most of the scenarios. And it can be very easily be implemented in Java by extending a beautiful data structure “LinkedHashMap” and overriding removeEldestEntry(final Map.Entry<A, B> eldest).  More on it here. But the issue with it is the size. How will you set the size of the cache? If the cache size is too small, it would not solve the purpose. If it is too large, it might eat away applications required memory.

Fixing the size of the cache indeed is tough. Ideally you would want a cache that scales according to the application. Under low memory consumption by application, one wont mind cache taking too much of memory. Under high memory contention, one would want cache size to decrease (though it will create performance problems as cache might be non-existent then. But it is atleast better than repetitive Full GC’s).

Hence I have been in search for an effective implementation of Cache which is:

  • LRU
  • Size variant depending upon the available Memory.

Though it is still work in progress, I will be discussing about the second option above in this post and the next. And a culmination of both in the third post.

Scaling of Cache

The aim is be to generate specifications based on quantitative analysis to for a perfect outlook to implement such a scenario.

To implement such a case, we need some support from the language which shall timely give us input about the available memory; Better if it can itself remove objects from cache. Luckily Java gives us this flexibility be providing us with a java.lang.ref package which provides limited communication with Garbage Collector.

For analysis here I have taken the code from from org.neo4j.kernel.impl.cache package of Neo4J graph database. I have slightly modified the code to generate statistics. The code is a property of NeoTechnologies and is used here only for educational purposes. It very well implements what we desire. The link to cache is here. Primarily it has 2 cache versions:

  • SoftRefCache
  • WeakRefCache
Both of them internally use ConcurrentHashMap data structure which hold a key-value pair. The difference in both above is that- SoftRefCache uses a SoftReference wrapper above the value  and WeakRefCache uses a WeakReference wrapper above the value pair in the HashMap.
The key is that – under different memory scenarios, the objects in cache automatically become Softly or Weakly reachable and ultimately becoming ready for garbage collection. Hence cache scaling according to needs.

Cache & Performance – In Worst Case Scenario

I have carried some tests to decide which version should be used under what scenario. The below is analysis under high contention where all different objects are repeatedly added to cache. In reality, this can only happen under heavy stress.

The code to exhibit the above can be found out at CacheTest.java inside cache.neo4j package. Roughly it is:

private void go() {
 SoftLruCache<EntityInteger> cache = new SoftLruCache<EntityInteger>("Soft Cache");
 test(cache);
 }

private void go2()
 {
 WeakLruCache<EntityInteger> cache2 = new WeakLruCache<>("Weak Cache");
 test(cache2);
 }

private void test(ReferenceCache<EntityInteger> cache) {
 for (int i = 0; i < Integer.MAX_VALUE; i++) {
 cache.put(new EntityInteger(i));
 }
 }

Below is individual analysis for each of the case. Though it is not true comparison of cache’s but rather SoftReference and WeakReference.
My configuration:

java version “1.7.0_05″
Java(TM) SE Runtime Environment (build 1.7.0_05-b05)
Java HotSpot(TM) Client VM (build 23.1-b03, mixed mode, sharing)
Windows 7.
intel i3 processor.
JVM arguments: -server  -Xmx200M -verbose:gc -XX:+PrintGCDetails (Xmx means JVM can at max hold 200 mb of RAM)

SoftLruCache

Below is a graph of size of cache vs time.

The memory behavior:

softlru

 

* Above the memory result is not correct as profiler itself might be consuming decent amount of memory. Without loss of generality, once can assume that it is consuming about 80-100 mb.

And the log.

Results:

  • The memory expand to full 200mb allotted, after which results in repeated Full GC’s which frees up memory. During which, the cache size drastically reduces from ~1,700,000 to mere 400,000.
  • The above cycle is repeated periodically. With the cache size increasing to 1,400,000 and then a drastic fall to less than 100,000. In some cases to even below 1000.
  • On an average, around 75% of applications running time was spent in Garbage Collection.
Analysis:
You for sure will face your administrators wrath if you are going to use it in such a case. 75 % time on GC is just a straight kill. Basically cache fills up till there is no more memory available. Which yields in Full GC. A lot of memory is cleared up and the cache again starts filling up.
Actually people might not agree with me. Here the objects are added at a very very fast rate. So its no wonder that performance is so bad. Though yes waiting till there is no memory available to clear up might be a bad option (as it might effect applications functioning). But in cases where you know that the size of the cache might never grow such significantly high; And even if it does, if the objects are not added at such high rate later. It is actually might be a good option.
To verify the above, I modified the program as: As soon as more than 3,000,000 elements are added to cache, reduce the rate of addition to cache by 500 times. The results were:
  • Time spent on GC reduced to less than 50% and below.
  • Constant memory consumption of 160 MB. This is different from previous results.
  • Cache size hardly ever went below 1,000,000 which in a way is a good thing.

Next post will be the same analysis on Weak Reference. Later repetition for a more realistic scenario

References:

For more on java.lang.ref:

  1. http://docs.oracle.com/javase/7/docs/api/index.html
  • http://jimwebber.org Jim Webber

    Actually the Neo4j code is (A)GPL so you’re quite free to share it around under the terms of those licenses. You can use them educationally, commercially, or however else you see fit within those T&C’s.