spacekookie/sled

(alpha) modern embedded database

sled

An (alpha) modern embedded database.

extern crate sled;

use sled::Tree;

let tree = Tree::start_default(path)?;

// set and get
tree.set(k, v1);
assert_eq!(tree.get(&k), Ok(Some(v1)));

// compare and swap
tree.cas(k, Some(v1), Some(v2));

// scan forward
let mut iter = tree.scan(k);
assert_eq!(iter.next(), Some(Ok((k, v2))));
assert_eq!(iter.next(), None);

// deletion
tree.del(&k);

We also support merge operators.

fn concatenate_merge(
  _key: &[u8],               // the key being merged
  old_value: Option<&[u8]>,  // the previous value, if one existed
  merged_bytes: &[u8]        // the new bytes being merged in
) -> Option<Vec<u8>> {       // set the new value, return None to delete
  let mut ret = old_value
    .map(|ov| ov.to_vec())
    .unwrap_or_else(|| vec![]);

  ret.extend_from_slice(merged_bytes);

  Some(ret)
}

let config = ConfigBuilder::new()
  .temporary(true)
  .merge_operator(concatenate_merge)
  .build();

let tree = Tree::start(config).unwrap();

tree.set(k, vec![0]);
tree.merge(k, vec![1]);
tree.merge(k, vec![2]);
assert_eq!(tree.get(&k), Ok(Some(vec![0, 1, 2])));

// sets replace previously merged data,
// bypassing the merge function.
tree.set(k, vec![3]);
assert_eq!(tree.get(&k), Ok(Some(vec![3])));

// merges on non-present values will add them
tree.del(&k);
tree.merge(k, vec![4]);
assert_eq!(tree.get(&k), Ok(Some(vec![4])));

features

• ordered map API
• fully atomic single-key operations, supports CAS
• zero-copy reads
• merge operators
• zstd compression (use the zstd build feature)
• cpu-scalable lock-free implementation
• SSD-optimized log-structured storage

goals

1. don't make the user think. the interface should be obvious.
2. don't surprise users with performance traps.
3. don't wake up operators. bring reliability techniques from academia into real-world practice.
4. don't use so much electricity. our data structures should play to modern hardware's strengths.

plans

• LSM tree-like write performance with traditional B+ tree-like read performance
• MVCC, transactions, and snapshots
• forward-compatible binary format
• prefix subscription semantics
• concurrent snapshot delta generation and recovery
• first-class access to replication stream
• consensus protocol for PC/EC systems
• pluggable conflict detection and resolution strategies for PA/EL systems
• SQL support
• native bindings

known issues, warnings

• the on-disk format is going to change in non-forward compatible ways before the 1.0.0 release! after that, we will always support forward migrations.
• quite young, should be considered unstable for the time being
• the C API is likely to change rapidly
• writepath is not well optimized yet. readpath is essentially wait-free and zero-copy.
• 32 bit architectures require Rust nightly with the nightly feature enabled.

contribution welcome!

want to help advance the state of the art in open source embedded databases? check out CONTRIBUTING.md!

architecture

lock-free tree on a lock-free pagecache on a lock-free log. the pagecache scatters partial page fragments across the log, rather than rewriting entire pages at a time as B+ trees for spinning disks historically have. on page reads, we concurrently scatter-gather reads across the log to materialize the page from its fragments.

References

• The Bw-Tree: A B-tree for New Hardware Platforms
• LLAMA: A Cache/Storage Subsystem for Modern Hardware
• Cicada: Dependably Fast Multi-Core In-Memory Transactions
• The Design and Implementation of a Log-Structured File System