Crate skl

SKL

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

Installation

• Only use heap backend (suppport no_std)

  [dependencies]
  skl = "0.9"
  

• Enable memory map backend

  [dependencies]
  skl = { version = "0.9", features = ["memmap"] }
  

Features

• MVCC and 3D access: Builtin MVCC (multiple versioning concurrency control) and key-value-version access support.
• Lock-free and Concurrent-Safe: SkipMap and SkipSet provide lock-free operations, ensuring efficient concurrent access without the need for explicit locking mechanisms.
• Extensible for Key-Value Database Developers: Designed as a low-level crate, SkipMap and SkipSet offer a flexible foundation for key-value database developers. You can easily build your own memtable or write-ahead-log (WAL) using these structures.
• Memory Efficiency: These data structures are optimized for minimal memory overhead. They operate around references, avoiding unnecessary allocations and deep copies, which can be crucial for efficient memory usage.
• Efficient Iteration: Enjoy fast forward and backward iteration through the elements in your SkipMap or SkipSet. Additionally, bounded iterators are supported, allowing you to traverse only a specified range of elements efficiently.
• Snapshot Support: Create snapshots of your SkipMap or SkipSet, offering a read-only view of the contents at a specific moment in time. Snapshots provide a consistent view of the data, enabling implementations of transactional semantics and other use cases where data consistency is crucial.
• Memory Management Options:
  • Heap Allocation: Memory allocation is handled by Rust’s allocator, ensuring all data resides in RAM.
  • Mmap: Data can be mapped to a disk file by the operating system, making it suitable for write-ahead-logs (WAL) and durable storage.
  • Mmap Anonymous: Mapped to anonymous memory (virtual memory) by the OS, ideal for large in-memory memtables, optimizing memory utilization.

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	✅

Pedigree

This code is inspired and modified based on Cockroachdb’s pebble arenaskl and Dgraph’s badger skl code:

https://github.com/cockroachdb/pebble/tree/master/internal/arenaskl

https://github.com/dgraph-io/badger/tree/master/skl

The pebble’s arenaskl code is based on Andy Kimball’s arenaskl code:

https://github.com/andy-kimball/arenaskl

The arenaskl code is based on the skiplist found in Badger, a Go-based KV store:

https://github.com/dgraph-io/badger/tree/master/skl

The skiplist in Badger is itself based on a C++ skiplist built for Facebook’s RocksDB:

https://github.com/facebook/rocksdb/tree/master/memtable

TODO (help wanted)

• make the crate test cases pass cargo loom

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.

Re-exports

• pub use map::MapIterator;
• pub use map::SkipMap;
• pub use set::SetIterator;
• pub use set::SkipSet;

Modules

• map
  A map implementation based on skiplist
• set
  A set implementation based on skiplist

Structs

• Arena
  Arena should be lock-free
• ArenaError
  An error indicating that the arena is full
• Ascend
  Ascend is a comparator that compares byte slices in ascending order.
• Descend
  Descend is a comparator that compares byte slices in descending order.
• MmapOptionsmemmap and non-target_family="wasm"
  A memory map options for file backed SkipMap and SkipSet, providing advanced options and flags for specifying memory map behavior.
• OccupiedValue
  An occupied value in the skiplist.
• OpenOptionsmemmap and non-target_family="wasm"
  Options for opening a file for memory mapping.
• TooLarge
  Returns when the bytes are too large to be written to the occupied value.

Traits

• Comparator
  Comparator is used for key-value database developers to define their own key comparison logic. e.g. some key-value database developers may want to alpabetically comparation
• Trailer
  A trait for extra information that can be stored with entry in the skiplist.