1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73
//! 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`. //! //! ```rust //! 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.