#skiplist #lock-free #arena #memtable

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

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

#131 in Concurrency

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–32MB
~468K SLoC