LSM-Tree Memtable Using a Skip List

Topic Overview

In-Memory Table Before Flush

LSM trees buffer writes in a memtable, usually a skip list or red-black tree, before flushing immutable SSTables to disk. RocksDB and LevelDB use skip lists for concurrent inserts with reader-writer friendly locking.

Skip List Properties

Expected O(log n) search with simpler concurrency than balanced trees. Each level skips forward with coin-flip height.

cCopy
Loading…

• Memtable size triggers flush when threshold reached
• Keys sorted for efficient sequential flush
• WAL protects memtable entries until flush completes
• Compare skip list depth distribution on random inserts

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

• Trace first: walk one failing input step by step
• Read the manual: skim the official doc for the mechanism named in this task
• Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will implement a skip list memtable supporting insert and lookup. This exercise requires maintaining sorted order and expected logarithmic search steps.

Document one invariant you will assert in tests and how you would detect its violation from observable symptoms.

Your Task

LSM-tree stores such as LevelDB and RocksDB buffer writes in a skip list memtable: a sorted linked list with extra "express" levels on top, giving O(log n) search with simple, lock-friendly inserts. Build one with MAX_LEVEL = 4.

• A sentinel head node is on every level. Each node is on levels 0 to L-1, where L is its level count, 1 to 4. Level 0 links every node in key order; higher levels skip ahead.
• In a real memtable L comes from coin flips. Here each put gives it, so results are reproducible. Clamp it to 1-4.
• Search starts at the head on level 3. On each level, step right while the next node's key is smaller than the target, then drop down a level. After level 0, the target is the next node, if its key matches. Count a comparison every time you look at an existing next node's key, including the look that makes you stop.
• Insert remembers the last node it passed on each level, then links the new node after it on each of its levels. A key that already exists only has its value updated; its level stays.

Input

Commands until the end of input:

• put K V L
• get K
• levels
• dump

Output

• put: put 15=150 level=2 for a new key, put 15=999 updated for an existing one.
• get: get 15 -> 150 (comparisons=3), or get 99 -> -1 (comparisons=2) when the key is absent.
• levels: one line per level from 3 down to 0, such as L1: 10 25 or L3: (empty).
• dump: sorted: 5=50 10=100 15=150 with every pair in key order.