Big data frameworks written in Java hold more data than fits in memory, so they push the excess onto a fast disk — which means converting objects into bytes on the way out and rebuilding them on the way back, and reloading them into a heap already too full, with the result that garbage collection and that conversion can consume 87 percent of the run; this paper (FORTH, Crete, ANU and Red Hat) gives the runtime a second heap on the disk holding real objects rather than bytes, and then does the hard part — teaching the collector to treat that heap as live without ever walking it.
The argument in one glance
-
Problem
The data is much larger than the heap, and it does not die
Analytics frameworks iterate over a dataset until something converges, and each pass creates a new set of objects derived from the last. The volume allocated over a run is several times the heap, and the objects live a long time, because a later iteration will want them. A garbage collector is built on the opposite assumption — that most objects die young — so it runs often and reclaims little each time, and the program spends its life collecting.
-
What people did
Move the excess out of the heap onto a fast device
Every framework in this space does the same thing. Take the data the collector is struggling with, convert it into a flat sequence of bytes, and store it outside the heap on an NVMe device. The heap shrinks back to a size the collector can manage, and the dataset can be far larger than memory. This is standard practice, not a research proposal.
-
Why it fell short
It swaps one cost for two
Flattening an object means walking its reference graph and writing out a self-contained copy, and rebuilding it means the reverse — expensive for the complex structures these frameworks actually use. Worse, nothing can be computed in that form, so every time the framework needs the data it reconstructs the objects back onto the heap that was already too full. Measured together, collection and conversion reach 87 percent of execution time.
-
This paper's idea
Put a second heap on the device, and forbid the collector to enter it
This paper (Kolokasis, Evdorou, Akram, Kozanitis, Papagiannis, Zakkak, Pratikakis and Bilas) extends the Java runtime with a second heap mapped over the device that holds ordinary objects, so the framework computes on them directly with no conversion at all. The difficulty is entirely in the collector — it must keep the illusion of one heap while never traversing the second one, which means tracking references in both directions by other means.
Why this problem is worth solving
Two costs are being attacked and it is worth being precise about each.
SERIALIZATION
turns a live object into a flat sequence of bytes that can be stored outside the heap. It
is not a memory copy, because an object is a node in a graph — it holds references to other
objects, which hold references in turn. The serializer must walk that graph from the chosen
root and write out everything reachable, then reconstruct all of it and all the references
on the way back. This has three consequences. It is expensive in proportion to how complex
the structure is, which is why frameworks using rich object graphs suffer most. It restricts
what can be moved, since the thing being written out has to be self-contained, with no
references crossing into or out of the heap. And nothing can be computed on the result while
it is in that form, so the data must be reconstructed before it can be touched — which puts
it back on the heap the whole exercise was meant to relieve.
The harder half is why the obvious alternative fails.
A
runtime can already map its heap over a storage device, and doing so would give direct access
to objects without conversion. Collection is what breaks. Liveness analysis is a traversal of
the object graph — follow a reference, look at what it points to, follow its references — and
the addresses it visits have no relationship to each other, so the accesses are effectively
random. Against memory that is merely slow; against a device that transfers whole pages, each
followed reference risks pulling in four kilobytes to read a few bytes, and may fault. Then
compaction, which moves live objects together to reclaim space, becomes a stream of
read-modify-write operations against storage. The traversal and the compaction are both
fundamental to how collectors work and both are exactly the wrong access pattern.
What people did before, and where it broke
-
Serialize to an off-heap store. What Spark and Giraph do today. Convert long-lived data to bytes, keep it on an NVMe device, bring it back when needed. It is general, it works, and it lets these frameworks handle datasets far past memory.
-
The gap. Conversion cost in both directions, and the data returns to the crowded heap to be used. In the measurements here, collection and conversion together reach 87 percent of execution time.
-
Compute directly on flat bytes. Some systems avoid reconstruction by operating on the serialized form, keeping data as arrays of primitives.
-
The gap. It only works for simple layouts. Arbitrary object graphs cannot be handled, so this becomes a per-application special case rather than something the framework can apply to whatever the user wrote.
-
Swap cold memory to a device transparently. Let the operating system move rarely used pages out to fast storage, which gives direct access with no conversion and needs no changes to the framework at all.
-
The gap. The collector still walks whatever it can reach. Pages that were swapped out get dragged back in by liveness analysis rather than by the program, so the traversal cost remains even though the conversion cost is gone.
-
Split the heap across fast and slow memory. A specialised collector places long-lived objects in the slower tier and keeps young ones in memory, so the heap can grow past what memory holds.
-
The gap. Every major collection still scans the whole old generation, so the cost grows with the address space. Compared here directly, this paper is 7 to 69 percent faster, and it drives far fewer accesses to the slow tier.
How a second heap can exist without being collected
From a framework hint to a region reclaimed in bulk
-
-
new
-
new
-
new
-
new
-
new
The idea
The framework already knows which objects are the problem. This is the observation that makes the rest tractable. A garbage collector has to infer everything about lifetimes, but the framework does not have to infer — it has an explicit notion of which data is long-lived and reused across stages, because that is precisely the data it was already choosing to push off the heap. So the interface is two calls. Tag a root object with a label, and later ask for everything with that label to be moved. The runtime computes the reachable set from those roots at the next major collection and relocates it. Groups sharing a label go into the same region, on the empirical basis that objects reachable from one root tend to die together. A safety valve handles the case where the heap fills before the framework asks, moving marked objects early under pressure. Taking a placement decision that a runtime would have to guess at and letting the layer that knows simply declare it is the same division of labour as the warehouse-scale memory tiering work covered elsewhere on this site, which arrives at the opposite answer by inferring coldness from observed access rather than being told.
Fencing the collector means replacing traversal with bookkeeping. A collector proves an object live by reaching it. If it may not enter the second heap, both directions of reference need another mechanism. Forward references, from the ordinary heap into the second, are handled by a range check — when the traversal meets one it does not follow it, it sets a live bit on the target region and stops. Since regions may reference each other, each keeps a dependency list, so marking one region live propagates to the regions it depends on, about ten per region on average here. Backward references, from the second heap into the ordinary one, are the harder direction, because those first-heap objects must survive and the collector cannot scan the second heap to find out which. They are recorded in a card table, a coarse map marking which chunks contain such references, and the card size is enlarged to keep it small. This is the reason a transparent swapping scheme cannot solve the problem — as the memory offloading work covered elsewhere on this site shows, moving cold pages to a device is straightforward, but nothing stops a collector from reaching them and dragging them back.
Reclaim lazily, because compaction on a device is unaffordable. Region-based heaps normally free space eagerly, evacuating the live objects out of a region so it can be reused. That is right when regions live in memory and wrong when they live on storage, where moving objects means read-modify-write traffic. The paper takes the other branch — never compact the second heap, and free a region only when nothing points into it, accepting that one surviving object keeps a whole region alive. The device capacity is what makes that affordable. The measurements are honest about the consequences: on two graph workloads only 28 and 6 percent of regions are ever reclaimed, because large dead arrays sit in regions kept alive by a few live objects, though internal waste stays between 1 and 3 percent because allocation is append-only. Trading space for the elimination of an access pattern the hardware handles badly is the same reasoning that shows up repeatedly in the runtime measurement work covered elsewhere on this site, where the real cost of collection turns out to be much larger than the numbers usually reported.
Following one cached dataset onto the device
How a Spark dataset moves to the second heap and is eventually freed
Following one group of cached objects from the framework hint to bulk reclamation.
Step 1 of 5
The framework marks a root and asks for the move
When the application caches an intermediate result, the framework tags that partition's root object with a label. Later, when the group is complete and no longer being mutated, it asks for everything with that label to move.
Waiting matters. Moving objects that are still being updated would mean writing to the device repeatedly. But waiting too long risks the heap filling first, so a pressure threshold moves marked objects early if the ordinary heap gets tight before the request arrives.
Why it works
- A hint replaces an inference the runtime cannot make well. The framework declares which object group is long-lived → the collector does not have to discover it from lifetimes → the set moved is exactly the set the framework would have serialized anyway, chosen by the layer that knows.
- Direct access removes conversion in both directions. Objects on the device stay objects, reachable through ordinary memory mapping → nothing is flattened on the way out or rebuilt on the way in → serialization cost falls by up to 93 percent on the Spark workloads that used complex structures.
- Fencing the traversal removes the device from the collection path. A range check turns a reference into a mark on a region instead of a page fetch → the collector never reads the device during liveness analysis → in one graph workload it avoids following about 109 million forward references per collection.
- Bulk reclamation avoids the access pattern storage handles worst. Freeing a whole region by resetting a pointer instead of evacuating live objects → no read-modify-write traffic on the device → the cost is that one live object holds a region, which is why only 6 percent of regions are reclaimed in the worst workload.
- Coarse cards keep the backward-reference map affordable. Enlarging card segments from 512 bytes to 16 kilobytes → a much smaller table to scan each minor collection → 64 percent less minor collection time on average, though scanning a dirty card gets more expensive, which costs 5 times more on the workload that mutates the second heap most.
What it costs (trade-offs and scope)
- Space is traded for the absence of compaction. Regions are freed only when entirely unreferenced, so one live object can pin a whole region. On two of the graph workloads this leaves most regions unreclaimed for the duration of the run.
- The framework must be modified, and modified thoughtfully. The hints are not automatic. Someone has to decide which roots to tag and when to request the move, and requesting too early means writing objects that are still changing while too late risks exhausting the heap.
- Card size is a workload-dependent tuning knob. Bigger cards make the table cheap to scan and each dirty card expensive to process. The right choice differs between a framework holding immutable results and one mutating objects in place.
- This is a specific collector in a specific runtime. The implementation extends one throughput collector in OpenJDK, along with the interpreter and both compilers. Nothing here transfers automatically to a concurrent or region-based collector.
- Some workloads become device-bandwidth bound. Three machine-learning workloads stream through cached data every iteration with no locality, reaching the device’s peak read throughput and spending up to 43 percent more time outside collection than the serialized baseline.
The evaluation
| Property | What was measured | The result | What it tells you |
|---|---|---|---|
| Speed at the same memory size | |||
| Memory needed for the same speed | |||
| Against a hybrid-memory collector | |||
| Where collection time goes now | |||
| How much of the second heap is ever reclaimed |
Check yourself
Check your understanding
1. Why does simply mapping the whole managed heap over a fast storage device not solve this problem?
2. The collector may not enter the second heap. How does it still establish that a region is live?
3. Why does the design never compact the second heap, even though that means one live object can keep a whole region alive?
4. Predict what happens if the card segments used to track references from the second heap back into the first are made much larger.
Sources
TeraHeap: Reducing Memory Pressure in Managed Big Data Frameworks. Iacovos G. Kolokasis, Giannos Evdorou, Shoaib Akram, Christos Kozanitis, Anastasios Papagiannis, Foivos S. Zakkak, Polyvios Pratikakis, Angelos Bilas. ASPLOS 2023, Volume 3, pages 694 to 709. DOI 10.1145/3582016.3582045. Full text read from the authors’ copy hosted at the third author’s academic page.