Documentation
¶
Overview ¶
Package memtable implements BeachDB's in-memory write buffer using a skip list.
What is a memtable? ¶
In an LSM-tree database, writes don't go directly to disk. They land here first: a sorted, in-memory structure that accumulates recent mutations until it's full enough to flush to an SSTable on disk. The memtable is where "fast writes" come from — appending to a sorted structure in RAM is orders of magnitude cheaper than random I/O to stable storage.
Why a skip list? ¶
Skip lists are a probabilistic data structure that give you O(log n) insertion and lookup without the rebalancing headaches of a tree. Think of it as a linked list that learned to skip ahead: each node has a random "height," and taller nodes act as express lanes that let you jump over large sections of the list.
The appeal for a memtable:
- Sorted iteration is trivial (it's a linked list at level 0)
- No rotations or rebalancing (insertion is local pointer surgery)
- Concurrent-friendly (fine-grained locking is possible, though we use a single RWMutex for v1)
- Simple to implement without getting clever
Redis, LevelDB, and RocksDB all use skip lists for their memtables. It's a battle-tested choice.
Key ordering ¶
This is the most important invariant in the whole package.
Keys are sorted by (user_key ASC, seqno DESC). For the same user key, the entry with the highest sequence number appears first. This ordering means "newest version wins" falls out naturally: when you iterate or search, you hit the freshest version before any older ones.
Example:
Put("foo", "v1") at seqno 5
Put("foo", "v2") at seqno 10
Delete("foo") at seqno 15
The skip list stores these as:
("foo", 15, Delete) -> nil
("foo", 10, Put) -> "v2"
("foo", 5, Put) -> "v1"
A Get("foo") at seqno 20 finds the tombstone first and returns "not found." A Get("foo") at seqno 12 skips the tombstone (seqno 15 > 12) and returns "v2."
Concurrency model ¶
The SkipList uses a single sync.RWMutex:
- Put takes an exclusive lock (we assume single-writer for v1)
- Get takes a shared lock
- Iterators acquire a shared lock on first Seek/SeekToFirst and hold it until Close is called
This means iterators block writers. It's a deliberate v1 simplicity choice — the frozen-memtable flush pattern routes new writes to a fresh memtable while the old one drains, so iterator lock contention becomes a non-issue in practice.
IMPORTANT: Callers MUST call Iterator.Close() to release the lock. Forgetting this will deadlock writers indefinitely. The compiler won't save you here.
What the iterator sees ¶
The iterator exposes ALL entries: puts, tombstones, every version of every key. It does not filter, deduplicate, or hide anything. That's intentional.
Filtering (hide old versions, skip tombstones, respect snapshot boundaries) happens at a higher layer — the merge iterator that combines memtable + SSTables during reads. The memtable iterator's job is to produce a sorted stream of internal keys. Nothing more.
Memory accounting ¶
Size() returns an approximate byte count of memory used. It's not exact — we estimate per-node overhead and don't account for allocator fragmentation — but it's good enough for "is this memtable full yet?" decisions.
The p=0.25 choice ¶
Skip list level probability affects the height distribution:
- p=0.5: Average node height ~2. More memory, faster search.
- p=0.25: Average node height ~1.33. Less memory, still O(log n).
We use p=0.25 because it's the standard choice (LevelDB, Redis) and keeps memory overhead reasonable. With maxLevel=12 and p=0.25, we can handle billions of entries before the math breaks down.
Package memtable implements the skiplist and other types for the Memtable
Index ¶
- type Iterator
- type Memtable
- type SkipList
- type SkipListIterator
- func (it *SkipListIterator) Close() error
- func (it *SkipListIterator) Key() keys.InternalKey
- func (it *SkipListIterator) Next()
- func (it *SkipListIterator) Seek(target []byte)
- func (it *SkipListIterator) SeekToFirst()
- func (it *SkipListIterator) Valid() bool
- func (it *SkipListIterator) Value() []byte
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Iterator ¶
type Iterator interface {
SeekToFirst() // Position at first key
Seek(target []byte) // Position at first key >= target
Valid() bool // True if positioned at valid entry
Next() // Advance to next key
Key() keys.InternalKey // Current key - only valid if Valid() == true
Value() []byte // Current value - only valid if Valid() == true
Close() error // Release resources
}
Iterator provides forward iteration over memtable entries in sorted order.
type Memtable ¶
type Memtable interface {
Put(key keys.InternalKey, value []byte) // Insert a key-value pair
// Get retrieves a value at the given seqno.
// Returns (nil, false) if the key was not found,
// and (nil, true) when the newest visible version is a tombstone.
Get(userKey []byte, seqno uint64) ([]byte, bool)
NewIterator() Iterator // Create an iterator over entries
Len() int // Number of entries
Size() int64 // Approximate memory usage in bytes
Empty() bool // True if no entries
}
Memtable is an in-memory sorted key-value store that buffers writes before flushing to SSTables.
type SkipList ¶
type SkipList struct {
// contains filtered or unexported fields
}
SkipList is a probabilistic data structure that provides O(log n) insertion and search with lock-friendly concurrent access. It implements the Memtable interface.
func NewSkipList ¶
func NewSkipList() *SkipList
NewSkipList creates a new SkipList struct pointer and returns it
func (*SkipList) Get ¶
Get returns the value for the given userKey at or before the given seqno. Returns (value, true) if found, (nil, false) if not found, and (nil, true) when the newest visible version is a tombstone.
Semantics: finds the newest version of userKey with seqno <= requested seqno. If that version is a tombstone (KindDelete), returns (nil, true).
func (*SkipList) NewIterator ¶
NewIterator returns an iterator over the skip list entries.
type SkipListIterator ¶
type SkipListIterator struct {
// contains filtered or unexported fields
}
SkipListIterator provides forward iteration over a SkipList's entries. Thread safety: The iterator holds a read lock from the first Seek/SeekToFirst call until Close. Concurrent writes will block until Close is called. Users MUST call Close to release the lock; failing to do so will deadlock writers.
func NewSkipListIterator ¶
func NewSkipListIterator(list *SkipList) *SkipListIterator
NewSkipListIterator creates a new iterator for the given skip list. The iterator is initially invalid; call SeekToFirst or Seek to position it.
func (*SkipListIterator) Close ¶
func (it *SkipListIterator) Close() error
Close releases any resources held by the iterator. After Close, the iterator must not be used.
func (*SkipListIterator) Key ¶
func (it *SkipListIterator) Key() keys.InternalKey
Key returns the key at the current position. Only valid if Valid() returns true.
func (*SkipListIterator) Next ¶
func (it *SkipListIterator) Next()
Next advances the iterator to the next entry. If the iterator is already at the end, it becomes invalid.
func (*SkipListIterator) Seek ¶
func (it *SkipListIterator) Seek(target []byte)
Seek positions the iterator at the first entry with key >= target. The target is treated as a user key; the iterator will position at the first internal key whose user key >= target (respecting internal key ordering).
func (*SkipListIterator) SeekToFirst ¶
func (it *SkipListIterator) SeekToFirst()
SeekToFirst positions the iterator at the first entry. After this call, Valid() returns true if the list is non-empty.
func (*SkipListIterator) Valid ¶
func (it *SkipListIterator) Valid() bool
Valid returns true if the iterator is positioned at a valid entry.
func (*SkipListIterator) Value ¶
func (it *SkipListIterator) Value() []byte
Value returns the value at the current position. Returns a copy to prevent caller mutation. Only valid if Valid() returns true.
Source Files