Expand description
SKL
- A lock-free thread-safe concurrent
SkipMap
implementation based on ARENA skiplist which helps develop MVCC memtable for LSM-Tree. - A lock-free thread-safe concurrent memory map based on-disk
SkipMap
.
§Installation
-
Only use heap backend (suppport
no_std
)[dependencies] skl = "0.10"
-
Enable memory map backend
[dependencies] skl = { version = "0.10", 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 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 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. Additionally, bounded iterators are supported, allowing you to traverse only a specified range of elements efficiently.
- Discard tracker: Builtin discard tracker to help decide when to compact or rewrite.
- Snapshot Support: Create snapshots of your SkipMap, 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::AllVersionsIter;
pub use map::SkipMap;
Modules§
- A map implementation based on skiplist
Structs§
- An error indicating that the arena is full
- Ascend is a comparator that compares byte slices in ascending order.
- Descend is a comparator that compares byte slices in descending order.
- MmapOptions
memmap
and non-target_family="wasm"
A memory map options for file backedSkipMap
, providing advanced options and flags for specifying memory map behavior. - OpenOptions
memmap
and non-target_family="wasm"
Options for opening a file for memory mapping. - Returns when the bytes are too large to be written to the vacant buffer.
- A vacant buffer in the skiplist.
Traits§
- 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
- A trait for extra information that can be stored with entry in the skiplist.