Lib.rs

› Database interfaces | Concurrency
#skip-list #lock-free #arena #memtable #memory-map

no-std skl

A lock-free thread-safe concurrent ARENA based (heap backend or memory map backend) skiplist implementation which helps develop MVCC memtable for LSM-Tree

by Al Liu

3 unstable releases

0.4.0-alpha.1 Sep 19, 2023
0.3.1 Sep 4, 2023
0.2.4 Jul 17, 2022
0.1.0 Oct 25, 2021

#327 in Database interfaces

31 downloads per month

MIT/Apache

79KB
2K SLoC

SKL

github Build codecov

docs.rs crates.io license

  1. A lock-free thread-safe concurrent ARENA based skiplist implementation which helps develop MVCC memtable for LSM-Tree.
  2. A lock-free thread-safe concurrent memory map based on-disk skiplist.

Inspired by Dgraph's badger.

Installation

  • Only use heap backend (suppport no_std)

    [dependencies]
skl = "0.4-alpha.1"

  • Enable memory map backend

    [dependencies]
skl = { version = "0.4.0-alpha.1", features = ["mmap"] }

Examples

Please see examples folder for more details.

Tests

  • test:

    cargo test --all-features

  • miri:

    cargo miri test --all-features

Support Platforms

targets status
aarch64-linux-android ✅
aarch64-unknown-linux-gnu ✅
aarch64-unknown-linux-musl ✅
i686-pc-windows-gnu ✅
i686-linux-android ✅
i686-unknown-linux-gnu ✅
mips64-unknown-linux-gnuabi64 ✅
powerpc64-unknown-linux-gnu ✅
riscv64gc-unknown-linux-gnu ✅
wasm32-unknown-unknown ✅
wasm32-unknown-emscripten ✅
x86_64-unknown-linux-gnu ✅
x86_64-pc-windows-gnu ✅
x86_64-linux-android ✅

TODO (help wanted)

  • make the crate test cases pass cargo miri
  • make the crate test cases pass cargo loom
  • Implement
    • get_or_insert
    • remove
    • contains
    • change signature from insert(k, v) => insert(k, v) -> Option<ValueRef>
    • mmap backend (currently is vector backend)
    • Supports SkipSet

License

skl-rs is under the terms of both the MIT license and the Apache License (Version 2.0).

See LICENSE-APACHE, LICENSE-MIT for details.

Copyright (c) 2022 Al Liu.

Dependencies

~2–36MB
~499K SLoC