LSM-Tree Memtable Using a Skip List

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.

c
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.

Write a C program that implements a skip list memtable for key-value pairs.

Requirements:

Define MAX_LEVEL as 4 and a Node struct with key, value, and forward array of size MAX_LEVEL
Implement create_node(key, value, level) that allocates a node
Implement random_level() that returns a level from 0 to MAX_LEVEL-1 with probability 1/2 for each increment (coin flip)
Implement skiplist_insert(list, key, value): find insertion position at each level, link the new node
Implement skiplist_search(list, key): return value or -1 if not found
Implement skiplist_print(list): print all key-value pairs at level 0
Insert these pairs: (10,100), (20,200), (15,150), (5,50), (25,250), (30,300)
Print the skip list after all insertions
Search for keys: 15, 100 (not found)
Print the level of each node to show the probabilistic structure
Calculate and print the average number of comparisons per search vs a linked list
Include a note about why skip lists are preferred over balanced trees for memtables

In-Memory Table Before Flush

Skip List Properties

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

c
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.

Write a C program that implements a skip list memtable for key-value pairs.

Requirements:

Define MAX_LEVEL as 4 and a Node struct with key, value, and forward array of size MAX_LEVEL
Implement create_node(key, value, level) that allocates a node
Implement random_level() that returns a level from 0 to MAX_LEVEL-1 with probability 1/2 for each increment (coin flip)
Implement skiplist_insert(list, key, value): find insertion position at each level, link the new node
Implement skiplist_search(list, key): return value or -1 if not found
Implement skiplist_print(list): print all key-value pairs at level 0
Insert these pairs: (10,100), (20,200), (15,150), (5,50), (25,250), (30,300)
Print the skip list after all insertions
Search for keys: 15, 100 (not found)
Print the level of each node to show the probabilistic structure
Calculate and print the average number of comparisons per search vs a linked list
Include a note about why skip lists are preferred over balanced trees for memtables

Topic Overview

In-Memory Table Before Flush

Skip List Properties

Working Through the Exercise

Why for this exercise

Implementation Task

Progressive Hints

Resources

Open Source

LSM-Tree Memtable Using a Skip List

Topic Overview

In-Memory Table Before Flush

Skip List Properties

Working Through the Exercise

Why for this exercise

Implementation Task

Progressive Hints

Resources

Open Source