 |
In-depth Software Development InformationTwitter: @ericjbrunoEmail: eric@ericbruno.com |
Eric J. Bruno
The Java garbage collector is one of the most sophisticated pieces of software ever shipped, and in most applications it is invisible. But invisible does not mean free. When you store millions of objects in a heap-based cache or an in-process data store, the GC must scan and collect all of them. GC pauses grow with heap size. In latency-sensitive systems, like trading engines, real-time analytics, gaming backends, those pauses are not a nuisance; they are outages.
The standard advice is to move to a smaller heap and let an external store (Redis, Memcached, RocksDB) hold the data. But that externalizes the cost instead of eliminating it: every lookup now crosses a network or a process boundary. The data is not in your address space, which means serialization, deserialization, and the overhead of a foreign API on every read.
NoHeapDB takes a different path. It keeps data in process, in the same JVM, but stores it completely outside the Java heap and without relying on JNI. The first version did this with ByteBuffer.allocateDirect(). The current version uses MemorySegment and Arena from Java's Foreign Function & Memory (FFM) API, final since Java 22. A store can live in memory or survive a restart as memory-mapped files. Either way, the GC never sees the stored data: Gigabytes of records run under an 8 MB heap.
That is not the same as "no GC activity", and finding out why was one of the more useful lessons of the project.
This article has three aims:
eric@ericbruno.comMemorySegment and Arena, relatively new Java features, and what changes when the storage layer is rebuilt on them, including a lock-free way for a reader to tell that a record changed or disappeared while it was looking at it.Note that this article follows one published years ago in Java Magazine and on my personal site, here., where the code and the article were all hand-written. I have since used Claude Code (Opus 5.5 Medium) to improve the performance, fix some bugs, and move to MemorySegment and Arena. Claude also helped me write this article, at my direction step-by-step, although I did all of the proofing and editing by hand myself.
The design has two layers: a journal and a hash index, both allocated off-heap (Figure 1). The journal is a sequence of variable-length records written back to back. The Java heap holds one NoHeapDB object as an anchor, a NoHeapDBStore object per store and any RecordViews. The journal chunks, the index and the free-list heads are off-heap.
Figure 1. What lives where. The heap holds a few objects per store and none per record. The records, the index and the free-list heads are all off-heap, and refer to records by location.
In the current version each record has a 16-byte header (Figure 2):
Byte 0: active flag (1 = live, 0 = inactive)
Byte 1: type tag (string, int, long, double, object, …)
Bytes 2–3: key length (2-byte; top bit set for a UTF-16 key)
Bytes 4–7: payload size (4-byte int)
Bytes 8–15: version stamp (8-byte long)
Bytes 16–N: the key, then the payload, padded together to a multiple of 8 bytes
The first version's header was 6 bytes: the active flag, the type tag and the size, and records held no key. The version stamp, the padding and the key arrived late in the project, for reasons covered later in this article.
Figure 2. A record's layout, and the same bytes once the record is removed: a new version stamp, no key, and a pointer to the next free record of its size.
Records are appended to the end of the journal on every write. When a record is deleted or overwritten, its active flag is set to 0 and it goes on a free list for its size. A later write of the same size, or a smaller one that leaves room for a trailing empty record, can reuse that slot instead of appending. For most of the project's life the free list was a TreeMap<Integer, LinkedList<Long>> on the heap; why that had to change, and how, is covered near the end of this article. Note that the size field means something different once a record is freed:
The hash index is a flat array of fixed-size buckets, also allocated off-heap. It maps string keys to their journal locations using open addressing with linear probing. Each bucket is 13 bytes:
Byte 0: occupied tag / key-length tag (doubles as a tiebreaker)
Bytes 1–4: key hashcode (4-byte int)
Bytes 5–12: record location (8-byte packed long)
The location field packs two values into one long: which chunk of the journal the record is in, and its byte offset within that chunk. How those bits are divided changed between versions, and the first division produced two of the worst bugs.
To look up a key (Figure 3), the engine hashes it, walks to the corresponding bucket, and reads the 8-byte location. It confirms the match by comparing the key stored in that record with the one it was asked for, and keeps probing if they differ. Then it reads the record's payload.
Figure 3. Looking up a key: hash to a bucket, probe until the tag and hashcode match, follow the packed location, and compare the key stored in the record.
The hash index being off-heap is the detail that most implementations miss. It is easy to store values off-heap but keep the index itself in a HashMap<String, Long>. That defeats the purpose: the index lives on the heap and the GC must trace it on every collection.
In NoHeapDB the index is a single block of native memory full of raw bytes, with no Java objects in it. The only Java objects are the reference to that memory and a few fields describing it. Hashcodes, offsets and flags are packed bytes, read and written in place. This means the GC's reachable object graph does not grow with the number of stored records. A store with 20 million entries has the same object graph as one with zero entries.
Java's ByteBuffer is indexed by int, so one buffer holds at most 2 GB. The first version capped each buffer at 1 GB (Integer.MAX_VALUE / 2) and represented the journal as a ByteBuffer[], adding a buffer whenever a write would overflow the current one.
The packed location carried the segment number in the low 32 bits and the offset within the segment in the high 32 bits:
// Packing (first version)
long value = (((long)offset) << 32) | (segment & 0xFFFFFFFFL);
// Unpacking (first version)
int offset = (int)(location >> 32);
int segment = (int)location;
ByteBuffer buffer = buffers[segment];
buffer.position(offset);
This encoding looks simple. It produced two critical bugs in the first implementation, and a third much later. The fix was mechanical: unpack the long correctly and use the segment to select the right buffer, as shown below.
long packed = getRecordOffset(key);
int segment = (int)(long) packed;
int recordOffset = (int)(packed >> 32);
buffers[segment].position(recordOffset);
buffers[segment].put(INACTIVE_RECORD);
The lesson: when you pack two values into one field, document it — and test both fields independently, not just the one you remember using first.
Until late in the project, each index entry stored a 4-byte hashcode and no key bytes (KEY_SIZE = 0). When two keys collide at the same bucket and linear probing places them in adjacent slots, findBucket() must be able to tell which slot belongs to which key. With only the hashcode to go on, it cannot — if two distinct keys happen to produce the same hashCode(), the second write overwrites the first key's index entry and the first key becomes unreachable.
Java's String.hashCode() is a 32-bit value. Collisions are rare but not impossible, For example, the pairs "Ea" and "FB" both produce hashcode 2236, and both are length 2. Without key bytes stored, they are indistinguishable in the index. The first thought was to store a key-length tag in the occupied byte (which would otherwise just be a 1-or-0 flag). Now two keys with the same hashcode but different lengths are correctly routed. This is cheap — the tag fits in the byte that was already there — and it eliminates the vast majority of observable collisions for typical key spaces.
The remaining risk is same-hashcode, same-length pairs. For random UUIDs as document IDs (all length 36), any one pair of keys collides with probability one in four billion. But n keys make about n ²/2 pairs, so the expected number of collisions is n ²/2³³. That is roughly 116 lost keys in a store of a million documents, not a rare event. Measurement agrees with the arithmetic. With 20 million random UUID keys, NoHeapDBTest read back 46,733 values belonging to some other key; the formula predicts about 46,600. A separate program that grouped the same 20 million keys by hashcode and length counted exactly 46,733 keys that a later key would overwrite. No read returned null, and no exception was thrown. Every one of those reads simply returned someone else's data.
The long-planned fix was to store the key's first 8 bytes in each entry. When it came time to implement it, a weakness showed: a prefix adds nothing for keys that share their first 8 bytes, and many do. Every URL starts with https://, and namespaced IDs start with something like customer:. Worse, collisions survive any shared prefix. String.hashCode() satisfies hash(p + t) = hash(p) × 31^len(t) + hash(t), so "https://example.com/items/Ea" and "https://example.com/items/FB" collide just as "Ea" and "FB" do, and agree on their first 26 bytes.
To resolve this, the 8 bytes held a fingerprint instead: a second, independent 64-bit hash over every character of the key.
// A 64-bit hash of every character of the key (FNV-1a, then the
// SplitMix64 finalizer), independent of String.hashCode(). Unlike the
// key's first bytes, it separates keys with a shared prefix such as
// "https://" or "customer:".
protected static long fingerprint(String key) {
long h = 0xCBF29CE484222325L;
for ( int i = 0; i < key.length(); i++ ) {
h ^= key.charAt(i); //XOR in the next char
h *= 0x100000001B3L; //64-bit FNV prime, 2⁴⁰ + 2⁸ + 0xB3
}
h = (h ^ (h >>> 30)) * 0xBF58476D1CE4E5B9L;
h = (h ^ (h >>> 27)) * 0x94D049BB133111EBL;
return h ^ (h >>> 31);
}
The constants aren't arbitrary. The first two are FNV-1a's 64-bit offset basis and prime; the last two, with the shifts, are the SplitMix64 finalizer, the same mixing function the JDK uses in SplittableRandom. FNV-1a alone mixes the key's last few characters only weakly into the high bits, and the finalizer makes every input bit affect every output bit.
An entry then matched a key only if the length tag, the hashcode and the fingerprint all matched:
} else if ( occupied == keyTag
&& index.get(INT, offset + HASH_OFFSET) == hashcode
&& index.get(LONG, offset + KEY_OFFSET) == fingerprint ) {
found = true;
This still wasn't a comparison of the actual key, which the index didn't hold. Two same-length keys would be confused only if they agreed on 96 bits of independent hash, about 1 in 2⁹⁶ per pair. Among 20 million keys, about 2 × 10¹⁴ pairs, the expected number of confusions is around 3 × 10⁻¹⁵.
The fix had costs. Index entries grew 62%, from 13 to 21 bytes, so 20 million keys needed a 1 GB index instead of 512 MB. And computing the fingerprint reads every character of the key. With 20 million UUID keys, writes dropped from 6.4 to 4.8 million per second and reads from 7.0 to 6.2 million. But every one of the 20 million values came back correct. With the short sequential keys, which never collided, the speed was unchanged within noise.
A fingerprint makes a wrong answer astronomically unlikely, but not impossible, and it left two other gaps. Nothing in the journal said which key a record belonged to, so the index couldn't be rebuilt from the journal, and there was no way to list the keys. All three point to the same change: store each key in its own record, between the header and the payload. The header's two padding bytes hold the key's length. A key whose characters all fit in a byte is stored one byte per character. Any other key is stored as UTF-16, two bytes per character, and the length's top bit indicates this.
The index entry goes back to 13 bytes (tag, hashcode, location), and a hashcode match is confirmed by comparing the key in the record. The comparison runs in place, with no String built from the stored bytes. For a one-byte-per-character key it compares one character at a time:
for ( int i = 0; i < length; i++ ) {
if ( (chunk.get(BYTE, at + i) & 0xFF) != key.charAt(i) ) {
return false;
}
}
The change brings one ordering rule. The index needs a record's key to find that record's entry, and freeing a record overwrites the start of its key with the free-list pointer. So an overwrite writes the new record and points the index at it before freeing the old one (Figure 5 shows the steps, and what a crash between them leaves), and a remove deletes the index entry before freeing the record. A value that needs the same space is still rewritten in place, since the key doesn't change.
20 M records, -Xmx32m |
Fingerprint, 21-byte entries | Key in record, 13-byte entries |
|---|---|---|
| Index size | 1 GB | 512 MB |
| Sequential keys: writes / reads per second | 6.1 M / 14.3 M | 7.9 M / 12.1 M |
| UUID keys: writes / reads per second | 4.7 M / 6.2 M | 4.5 M / 5.9 M |
| Wrong values | 0 | 0 |
Each configuration ran twice, on one machine, and the figures are the averages. Writes with short keys got faster: there is no fingerprint to compute, and the smaller index resized once instead of twice. Reads got slower, most with the short keys. Comparing eight characters at a time, packed into one 8-byte read, sped up UUID reads by only about 2% and left the short-key reads unchanged, so the simpler loop stayed. The comparison isn't what slows the short keys. More likely it is the records themselves: with a 10-to-12-character key added, these small records are a quarter to a half larger, so the same reads touch more memory. Storing keys trades some read speed on small records for exact matches, iterable keys, and an index that can always be rebuilt.
A hash table needs to grow and rehash when its load factor exceeds a threshold. Rehashing copies every live entry into a new, larger table, which is O(n) work. The question is, how much larger?
The original implementation grew the index by a fixed 100 MB on each expansion. For a store eventually holding 20 million entries at 13 bytes each (260 MB), the index expanded from its initial 256 MB through approximately 14 rehash cycles of 100 MB each to reach 1.6 GB. Each rehash was O(n) for the entries at that point. The total work was O(n/increment × n), effectively O(n²).
The fix I chose instead doubles the index size on each expansion. Standard amortized analysis applies: if you insert n total elements and the table doubles, the total rehash work across all expansions is n + n/2 + n/4 + … = 2n. The total work is O(n) regardless of how many expansions occur.
For a 4 GB store, the initial index (sized at 25% of the data store, clamped between 8 MB and 256 MB) holds about 20.6 million 13-byte entries. It doubles at 50% load, about 10.3 million entries, ending at 512 MB with 20 million records at 48% load. (For comparison, the 21-byte entries of the fingerprint version doubled twice and ended at 1 GB.)
Early versions of this article claimed that a 4 GB store ran under -Xmx32m "with no GC activity". It is a natural thing to believe: the data is off-heap, so the collector has nothing to do. To test it properly, I wrote NoHeapDBLargeDataTest. It loads 163,840 records of 64 KB each, 10 GB in all, with an 8 MB JVM heap. It then reads random records for 90 seconds, checking every byte of each one, with GC logging on.
The JVM heap never held more than 4 MB, and the 10 GB stayed off-heap. But in 90 seconds of reads the JVM ran 62,332 young-generation collections, about 690 per second. The data was off-heap. The values handed back to the caller were not. Measuring heap allocation per call with the JVM's per-thread allocation counter showed where it came from:
| Test application | NoHeapDB | |
|---|---|---|
| Per put | 66 KB | 131 KB |
Per get (getString) |
0.5 KB | 131 KB |
The GC counts came from running the test with -Xlog:gc, which logs every collection. The per-call figures came from a small probe program. HotSpot keeps a running count of the bytes each thread has allocated on the heap, and it is on by default, so nothing had to be turned on. Casting ManagementFactory.getThreadMXBean() to com.sun.management.ThreadMXBean gives access to it through getCurrentThreadAllocatedBytes(). The probe wrote 4,000 records of 64 KB to an in-memory store, then read them back in random order, reading the counter before and after each step. For a put, one difference covered building the key and value (the test application's share), and another covered the putString() call alone (NoHeapDB's share). Reads were split the same way. The table shows the averages per call. Because the counter belongs to the thread, the figures include no allocation by other threads, and they don't depend on when a collection happens to run.
Every getString() copied the 64 KB record into a new byte[], then decoded that into a second 64 KB array inside the String. Every put called String.getBytes() twice: once for the length, and again to write the bytes. With an 8 MB heap, each young collection had about 3 MB of short-lived garbage to clear, and at 15,500 reads per second that is 2 GB/s. All of those collections were cheap, between 0.1 and 0.5 ms, because nothing survived. The off-heap design was doing its job: no old-generation or full collections ever ran. But "zero-GC" was only true of the stored data.
Two changes fixed most of it. putVal() now encodes a String once. And a new read path, getView(key), returns a view of the record's bytes where they sit, with no copy. The same test then ran only 456 collections during the read phase instead of 62,332, and the average time inside the read call dropped from 12.6 µs to 0.8 µs.
A zero-copy view raises its own problem: the bytes it points at belong to the store, not the caller. That problem, and its solution below, come after the storage rewrite that made it possible.
MemorySegmentBy the end of the ByteBuffer version, the limits of the buffer API itself were showing:
ByteBuffer objects and their cleaners run. Every resize of the index left the old index waiting in the same way.ByteBuffer keeps a position, and nearly every read and write moved it. That is why "Defensive position() calls before every read" appeared among the lessons in the first version of this article. It also forced every read to take the store's write lock, so readers queued behind each other.-XX:MaxDirectMemorySize, which defaults to the maximum heap size. With an 8 MB heap, that is an 8 MB limit on a 10 GB store.Java 22 finalized the FFM API. Its MemorySegment is a bounded, 64-bit-addressed block of memory, and an Arena controls when that memory is freed. NoHeapDB's storage layer is now built on both.
Each store owns one shared arena for its journal. Each generation of the index gets its own arena, so a resize can free the old index the moment the new one is built:
// NoHeapDBStore: the journal's chunks all come from the store's arena
protected final void createMessageJournal() {
arena = Arena.ofShared();
long remaining = Math.max(totalSpace, MIN_CHUNK_SIZE);
while ( remaining > 0 ) {
long size = Math.max(Math.min(remaining, MAX_CHUNK_SIZE), MIN_CHUNK_SIZE);
addChunk(size);
remaining -= size;
}
tailChunk = 0;
tailOffset = 0;
}
Arena.ofShared() gives memory that any thread can read and write, and that is freed when the arena is closed. Two other arena types don't fit. Arena.global() never frees. Arena.ofAuto() frees when the GC decides to, which is the ByteBuffer behavior over again.
Deleting a store closes its arena:
@Override
public void delete() {
writeLock.lock();
try {
if ( closed ) {
return;
}
closed = true;
index.reset();
freeClasses.clear();
freeCount = 0;
chunks.clear();
arena.close();
OffHeap.released(journalBytes);
journalBytes = 0;
recordCount = 0;
}
finally {
writeLock.unlock();
}
}
After arena.close(), any access to a segment from that arena, including a slice someone else is still holding, throws IllegalStateException instead of reading freed memory. With ByteBuffer there was no way to revoke a buffer once it had been handed out.
A MemorySegment is addressed with long offsets, so one segment can be far larger than 2 GB. FFM has no in-place resize, though. Growing a single huge segment would mean allocating a bigger one and copying everything into it. So the journal is still a list of chunks, but each can now be up to 4 GB, and growth adds a chunk without copying:
// Moves the tail to the next chunk, allocating one if needed, so that a
// record of recordSize bytes fits at the tail
protected void advanceTail(long recordSize) {
if ( recordSize > MAX_CHUNK_SIZE ) {
throw new IllegalArgumentException("Record of " + recordSize
+ " bytes exceeds the maximum chunk size");
}
if ( tailChunk == chunks.size() - 1 ) { // last chunk
long last = chunks.get(tailChunk).byteSize();
long size = doublingExpansion
? Math.min(last * 2, MAX_CHUNK_SIZE)
: GROWTH_CHUNK_SIZE;
addChunk( Math.min(Math.max(size, recordSize), MAX_CHUNK_SIZE) );
}
tailChunk++;
tailOffset = 0;
}
The packed location now gives 16 bits to the chunk number and 48 bits to the offset, which is enough for 65,536 chunks of up to 256 TB each. The location still fits the index entry's 8-byte field, and packing and unpacking now happen in exactly one place each:
protected static final int OFFSET_BITS = 48;
protected static final long OFFSET_MASK = (1L << OFFSET_BITS) - 1;
protected static long pack(int chunk, long offset) {
return ((long) chunk << OFFSET_BITS) | offset;
}
protected static int chunkOf(long location) {
return (int) (location >>> OFFSET_BITS);
}
protected static long offsetOf(long location) {
return location & OFFSET_MASK;
}
The index no longer knows how locations are packed: HashBase.put() takes the packed long, and only the store unpacks it. A test writes 2.25 GB of 64 KB records into a single 3 GB chunk and reads every one back, to show the offsets past 2 GB work.
There was a side benefit. The previous ByteBuffer version allocated every buffer at the 1 GB page size, even for a store that asked for 100 MB. The document and graph layers create 100 MB stores, so one graph reserved about 4 GB across its four stores. Chunks are now sized to the request, and those stores allocate 100 MB each.
A MemorySegment has no position. Every read and write names its offset:
// putVal: the header and payload, written at absolute offsets
chunk.set(BYTE, offset, ACTIVE_RECORD);
chunk.set(BYTE, offset + 1, type);
chunk.set(INT, offset + Header.SIZE_OFFSET, datalen);
long data = offset + Header.HEADER_SIZE;
switch ( type ) {
case LONG_RECORD_TYPE:
chunk.set(LONG, data, (Long)val);
break;
// ...
case TEXT_RECORD_TYPE:
case BYTEARRAY_RECORD_TYPE:
MemorySegment.copy(bytes, 0, chunk, BYTE, data, datalen);
break;
}
BYTE, INT and LONG are value layouts that tell the segment how to read and write each type. NoHeapDB defines its own, and two details in those definitions matter:
// OffHeap: records and index entries are packed back to back, so fields
// are unaligned; and they stay big-endian, the ByteBuffer default
static final ValueLayout.OfInt INT = ValueLayout.JAVA_INT_UNALIGNED.withOrder(ByteOrder.BIG_ENDIAN);
static final ValueLayout.OfLong LONG = ValueLayout.JAVA_LONG_UNALIGNED.withOrder(ByteOrder.BIG_ENDIAN);
First, the plain JAVA_INT and JAVA_LONG layouts require their offsets to be aligned to the type's size. Records are packed at arbitrary byte offsets, so the store uses the _UNALIGNED variants. Second, ByteBuffer defaults to big-endian, but FFM layouts default to the platform's native order, which on x86 and Apple Silicon is little-endian. Without withOrder(BIG_ENDIAN), the rewrite would have silently changed the record format, and a persisted store written by one version would read as garbage in another.
Because no read moves shared state, readers no longer need the write lock. getValue(), getView() and iteration take the read lock and run in parallel; only writers take the write lock. The index made the same move: findBucket() and get() read at absolute offsets, so a lookup modifies nothing.
Before rewriting anything, I checked the FFM behaviors the design depended on with small programs on JDK 26. Two results were surprises:
| Behavior | Result |
|---|---|
A 3 GB Arena.ofShared().allocate() with -XX:MaxDirectMemorySize=100m |
Succeeds. Arena memory is not subject to the direct-memory cap. |
BufferPoolMXBean "direct" pool with 3 GB allocated from an arena |
Reports 0 MB. |
Native memory tracking (-XX:NativeMemoryTracking=summary) |
Shows 1 GB under "Other", then 0 KB right after arena.close(). |
| Process resident memory (RSS) after closing a 2 GB arena | Unchanged. The OS-specific allocator I tested with keeps the pages and reuses them for the next allocation of the same size. |
A slice, or its asByteBuffer(), read after close() |
IllegalStateException: Already closed |
The first two rows cut both ways. You no longer have to size -XX:MaxDirectMemorySize for your data. But the JVM no longer protects you from runaway growth, and the standard monitoring for direct memory doesn't see NoHeapDB at all. The store has to count for itself:
public final class OffHeap {
private static final AtomicLong allocated = new AtomicLong();
// Allocates zeroed, 8-byte-aligned memory from the arena and adds it to the total
static MemorySegment allocate(Arena arena, long bytes) {
MemorySegment segment = arena.allocate(bytes, Long.BYTES);
allocated.addAndGet(bytes);
return segment;
}
// Call after closing the arena that held these bytes
static void released(long bytes) {
allocated.addAndGet(-bytes);
}
// Off-heap bytes currently allocated by all NoHeapDB stores and indexes
public static long allocatedBytes() {
return allocated.get();
}
}
NoHeapDB.getTotalAllocatedBytes() and getAllocatedBytes(store) expose those totals, and the large-data test reports from them.
The RSS row is a reminder that "freed" has layers. When the arena closes, the JVM hands the memory back to the C allocator immediately; native memory tracking confirms it. Whether the allocator then returns it to the operating system is the platform's decision. On Linux, glibc normally serves allocations this large with mmap and returns them on free, but that should be measured on the deployment platform, not assumed.
On the 10 GB data / 8 MB-heap test, the MemorySegment build matched the ByteBuffer build on every measure, within run-to-run noise: 6.8 s versus 6.7 s to load, 24,880 versus 25,386 reads per second, 0.9 µs per read, and 457 versus 454 collections during reads. The rewrite was never meant to be faster. Its point was to remove the 2 GB ceiling, free memory deterministically, let readers run in parallel, and drop the JVM flag. It did all four without costing throughput, at least on this single-threaded test.
Parallel readers do raise read throughput, but less than you might hope. In a separate test that read 2 million small records with getString(), two threads read 6.8 million records per second, against 2.9 million for the old build, whose reads took the write lock. Beyond two threads, throughput fell again, to about 2.4 million records per second at eight threads for both builds. Every acquire and release of the read lock updates one shared counter inside ReentrantReadWriteLock, and with more threads, that counter becomes the bottleneck. When each thread read from its own store, and so used its own lock, eight threads read 22.9 million records per second. Potential fixes include optimistic reads that avoid the read lock altogether, but that's for another day.
The zero-copy getView() that fixed the GC problem returned a read-only ByteBuffer over the record's bytes in the journal. It was fast, but it handed the caller a pointer into memory the store still controlled. Three things could go wrong:
remove(key) puts the record's slot on the free list. A later put of a different key of a fitting size can land in that slot, and the old view then shows another key's data.Arenas don't solve the first two. An arena covers a whole chunk, and an arena per record would be absurdly expensive. What's needed is a way for each record to say "I am no longer the record you saw."
Each record header now carries an 8-byte version stamp. The store keeps a counter, changed only under its write lock, and stamps a new value into a header whenever the record is freed, and again whenever a slot is written. A view remembers the stamp it saw when it was created. If the stamp in the header no longer matches, the view is stale.
The stamp has to be read and written with memory-ordering guarantees, or a reader on another core could see the new payload bytes before the new stamp. The FFM API provides that through a var handle derived from a value layout:
// Record version stamps need acquire/release access, which the JVM
// only supports on aligned memory: this layout requires 8-byte alignment
static final ValueLayout.OfLong ALIGNED_LONG = ValueLayout.JAVA_LONG.withOrder(ByteOrder.BIG_ENDIAN);
static final VarHandle VERSION = ALIGNED_LONG.varHandle();
This is where the record format had to change. Acquire and release access through a MemorySegment var handle requires the field to be aligned. Every payload is padded to a multiple of 8, and chunks are allocated 8-byte aligned. Together they guarantee every header, and therefore every stamp, sits on an 8-byte boundary. The cost is 10 more header bytes per record plus up to 7 bytes of padding: a 64 KB record barely notices, but a 4-byte integer record grows from 10 bytes to 24.
Any write to a slot is preceded by a stamp change, ordered before it:
// putVal: the new version stamp first, ordered before every other write to
// this slot, so a view of a record that used the slot before sees the change
// before it can see new bytes
writeVersion(chunk, offset, ++versionCounter);
VarHandle.storeStoreFence();
// Then the rest of the header
chunk.set(BYTE, offset, ACTIVE_RECORD);
// ...
Freeing a record changes its stamp before anything else:
private void freeRecord(long location) {
MemorySegment chunk = chunks.get(chunkOf(location));
long offset = offsetOf(location);
long body = bodyCapacity(chunk, offset);
// A new version stamp first: any view of this record is now stale
writeVersion(chunk, offset, ++versionCounter);
chunk.set(BYTE, offset, INACTIVE_RECORD);
chunk.set(BYTE, offset + 1, EMPTY_RECORD_TYPE);
// A free record has no key: its size covers the whole body
chunk.set(SHORT, offset + Header.KEY_LENGTH_OFFSET, (short) 0);
chunk.set(INT, offset + Header.SIZE_OFFSET, (int) body);
storeEmptyRecord(location, body);
}
writeVersion is VERSION.setRelease(...) and readVersion is VERSION.getAcquire(...).
getView() now returns a RecordView. Every read through it follows the seqlock pattern (Figure 4): read the stamp, read the data, fence, then read the stamp again. The bytes are accepted only if both reads match the stamp the view was created with:
public <T> T read(Function<ByteBuffer, T> fn) {
try {
check(currentVersion());
T result = fn.apply(payload.asByteBuffer());
VarHandle.acquireFence();
check(currentVersion());
return result;
}
catch (StaleViewException e) {
throw e;
}
catch (IllegalStateException closed) {
throw new StaleViewException(key, closed);
}
}
The second check is what catches torn reads. Any writer that touched the slot while fn ran must have changed the stamp first, and the acquire fence ensures the payload reads complete before the stamp is read again. Readers take no lock and never block a writer.
Figure 4. A read through a RecordView. The writer changes the stamp before any other byte, and the reader checks it again after reading, so any overlap is caught.
StaleViewException extends IllegalStateException, the same type a closed arena throws. So callers handle a removed record, a reused slot and a deleted store in one place. status() tells an update of the same key (UPDATED) from a removal (REMOVED), and refresh() returns a view of the key's current value. The large-data test now verifies each 64 KB record inside a single read(fn), one pair of stamp checks per record rather than per byte.
A test of this kind is only meaningful if the failure it guards against really happens. The torn-read test runs one writer that rewrites a 64 KB record in place, alternating every byte between A and B. Four readers read it through fresh views, and any accepted read must be all As or all Bs.
With the version check in place, a 2-second run accepted 8,734 reads, rejected 3,005 as stale, and accepted no torn reads. To make sure the test wasn't simply too gentle to catch anything, I compiled a copy of RecordView with the check disabled and ran the same workload. It accepted 905 torn reads in 2 seconds. The race is real, and the stamp closes it.
On the 10 GB test, the version-stamped build again matched the earlier builds: 6.4 s to load, 24,720 reads per second, 1.0 µs per read, and 412 collections during the read phase.
The ByteBuffer version had a persisted mode that mostly woked, but it was made obsolete with the move to MemorySegment. The FFM rewrite made persistence a small change, because a mapped file is just another way to get a MemorySegment into an arena:
// OffHeap: maps the first `bytes` of a file read-write into the arena,
// growing the file (sparsely) if it is shorter
static MemorySegment map(Path path, long bytes, Arena arena) throws IOException {
try ( RandomAccessFile file = new RandomAccessFile(path.toFile(), "rw") ) {
if ( file.length() < bytes ) {
file.setLength(bytes);
}
MemorySegment segment = file.getChannel()
.map(FileChannel.MapMode.READ_WRITE, 0, bytes, arena);
mapped.addAndGet(bytes);
return segment;
}
}
The file is closed as soon as it is mapped; the mapping stays valid until the arena closes. Unlike FileChannel.map() returning a MappedByteBuffer, this version takes an arena, and the segment it returns can be larger than 2 GB. Closing the arena unmaps the file immediately. A MappedByteBuffer stays mapped until the GC collects it, which is why Java code has long resorted to calling internal cleaner methods to unmap files.
A persisted store maps each journal chunk as its own file (…journal0, …journal1, …), each starting with a 64-byte header: a version string, the creation time and the chunk number, plus, in the first chunk, a flag that says whether the store was closed cleanly. The header is 64 bytes, not something smaller, so the first record still starts on an 8-byte boundary, as the version stamps require. The record code didn't change at all: a chunk is a MemorySegment whether it came from Arena.allocate() or from a file. The only branch is in addChunk():
if ( inMemory ) {
chunks.add( OffHeap.allocate(arena, size) );
}
else {
int number = chunks.size();
Files.deleteIfExists(chunkPath(number)); // a new chunk starts zeroed
MemorySegment chunk = OffHeap.map(chunkPath(number), size, arena);
writeChunkHeader(chunk, number);
chunks.add(chunk);
}
Reopening a store maps its files back, then walks every record to rebuild what isn't saved in its files: the record count, the free lists, the write position, and the version counter, which must resume above the highest stamp on disk or a new record could reuse an old view's version. If the store wasn't closed cleanly, the same walk also rebuilds the index from the keys in the records:
for ( int c = 0; c < chunks.size(); c++ ) {
MemorySegment chunk = chunks.get(c);
long offset = dataStart;
while ( offset + Header.HEADER_SIZE <= chunk.byteSize() ) {
byte type = chunk.get(BYTE, offset + 1);
if ( type == 0 ) {
break; // zeroed memory: end of records in this chunk
}
long body = bodyCapacity(chunk, offset);
maxVersion = Math.max(maxVersion, readVersion(chunk, offset));
if ( chunk.get(BYTE, offset) != ACTIVE_RECORD ) {
storeEmptyRecord(pack(c, offset), body);
}
else if ( rebuildIndex ) {
recoverRecord(pack(c, offset));
}
else {
recordCount++;
}
offset += Header.HEADER_SIZE + body;
}
if ( offset > dataStart ) {
tailChunk = c;
tailOffset = offset;
}
}
versionCounter = Math.max(versionCounter, maxVersion);
closeStore() calls force() on every mapped segment, then closes the arena; the files stay. deleteStore() closes the arena and deletes them. The index grows the same way it does in memory, with one change from the old code. The old code extended the index file in place and then rehashed from the old mapping into the new one, which covered the same bytes. The new code rehashes into a separate file and renames it over the old one, so a crash mid-resize leaves the old index intact.
A process that dies without closing its store loses nothing it wrote, because the operating system still owns a mapped file's dirty pages after the process exits, and writes them out on its own schedule. But the index file could then be out of step with the journal: an entry written, a record not, or the reverse. The clean flag handles that. Opening a store clears the flag and forces that one header to disk; closeStore() forces the journal and the index, and only then sets the flag. A store that opens with the flag clear, or with no index file at all, discards its index file and rebuilds the index during the scan. One more case needs care, shown in Figure 5. A crash partway through an overwrite can leave both the old and the new record of a key marked live. The version stamps settle it: the higher stamp is the newer record, and the other is freed.
private void recoverRecord(long location) {
MemorySegment chunk = chunks.get(chunkOf(location));
long offset = offsetOf(location);
String key = readKey(chunk, offset);
long other = index.get(key);
if ( other == -1L ) {
index.put(key, location);
recordCount++;
}
else if ( readVersion(chunk, offset)
> readVersion(chunks.get(chunkOf(other)), offsetOf(other)) ) {
index.put(key, location); // matches other's key, still intact
freeRecord(other);
}
else {
freeRecord(location);
}
}
Figure 5. The order of an overwrite, and what a reopen finds if the process died at each point. The version stamps settle the one ambiguous case.
The tests check each path. In one process, a store is written across two chunk files, partly removed and overwritten, closed, and reopened by a fresh NoHeapDB; every value, type, removal and the record count survive, and the index file is used as is. A store that is never closed, with an overwrite left half-done by hand, reopens with its index rebuilt, every key correct, and the newer record of the duplicated key kept. So does a store whose index file was deleted. Across processes, a writer stores 500,000 records, removes and updates some, and stops through Runtime.halt(), with no shutdown hooks and no flush; a new JVM rebuilds the index and reads back all 450,000 surviving records correctly. Rebuilding costs little: a store of 10 million small records reopened in 0.12 s after a clean close and in 0.65 s with a rebuild.
What this doesn't cover is a machine crash or power loss. There is no write-ahead log, and force() runs only on close, so writes the operating system hadn't yet written out are lost. And a record caught half-written by the power failing can't be detected, because records carry no checksum.
On the 10 GB test, a persisted store loaded in 6.5 s, the same as in memory. Closing it, which flushed 11 GB of mapped files, took 2.0 s, and reopening and scanning 163,840 records took 0.9 s. Reads then ran at 23,403 per second with 0.9 µs per read and 389 young collections, against 24,720, 1.0 µs and 412 in memory. One caveat on those reads: the files were still in the operating system's page cache when the store reopened. A reopen after a reboot would read the data from disk, and would be slower until the pages it touches are cached again.
With the data and the index off the heap, one structure still grew with the store. The free list was a TreeMap<Integer, LinkedList<Long>>, and every freed record added a list node and a boxed Long to the heap. A record left the list only when a later write of a fitting size reused it. The 10 GB test only writes and reads, so it never noticed. A workload that deletes and updates would.
To measure it, NoHeapDBChurnTest loads a million records of random sizes between 16 bytes and 2 KB under an 8 MB heap. It then removes, updates and re-adds random keys for 30 seconds, deletes three keys in every four, and checks every remaining value through a view. With the on-heap free list, the run never got out of the churn phase. Two seconds in, with 74,000 free records, the live heap after collection had grown from 2.8 MB to 6.1 MB, about 45 bytes per free record. The collector fell back to 509 full collections, and then the JVM threw OutOfMemoryError.
The fix is an old one from memory allocators: keep the list in the free memory itself (Figure 6). A free record's payload is dead space, so it holds the packed location of the next free record in the same size class. The only state outside the journal is a table of list heads, one location per class, allocated in the store's arena:
// Pushes a free record onto its size class's list, writing the old head
// into the record's payload as its next pointer
protected void storeEmptyRecord(long location, long capacity) {
int cls = freeClass(capacity);
long head = cls * (long) Long.BYTES;
MemorySegment chunk = chunks.get(chunkOf(location));
chunk.set(LONG, offsetOf(location) + Header.HEADER_SIZE, freeHeads.get(LONG, head));
freeHeads.set(LONG, head, location);
freeClasses.set(cls);
freeCount++;
}
Up to 4 KB there is one class per payload capacity, in 8-byte steps; above that, one per power of two. That makes 531 heads, 4,248 bytes, the same for a store of any size. A BitSet of the same fixed size marks the non-empty classes, so finding a slot is a jump to the next set bit rather than a walk through every size, which the old code did whenever there was no exact match. Only the head of each list is examined. In a class below 4 KB every record has the same capacity, so the head fits exactly or not at all. In a larger class a record further down might fit when the head doesn't, but finding it would mean following pointers through dead records scattered across the store.
Figure 6. The free lists live in the free records themselves. The only other state is the 4,248-byte table of heads and a fixed-size BitSet.
Three details mattered:
What it doesn't do is merge neighboring free records. Doing that needs a doubly linked list or boundary tags, so fragmentation is the same as before.
| 1 M keys, 16 B–2 KB values, 8 MB heap | On-heap free list | Off-heap free lists |
|---|---|---|
| Outcome | OutOfMemoryError 2 s into the churn |
Completed all phases |
| Operations | more than 1.26 million | 38.7 million |
| Free records tracked | 74,000 at failure | up to 813,000 |
| Live heap after GC | 2.8 MB, rising to 6.1 MB | 2.76 MB throughout |
| Full collections | 509 | 0 |
| Wrong values in the final check | — | 0 of 187,880 |
The off-heap memory also stayed at the same 1,344 MB from the end of the load to the end of the run. Through 37 million deletes, updates and re-adds, every write found room in a free slot or at the end of an existing chunk, and the journal never grew.
The microbenchmarks in the test suite, on in-memory stores of a few thousand to 100,000 records, run in the millions of operations per second: roughly 11–17 million per second for 64-byte strings, integers and longs, 3–5 million for 4 KB strings, and about 10 million writes and reads per second in the 100,000-record stress test. Individual runs of these short benchmarks vary considerably.
The large-data test is the more useful measure, because it shows what happens to the heap:
| 10 GB, 8 MB heap, 90 s of reads | First version (ByteBuffer, getString) |
Current (MemorySegment, RecordView) |
|---|---|---|
| Load time | 7.9 s | 6.4 s |
| Reads per second | 15,583 | 24,720 |
| Time in the read call | 12.6 µs | 1.0 µs |
| Young collections during reads | 62,332 | 412 |
| GC pause, median / 99.9th percentile | 0.08 / 0.17 ms | 0.08 / 0.21 ms |
| Old-generation or full collections | 0 | 0 |
| Peak heap used | 2.8 MB | 3.9 MB |
All runs were on one laptop with the JDK 26 runtime and G1. Each configuration ran once, so differences of a few percent are noise. Across all six runs, two had a single young-collection outlier, of 3.5 ms and 9.1 ms. Each did the same amount of work as its sub-0.2 ms neighbors, which points at the operating system rather than the collector. The current read rate is limited by the test comparing all 64 KB of every record, not by the store.
The read/write asymmetry in the small-record benchmarks comes from write-path work the read path skips: the free-list search, the index load check, and the potential rehash. The read path is a hash lookup followed by a read at a known offset.
With a reliable key-value store underneath, the document and graph layers follow naturally.
NoHeapCollection maps string document IDs to serialized Document objects stored in the key-value layer. Secondary indexes are additional key-value stores where the key is a field value and the stored value is a list of matching document IDs. A find("lastName", "Smith") is two lookups: one into the secondary index to get the ID list, then one per ID into the primary store.
HybridDB db = new HybridDB();
NoHeapCollection clients = db.createCollection("clients");
clients.createIndex("lastName");
String id = clients.insert(Document.create()
.set("firstName", "Alice")
.set("lastName", "Smith")
.set("balance", 12500.00));
List<Document> smiths = clients.find("lastName", "Smith"); // O(1) via index
NoHeapGraph stores nodes and edges as documents and maintains an adjacency index per node. BFS, DFS, and shortest-path traversal are iterative (not recursive) to avoid stack overflow on large graphs.
Both layers inherit the off-heap property of the underlying store: nodes, edges, and documents all live off-heap. The heap holds the thin Java wrapper classes, the collections used for traversal bookkeeping during a single query, and the objects each read returns. Neither layer needed a single change for the MemorySegment rewrite.
Nineteen bugs in a small implementation might seem like a lot. It is not — it is typical for low-level systems code written without the safety nets that higher-level abstractions provide. The value is in understanding why they appeared.
Bit-packing is a hazard surface. The packed location accounted for two critical bugs in the first draft and a third much later, after a fix for a crash quietly assumed one of the two fields was always zero. The MemorySegment version keeps packing and unpacking in three small functions, and nothing else touches the bits.
Shared mutable position is a design flaw, not a coding hazard. The first version of this article recommended defensive position() calls before every read. That treats the symptom. ByteBuffer's cursor made every read a write to shared state, which caused bugs and forced readers to serialize. Moving to absolute offsets removed both problems at once.
Open-addressing has exactly one non-obvious rule (tombstones), and it will bite you. Every developer who has implemented open addressing from scratch has gotten the deletion case wrong at least once. The first lesson is that whatever byte marks a slot as empty or deleted must be impossible to produce from real data.
Off-by-one errors in buffer loops are catastrophic. A <= instead of < in a rehash loop throws away your entire index. Fuzz tests over the range boundary (exactly at capacity, one under, one over) would have caught Bug 7 immediately.
Silence is the enemy. The most dangerous bugs here — the no-op remove, the wrong-record read, the overwrite leak, the cross-segment slot reuse — produced no exceptions. They returned incorrect values or corrupt state while reporting success. A stale view that throws is the same lesson applied to the API: make the wrong outcome loud.
"Off-heap" is not "allocation-free". Keeping the data off-heap keeps the collector's work small. It doesn't stop the API from allocating on every call. Measure allocation per operation, not just heap size. And look for the bookkeeping: a structure that grows with the data, like a free list, is data too, even if it only holds locations.
A test that only checks for null can't see a wrong answer. The original 20-million-record test reported "0 failed gets" because it counted only null results. A hash collision returns a value, just the wrong one. Check what comes back, not only that something did.
Verify the platform's promises. The FFM API changed what the JVM counts, limits, and frees, in ways the documentation doesn't put in front of you. A few minutes with a probe program found that -XX:MaxDirectMemorySize no longer applies, that the standard memory statistics go blind, and that "freed" stops at the C allocator on the OS. Each of those changed the design.
The implementation passes all available tests, including the two collision tests that failed until the fingerprint fix. The 10 GB test produces zero failed or mismatched reads, in memory and persisted, and the churn test keeps a flat heap through tens of millions of deletes and updates.
Immediate next steps:
force() points, and a checksum in each record, would close both. Measuring a cold reopen, after the page cache is gone, belongs here too.find(age > 30) require a full scan. A sorted secondary structure (B-tree or skip list, also off-heap) would support range predicates efficiently.The code is available at github.com/…/NoHeapDB under an open-source license.
Building an off-heap database in Java is not principally a research problem. It is an engineering problem with a clear solution (native memory, open addressing, a journal) and a long list of implementation hazards that are easy to describe and surprisingly easy to get wrong.
The FFM API changes the shape of the problem more than its difficulty. MemorySegment removes the 2 GB ceiling and the shared cursor that caused so many of the first version's bugs. Arena turns "freed eventually" into "freed now", for allocated memory and mapped files alike, which made the long-unfinished persisted mode a small change. And a closed arena, like a stale version stamp, fails loudly instead of returning someone else's bytes. In exchange, you take on accounting the JVM used to do, and alignment rules the old API hid.
The mitigation is not cleverness. It is the same thing it always is in systems programming: boundary tests, explicit state invariants, measurements that check your assumptions, and a healthy suspicion of any code that packs multiple values into a single field.
The payoff is a store that holds gigabytes (or more!) of data behind an incredibly small Java heap. Its reads return in about a microsecond without copying, never return bytes from a record that has since changed, and leave the garbage collector almost nothing to do. That is worth the engineering discipline it takes to get there.
The complete source code, tests and diagrams are on GitHub at github.com/ericjbruno/NoHeapDB, under the Apache License 2.0.
Eric Bruno is a software architect and author. He has written about Java performance, concurrency, and systems programming for Java Magazine, Dr. Dobb's Journal, JavaWorld, and others. He can be reached at eric@ericbruno.com.