Memory Management Optimizations in HBase MemStore: SkipList, MemStoreLAB, ChunkPool, Off‑heap and CCSMap

Java memory management is a critical topic for large‑scale systems such as HBase, Flink and Spark, especially when the JVM heap is large and low latency is required. HBase’s MemStore consists of two major components: the native KeyValue storage and a ConcurrentSkipListMap that indexes these values.

SkipList‑based MemStore model

The basic MemStore implementation stores KeyValue objects in a ConcurrentSkipListMap , which provides O(log N) expected time for query, insert and delete operations. The JDK’s native implementation is ConcurrentSkipListMap (CSLM) and its underlying data structure is a skip list.

When a KeyValue is written, the JVM first allocates an object for the key/value pair and then calls ConcurrentSkipListMap.put(key, value) . This simple approach leads to high GC pressure because each write creates a separate object that quickly promotes to the old generation.

MemStoreLAB – batch allocation

To reduce per‑KV allocations, HBase introduces MemStoreLAB (MSLAB) . Instead of allocating a new object for each KeyValue , MSLAB pre‑allocates a 2 MiB Chunk and copies successive KeyValue instances into it. After copying, a lightweight Cell (implemented as ByteBufferChunkKeyValue ) points to the data inside the chunk, and only the Cell is inserted into the skip list. The original KeyValue objects become eligible for young‑generation GC.

Memory layout of ByteBufferChunkKeyValue :

protected final ByteBuffer buf;
protected final int offset;
protected final int length;
private long seqId = 0;

The size of a Cell is roughly 40 bytes, while a native KeyValue can be around 120 bytes, i.e., three times larger.

ChunkPool – reusable chunks

MSLAB still creates a new Chunk each time the current one fills. ChunkPool reuses freed chunks: after a MemStore flush, all its chunks are returned to a global pool managed by the RegionServer. Subsequent writes can obtain a chunk from the pool, reducing the frequency of heap allocations and easing young‑generation GC.

Off‑heap chunk allocation

Starting with HBase 2.x, chunks can be allocated off‑heap using ByteBuffer.allocateDirect . The configuration key hbase.regionserver.offheap.global.memstore.size enables a global off‑heap budget for all MemStores, allowing the system to keep large chunks outside the JVM heap.

Problems with the native CSLM

The JDK CSLM creates a separate Node object for each entry and an Index object for each level. The relevant source snippets are:

static final class Node<K,V> {
    final K key;
    volatile Object value;
    volatile Node<K,V> next;
    ...
}
static final class Index<K,V> {
    final Node<K,V> node;
    final Index<K,V> down;
    volatile Index<K,V> right;
    ...
}

For a workload of 50 M KV pairs, this results in roughly 62.5 M objects and about 2.5 GiB of memory solely for the skip‑list structure, dramatically increasing GC pressure.

CompactingMemStore – flattening the skip list

CompactingMemStore converts the CSLM‑based immutable segments into either a contiguous CellArrayImmutableSegment (simple array) or a CellChunkImmutableSegment (array stored in a large off‑heap chunk). This “flatten” step removes the heavy Node/Index objects, reduces fragmentation, and allows the memory to be managed more efficiently.

CCSMap – a compressed CSLM

Alibaba’s CCSMap (CompactedConcurrentSkipListMap) further compresses the CSLM by merging the Index information into the Node itself, resulting in a single‑object representation. Nodes are then stored sequentially in fixed‑size chunks, similar to MSLAB, and can be allocated off‑heap.

Memory savings example (50 M KV): CCSMap uses about 900 MiB versus 2.5 GiB for the original CSLM—a reduction of roughly 64 %.

Conclusion

The evolution of MemStore memory management shows that the key to performance is reducing per‑KV object creation and keeping data in large, contiguous memory regions (chunks). Techniques such as MemStoreLAB, ChunkPool, off‑heap allocation, CompactingMemStore and CCSMap collectively lower GC overhead, improve memory utilization and increase overall HBase throughput.