Micromanaging Memory Consumption

by Eduardo Rodrigues

As we all know, specially since Java 5.0, the JVM guys have been doing good job and have significantly improved a lot of key aspects, specially performance and memory management, which basically translates into our good old friend, the Garbage Collector (a.k.a. GC).

In almost all articles I’ve read on the memory subject, including those from Sun itself, a particular comment was always present. That briefly is:

The JVM loves small-and-short-living objects.

Don’t “nullify” variables (myObject = null;) when you decide they aren’t needed anymore as a way of hinting the GC that the objects once referenced by those variables are OK to be disposed.

I guess, after reading this “message” so many times, I finally internalized it in the form of a programming style, if I may. It’s actually very simple and takes advantage of a very basic structure, which is extremely common and kind of taken for granted. I’m talking about the very well-known code block. Yes, I’m talking about those code snippets squeezed and indented between a pair of curly braces like { <my lines of code go here> }.

In general, most programmers use these structures just because they have to as they are mandatory in so many portions of the Java language’s syntax. You need them when declaring classes, methods, try-catch-finally blocks, multi-line for loops, multi-line if-then-else blocks, etc. But the detail many programmers seem to forget is that these code blocks may actually be defined anywhere in a method body, unattached to any particular keyword or command. Even more, code blocks can be nested as well.

Besides being syntactically mandatory, the use of code blocks demarcated by opening and closing curly braces also imply a very important feature of the language. Code blocks also define variables scopes! I’ll explain…

Any variable that happens to declared inside a curly-braces-pair-demarcated code block will “exist” only within the context of that particular code block (or scope). Such variables are said to be “local variables”. Actually, if we try to use a local variable outside of its scope, we’ll most certainly get a compilation error, because that variable literally doesn’t exist outside that code block (or scope) where it was declared. And right there lies the very code of this best-practice tip.

Specifying well-defined scopes for all your local variables is actually the best way of hinting the GC about what strong references are or not in use when it kicks in. Simple enough, any strong reference coming from a variable declared inside a scope that is currently not being executed, is clearly to be considered as not in use by the GC, thus increasing the chances of proper and prompt disposal of the referenced object (if no other strong references to it exist, of course).

So, in order to better illustrate my case, here is a simple example. First let’s consider this very innocent piece of code:

public class Foo
{
   public final static void main(final String args[])
   {
        try 
        {
            DocumentBuilderFactory builderFactory = DocumentBuilderFactory.newInstance();
            DocumentBuilder builder = builderFactory.newDocumentBuilder();
            URL cfgUrl = this.getClass().getClassLoader().getResource("config.xml");
            File cfgFile =  new File(cfgUrl.toURI());

            Document cfg = builderFactory.newDocumentBuilder().parse(cfgFile);
            XPath xpath = XPathFactory.newInstance().newXPath();
            Node cfgNode = (Node)xpath.evaluate("//*[local-name()='config']", cfg, XPathConstants.NODE);

            (...)
           
        } catch (Exception ex) {
           ex.printStackTrace();
        }
    }
}

If we consider that in the very first part, variables builderFactory, builder and cfgUrl are not really needed after cfgFile is instantiated, rewriting that part like this would be preferred:

public class Foo
{
   public final static void main(final String args[])
   {
        try 
        {
            Document cfg;

            {
                DocumentBuilderFactory builderFactory = DocumentBuilderFactory.newInstance();
                DocumentBuilder builder = builderFactory.newDocumentBuilder();
                URL cfgUrl = this.getClass().getClassLoader().getResource("config.xml");
                File cfgFile =  new File(cfgUrl.toURI());
                cfg = builder.parse(cfgFile);
            }

            XPath xpath = XPathFactory.newInstance().newXPath();
            Node cfgNode = (Node)xpath.evaluate("//*[local-name()='config']", cfg, XPathConstants.NODE);

            (...)
           
        } catch (Exception ex) {
            ex.printStackTrace();
        }
    }
}

With that, when the execution is passed the red code block, all local variables declared only in that context will cease to exist for all practical means. This simple example is a mere illustration and certainly doesn’t represent any major benefit but, believe me, in a real life code, using this approach of well-defined scopes for local variables may have a significant and positive impact on your application’s memory consumption profile.

As you can see, this is indeed a very simple Java best-practice tip. It’s easy to adopt, has no collaterals whatsoever and can prove to be very powerful. So, why not use it?

Enjoy!

How to write a simple yet “bullet-proof” object cache

…continued from a previous post, by Eduardo Rodrigues

As promised, in this post, I’ll explain how we solved the 2nd part of the heap memory exhaustion problem described in my previous post: the skin resources cache. This part was much trickier to fix because we couldn’t simply get rid of the custom cache as we did with the resources bundle. We needed to keep the skins cache for 2 reasons: the cached objects were not instances of java.util.ResourceBundle but a String containing a CSS and they had to be indexed by a specific combination of variables as cache keys, which include skin base name, client locale and user agent. As already mentioned before, what causes the heap exhaustion are the various different possible combinations of the components used to compose the cache keys so the challenge here was to find a safe and efficient way of dealing with any possible amount of entries in our skins cache and also ensuring its size won’t ever cause an OutOfMemoryException that would ultimately crash the JVM.

(I know this will be a rather complicated post but I’ll do my best to keep it as simple as possible.)

The very first and most obvious approach that came to mind was to implement our own “HashMap” using weak or soft references, available since JDK 1.2. In a tiny nutshell, objects of these classes wrap the access to a specified target object and they receive a special treatment from the garbage collector (GC). If the only “live” references – meaning references that are valid and currently in use, therefore are not orphans – to an object come from instances of either java.lang.ref.WeakReference or java.lang.ref.SoftReference then such objects, including the Weak/SoftReference objects referencing them, are eligible for discard even if the Weak/SoftReference objects themselves are “alive”. The main difference between a weak and a soft reference is that the former allows the GC to discard them as soon as possible while the latter causes the GC to keep them alive as long as heap space available is not critical yet.

The reason why we didn’t initially think of using class java.util.WeakHashMap is obviously due to the fact that it uses a weak reference as the map’s key and we needed it to be as the map’s value. Another detail is that we wanted to have 2 implementations in hand, one using weak and the other using soft references. That’s because we had some concerns regarding how each solution would affect the GC performance on a heavily loaded and concurrent productions environment. Actually, our concern was more with regard to the soft references. We feared that the leniency of the GC with soft references would potentially cause such objects to quickly accumulate in the heap until the critical point where the GC would have to discard them. Since the amount of soft references to be discarded tends increase fast, this could have a substantial impact on the overall cost for the GC to do its job.

So, we started implementing our first idea, which basically consisted in writing classes WeakCache and SoftCache, both implementing interface java.util.Map and using an internal java.util.HashMap<String, java.lang.ref.WeakReference or java.lang.ref.SoftReference> as backing storage. With that, we also needed to associate each new value reference with its own java.lang.ref.ReferenceQueue since this would apparently be the only way of keeping track of the target objects being discarded by the GC and, thus making it possible for us to remove the corresponding map entry as well. Hopefully, with that we’d ultimately achieve the same functionality offered by java.util.WeakHashMap but adding a soft reference flavor to it and moving the auto-discardable references from the map’s keys to its values.

Looks good. But not good enough.

There are two big issues with the approach described above:

1. A WeakReference can be too volatile.
   
   In theory, even to the point where it can render our WeakCache almost useless. The main reason for this is the fact that, in our particular case, we were dealing with a web application where the view layer is practically 100% implemented as an AJAX client and the skin resources being cached are only used in the mid-tier (where the cache exists) during the user login flow, which is processed in one single request. Therefore, we can pretty much assume that once a login request is over, unless another one that works with the same just-cached skin resource is currently being processed on the same JVM, there won’t be any "hard” references left at all to that object.
   
   If you are somewhat familiar with Java, you’ll probably agree with me that one of the most certain things about the Garbage Collector is actually its uncertainty. By definition, we can never guarantee when the GC will kick in, much less how it will behave or which objects will be actually discarded during its cycle, therefore, no code should ever rely on any particular assumption regarding any behavioral aspect of the GC. On top of that, if we look closely into the Javadoc for java.lang.ref.WeakReference we’ll also notice that there are no guarantees whatsoever on the exact moment when disposable weakly-referenced objects will in fact be discarded by the GC. In our case, in a worse case scenario, this unpredictability pretty much means that a new skin resource object that’s just been added to our WeakCache during a login request could be immediately discarded by the GC soon after the request was processed by the mid-tier. In other words, depending on the rate at which new login requests would reach the container (or JVM) where the cache lives as well as on the skin resources they would be working with, our WeakCache could tend to be empty most of the time. And that wouldn’t be a very useful cache :)
   
   The way we solved this “minor set-back”  was by adding a configurable structure to our WeakCache, which we called a “hard cache”. The idea is very simple: we just added an internal linked list and an optional argument called “hardCacheSize”. If not needed, then specifying zero as the hardCacheSize (or not specifying it at all) would basically turn the internal hard cache off. But if the hard cache is needed (and it was in our case), then a greater than zero hardCacheSize should be specified in which case, every time a skin resource is added to the cache as a weakly-referenced value in its internal HashMap or when a skin resource is found and fetched directly from the cache, a normal (“hard”) reference to the very same instance of the skin resource is also appended to the internal LinkedList until its size reaches the defined hardCacheSize at which point the first (oldest) node in the list will simply be removed to make room for the one being appended (newest), thus limiting the list’s maximum size so that it will never overflow the hardCacheSize defined. The intention here is to add a simple LRU (Least Recently Used) feature to our cache. The more an object is “hit” in the cache, the more hard references to it will exist in the LinkedList and, because its a linked list, the order in which each hard reference was added is maintained, thus ensuring that its first node will always point to the oldest reference and its last node to the newest. Having at least one hard reference to a cached object coming from the internal hard cache should be enough to prevent the high volatility issue described here.
   
   If you’re asking why haven’t I mentioned the SoftCache here, it’s not because I forgot. Due to the nature of soft references, at least in theory, they are much less vulnerable to the issue just described.
   
   
2. Efficient monitoring of associated reference queues can be tricky and costly.
   
   As I mentioned before, the Javadocs for package java.lang.ref you’ll see that the recommended way to keep track of which weakly or softly-referenced objects have been disposed by the GC is to associate a java.lang.ref.ReferenceQueue instance with the references. We have two distinct ways to work with this queue:
   
   2.1. keep polling the queue in a controlled loop to check whether a new discarded reference is available;
   2.2. “listen” to the queue by using blocking method remove([long timeout]).
   
   Either way, if we want to keep our cache’s availability high, the smartest way of implementing a reference queue handler in our cache would probably involve the use of background threads or, since we’re talking about a J2EE application using Java 5.0, we should then make use of some executor service available in package java.util.concurrent.
   
   Needless to say, this certainly represents an overhead both in terms of code writing and complexity.

So, while we were thinking hard to come up with the most efficient, generic and elegant way of finally implementing our weak and soft caches, Mr. Eric Chan, who is one of the main architects in Oracle Beehive team, had a very interesting breakthrough. In short terms, he thought of a very nice way of combining both WeakReference and SoftReference in our weak and soft caches so that they would provide exactly the same functionality without having to deal with those reference queues at all. Basically, instead of using a plain HashMap as our backing storage, we used a java.util.WeakHashMap in both our cache implementations. The hat trick was what and how to store things in it.

Let’s start with the easiest one…

The WeakCache

This one was simple. We just replaced the backing HashMap<Key,Value> with a WeakHashMap<Key,Value> and then we used that internal “hard cache” I mentioned above as an implicit way of controlling which entries in the internal map are still in use and which ones can be disposed. The trick here was to add hard references to the map entries’ keys in the “hard cache” instead of to the values. So, if  there aren’t any hard references to a map’s key neither outside the WeakCache nor in the cache’s internal linked list, this naturally implies that the corresponding map entry in the WeakHashMap is available for disposal. To make it easier to understand, look at the diagram bellow, summarizing how the WeakCache works:

 

Now let’s go on to the trickier one…

The SoftCache

This one was the trickiest. We also replaced the internal HashMap with a WeakHashMap, however the mapped values are SoftReference objects. But instead of simply pointing them directly to the target object being added to the cache, they point to a wrapper class called ValueHolder. The trick here was to not only hold the map entries’ value objects but also their corresponding key objects. And what goes into the internal “hard cache” in this case are hard references to these ValueHolder instances. Therefore, because the internal “hard cache” is the only place where hard references to the softly referenced ValueHolder objects mapped in the internal WeakHashMap are being held and those ValueHolder objects hold hard references to their corresponding map keys, ultimately, we can assume that, provided no external hard references to a key K inside the map exist, the map entry corresponding to that key K will be kept in the map as long as there’s at least 1 instance of ValueHolder containing key K exists in the internal “hard cache”. Otherwise, the weakly referenced key K will be available for disposal and so will be its corresponding map entry.

Explaining the internal “hard cache”

This is merely an auxiliary structure. Its content does not represent the cache’s actual content, which will always be identical to that of the internal WeakHashMap. This, by the way, is a sine qua non condition. Other then that, the following rules apply:

1. when a new object is added to the cache a new reference to it is also immediately appended to the “hard cache”;
2. when an object which exists in the cache is requested, a new reference to this object is appended to the “hard cache”;
3. when the amount of elements in the “hard cache” reaches the maximum limit defined for it, then, immediately before any addition of a new reference to the “hard cache”, the oldest one (least recent) will be removed from it in order to open space to the new one (most recent);
4. the size limit that is imposed to the “hard cache” does not apply to the cache itself but uniquely and exclusively to the “hard cache”.

From that, we can extract this corollaries:

The “hard cache” contains only “hard” (or normal) references to objects that exist in the cache, therefore are contained in its internal WeakHashMap, in the natural and sequential order by which those references were added. Hence, the smaller the order of a reference in the “hard cache”, the least recent was its utilization.

There will never be a reference in the “hard cache” to an object that does not exist in the WeakHashMap. The contrary, however, is allowed. In other words: an object may exist in the WeakHashMap even if there aren’t any references to it in the “hard cache”. In this case, that particular object would be available for disposal if it’s not referenced at all from outside the cache.

The quantity Q of references in the “hard cache” to a single cached object may be defined as:

Q = [ 1 (object was simply added to the cache but never requested from it) , N ]
N = [ total # of requests to that object , S ]
S = maximum size defined for the “hard cache”

From the definition of Q above, in an extreme scenario, nothing prevents that during any given period of time the “hard cache” be completely filled with references to one single object A in the cache. For that, these 3 conditions must be met by a consumer application:

1. add object A to the cache;
2. make N requests for A to the cache where N = S (size limit defined for the “hard cache”) – 1;
3. the requests mentioned in the previous condition must be contiguous. They cannot intercalate with requests or additions of other objects.

Just to illustrate how both cache will work, consider this scenario:
Given objects A, B, C, D and E and the following sequence of operations on a cache with a maximum “hard cache” size limited to 10 elements:

   1: put ( “c” , C ); 

   2: put ( “a” , A ); 

   3: put ( “d” , D ); 

   4: get ( “a” ); 

   5: get ( “e” ); // returns null as “e” wasn’t added to the cache yet 

   6: get ( “a” ); 

   7: get ( “d” ); 

   8: put ( “b” , B ); 

   9: put ( “e” , E ); 

  10: get ( “b” );

  11: get ( “e” );

  12: get ( “a” );

Then the internal state of the cache would be:



Notice that there are no references (arrows) to the map’s entry containing object C coming from the “hard cache”. Therefore, provided there aren’t any references to C from outside the cache either, if the GC was to execute now, there’s a fair chance the internal state of the cache would become like this:

Don’t forget to get the sample code

For convenience, I’ve also made sample implementations of both caches explained available for download:

• WeakCache.java
• SoftCache.java

Beware of the obvious fact that, being sample implementations, they’re only intended to better illustrate the concepts described here and are not at all to be used as-is in real world applications. Even though they’re very good initial templates. Some of the issues I see for a high-end real world application are:

1. the use of wrapper java.util.Collections.synchronizedCollections(…) as a solution for concurrent access to the internal WeakHashMap as opposed to a more fine grained and efficient use of java.util.concurrent.locks.ReentrantReadWriteLock to establish and control all needed critical regions.
2. the use of a java.util.LinkedList as the internal “hard cache” has the main advantage of guaranteeing constant performance for the most used operations add(…) and getFirst() but the remove(…) operation on the other hand doesn’t. Actually, this is the main issue with these samples because it tends to add significant overhead when explicitly removing any object from the cache. I don’t really have any quick and ready solution for this particular problem but it could involve using a more sophisticated data structure and/or some parallel processing to mitigate the overhead.

So, enjoy and…
Keep reading!

* credits go to Mr. Eric Chan for the conceptual design and to Mrs. Khushboo Bhatia for the implementation of both caches.

Don’t be smart. Never implement a resource bundle cache!

by Eduardo Rodrigues

Well, first of all, I’d like to apologize for almost 1 year of complete silence. Since I’ve transferred from Oracle Consulting in Brazil to product development at the HQ in California, it’s been a little bit crazy here. It took a while for me to adjust and adapt to this completely new environment. But I certainly can’t complain, cause it’s been AWESOME! Besides, I'm of the opinion that, if there’s nothing really interesting to say, then it’s better to keep quiet :)

Having said that, today I want to share an interesting experience I had recently here at work. First I’ll try to summarize the story to provide some context.

The Problem

A few months ago, a huge transition happened in Oracle’s internal IT production environment when 100% of its employees (something around 80K users) were migrated from old OCS (Oracle Collaboration Suite) 10g to Oracle’s next generation enterprise collaboration solution: Oracle Beehive. Needless to say, the expectations were big and we were all naturally tense, waiting to see how the system would behave.

Within a week with the system up and running, some issues related to the component I work on (open source Zimbra x Oracle Beehive integration) started to pop up. Among those, the most serious was a mysterious memory leak, which had never been detected before during any stress test or even after more than a year of production, but was now causing containers in the mid-tier cluster to crash after a certain period.

After a couple days of heap dump and log files analysis, we discovered that the culprit were 2 different resource caches maintained by 2 different components in Zimbra’s servlet layer, both related to its internationalization capabilities. In summary, one was a skin cache and the other was a resource bundle cache.

Once we dove into Zimbra’s source code, we quickly realized we were not really facing a memory leak per se but an implementation which clearly underestimated the explosive growth in memory consumption that a worldwide deployment like ours has a huge potential to trigger.

Both caches were simply HashMap objects and, ironically, their keys were actually the key to our problem. The map keys were defined as a combination that included client’s locale, user agent and, in the case of the skins cache, the skin name was also included. Well… you can probably imagine how many different combinations of these elements are possible within a worldwide system deployment, right? Absolutely! In our case, each HashMap would quickly reach 200MB. Of course, consuming 400MB out of 1GB of configured heap space with only 2 objects is not very economic (to say the least).

So, OK. Great! We found our root cause (which is awesome enough in this kind of hard-to-analyze-production-only bugs). But now comes the harder part: how can we fix it?!

The Solution

First of all, it’s very important to keep this very important aspect in mind: we were dealing with a source code that wasn’t ours, therefore, keeping changes as minimal as possible was always crucial.

One thing we noticed right away was the fact that we were most likely creating multiple entries in both maps that ended up containing identical copies of a same skin or resource bundle content. That’s because our system only supported 15 distinct locales, which means, every unsupported client locale would fallback to one of the supported locales, ultimately, the default English locale. However, the map key would still be composed with the client’s locale, thus creating a new map entry, and even worse, mapping to a new copy of the fallback locale. Yes, locales and skins that had already been loaded and processed, were constantly being reloaded, reprocessed and added to the caches.

So, our first approach was to perform a small intervention with the only intention to prevent any unsupported client locale from originating a new entry in those maps. Ideally, we would want to change the maps’ key composition but we were not very comfortable with this idea, mainly because we were not sure we fully understood all the consequences of that, and fix the problem causing another was not an option.

Unfortunately, days after patching the system, our containers were crashing with OutOfMemory exceptions again. As we discovered – the hardest way – simply containing the variation of the locale component in the maps’ key composition was enough to slow down the heap consumption but not enough to avoid the OOM crashes.

Now it was time to put our “fears” aside and dig deeper. And we decided to dig in two simultaneous fronts: the skin cache and the resource bundle cache. In this post, I’ll only talk about the resource bundle front leaving the skin cache front to a next post.

When I say “resource bundle”, I’m actually referring to Java’s java.util.ResourceBundle, more specifically its subclass java.util.PropertyResourceBundle. With that in mind, 2 strange things caught my attention while looking carefully into the heap dumps:

1. Each ResourceBundle instance had a “parent” attribute pointing to its next fallback locale and so on, until the ultimate fallback, the default locale. This means that each loaded resource bundle could actually encapsulate other 2 bundles.
2. There were multiple ResourceBundle instances (each one with a different memory address) for 1 same locale.

So, number 1 made me realize that the memory consumption issue was even worse than I thought. But number 2 made no sense at all. Why have a cache that is only stocking objects but is not able to reuse existing ones? So I decided to take a look at the source code of class java.util.ResourceBundle in JDK 5.0. The Javadoc says:

“Implementations of getBundle may cache instantiated resource bundles and return the same resource bundle instance multiple times.”

Well, turns out Sun’s implementation (the one we use) DOES CACHE instantiated resource bundles. Even better, it uses a soft cache, which means all content is stored as soft references, granting the garbage collector the permission to discard one or more of its entries if it decides it needs to free up more heap space. Problem solved! – I thought. I just needed to completely remove the unnecessary resource bundle cache from Zimbra’s code ant let it take advantage of the JVM’s internal soft cache. And that’s exactly what I tried. But, of course, it wouldn’t be that easy…

Since at this point I already knew exactly how to simulate the root cause of our problem, I started debugging my modified code and I was amazed when I saw that the internal JVM’s cache was also stocking up multiple copies of bundles for identical locales. The good thing was that now I could understand what was causing #2 above. But why?! The only logical conclusion was, again, to blame the cache’s key composition.

The JVM’s resource bundle cache also uses a key, which is composed by the bundle’s name + the corresponding java.util.Locale instance + a weak reference to the class loader used to load the bundle. But then, how come a second attempt to load a resource bundle named “/zimbra/msg/ZmMsg_en_us.properties”, corresponding to en_us locale and using the very same class loader was not hitting the cache?

After a couple hours thinking I was loosing my mind, I finally noticed that, in fact, each time a new load attempt was made, the class loader instance, although of the same type, was never the same. And I also noticed that its type was actually an extended class loader implemented by inner-class com.zimbra.webClient.servlet.JspServlet$ResourceLoader. When I checked that code, I immediately realized that class com.zimbra.webClient.servlet.JspServlet, which itself is an extension of the real JspServlet being used in the container, was overriding method service() and creating a new private instance of custom class loader ResourceLoader and forcefully replacing the current thread’s context class loader with this custom one, which was then utilized to load the resource bundles.

My first attempt to solve this mess was to make the custom class loader also override methods hashCode() and equals(Object) so they would actually proxy the parent class loader (which was always the original one that was replaced in method service()). Since the web application’s class loader instance would always be the same during the application’s entire life cycle, both hashCode and equals for the custom loader would consistently return the same results at all times, thus causing the composed keys to match and cached bundles to be reused instead of reloaded and re-cached. And I was wrong once again.

Turns out, as strange as it may look at first sight, when the JVM’s resource bundle cache tries to match keys in its soft cache, instead of calling the traditional equals() to compare the class loader instances, it simply uses the “==” operator, which simply compares their memory addresses. Actually, if we think more about it, we start to understand why they implemented this way. Class loaders are never expected to be constantly instantiated, over and over again, during the life cycle of any application, so why make an overhead method call to equals()?

Finally, now I knew for sure what was the definitive solution. I just needed to transform the private instances of ResourceLoader into a singleton, keeping all the original logic. Bingo! Now I could see the internal bundle cache being hit as it should be. Problem solved, at last!

At the end, after having completely removed the custom resource bundle cache implemented in Zimbra’s servlet layer and performed the necessary changes to make Zimbra take full and proper advantage of the built-in bundle cache offered by the JVM, instead of wasting a lot of time and memory reloading and storing hundreds of instances of resource bundles, mostly multiple copies of identical bundles, I could now confirm that despite all different client locales coming in clients' requests, the JVM’s bundle cache was holding no more than those corresponding to the 15 supported locales. With that, we had finally fixed the memory burning issue for good.

Conclusion

As this article’s title suggests, don’t try to be smarter than the JVM itself without first checking whether it’s doing it’s job well enough or not. Always do carefully read the Javadocs and, if needed, check your JVM’s source code to be sure about its behavior.

And remember…. never implement a resource bundle cache in your application (at least if you’re using Sun’s JVM) and be very careful when implementing and using your own custom class loaders too.

That’s all for now and…
Keep reading!