merge operators

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 add merged bytes together. Not 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)
  .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])));

warnings

If you start a database using a merge operator, you will always need to provide one in the future. If you call merge without setting a merge operator, an error will be returned.