Prelude
These are just some of my notes and references from implementing a skip list in Rust. Creating a skip list implementation that has concurrency features is my personal intro project to Rust so there will also be some notes on lock-free and wait-free techniques. The overarching goal is to utilize this skip list as the in-memory component of an LSM-tree based storage engine, that I will maybe, hopefully, aspirationally, try to make. LevelDB in Rust if you will.
Notes
-
Used as the in-memory component of LevelDB’s log structured merge tree (LSM tree) implementation
-
Skip list vs self-balancing search trees (e.g. Red-black trees)
-
A skip list is more amenable to concurrency because less nodes are required to be updated during an insert
-
On update, a self-balancing tree may require multiple ancestors to be changed when the balancing operations (e.g. rotations in a Red-black tree)
-
-
LevelDB is doesn’t have concurrent writes? Source appears to require an external lock mechanism for writes.
-
When used as the in-memory component of an LSM tree, the skip list should support sorting by reverse chronological order. This can be done by having a synthetic key with a timestamp/revision number or via reverse iteration by back pointers. This is because the LSM tree is an append only structure.
Some concurrency stuff
- Jon Gjengset - Rust at speed - building a fast concurrent database
- Using an RwLock can become a bottleneck for operations with a short critical section. You will effectively benchmarking the time it takes to lock and unlock.
- Jon Gjengset - Lock-Free to Wait-Frre Simulation in Rust
- Aaron Turon - Lock-freedom without garbage collection
- Epoch-based reclamation in Rust
- Keir Fraser - Practical Lock Freedom
Useful references
- William Pugh - Skip Lists: A Probablistic Alternative To Balanced Trees
- Open Data Structures and Algorithms - Skip List
- Facebook’s Folly implementation of a concurrent skip list in C++
- LevelDB implementation of a skip list in C++
- Maurice Herlihy, et al. - A Provably Correct Scalable Concurrent Skip List
- Fomitchev and Ruppert - Lock-Free Linked Lists and Skip Lists
- Learn Rust With Entirely Too Many Linked Lists
- Rust std::collections::LinkedList
- Ticki - Skip Lists: Done Right
- Adam Prout - The Story Behind SingleStore’s Skiplist Indexes