Reading LevelDB: The Arena Region Allocator

While tracing MemTable’s deleted copy-control (= delete in db/memtable.h) I kept falling through layers until I hit the memory floor underneath it all: Arena. It is a small, single-purpose allocator, and almost every design decision in it is a direct answer to one question — what does MemTable’s skip list actually need from memory?

This article walks through util/arena.h and util/arena.cc and explains not just what the code does but why the constants and ordering choices are what they are.

1. What Arena is

Arena (util/arena.h:16) is a bump allocator (pointer-bump region allocator):

• it allocates big blocks of memory up front;
• an allocation is just moving a pointer — O(1), lock-free, no system call;
• all memory is released in one shot when the Arena is destroyed.

It exists to give MemTable’s skip-list nodes a high-performance memory home. The fit is exact: skip-list nodes are allocated constantly but never freed individually (a node, once inserted, is never deleted until the whole MemTable is destroyed), so there is simply no need for a general-purpose heap’s per-node free.

2. Core members (arena.h)

Member	Type	Role
blocks_	std::vector<char*>	all blocks owned; default kBlockSize = 4096
alloc_ptr_	char*	allocation cursor in the current block
alloc_bytes_remaining_	size_t	free bytes left in the current block
memory_usage_	std::atomic<size_t>	bytes-used counter (the only atomic member)

The destructor ~Arena walks blocks_ and delete[]s each one — that is the “release in one shot” model.

3. Two allocation paths

Fast path — Allocate (arena.h:55-67)

if (bytes <= alloc_bytes_remaining_) {   // fits in current block?
    char* result = alloc_ptr_;
    alloc_ptr_ += bytes;
    alloc_bytes_remaining_ -= bytes;
    return result;
}
return AllocateFallback(bytes);          // no → open a new block

The vast majority of small allocations are satisfied here; the hot path is extremely cheap.

Slow path — AllocateFallback (arena.cc:20-36)

Triggered when the current block cannot hold bytes. Two strategies:

• Strategy A (small object, bytes <= kBlockSize/4): open a fresh full kBlockSize (4 KB) block as the current block and cut bytes out of it. Cost: the leftover alloc_bytes_remaining_ in the old block is discarded. Benefit: the new block still has room, only one new, good locality.
• Strategy B (large object, bytes > kBlockSize/4): use AllocateNewBlock(bytes) to open a block sized exactly bytes and return it, without making it the current block. Cost: one extra new. Benefit: the old block’s remainder is preserved, and no half-full new block is created.

AllocateNewBlock (arena.cc:58-64) is where the real new char[] happens and where memory_usage_ is bumped atomically.

4. The key derivation: what the 1/4 threshold really bounds

When AllocateFallback fires (current block could not hold bytes), the leftover alloc_bytes_remaining_ in the old block is dropped — that is the only genuinely wasted space at runtime.

Strict upper bound on the fragment discarded per block switch:

alloc_bytes_remaining_ < bytes        (if it fit, we'd never reach fallback)
bytes <= kBlockSize/4                  (only Strategy A discards the old block)
⇒  waste = alloc_bytes_remaining_ < kBlockSize/4

So the fragment thrown away on every block switch is strictly less than one quarter of a block.

Three object-size classes fall out of this:

• > 1/4 block: Strategy B, dedicated block, zero waste in the main block.
• == 1/4 block: Strategy A, four objects exactly tile one 4 KB block, no imperfection.
• < 1/4 block: Strategy A, may open a new block, old remainder discarded — but the discarded amount is < 1/4 block.

Why 1/4 and not something else

The core tension is internal fragmentation vs. allocation overhead:

• Threshold too high (e.g. 1/2) → midsize objects also take Strategy B, spawning many scattered small new blocks; blocks_ bloats and locality degrades.
• Threshold too low (e.g. 1/16) → slightly-larger objects still get stuffed into a whole 4 KB block, leaving 3 KB+ that will most likely never be used → severe waste.

1/4 is an empirical heuristic tuned for LevelDB’s workload (small nodes dominant, occasional large values). The comment states the intent plainly: “avoid wasting too much space in leftover bytes”.

Concrete numbers: kBlockSize = 4096, 4096/4 = 1024 bytes = 1 KB. The threshold is written as the expression kBlockSize/4, so it scales automatically with kBlockSize; 4096 is divisible by 4, so there is no integer-division precision loss.

Two footnotes

1. Tiny alignment overflow: AllocateAligned adds slop (≤ align-1 ≤ 7 bytes) for alignment, so in the extreme the discarded amount can slightly exceed 1/4 block — negligible; the unaligned Allocate is strictly < 1/4.
2. Tail-block overhead: at destruction the last block may be partially used, up to nearly a whole block — this is “end-of-life” overhead and is outside the 1/4 threshold’s control.

5. Alignment — AllocateAligned (arena.cc:38-56)

const int align = (sizeof(void*) > 8 ? sizeof(void*) : 8);
static_assert((align & (align - 1)) == 0, "Pointer size should be a power of 2");
size_t current_mod = reinterpret_cast<uintptr_t>(alloc_ptr_) & (align - 1);
size_t slop = (current_mod == 0 ? 0 : align - current_mod);
char* result = alloc_ptr_ + slop;

• Value of align: on real 32/64-bit platforms sizeof(void*) is 4 or 8; after max(., 8) it is always 8. The > 8 branch only leaves headroom for future >64-bit pointer platforms.
• Why the floor of 8: in a 32-bit build void* itself needs only 4-byte alignment, but a node contains an AtomicPointer and an 8-byte sequence number, so forcing ≥8 guarantees 8-byte quantities are safely aligned.
• static_assert((align & (align-1)) == 0): the classic “is power of two” check. It guards the premise of the whole alignment trick — x & (align-1) is only equivalent to x % align when align is a power of two, and align - (x % align) only then gives a correct padding. Otherwise the compiler errors out, preventing a wrong alignment offset at runtime.

6. Memory ordering: why memory_usage_ uses relaxed

Both the fetch_add (on allocation) and the load (when reading the stat) on memory_usage_ use relaxed.

• Safe in practice: the read sites are all on the writer path inside db/db_impl.cc, executed under DBImpl::mutex_. The fetch_add also runs on the writer thread under the lock. Effectively a single thread touches this field.
• Correct in essence: std::atomic’s relaxed still guarantees the variable’s own atomicity (RMW does not tear, load does not tear). The only thing it does not do is establish happens-before with other memory. And memory_usage_ is merely an independent approximate statistic (the function is literally named ApproximateMemoryUsage) — it is not a synchronization flag and does not “publish” any other non-atomic data, so it needs no ordering constraint.
• Using seq_cst/acquire/release would only add synchronization cost with no correctness benefit.

Answering the TODO in arena.h

The header asks: “only this member is atomic, others aren’t locked. Is this OK?” → Yes, intentional:

• alloc_ptr_ / alloc_bytes_remaining_ / blocks_ are only touched by the allocating thread (in practice under the MemTable write lock), so they need no atomics;
• only memory_usage_ is read by other threads as a statistic, so making just it atomic suffices. It is also a cheap defensive choice.

7. Relationship to MemTable / SkipList

• The skip list is constructed with an Arena* (skiplist.h:48); nodes use arena_->AllocateAligned(...).
• Nodes are never individually deleted → Arena’s “release in one shot” model is a perfect fit: zero fragmentation, no per-node free.
• Because MemTable holds arena-allocated, never-freed skip-list nodes and is reference-counted in several places (Ref()/Unref()), memtable.h explicitly = deletes copy constructor and assignment — it can only be shared/transferred by pointer, never copied by value.

8. Connecting to DDIA (Designing Data-Intensive Applications)

• Arena is a classic implementation of region-based memory management, serving the LSM-tree’s in-memory component, MemTable.
• It embodies the book’s “build custom data structures for your specific workload” idea: for the “many short-lived objects, freed all at once” scenario, node allocation on the write path becomes nearly zero-overhead and zero-fragmentation (compilers and game engines use the same family of allocators).
• It echoes Chapter 3’s LSM-tree in-memory semantics: when a MemTable fills up it is not “copied” but frozen / transferred wholesale (DBImpl swaps it into imm_), and this model of transferring ownership wholesale is what naturally forbids value copies.

9. Where to read next

Arena is the floor under MemTable. Suggested continuation:

1. db/skiplist.h: the concurrent skip list — how nodes are allocated via AllocateAligned, and the lock-free insert/lookup logic;
2. Reading LevelDB: The MemTable — how the internal key is encoded into nodes, and the Add/Get implementation;
3. Reading LevelDB: Flushing MemTables and the SSTable Format — what happens when mem_ fills and how the SSTable is laid out on disk;
4. back to the main line: MemTable → WAL(log) → SSTable(table/block) → Compaction(version_set).