Memory Allocator¶

What it is¶

The memory allocator is the layer between the application and the operating system that manages heap memory. malloc(n) / new T finds a free block of at least n bytes; free(p) / delete p returns it. The OS only hands out memory in large units — pages, via brk/sbrk (grow the heap) or mmap (map anonymous pages) — and each of those is a system call costing ~1 µs or more. The allocator requests memory from the OS in large chunks and carves them into small blocks in user space, so most malloc calls cost tens of nanoseconds and no system call.

Memory obtained from the OS is only virtual until first written — see Virtual Memory and Page Faults.

Size classes and free lists¶

General-purpose allocators round each request up to a size class (for example 16, 32, 48, 64, 80, ... bytes, then coarser steps) and keep a free list per class. Allocating pops the head of the list; freeing pushes onto it. Both are O(1).

Internal fragmentation is the waste from rounding: a 33-byte request in a 48-byte class wastes 15 bytes. It is bounded and predictable.

External fragmentation is free memory that exists but is split into pieces that cannot satisfy a request, or spread across many partially used pages that cannot be returned to the OS. A long-running server that allocated 10 GB at peak, then freed 90% of the objects scattered across all pages, may still hold most of the 10 GB — every page keeps one live object. This is why resident memory (RSS) can stay high after the data shrinks, a common surprise in database processes.

Allocators you will meet¶

Switching a native (C or C++) storage engine such as RocksDB from glibc malloc to jemalloc often reduces memory usage noticeably for workloads with many threads and variable-sized allocations; RocksDB documentation recommends it. It can be done without code changes by linking against it or with LD_PRELOAD=libjemalloc.so.

Thread-local caching: the tcmalloc / Go design¶

The fast path touches only memory owned by the current thread (or CPU or, in Go, the current P), so it needs no lock. Batched refills and returns amortize the locking on the central lists. Go's allocator uses exactly these three tiers — mcache per P, mcentral per size class, mheap for spans and for allocations over 32 KB.

Arena allocation: what storage engines do on top¶

For data with a shared lifetime, a general-purpose allocator does unnecessary work: each object is tracked and freed individually even though all of them die together. An arena (also called a region or bump allocator) hands out memory by advancing a pointer through a large block, and frees everything at once when the arena is destroyed.

// Arena hands out byte ranges from large chunks. Entries are referenced
// by (chunk, offset), so whatever indexes them contains no pointers.
type Arena struct {
    chunks [][]byte
    cur    []byte
}

const chunkSize = 1 << 20

func (a *Arena) Alloc(n int) (chunk, off int) {
    if len(a.cur)+n > cap(a.cur) {
        a.cur = make([]byte, 0, max(chunkSize, n)) // one allocation per MiB
        a.chunks = append(a.chunks, a.cur)
    }
    off = len(a.cur)
    a.cur = a.cur[:off+n]
    a.chunks[len(a.chunks)-1] = a.cur
    return len(a.chunks) - 1, off
}

func (a *Arena) Bytes(chunk, off, n int) []byte { return a.chunks[chunk][off : off+n] }

// No Free: drop the whole Arena when its contents die together.

A memtable is the textbook case: millions of entries are inserted, none are freed individually, and the whole memtable is discarded after it is flushed to an SSTable. Measured in Go (Go 1.26.4, Apple M1 Pro): 2 million 64-byte entries, kept live, allocated either with one make each (references kept in a [][]byte) or from the arena above (references kept as pointer-free (chunk, offset) pairs):

Allocating from an arena:

• costs a few instructions instead of a call into the allocator,
• packs entries contiguously (better cache behavior),
• makes memory usage trivially measurable (the arena's size decides when the memtable is full),
• and, in a garbage-collected language, removes the entries from the collector's work: a []byte chunk contains no pointers, so marking it costs nothing, and 2 million objects become 2 heap objects per MiB — a 40x shorter collection in the measurement above.

The price is that nothing in the arena can be freed individually, and an arena that outlives its purpose holds all of its memory. LevelDB's memtable uses exactly this design; Pebble's arenaskl is the Go version. Why the engine in this handbook does not (yet) is in Memtable and Skip List.

Garbage-collected runtimes: Go¶

Go's GC is a concurrent tricolor mark-and-sweep: white (not yet seen), gray (seen, children not scanned), black (seen and scanned). When marking finishes, remaining white objects are unreachable and swept. Write barriers keep marking correct while the program keeps running; stop-the-world pauses are typically well under a millisecond. A GC cycle starts when the heap grows by GOGC percent (default 100) over the live heap after the last collection; GOMEMLIMIT sets a soft total limit. Go storage engines (Pebble, Badger) still use arena-like manual memory for block caches and memtables, to keep large data off the GC's scanning path.

Real-world usage: ValkeyDB uses sync.Pool for frequently-allocated command parser buffers to reduce GC pressure.

Measuring allocation¶

Details in Reducing Allocations and GC Pressure.

Common pitfall¶

Allocating many small objects in a hot path costs more than the allocator's own time. In Go every live allocation is also something the GC must mark, and allocation rate decides how often it runs, so a loop that allocates a small struct per iteration can show up as most of the CPU profile inside runtime.mallocgc, gcAssistAlloc, and GC background workers. The fix is to make allocation proportional to batches, not to items: reuse buffers (sync.Pool, or a buffer kept across iterations), store values instead of pointers, or allocate items with a shared lifetime from an arena.