Reading LevelDB: The MemTable

The Arena piece showed where MemTable’s nodes come from in memory; the SkipList piece showed the index structure they are woven into. This article sits at the top of that stack: MemTable (db/memtable.h, db/memtable.cc) — the LSM tree’s in-memory write buffer, the structure that actually encodes the K/V pairs, orders them, and hides deletes behind tombstones.

If you haven’t read the two prerequisite pieces, they are the natural lead-in: → Reading LevelDB: The Arena Region Allocator → Reading LevelDB: The SkipList Index

1. What MemTable is

A MemTable is the LSM tree’s in-memory component. Writes (Put/Delete) land here first; once it fills (write_buffer_size) it is frozen and flushed to an SSTable. Internally it is just three things:

an Arena that owns all node memory (bump-allocated, freed wholesale);
a SkipList<const char*, KeyComparator> that indexes entries by internal key;
a KeyComparator that knows how two encoded entries compare.

The skip-list node key is nothing more than a const char* pointer to the head of an entry buffer. So everything MemTable does — encoding, ordering, lookup — reduces to how that buffer is laid out and how two buffers are compared.

2. The memory entry format

From db/memtable.cc:78-99, Add packs one K/V pair into a single contiguous arena buffer:

// Format of an entry is concatenation of:
//  key_size     : varint32 of internal_key.size()
//  key bytes    : char[internal_key.size()]
//  tag          : uint64((sequence << 8) | type)
//  value_size   : varint32 of value.size()
//  value bytes  : char[value.size()]
...
char* buf = arena_.Allocate(encoded_len);
char* p = EncodeVarint32(buf, internal_key_size);
std::memcpy(p, key.data(), key_size);
p += key_size;
EncodeFixed64(p, (s << 8) | type);
p += 8;
p = EncodeVarint32(p, val_size);
std::memcpy(p, value.data(), val_size);
table_.Insert(buf);

One entry = key and value packed in the same contiguous span of arena memory (fully owned by the arena):

┌──────────┬──────────────────────────┬────────┬───────────┬──────────┐
│ key_size │ userkey + tag (8B)        │ tag    │ value_size│ value    │
│ varint32 │ char[internal_key_size-8] │ uint64 │ varint32  │ char[]   │
└──────────┴──────────────────────────┴────────┴───────────┴──────────┘
              └──── together = internal_key (the sort key) ────┘

internal_key = userkey + 8-byte tag, where tag = (sequence << 8) | type.
Note that userkey and tag are written by separate memcpy / EncodeFixed64 calls, but they are semantically contiguous — together they form the sort key, internal_key.
table_.Insert(buf) inserts the start pointer of this buffer as the skip-list node’s “key”. The node itself is just a const char* pointing at the entry.
The sort order only ever looks at internal_key; it never touches value (see §4).

3. Variable-length encoding (varint) — byte-compatible with Protobuf

EncodeVarint32 (util/coding.cc:21-47):

char* EncodeVarint32(char* dst, uint32_t v) {
  uint8_t* ptr = reinterpret_cast<uint8_t*>(dst);
  static const int B = 128;
  if (v < (1 << 7))      { *(ptr++) = v; }
  else if (v < (1 << 14)){ *(ptr++) = v | B; *(ptr++) = v >> 7; }
  ...
}

Rule: each byte stores 7 bits of data in its low 7 bits; the high bit (0x80) is the continuation flag. Multi-byte values are laid out little-endian (low-order byte first).
Decode (GetVarint32PtrFallback, util/coding.cc:86-102): loop over bytes; if byte & 128 there is more, result |= (byte & 127) << shift, shift increments by 7 each round.
VarintLength (:77-84) pre-computes how many bytes a value needs (while (v >= 128) { v >>= 7; len++; }).

Relation to Protobuf

LevelDB’s varint is byte-level compatible with Protobuf’s varint encoding. The only difference is that Protobuf additionally offers zigzag (mapping signed integers to unsigned), whereas LevelDB here only encodes unsigned lengths / sequence numbers and never applies signed zigzag.

4. KeyComparator — compares only internal_key, never value

int MemTable::KeyComparator::operator()(const char* aptr,
                                        const char* bptr) const {
  Slice a = GetLengthPrefixedSlice(aptr);   // skip key_size, take internal_key
  Slice b = GetLengthPrefixedSlice(bptr);
  return comparator.Compare(a, b);
}

The comparator receives the entry start pointer aptr.
GetLengthPrefixedSlice (:14-19) first reads key_size via GetVarint32Ptr, then returns the slice [after key_size, length = key_size] — i.e. it cuts out exactly the internal_key (userkey + tag) and the value is skipped entirely.
So the sort comparison only ever looks at internal_key; the value’s byte order and size have zero effect on ordering.

The `Get` lookup flow and tombstones

bool MemTable::Get(const LookupKey& key, std::string* value, Status* s) {
  Slice memkey = key.memtable_key();
  Table::Iterator iter(&table_);
  iter.Seek(memkey.data());          // skip-list: first entry >= memkey
  if (iter.Valid()) {
    const char* entry = iter.key();
    const char* key_ptr = GetVarint32Ptr(entry, entry + 5, &key_length);
    if (user_comparator()->Compare(
            Slice(key_ptr, key_length - 8), key.user_key()) == 0) {
      const uint64_t tag = DecodeFixed64(key_ptr + key_length - 8);
      switch (static_cast<ValueType>(tag & 0xff)) {
        case kTypeValue:    /* read value, return it */;
        case kTypeDeletion: *s = Status::NotFound(...); return true;
      }
    }
  }
  return false;
}

Flow: encode memkey → skip-list Seek to target → verify user_key equality (the tag’s low 8 bits tag & 0xff is the type; tag >> 8 is the sequence) → branch on type:

kTypeValue: use GetLengthPrefixedSlice(key_ptr + key_length) to skip the internal_key and return the value.
kTypeDeletion: return NotFound — that is the tombstone.

Tombstone semantics (correcting the “it deletes” misconception)

The MemTable layer never physically deletes any entry; a delete is just inserting a kTypeDeletion tombstone record into the skip list.
Real cleanup happens during compaction, when an SSTable merge meets a tombstone against an older value and discards both.
So “inserted data is never deleted, only marked invalid” is precise in the local sense: nothing is removed here; global convergence relies on background compaction.

5. The `Add` path — how a write becomes an entry

Add (memtable.h:53-57, implemented in memtable.cc) is the landing point of the write path:

void Add(SequenceNumber s, ValueType type, const Slice& key,
         const Slice& value);

Parameters: s is the sequence number (the MVCC version); type is kTypeValue or kTypeDeletion (value is usually empty for deletes); key is the user key (the internal key is synthesized here); value is the value.
What it does (tied to §2’s format): first synthesize the internal key from the user key (userkey + 8B tag, tag = (s << 8) | type), then pack internal_key + value into one arena buffer, then table_.Insert(buf). Three design points:
1. Tag packing (s << 8) | type: sequence occupies the high 56 bits, type the low 8. The skip list orders internal keys descending, so under the same user key the largest sequence comes first — meaning Get’s Seek hits the newest version first. That is how multi-version reads are implemented.
2. Key + value in one arena buffer: the skip-list node stores just one const char*; after packing it is a single allocation, cache-friendly; the comparator reads only the internal_key prefix, and the value is fetched on demand at offset key_ptr + key_length (see §4).
3. Uses arena_.Allocate (unaligned), not AllocateAligned: the buffer is pure byte data needing no 8-byte alignment; node alignment is handled separately inside SkipList via AllocateAligned (echoing the Arena notes).

6. Class design — non-copyable and reference-counted

The first three sections are about memtable.cc (encoding & lookup). This section is about memtable.h — the ownership design at the class level.

6.1 Disable copying (`memtable.h:26-27`)

MemTable(const MemTable&) = delete;
MemTable& operator=(const MemTable&) = delete;

Line 26 is the copy constructor (const MemTable& parameter); line 27 is the copy assignment operator (returns MemTable&). = delete disables any value copy at compile time.
Why non-copyable:
- member arena_ owns raw memory (std::vector<char*> blocks_, etc.) and itself = deletes copying;
- member table_ is a SkipList whose nodes are all allocated in arena_ and never freed individually (a node lives until the MemTable is destroyed); SkipList itself also = deletes copying.
- Even if copying were possible, a shallow copy is fatal: skip-list nodes store pointers into arena memory, so two MemTables would share the same nodes; when one side Unref()s to 0 and does delete this, it frees the other side’s node memory too → dangling pointers. A deep copy is hugely expensive and unnecessary.
The correct semantics is “shared ownership + reference counting”, not value copying — this matches the LSM in-memory component’s “freeze / hand-off” model: when mem_ fills it is swapped wholesale into imm_, not copied.

6.2 Reference counting `Ref` / `Unref` (`memtable.h:29-39`)

void Ref() { ++refs_; }
void Unref() {
  --refs_;
  assert(refs_ >= 0);
  if (refs_ <= 0) delete this;
}

Why needed: a MemTable is shared by the same instance in many places (it cannot be copied, yet cannot have a single owner). Typical holders:
1. DBImpl::mem_ — the active memtable (holds 1 ref, written by the write path);
2. DBImpl::imm_ — the frozen memtable pending flush (holds 1 ref; Unref() after background flush);
3. user iterators (NewIterator calls Ref(), guaranteeing the memtable survives the traversal even if a background flush already happened);
4. background compaction tasks (hold a ref while operating on imm_).
- whoever Unref()s last to refs_ <= 0 is responsible for delete this.
Relation to shared_ptr: same idea (shared ownership + destroy on count zero), but implemented as a hand-written intrusive reference count, not std::shared_ptr. Four key differences:
1. Intrusive vs external control block: shared_ptr keeps its count in a separate control block, invisible to the managed type; here refs_ is a member inside the object (memtable.h:80), the object carries its own count.
2. Initial count is 0 (memtable.h:22-23 comment: “initial reference count is zero and the caller must call Ref() at least once”): a newed object is “owned by nobody yet” and the caller must immediately Ref() to take it over — more explicit, more discipline-bound than shared_ptr’s default count of 1.
3. Not thread-safe: refs_ is a plain int, not std::atomic; all Ref/Unref must run under DBImpl::mutex_ (external lock guarantees safety, saving atomic cost).
4. Purely manual, no smart-pointer wrapper: there is no shared_ptr<MemTable> in the code; callers hold a raw pointer and manually pair Ref/Unref; the destructor is even declared private (memtable.h:77), so only Unref() can delete it — the type system forces “destruction only via the reference-count protocol”.
Why not just use shared_ptr: avoids the control block’s extra heap allocation, avoids atomic RMW overhead, fits the “hand-off” semantics (mem_ → imm_ transfers ownership wholesale), and reflects the early (C++03-era) style that also disables exceptions/RTTI.
Tie to DDIA: the LSM in-memory component is shared / handed off in many places; reference counting is exactly the “multiple owners, last releaser destroys” model landed in C++ — the same problem shared_ptr solves, just LevelDB’s lighter, more controllable hand-written variant.

7. Connection to Arena & SkipList

MemTable composes an Arena (arena_) and a SkipList (table_) built on it. The entry buffer in §2 is arena_.Allocate’d; the skip-list node storing its pointer is arena_.AllocateAligned’d.
The “nodes never individually freed” invariant (SkipList) and the “freed wholesale” model (Arena) are why MemTable can = delete copying and rely on reference counting instead — the three pieces are mutually consistent.
Add produces the bytes, KeyComparator interprets them, SkipList orders them, Arena owns them. MemTable is the glue that turns a Put/Delete into a sorted, versioned, immortal-until-flush record.

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

Every record carries a sequence number = MVCC / timestamp (enabling snapshot isolation and multi-version reads); deletes use a tombstone rather than a true delete, with cleanup deferred to background compaction — echoing the §4 tombstone semantics and the §5 Add design.
MemTable is the canonical LSM in-memory component: writes accumulate here, then spill to SSTable; the “freeze and hand off” model (§6.1) is exactly the ownership-transfer pattern behind compaction.

9. Where to read next

MemTable is the top of this stack, and you have already seen the two pieces underneath it:

Reading LevelDB: The Arena Region Allocator — the bump allocator that owns every byte;
Reading LevelDB: The SkipList Index — the lock-free index over those bytes.

The natural continuation past MemTable is the main LSM line: MemTable → WAL (log) → SSTable (table/block) → Compaction (version_set).

The very next step — what happens when mem_ fills and how the SSTable on disk is laid out — is here: Reading LevelDB: Flushing MemTables and the SSTable Format.

Quick reference

Topic	Key point
Entry format	varint(key_size) \| userkey \| tag \| varint(val_size) \| value, KV same span
internal_key	userkey + 8B tag = (sequence<<8)\|type, is the sort key
varint	7-bit payload + high continuation bit + little-endian; byte-compatible with Protobuf
KeyComparator	cuts internal_key only, never touches value
Get / tombstone	Seek → check user_key → by type return value or NotFound
Add	seq+type+userkey+value; synthesize internal key, pack into arena, insert; delete = tombstone
Non-copyable	memtable.h:26-27; arena/skiplist uncopyable, shallow copy fatal, deep copy wasteful
Ref counting	memtable.h:29-39; intrusive Ref/Unref, initial 0, plain int under mutex, not shared_ptr