Module sled::doc::merge_operators [−][src]
Expand description
Merge operators are an extremely powerful tool for use in embedded kv stores. They allow users to specify custom logic for combining multiple versions of a value into one.
As a motivating example, imagine that you have a counter. In a traditional
kv store, you would need to read the old value, modify it, then write it
back (RMW). If you want to increment the counter from multiple threads, you
would need to either use higher-level locking or you need to spin in a CAS
loop until your increment is successful. Merge operators remove the need for
all of this by allowing multiple threads to “merge” in the desired
operation, rather than performing a read, then modification, then later
writing. +1 -> +1 -> +1
instead of w(r(key) + 1) -> w(r(key)+ 1) -> w(r(key) + 1)
.
Here’s an example of using a merge operator to just concatenate merged bytes
together. Note that calling set
acts as a value replacement, bypassing the
merging logic and replacing previously merged values. Calling merge
is
like set
but when the key is fetched, it will use the merge operator to
combine all merge
’s since the last set
.
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)
.build();
let tree = Tree::start(config).unwrap();
tree.set_merge_operator(concatenate_merge);
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])));
beyond the basics
Merge operators can be used to express arbitrarily complex logic. You can use them to implement any sort of high-level data structure on top of sled, using merges of different values to represent your desired operations. Similar to the above example, you could implement a list that lets you push items. Bloom filters are particularly easy to implement, and merge operators also are quite handy for building persistent CRDTs.
warnings
If you call merge
without setting a merge operator, an error will be
returned. Merge operators may be changed over time, but make sure you do
this carefully to avoid race conditions. If you need to push a one-time
operation to a value, use update_and_fetch
or fetch_and_update
instead.