[Notes]: Skip Lists

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