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 the SkipMap and SkipSet
  • Support specify max key size and max value size
  • Support set the max height

v0.9.0

Changes

• Make file backed mmap SkipMap and SkipSet 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 use Arc wrapper anymore.
• Add OpenOptions and MmapOptions to support better controls on file mmap backed SkipMap and SkipSet.

v0.8.0

Changes

• Make SkipMap::insert and SkipSet::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 for MapIterator and SetIterator.
• Optimize Arena::alloc logic.
• Change mmap related API.
• Support open existing SkipMap and SkipSet 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

• Refactor the project
• Pass cargo miri

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