Memtable

The memtable buffers writes in-memory before they are flushed to SSTables on S3.

Lifecycle

Loading diagram...

Skip List

Loading diagram...

O(log n) insert, lookup, and iteration. Max height 12 (supports ~4 billion entries). Probability 1/4 per level.

Since this is shard-per-core, the owning core is the sole writer — inserts are plain pointer writes with no CAS or locking.

Each entry stores:

MemtableEntry {
    composite_key:    Bytes,            // [record_id][0x00][item_key]
    value:            Bytes,
    metadata:         Bytes,
    idempotency_key:  IdempotencyToken, // dedup during unflushed window
    sequence_number:  u64,              // WAL sequence for ordering
    entry_type:       EntryType,        // PUT | DELETE | RANGE_DELETE
}

Arena Allocator

Each memtable owns a bump allocator backed by 1 MB blocks:

Arena {
    blocks: Vec<Box<[u8; 1_048_576]>>,
    current_offset: usize,
    total_allocated: usize,
}

Thousands of skip list node allocations become pointer bumps. Cache locality improves because nodes are contiguous. Deallocation is O(1) — drop all blocks when the memtable is released after flush. No atomics needed (single-owner).

Batch Insert

The memtable supports a batch insert fast path (insert_batch_prechecked) for multi-item writes. Entries are pre-validated (dedup checks done at the engine level) and inserted in a single pass. This avoids per-entry validation overhead when the engine has already confirmed idempotency tokens.

Freeze and Swap

When total_allocated >= 64 MB or 5 minutes elapse:

1. Swap the active memtable pointer with a new empty memtable.
2. The old memtable becomes frozen with a generation ID — pushed onto a read-only list, still checked during reads. The generation ID links the frozen memtable to its WAL segments for correct dirty tracking during recovery.
3. A background flush task is notified.

If 3 frozen memtables accumulate (flush can't keep up), writes are rejected — 192 MB is the ceiling.

Range Tombstone Index

A secondary index for range deletes, sorted by (record_id, start_key):

RangeTombstone {
    record_id: Bytes,
    start_key: Bytes,       // inclusive
    end_key: Bytes,          // exclusive
    sequence_number: u64,
}

During point reads, this index determines if a key falls within a range tombstone with a higher sequence number. If so, the entry is dead.

Idempotency Dedup

Each memtable maintains a HashSet of idempotency tokens. On write: check active + frozen sets. If found, skip (already applied). Tokens are flushed into the SSTable's dedup block and expire after 10 minutes.