Struct sled::Tree [−][src]
pub struct Tree(_);
Expand description
A flash-sympathetic persistent lock-free B+ tree.
A Tree
represents a single logical keyspace / namespace / bucket.
Separate Trees
may be opened to separate concerns using
Db::open_tree
.
Db
implements Deref<Target = Tree>
such that a Db
acts
like the “default” Tree
. This is the only Tree
that cannot
be deleted via Db::drop_tree
.
Examples
use sled::IVec;
let db: sled::Db = sled::open("db")?;
db.insert(b"yo!", b"v1".to_vec());
assert_eq!(db.get(b"yo!"), Ok(Some(IVec::from(b"v1"))));
// Atomic compare-and-swap.
db.compare_and_swap(
b"yo!", // key
Some(b"v1"), // old value, None for not present
Some(b"v2"), // new value, None for delete
)?;
// Iterates over key-value pairs, starting at the given key.
let scan_key: &[u8] = b"a non-present key before yo!";
let mut iter = db.range(scan_key..);
assert_eq!(
iter.next().unwrap(),
Ok((IVec::from(b"yo!"), IVec::from(b"v2")))
);
assert_eq!(iter.next(), None);
db.remove(b"yo!");
assert_eq!(db.get(b"yo!"), Ok(None));
let other_tree: sled::Tree = db.open_tree(b"cool db facts")?;
other_tree.insert(
b"k1",
&b"a Db acts like a Tree due to implementing Deref<Target = Tree>"[..]
)?;
Implementations
Insert a key to a new value, returning the last value if it was set.
Examples
assert_eq!(db.insert(&[1, 2, 3], vec![0]), Ok(None));
assert_eq!(db.insert(&[1, 2, 3], vec![1]), Ok(Some(sled::IVec::from(&[0]))));
pub fn transaction<F, A, E>(&self, f: F) -> TransactionResult<A, E> where
F: Fn(&TransactionalTree) -> ConflictableTransactionResult<A, E>,
pub fn transaction<F, A, E>(&self, f: F) -> TransactionResult<A, E> where
F: Fn(&TransactionalTree) -> ConflictableTransactionResult<A, E>,
Perform a multi-key serializable transaction.
Examples
// Use write-only transactions as a writebatch:
db.transaction(|tx_db| {
tx_db.insert(b"k1", b"cats")?;
tx_db.insert(b"k2", b"dogs")?;
Ok(())
})?;
// Atomically swap two items:
db.transaction(|tx_db| {
let v1_option = tx_db.remove(b"k1")?;
let v1 = v1_option.unwrap();
let v2_option = tx_db.remove(b"k2")?;
let v2 = v2_option.unwrap();
tx_db.insert(b"k1", v2)?;
tx_db.insert(b"k2", v1)?;
Ok(())
})?;
assert_eq!(&db.get(b"k1")?.unwrap(), b"dogs");
assert_eq!(&db.get(b"k2")?.unwrap(), b"cats");
A transaction may return information from an intentionally-cancelled transaction by using the abort function inside the closure in combination with the try operator.
use sled::{transaction::{abort, TransactionError, TransactionResult}, Config};
#[derive(Debug, PartialEq)]
struct MyBullshitError;
fn main() -> TransactionResult<(), MyBullshitError> {
let config = Config::new().temporary(true);
let db = config.open()?;
// Use write-only transactions as a writebatch:
let res = db.transaction(|tx_db| {
tx_db.insert(b"k1", b"cats")?;
tx_db.insert(b"k2", b"dogs")?;
// aborting will cause all writes to roll-back.
if true {
abort(MyBullshitError)?;
}
Ok(42)
}).unwrap_err();
assert_eq!(res, TransactionError::Abort(MyBullshitError));
assert_eq!(db.get(b"k1")?, None);
assert_eq!(db.get(b"k2")?, None);
Ok(())
}
Transactions also work on tuples of Tree
s,
preserving serializable ACID semantics!
In this example, we treat two trees like a
work queue, atomically apply updates to
data and move them from the unprocessed Tree
to the processed Tree
.
use sled::Transactional;
let unprocessed = db.open_tree(b"unprocessed items")?;
let processed = db.open_tree(b"processed items")?;
// An update somehow gets into the tree, which we
// later trigger the atomic processing of.
unprocessed.insert(b"k3", b"ligers")?;
// Atomically process the new item and move it
// between `Tree`s.
(&unprocessed, &processed)
.transaction(|(tx_unprocessed, tx_processed)| {
let unprocessed_item = tx_unprocessed.remove(b"k3")?.unwrap();
let mut processed_item = b"yappin' ".to_vec();
processed_item.extend_from_slice(&unprocessed_item);
tx_processed.insert(b"k3", processed_item)?;
Ok(())
})?;
assert_eq!(unprocessed.get(b"k3").unwrap(), None);
assert_eq!(&processed.get(b"k3").unwrap().unwrap(), b"yappin' ligers");
Create a new batched update that can be atomically applied.
It is possible to apply a Batch
in a transaction
as well, which is the way you can apply a Batch
to multiple Tree
s atomically.
Examples
db.insert("key_0", "val_0")?;
let mut batch = sled::Batch::default();
batch.insert("key_a", "val_a");
batch.insert("key_b", "val_b");
batch.insert("key_c", "val_c");
batch.remove("key_0");
db.apply_batch(batch)?;
// key_0 no longer exists, and key_a, key_b, and key_c
// now do exist.
Retrieve a value from the Tree
if it exists.
Examples
db.insert(&[0], vec![0])?;
assert_eq!(db.get(&[0]), Ok(Some(sled::IVec::from(vec![0]))));
assert_eq!(db.get(&[1]), Ok(None));
Delete a value, returning the old value if it existed.
Examples
db.insert(&[1], vec![1]);
assert_eq!(db.remove(&[1]), Ok(Some(sled::IVec::from(vec![1]))));
assert_eq!(db.remove(&[1]), Ok(None));
Compare and swap. Capable of unique creation, conditional modification,
or deletion. If old is None
, this will only set the value if it
doesn’t exist yet. If new is None
, will delete the value if old is
correct. If both old and new are Some
, will modify the value if
old is correct.
It returns Ok(Ok(()))
if operation finishes successfully.
If it fails it returns:
- Ok(Err(CompareAndSwapError(current, proposed)))
if operation
failed to setup a new value. CompareAndSwapError
contains
current and proposed values.
- Err(Error::Unsupported)
if the database is opened in read-only
mode.
Examples
// unique creation
assert_eq!(
db.compare_and_swap(&[1], None as Option<&[u8]>, Some(&[10])),
Ok(Ok(()))
);
// conditional modification
assert_eq!(
db.compare_and_swap(&[1], Some(&[10]), Some(&[20])),
Ok(Ok(()))
);
// failed conditional modification -- the current value is returned in
// the error variant
let operation = db.compare_and_swap(&[1], Some(&[30]), Some(&[40]));
assert!(operation.is_ok()); // the operation succeeded
let modification = operation.unwrap();
assert!(modification.is_err());
let actual_value = modification.unwrap_err();
assert_eq!(actual_value.current.map(|ivec| ivec.to_vec()), Some(vec![20]));
// conditional deletion
assert_eq!(
db.compare_and_swap(&[1], Some(&[20]), None as Option<&[u8]>),
Ok(Ok(()))
);
assert_eq!(db.get(&[1]), Ok(None));
Fetch the value, apply a function to it and return the result.
Note
This may call the function multiple times if the value has been changed from other threads in the meantime.
Examples
use sled::{Config, Error, IVec};
use std::convert::TryInto;
let config = Config::new().temporary(true);
let db = config.open()?;
fn u64_to_ivec(number: u64) -> IVec {
IVec::from(number.to_be_bytes().to_vec())
}
let zero = u64_to_ivec(0);
let one = u64_to_ivec(1);
let two = u64_to_ivec(2);
let three = u64_to_ivec(3);
fn increment(old: Option<&[u8]>) -> Option<Vec<u8>> {
let number = match old {
Some(bytes) => {
let array: [u8; 8] = bytes.try_into().unwrap();
let number = u64::from_be_bytes(array);
number + 1
}
None => 0,
};
Some(number.to_be_bytes().to_vec())
}
assert_eq!(db.update_and_fetch("counter", increment), Ok(Some(zero)));
assert_eq!(db.update_and_fetch("counter", increment), Ok(Some(one)));
assert_eq!(db.update_and_fetch("counter", increment), Ok(Some(two)));
assert_eq!(db.update_and_fetch("counter", increment), Ok(Some(three)));
Fetch the value, apply a function to it and return the previous value.
Note
This may call the function multiple times if the value has been changed from other threads in the meantime.
Examples
use sled::{Config, Error, IVec};
use std::convert::TryInto;
let config = Config::new().temporary(true);
let db = config.open()?;
fn u64_to_ivec(number: u64) -> IVec {
IVec::from(number.to_be_bytes().to_vec())
}
let zero = u64_to_ivec(0);
let one = u64_to_ivec(1);
let two = u64_to_ivec(2);
fn increment(old: Option<&[u8]>) -> Option<Vec<u8>> {
let number = match old {
Some(bytes) => {
let array: [u8; 8] = bytes.try_into().unwrap();
let number = u64::from_be_bytes(array);
number + 1
}
None => 0,
};
Some(number.to_be_bytes().to_vec())
}
assert_eq!(db.fetch_and_update("counter", increment), Ok(None));
assert_eq!(db.fetch_and_update("counter", increment), Ok(Some(zero)));
assert_eq!(db.fetch_and_update("counter", increment), Ok(Some(one)));
assert_eq!(db.fetch_and_update("counter", increment), Ok(Some(two)));
pub fn watch_prefix<P: AsRef<[u8]>>(&self, prefix: P) -> SubscriberⓘNotable traits for Subscriberimpl Iterator for Subscriber type Item = Event;impl Future for Subscriber type Output = Option<Event>;
pub fn watch_prefix<P: AsRef<[u8]>>(&self, prefix: P) -> SubscriberⓘNotable traits for Subscriberimpl Iterator for Subscriber type Item = Event;impl Future for Subscriber type Output = Option<Event>;
impl Iterator for Subscriber type Item = Event;impl Future for Subscriber type Output = Option<Event>;
Subscribe to Event
s that happen to keys that have
the specified prefix. Events for particular keys are
guaranteed to be witnessed in the same order by all
threads, but threads may witness different interleavings
of Event
s across different keys. If subscribers don’t
keep up with new writes, they will cause new writes
to block. There is a buffer of 1024 items per
Subscriber
. This can be used to build reactive
and replicated systems.
Subscriber
implements both Iterator<Item = Event>
and Future<Output=Option<Event>>
Examples
Synchronous, blocking subscriber:
// watch all events by subscribing to the empty prefix
let mut subscriber = db.watch_prefix(vec![]);
let tree_2 = db.clone();
let thread = std::thread::spawn(move || {
db.insert(vec![0], vec![1])
});
// `Subscription` implements `Iterator<Item=Event>`
for event in subscriber.take(1) {
match event {
sled::Event::Insert{ key, value } => assert_eq!(key.as_ref(), &[0]),
sled::Event::Remove {key } => {}
}
}
Aynchronous, non-blocking subscriber:
Subscription
implements Future<Output=Option<Event>>
.
while let Some(event) = (&mut subscriber).await { /* use it */ }
Synchronously flushes all dirty IO buffers and calls fsync. If this succeeds, it is guaranteed that all previous writes will be recovered if the system crashes. Returns the number of bytes flushed during this call.
Flushing can take quite a lot of time, and you should measure the performance impact of using it on realistic sustained workloads running on realistic hardware.
Asynchronously flushes all dirty IO buffers and calls fsync. If this succeeds, it is guaranteed that all previous writes will be recovered if the system crashes. Returns the number of bytes flushed during this call.
Flushing can take quite a lot of time, and you should measure the performance impact of using it on realistic sustained workloads running on realistic hardware.
Returns true
if the Tree
contains a value for
the specified key.
Examples
db.insert(&[0], vec![0])?;
assert!(db.contains_key(&[0])?);
assert!(!db.contains_key(&[1])?);
Retrieve the key and value before the provided key, if one exists.
Examples
use sled::IVec;
for i in 0..10 {
db.insert(&[i], vec![i])
.expect("should write successfully");
}
assert_eq!(db.get_lt(&[]), Ok(None));
assert_eq!(db.get_lt(&[0]), Ok(None));
assert_eq!(
db.get_lt(&[1]),
Ok(Some((IVec::from(&[0]), IVec::from(&[0]))))
);
assert_eq!(
db.get_lt(&[9]),
Ok(Some((IVec::from(&[8]), IVec::from(&[8]))))
);
assert_eq!(
db.get_lt(&[10]),
Ok(Some((IVec::from(&[9]), IVec::from(&[9]))))
);
assert_eq!(
db.get_lt(&[255]),
Ok(Some((IVec::from(&[9]), IVec::from(&[9]))))
);
Retrieve the next key and value from the Tree
after the
provided key.
Note
The order follows the Ord implementation for Vec<u8>
:
[] < [0] < [255] < [255, 0] < [255, 255] ...
To retain the ordering of numerical types use big endian reprensentation
Examples
use sled::IVec;
for i in 0..10 {
db.insert(&[i], vec![i])?;
}
assert_eq!(
db.get_gt(&[]),
Ok(Some((IVec::from(&[0]), IVec::from(&[0]))))
);
assert_eq!(
db.get_gt(&[0]),
Ok(Some((IVec::from(&[1]), IVec::from(&[1]))))
);
assert_eq!(
db.get_gt(&[1]),
Ok(Some((IVec::from(&[2]), IVec::from(&[2]))))
);
assert_eq!(
db.get_gt(&[8]),
Ok(Some((IVec::from(&[9]), IVec::from(&[9]))))
);
assert_eq!(db.get_gt(&[9]), Ok(None));
db.insert(500u16.to_be_bytes(), vec![10]);
assert_eq!(
db.get_gt(&499u16.to_be_bytes()),
Ok(Some((IVec::from(&500u16.to_be_bytes()), IVec::from(&[10]))))
);
Merge state directly into a given key’s value using the configured merge operator. This allows state to be written into a value directly, without any read-modify-write steps. Merge operators can be used to implement arbitrary data structures.
Calling merge
will return an Unsupported
error if it
is called without first setting a merge operator function.
Merge operators are shared by all instances of a particular
Tree
. Different merge operators may be set on different
Tree
s.
Examples
use sled::IVec;
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)
}
db.set_merge_operator(concatenate_merge);
let k = b"k1";
db.insert(k, vec![0]);
db.merge(k, vec![1]);
db.merge(k, vec![2]);
assert_eq!(db.get(k), Ok(Some(IVec::from(vec![0, 1, 2]))));
// Replace previously merged data. The merge function will not be called.
db.insert(k, vec![3]);
assert_eq!(db.get(k), Ok(Some(IVec::from(vec![3]))));
// Merges on non-present values will cause the merge function to be called
// with `old_value == None`. If the merge function returns something (which it
// does, in this case) a new value will be inserted.
db.remove(k);
db.merge(k, vec![4]);
assert_eq!(db.get(k), Ok(Some(IVec::from(vec![4]))));
Sets a merge operator for use with the merge
function.
Merge state directly into a given key’s value using the configured merge operator. This allows state to be written into a value directly, without any read-modify-write steps. Merge operators can be used to implement arbitrary data structures.
Panics
Calling merge
will panic if no merge operator has been
configured.
Examples
use sled::IVec;
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)
}
db.set_merge_operator(concatenate_merge);
let k = b"k1";
db.insert(k, vec![0]);
db.merge(k, vec![1]);
db.merge(k, vec![2]);
assert_eq!(db.get(k), Ok(Some(IVec::from(vec![0, 1, 2]))));
// Replace previously merged data. The merge function will not be called.
db.insert(k, vec![3]);
assert_eq!(db.get(k), Ok(Some(IVec::from(vec![3]))));
// Merges on non-present values will cause the merge function to be called
// with `old_value == None`. If the merge function returns something (which it
// does, in this case) a new value will be inserted.
db.remove(k);
db.merge(k, vec![4]);
assert_eq!(db.get(k), Ok(Some(IVec::from(vec![4]))));
Create a double-ended iterator over the tuples of keys and values in this tree.
Examples
use sled::IVec;
db.insert(&[1], vec![10]);
db.insert(&[2], vec![20]);
db.insert(&[3], vec![30]);
let mut iter = db.iter();
assert_eq!(
iter.next().unwrap(),
Ok((IVec::from(&[1]), IVec::from(&[10])))
);
assert_eq!(
iter.next().unwrap(),
Ok((IVec::from(&[2]), IVec::from(&[20])))
);
assert_eq!(
iter.next().unwrap(),
Ok((IVec::from(&[3]), IVec::from(&[30])))
);
assert_eq!(iter.next(), None);
Create a double-ended iterator over tuples of keys and values, where the keys fall within the specified range.
Examples
use sled::IVec;
db.insert(&[0], vec![0])?;
db.insert(&[1], vec![10])?;
db.insert(&[2], vec![20])?;
db.insert(&[3], vec![30])?;
db.insert(&[4], vec![40])?;
db.insert(&[5], vec![50])?;
let start: &[u8] = &[2];
let end: &[u8] = &[4];
let mut r = db.range(start..end);
assert_eq!(r.next().unwrap(), Ok((IVec::from(&[2]), IVec::from(&[20]))));
assert_eq!(r.next().unwrap(), Ok((IVec::from(&[3]), IVec::from(&[30]))));
assert_eq!(r.next(), None);
let mut r = db.range(start..end).rev();
assert_eq!(r.next().unwrap(), Ok((IVec::from(&[3]), IVec::from(&[30]))));
assert_eq!(r.next().unwrap(), Ok((IVec::from(&[2]), IVec::from(&[20]))));
assert_eq!(r.next(), None);
Create an iterator over tuples of keys and values, where the all the keys starts with the given prefix.
Examples
use sled::IVec;
db.insert(&[0, 0, 0], vec![0, 0, 0])?;
db.insert(&[0, 0, 1], vec![0, 0, 1])?;
db.insert(&[0, 0, 2], vec![0, 0, 2])?;
db.insert(&[0, 0, 3], vec![0, 0, 3])?;
db.insert(&[0, 1, 0], vec![0, 1, 0])?;
db.insert(&[0, 1, 1], vec![0, 1, 1])?;
let prefix: &[u8] = &[0, 0];
let mut r = db.scan_prefix(prefix);
assert_eq!(
r.next(),
Some(Ok((IVec::from(&[0, 0, 0]), IVec::from(&[0, 0, 0]))))
);
assert_eq!(
r.next(),
Some(Ok((IVec::from(&[0, 0, 1]), IVec::from(&[0, 0, 1]))))
);
assert_eq!(
r.next(),
Some(Ok((IVec::from(&[0, 0, 2]), IVec::from(&[0, 0, 2]))))
);
assert_eq!(
r.next(),
Some(Ok((IVec::from(&[0, 0, 3]), IVec::from(&[0, 0, 3]))))
);
assert_eq!(r.next(), None);
Returns the first key and value in the Tree
, or
None
if the Tree
is empty.
Returns the last key and value in the Tree
, or
None
if the Tree
is empty.
Atomically removes the maximum item in the Tree
instance.
Examples
db.insert(&[0], vec![0])?;
db.insert(&[1], vec![10])?;
db.insert(&[2], vec![20])?;
db.insert(&[3], vec![30])?;
db.insert(&[4], vec![40])?;
db.insert(&[5], vec![50])?;
assert_eq!(&db.pop_max()?.unwrap().0, &[5]);
assert_eq!(&db.pop_max()?.unwrap().0, &[4]);
assert_eq!(&db.pop_max()?.unwrap().0, &[3]);
assert_eq!(&db.pop_max()?.unwrap().0, &[2]);
assert_eq!(&db.pop_max()?.unwrap().0, &[1]);
assert_eq!(&db.pop_max()?.unwrap().0, &[0]);
assert_eq!(db.pop_max()?, None);
Atomically removes the minimum item in the Tree
instance.
Examples
db.insert(&[0], vec![0])?;
db.insert(&[1], vec![10])?;
db.insert(&[2], vec![20])?;
db.insert(&[3], vec![30])?;
db.insert(&[4], vec![40])?;
db.insert(&[5], vec![50])?;
assert_eq!(&db.pop_min()?.unwrap().0, &[0]);
assert_eq!(&db.pop_min()?.unwrap().0, &[1]);
assert_eq!(&db.pop_min()?.unwrap().0, &[2]);
assert_eq!(&db.pop_min()?.unwrap().0, &[3]);
assert_eq!(&db.pop_min()?.unwrap().0, &[4]);
assert_eq!(&db.pop_min()?.unwrap().0, &[5]);
assert_eq!(db.pop_min()?, None);
Returns the number of elements in this tree.
Beware: performs a full O(n) scan under the hood.
Examples
db.insert(b"a", vec![0]);
db.insert(b"b", vec![1]);
assert_eq!(db.len(), 2);
Clears the Tree
, removing all values.
Note that this is not atomic.
Trait Implementations
type View = TransactionalTree
type View = TransactionalTree
An internal reference to an internal proxy type that mediates transactional reads and writes. Read more
An internal function for creating a top-level transactional structure. Read more
An internal function for viewing the transactional subcomponents based on the top-level transactional structure. Read more
fn transaction<F, A>(&self, f: F) -> TransactionResult<A, E> where
F: Fn(&Self::View) -> ConflictableTransactionResult<A, E>,
fn transaction<F, A>(&self, f: F) -> TransactionResult<A, E> where
F: Fn(&Self::View) -> ConflictableTransactionResult<A, E>,
Runs a transaction, possibly retrying the passed-in closure if a concurrent conflict is detected that would cause a violation of serializability. This is the only trait method that you’re most likely to use directly. Read more
type View = TransactionalTree
type View = TransactionalTree
An internal reference to an internal proxy type that mediates transactional reads and writes. Read more
An internal function for creating a top-level transactional structure. Read more
An internal function for viewing the transactional subcomponents based on the top-level transactional structure. Read more
fn transaction<F, A>(&self, f: F) -> TransactionResult<A, E> where
F: Fn(&Self::View) -> ConflictableTransactionResult<A, E>,
fn transaction<F, A>(&self, f: F) -> TransactionResult<A, E> where
F: Fn(&Self::View) -> ConflictableTransactionResult<A, E>,
Runs a transaction, possibly retrying the passed-in closure if a concurrent conflict is detected that would cause a violation of serializability. This is the only trait method that you’re most likely to use directly. Read more
Auto Trait Implementations
Blanket Implementations
Mutably borrows from an owned value. Read more