SKL

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.