Reading LevelDB: The SkipList Index

The Arena article showed where MemTable’s nodes come from in memory. This one walks the index structure they are woven into: LevelDB’s skip list (db/skiplist.h). It is one of the cleanest production examples of a single-writer / multi-reader lock-free data structure in the wild, and almost every line is a consequence of one rule — writes are externally synchronized, reads are not.

If you haven’t read the Arena piece yet, it is the natural prerequisite: nodes here are allocated through arena_->AllocateAligned(...). → Reading LevelDB: The Arena Region Allocator

1. The thread-safety contract

The file header states the contract plainly (db/skiplist.h:11-14):

// Writes require external synchronization, most likely a mutex.
// Reads require a guarantee that the SkipList will not be destroyed
// while the read is in progress.  Apart from that, reads progress
// without any internal locking or synchronization.

Two consequences fall out of this:

Writes (Insert) carry no internal lock; they are protected entirely by an external mutex (the MemTable/DB write lock).
Reads (Contains, iterator seeks) take no lock at all and can run fully concurrently — the only requirement is that the list object is not destroyed mid-read.

This is only sound because of two invariants the code upholds:

Nodes are never deleted while the list lives (§2).
A node’s contents (other than next pointers) are immutable, and a newly inserted node is published with a release store (§4).

2. Nodes are permanent — lifetime and Arena

// (1) Allocated nodes are never deleted until the SkipList is
// destroyed.  This is trivially guaranteed by the code since we
// never delete any skip list nodes.

A node, once allocated, stays resident until the whole SkipList (and thus its MemTable) is destroyed. There is no per-node free; when a MemTable fills and is flushed to disk (minor compaction), the entire Arena — and every node in it — is released at once.

In LevelDB this is the natural fit:

Deletes are also inserts — a “tombstone” key is written rather than the old node being removed.
The structure trades fine-grained memory reclamation for batch reclamation at flush time, which matches the “accumulate, then spill” MemTable lifecycle exactly.

3. Node allocation: `NewNode` + placement new

template <typename Key, class Comparator>
typename SkipList<Key, Comparator>::Node* SkipList<Key, Comparator>::NewNode(
    const Key& key, int height) {
  char* const node_memory = arena_->AllocateAligned(
      sizeof(Node) + sizeof(std::atomic<Node*>) * (height - 1));
  return new (node_memory) Node(key);
}

Reading the pieces:

height is how many forward (next) pointers this node carries — randomly chosen by RandomHeight() and bounded by kMaxHeight.
Size math: sizeof(Node) already includes next_[0] (one pointer), so we add (height - 1) more pointer slots to reach a total of height forward pointers. This is the classic flexible-array trick (§5).
char* const: AllocateAligned returns raw, untyped, aligned bytes. The const only pins the local pointer; the memory is writable.
placement new new (node_memory) Node(key): constructs the object in already-allocated memory — no fresh allocation. Memory stays owned by the Arena (freed wholesale) and the size/alignment are controlled precisely.
One Arena block holds many nodes: kBlockSize = 4096 (4 KB) is the block granularity, not per-node. A small node (~24 B) is packed back-to-back into the same 4 KB block; only objects larger than 1 KB get a dedicated block.

4. Memory ordering: the acquire/release pair

This is the heart of the lock-free read. The Node exposes four accessors (db/skiplist.h:151-172):

Node* Next(int n) {                        // acquire load
  return next_[n].load(std::memory_order_acquire);
}
void SetNext(int n, Node* x) {             // release store
  next_[n].store(x, std::memory_order_release);
}
Node* NoBarrier_Next(int n) {
  return next_[n].load(std::memory_order_relaxed);
}
void NoBarrier_SetNext(int n, Node* x) {
  next_[n].store(x, std::memory_order_relaxed);
}

Why the pairing matters:

release (writer): guarantees everything before the store (the node’s full initialization — key, value, lower-level pointers) stays before it. The pointer is published only after the node is constructed.
acquire (reader): guarantees everything after the load sees that complete initialization.
release + acquire ⇒ synchronizes-with: the initializing writes the writer did before the release become visible to the reader after the acquire. That pairing — not a mutex — is what makes concurrent lock-free traversal safe.

relaxed is used only where ordering is irrelevant: a single thread’s own pointer walks, or stale reads that are tolerable (e.g. a racy read of max_height_, §10).

5. `next_[1]` — the flexible array

std::atomic<Node*> next_[1];

Despite the [1], this is not a single pointer. It is a length-1 array used as a flexible-array placeholder: NewNode overallocates the node to height slots (§3), and next_[0 .. height-1] are treated as the per-level forward pointers. Next(n) / SetNext(n, x) read and write exactly the n-th level’s successor.

6. Bounds safety by discipline, not by check

void SetNext(int n, Node* x) {
  assert(n >= 0);          // only a lower-bound check; no upper bound

There is no upper-bound check on SetNext / Next. Reading next_[n] for n ≥ 1 on a standard-C++ object is technically out-of-bounds — it is kept safe only by the overallocation in §3. The two disciplines that prevent real overruns:

In Insert, the loop for (int i = 0; i < height; i++) is bounded by the node’s own height, and NewNode allocated exactly height slots.
Any node linked at level i sits above level i, so its height > i ⇒ it is guaranteed to have next_[i].

The takeaway: the store itself does not prevent an out-of-bounds access; physical safety comes from overallocation, logical safety from the call discipline. Both are required.

7. Where `kMaxHeight = 12` comes from

enum { kMaxHeight = 12 };

Paired with the branching factor kBranching = 4 (§9), a node has height ≥ h with probability (1/4)^(h-1). The expected span at level i is 4^i, so to index N nodes you need about log_4(N) levels.

4^12 ≈ 16,777,216 — 12 levels comfortably index ~16 million nodes.
That dwarfs any realistic MemTable: write_buffer_size caps it at 4 MB by default (1 GB max), nowhere near 16 M nodes.
12 is the balance point between enough coverage and not wasting pointer memory. The live height (max_height_) starts at 1 and only grows when RandomHeight rolls higher.

8. The “64 GB” myth, corrected

A common misconception: “16 M nodes × 4 KB = 64 GB” — wrong, because it mistakes the Arena’s 4 KB block granularity for a per-node size.

Reality:

A MemTable node is tiny (key const char* = 8 B + next_ averaging ~1.33 levels × 8 B ≈ 19 B, plus alignment ≈ 24 B).
Many such nodes are packed into one 4 KB block.
The MemTable is hard-capped by write_buffer_size, so it never reaches 16 M nodes. 4^12 is the theoretical coverage of 12 levels, not the real node count.

9. `RandomHeight` — a geometric distribution

int SkipList<Key, Comparator>::RandomHeight() {
  static const unsigned int kBranching = 4;
  int height = 1;
  while (height < kMaxHeight && rnd_.OneIn(kBranching)) {
    height++;
  }
  return height;
}

OneIn(4) returns true with probability 1/4 each step (keep adding a level) and false with 3/4 (stop). So most nodes are 1 level tall, and taller nodes get exponentially rarer — the classic “dense at the bottom, sparse at the top” shape.

Expected height derivation. Let K = number of level increments, P(K = k) = (1/4)^k · (3/4), height = 1 + K:

E[K] = Σ k·(1/4)^k·(3/4)
     = (3/4) · (1/4) / (3/4)²
     = 1/3
E[height] = 1 + 1/3 = 4/3 ≈ 1.33

Hitting the 12-level cap is astronomically unlikely: (1/4)^11 ≈ 2.4×10⁻⁷.

10. `FindGreaterOrEqual` — the core search

bool KeyIsAfterNode(const Key& key, Node* n) const {
  return (n != nullptr) && (compare_(n->key, key) < 0);  // n->key < key ?
}

Node* FindGreaterOrEqual(const Key& key, Node** prev) const {
  Node* x = head_;
  int level = GetMaxHeight() - 1;
  while (true) {
    Node* next = x->Next(level);
    if (KeyIsAfterNode(key, next)) {
      x = next;                       // can move right: advance
    } else {
      if (prev != nullptr) prev[level] = x;   // record this level's predecessor
      if (level == 0) return next;    // at bottom: first node >= key
      else level--;                   // descend one level
    }
  }
}

The algorithm:

Start at the highest level. If next is still before the target (KeyIsAfterNode true), move right.
Otherwise record the current node as this level’s predecessor (prev[level]) and descend.
At level 0, next is the first node ≥ key — or nullptr if none exists.

KeyIsAfterNode treats n == nullptr as +∞ (the tail sentinel); for a real node it just tests n->key < key.

What `prev[]` is

prev is an array with one slot per level, holding “the node a new entry should be spliced after, at this level.” Because the search descends from the top, it incidentally records every level’s predecessor on the way down; Insert then links the new node at each level with the standard new->next = prev[i].next; prev[i].next = new. No second search needed.

Example (insert 15 at height 2): the search yields prev = {14, 10, 10} for levels 0/1/2; splicing links 15 into level 0 and level 1.

`prev` is an optional parameter — one function, two callers

FindGreaterOrEqual serves both paths behind a single if (prev != nullptr) guard:

Insert calls FindGreaterOrEqual(key, prev) — passes the array, collects predecessors.
Reads (Contains, Iterator::Seek) call FindGreaterOrEqual(key, nullptr) — pure lookup; the predecessor-recording block is skipped entirely.

One search routine, reused for insert and read. Note that Insert itself has no “skip if key exists” branch — dedup is the MemTable’s job, not the list’s. Once Insert is called, it assumes the predecessor array will be used.

11. Where to read next

The skip list is the in-memory index of MemTable. Natural follow-ups:

Reading LevelDB: The MemTable — how the internal key (user key + sequence + type) is encoded into nodes, and the Add / Get implementation;
Reading LevelDB: Flushing MemTables and the SSTable Format — what happens when mem_ fills and how the SSTable is laid out on disk;
back to the main line: MemTable → WAL (log) → SSTable (table/block) → Compaction (version_set).

The Arena piece is the floor under all of this — Reading LevelDB: The Arena Region Allocator.

Quick reference

Topic	Key point
Thread safety	writes locked, reads lock-free; read only fears list destruction
Node lifetime	resident until SkipList/MemTable destroyed, freed wholesale
Allocation	Arena overallocation + placement new; flexible array `next_[1]`
Memory ordering	release store + acquire load pairing enables lock-free reads
Levels	`kMaxHeight = 12`, `log_4(N)` covers ~16 M
Expected height	`4/3 ≈ 1.33` levels
Search	descend from top, move right, record `prev[]`
`prev`	predecessors per level for insert; reads pass `nullptr`

Reading LevelDB: The SkipList Index

1. The thread-safety contract

2. Nodes are permanent — lifetime and Arena

3. Node allocation: NewNode + placement new

4. Memory ordering: the acquire/release pair

5. next_[1] — the flexible array

6. Bounds safety by discipline, not by check

7. Where kMaxHeight = 12 comes from