Releases: al8n/skl
Releases · al8n/skl
v0.11.0
Changes
- Refactor and extract lock-free ARENA allocator implementation to
rarena-allocator
crate.- Add an ordered linked list to track segments.
- Increase maximum key size to
u27::MAX
- Support key prefix compression
- Support version compatibility check
- Add
Options
as a parameter when constructing theSkipMap
andSkipSet
- Support specify max key size and max value size
- Support set the max height
v0.9.0
Changes
- Make file backed mmap
SkipMap
andSkipSet
still can be reopened even last time the program was aborted. - Remove checksum validation, users should take care of data integrity by themselves.
- Support
Clone
directly, no need to useArc
wrapper anymore. - Add
OpenOptions
andMmapOptions
to support better controls on file mmap backedSkipMap
andSkipSet
.
v0.8.0
Changes
- Make
SkipMap::insert
andSkipSet::insert
return the current value if the key and trailer already exist. - Add the
SkipMap::insert_with
method to support inserting an occupied key first, then write the value in the closure semantic. - Implement
Iterator
trait forMapIterator
andSetIterator
. - Optimize
Arena::alloc
logic. - Change mmap related API.
- Support open existing
SkipMap
andSkipSet
files in read-only mode.
v0.5.0
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.
Example
use skl::SkipMap;
use std::sync::Arc;
pub fn key(i: usize) -> Vec<u8> {
format!("{:05}", i).into_bytes()
}
pub fn new_value(i: usize) -> Vec<u8> {
format!("{:05}", i).into_bytes()
}
fn main() {
const N: usize = 1000;
let l = Arc::new(SkipMap::new(1 << 20).unwrap());
let wg = Arc::new(());
for i in 0..N {
let w = wg.clone();
let l = l.clone();
std::thread::spawn(move || {
l.insert(0, &key(i), &new_value(i)).unwrap();
drop(w);
});
}
while Arc::strong_count(&wg) > 1 {}
for i in 0..N {
let w = wg.clone();
let l = l.clone();
std::thread::spawn(move || {
let k = key(i);
assert_eq!(l.get(0, &k).unwrap().value(), new_value(i), "broken: {i}");
drop(w);
});
}
}
v0.3.0
skl-rs v0.2
A lock-free thread-safe skiplist implementation (no_std) for writing memory table, SST table, or something else. skl-rs is a pure Rust implementation for https://github.com/dgraph-io/badger/tree/master/skl