Crates.io | skl |
lib.rs | skl |
version | |
source | src |
created_at | 2021-10-25 16:06:27.830038 |
updated_at | 2024-11-12 09:55:39.63402 |
description | A lock-free thread-safe concurrent ARENA based (heap backend or memory map backend) skiplist implementation which helps develop MVCC memtable for LSM-Tree. |
homepage | https://github.com/al8n/skl |
repository | https://github.com/al8n/skl |
max_upload_size | |
id | 471036 |
Cargo.toml error: | TOML parse error at line 18, column 1 | 18 | autolib = false | ^^^^^^^ unknown field `autolib`, expected one of `name`, `version`, `edition`, `authors`, `description`, `readme`, `license`, `repository`, `homepage`, `documentation`, `build`, `resolver`, `links`, `default-run`, `default_dash_run`, `rust-version`, `rust_dash_version`, `rust_version`, `license-file`, `license_dash_file`, `license_file`, `licenseFile`, `license_capital_file`, `forced-target`, `forced_dash_target`, `autobins`, `autotests`, `autoexamples`, `autobenches`, `publish`, `metadata`, `keywords`, `categories`, `exclude`, `include` |
size | 0 |
SkipMap
implementation based on ARENA skiplist which helps develop MVCC memtable for LSM-Tree.SkipMap
.Only use heap backend (suppport no_std
)
[dependencies]
skl = "0.20"
Enable memory map backend
[dependencies]
skl = { version = "0.20", features = ["memmap"] }
SkipMap
provide lock-free operations, ensuring efficient concurrent access without the need for explicit locking mechanisms.SkipMap
offer a flexible foundation for key-value database developers. You can easily build your own memtable or durable storage using these structures.CompressionPolicy::High
).SkipMap
. Additionally, bounded iterators are supported, allowing you to traverse only a specified range of elements efficiently.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.Please see examples folder for more details.
Does the on-disk version SkipMap
ensure crash safety or power failure resilience?
No, If you really need a crash safe, power failure resilience, concurrent-safe and durable ordered write-ahead log implementation,
see orderwal
project.
On-disk version SkipMap
does not ensure crash safety or power failure resilience. Hence, it is not recommended to directly
use the SkipMap
as a durable database. It is recommended to use the on-disk version SkipMap
as a final frozen file for quick lookup.
aol
: Yet another generic purpose, append-only write-ahead log implementation.orderwal
: A generic-purpose, atomic, ordered, zero-copy, concurrent-safe, pre-allocate style (memory map) write-ahead-log for developing databases.test
:
cargo test --all-features
miri
(Stack Borrows)
MIRIFLAGS="-Zmiri-strict-provenance -Zmiri-disable-isolation -Zmiri-symbolic-alignment-check" \
RUSTFLAGS = "--cfg all_skl_tests" \
cargo miri test --all-features
miri
(Tree Borrows)
MIRIFLAGS="-Zmiri-strict-provenance -Zmiri-disable-isolation -Zmiri-symbolic-alignment-check -Zmiri-tree-borrows" \
RUSTFLAGS = "--cfg all_skl_tests" \
cargo miri test --all-features
See cross
section in GitHub CI file.
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
skl
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.