al8n / skl

A lock-free thread-safe arena based Skiplist impelementation for building memtable.

SKL

1. A lock-free thread-safe concurrent SkipMap 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.

Installation

• Only use heap backend (suppport no_std)

  [dependencies]
  skl = "0.13"

• Enable memory map backend

  [dependencies]
  skl = { version = "0.13", 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.
  • Segment tracker: Builtin segment recollection support, a lock-free freelist helps reuse free segments.
  • Prefix compression:
    • Same key will only be stored once.
    • Keys with common prefix will be stored once (longest one must be inserted first).
  • Discard tracker: Builtin discard tracker, which will track discarded bytes to help end-users decide when to compact or rewrite.
• 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.
• 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

License

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.

skl's Issues

Code review

Hi guys, I am a real newbie for writing lock-free data structure in Rust, really want someone can do a code review for me.

Thank you very much!

Fix `loom` tests

Currently, this crate cannot run loom testing because when there are too many CAS operations, the loom crate will lead to "stack overflow."

Make crossbeam-epoch based growable ARENA skiplist lock-free

Hi guys, in original Go implementation, because Go has garbage collection, it is very simple to implement a growable lock-free ARENA (directly replace the buffer with a new one), but in Rust, it becomes extremely difficult and I have to use a Mutex.

func (s *Arena) allocate(sz uint32) uint32 {
	offset := atomic.AddUint32(&s.n, sz)
	if !s.shouldGrow {
		y.AssertTrue(int(offset) <= len(s.buf))
		return offset - sz
	}

	// We are keeping extra bytes in the end so that the checkptr doesn't fail. We apply some
	// intelligence to reduce the size of the node by only keeping towers upto valid height and not
	// maxHeight. This reduces the node's size, but checkptr doesn't know about its reduced size.
	// checkptr tries to verify that the node of size MaxNodeSize resides on a single heap
	// allocation which causes this error: checkptr:converted pointer straddles multiple allocations
	if int(offset) > len(s.buf)-MaxNodeSize {
		growBy := uint32(len(s.buf))
		if growBy > 1<<30 {
			growBy = 1 << 30
		}
		if growBy < sz {
			growBy = sz
		}
		newBuf := make([]byte, len(s.buf)+int(growBy))
		y.AssertTrue(len(s.buf) == copy(newBuf, s.buf))
		s.buf = newBuf
	}
	return offset - sz
}

The Go version, lock-free growable ARENA source code is here:

• ARENA: https://github.com/dgraph-io/badger/blob/master/skl/arena.go
• Skiplist: https://github.com/dgraph-io/badger/blob/master/skl/skl.go

The Rust version lock-free(not lock-free in current implementation) growable ARENA source code is here:

• ARENA: https://github.com/al8n/skl-rs/blob/main/src/arena/epoch.rs
• Skiplist: https://github.com/al8n/skl-rs/blob/main/src/epoch.rs

I am a real newbie for writing lock-free data structure in Rust, really want someone can help me to complete this feature, or give me some instructions.

Thank you very much!

Pass `cargo miri test`

Make the project pass cargo miri tests