Who’s keeping them? – Java Objects, Caching and OutOfMemory errors

In 1999, Ed Lycklama, then CTO at the KL Group, gave a now-famous talk at JavaOne about how Java applications run out of memory. Lycklama not only summarized the differences in memory management between C++ and Java. He also classified the types of errors that can run Java programs out of memory. Lycklama coined a new term for objects that remain in memory past their usefulness: loiterers.

For sure, references that make an object appear useful are sometimes straight-out bugs. Lycklama mentions several of such developer oversights: failing to deregister event listeners; failing to completely clear old state in a setter; or failing to drop references in outer scopes of long-running threads.

But garbage collectors use the liveness of objects to determine what to collect as trash. And there are programming strategies which manipulate liveness purposefully, as a wager.

Lying about Liveness

Dynamic programming is such a strategy. Dynamic programming trades space on the heap for execution time. The wager is that a computed value may well prove useful again really soon. For if that value is requested again in the near future, not forgetting about it immediately will pay off in terms of computing effort saved.

The best-known implementation for achieving this effect is to store the expensive item in a special data structure, the cache. The advantages such a strategy are well illustrated by how ubiquitous caches are through-out the memory hierarchy. CPUs, GPUs, main memory, disk devices, network cards—they all use caches. And caching is not just particular to hardware. Operating systems cache disk blocks; browsers cache frequently visited contents. To make the user experience lively, the liveness of the object is manipulated.

There is no API in Java to communicate such an intention to the garbage collector. There are other APIs for references – weak references, for example; even soft references for memory panics; but nothing to capture the wager of cached references. So the garbage collector must be tricked into thinking that the value is immediately useful to the cache. Because the garbage collector has been hood-winked, the cache must now decide on its own when an object’s usefulness has passed.

And determining which wagers to take when they involve notions such as “really soon” is a very hard problem indeed—unlike liveness, which is a deterministic property. So the cache has to act heuristically. Its loyalty to the objects retained must be bounded. Old information may not just have grown uninteresting—it may have become incorrect.

Shared Responsiveness

When systems respond to button clicks in <200ms, page navigation in <1s, search results in 1-2s, and report generation in 5-8s with progress bars, users experience performance as appropriate and professional. —UXUIPrinciples

User experiences feel “appropriate and professional” if all interactions are within very tight time windows. These expectations can feed directly into key performance indicators by which developers are judged. Simple KPIs for responsiveness lead to pervasive caching at all levels of the application stack. This is a classic tragedy of the commons situation. Every member of the development team is incentivized to meet their responsiveness goals. The heap space is a shared resource. Assume that everyone only takes what they need to meet the common responsiveness goal in all reported situations. Even then it remains unclear where to point the finger when the first java.lang.OutOfMemory errors roll in.

Before reaching for the memory profiler, though, consider this: Some out-of-memory errors are failures of incentives rather than of software engineering. The KPI called for responsiveness above all else, and that is what the team delivered. The solutions are therefore interventions of policy, not necessarily of coding.

1. Introduce visibility – an API to query how big all caches are and how big they are allowed to grow. Be warned that this is a registration pattern, so all of Ed Lycklama’s concerns about loitering apply.
2. Introduce KPIs for cache consumption. Teams are allocated fixed budgets. This makes the decision which objects to cache one of design, not of convenience. Finding faster implementation now carries rewards – removing caching here frees up the budget to cache over there.
3. If change has to come immediately, make some cache settings global and non-negotiable. That is uniformly unfair while generating the uptime needed to focus on improving individual parts of the system.

Finding the Loiterers

Eventually, that day will arrive where the Operations team reports that a Java heap dump is all that remains of a production instance. Now the time has come to reach for the memory profiler. Assume it is VisualVM, though Eclipse’s MAT is equally popular in the community.

Pulling up the heap dump provides some basic statistics about the memory and a way to surf around the object graph. Perhaps it is luck, perhaps it is a suspicion … eventually one object jumps out. That one should no longer be here!

Asking what is keeping that object is pointless. The cache by design told the garbage collector to go away and mind its own business. The question instead becomes: which cache is still referring to this loiterer mistakenly? Or to its containing object. Or the containing object of that containing object?

By that point, the UI starts looking less than ideal for this task. Clicking through all the referrers of an object and all of those objects’ referrers sounds … like the work that the garbage collector does. Which is not surprising; that was the role that the faulty cache pretended to take.

Back up to first principles then. What exactly does a garbage collector do? A garbage collector walks an object graph. It starts from known keepers (the so-called roots, such as thread stacks and global variables) and preserves the ones it reaches. Everything else, the unreached, by definition is trash.

Speaking in terms of implementation, the garbage collector builds a queue of objects still to visit. The queue is first filled with the roots. Objects are popped off until none are left. Each object is analyzed, that is, checked for which objects they point to. Since object graphs can form cycles legally, the collector must deduplicate them to terminate. All unvisited objects are queued and the scan continues.

This basic algorithm, mark-and-sweep, is exactly the tool this problem needs, but run outwards. Seed the queue with the loitering object. For each dequeued object, skip those already analyzed. As for the newly seen objects, check if they are cache entries. If they are, success; that is the guilty party. If not, push their referrers — the objects that point to the dequeued item — onto the queue to check soon.

Object Query Language (OQL)

No point looking for such a search tool in the menus. Not only is it not there, it is not even necessary. Because there is OQL. One of the most powerful tools of the memory profiler. Surprised? That is because OQL suffers from sad marketing. Every tutorial on heap debugging that mentions OQL gives the same handful of examples that the documentation had since Java 1.4 or thereabouts. Apparently no one ever found any more useful examples?

Indeed, OQL as presented is not very useful. What is enormously useful is the ability to write one’s own JavaScript functions that can access the heap dump programmatically and run them in OQL. That capability is enough to write two functions that implement a backward garbage collector. They will find all the referrers to a seed object that belong to a specific class, in a mark-and-sweep fashion.

objectnum (clazz, num) will find the seed object of class clazz displayed in the visual UI with id num.

find_enclosing(enclosing_class, seed, max_rounds) will find the instance of the enclosing class that is the ancestor referrer of the seed; it may return multiple of them or nothing if max_rounds is reached first.

The JavaScript code in these screenshots is also in the git repo that is linked at the end of the text.

Become what you Fear

As a shared resource, heap space must be supervised: Either by policy, by automation, or by accepting responsibility. In production systems, these three components – allocating space budgets, running garbage collection and handling cache liveness – together keep OOM out of the uptime statistics.

If the liveness management fails, accept the contract to be the garbage collector now. Find an example loiterer. Next, reach for the sharpest tool in the box: take OQL, trace the liveness in reverse, and corner the loiterer. Therein lies the fastest return to stability.

Addendum: Just another lie

It is easy to claim that the Operations team reported a Java heap dump in production. The truth is, that is very unlikely. Operations teams do not like heap dumps one tiny bit. Heap dumps are huge. Capturing them requires fast disks that can save gigabytes rapidly. But that fast spacious disk complicates dockerization and other VM deployment strategies.

Yet speed is of the essence; the Operations team is eager to bring up a new instance to replace the old instance that ran out of heap space.

Perhaps most vexing of all, the dump is a massive security risk. All those carefully injected secrets, handled by a vault or an encrypted store? Readable in plain text in the heap dump, their UTF-8 bytes there for the taking. Those certificates and private keys purposefully not stored on disk? After the dump they are … and nothing to protect them.