lsm_tree/
merge_operator.rs

1// Copyright (c) 2024-present, fjall-rs
2// This source code is licensed under both the Apache 2.0 and MIT License
3// (found in the LICENSE-* files in the repository)
4
5use crate::UserValue;
6use std::panic::RefUnwindSafe;
7
8/// A user-defined merge operator for commutative LSM operations.
9///
10/// Merge operators enable efficient read-modify-write operations by storing
11/// partial updates (operands) that are lazily combined during reads and
12/// compaction, avoiding the need for explicit read-modify-write cycles.
13///
14/// # Implementor contract
15///
16/// The merge function must be **deterministic and stable across multiple
17/// passes**. The `base_value` may itself be the result of a previous merge
18/// (e.g., from compaction or an earlier read resolution) rather than the
19/// original stored value. Repeated merging must produce identical bytes
20/// for the same logical state.
21///
22/// # Examples
23///
24/// A simple counter merge operator that sums integer operands:
25///
26/// ```
27/// use lsm_tree::{MergeOperator, UserValue};
28///
29/// struct CounterMerge;
30///
31/// impl MergeOperator for CounterMerge {
32///     fn merge(
33///         &self,
34///         _key: &[u8],
35///         base_value: Option<&[u8]>,
36///         operands: &[&[u8]],
37///     ) -> lsm_tree::Result<UserValue> {
38///         let mut counter: i64 = match base_value {
39///             Some(bytes) if bytes.len() == 8 => i64::from_le_bytes(
40///                 bytes.try_into().expect("checked length"),
41///             ),
42///             Some(_) => return Err(lsm_tree::Error::MergeOperator),
43///             None => 0,
44///         };
45///
46///         for operand in operands {
47///             if operand.len() != 8 {
48///                 return Err(lsm_tree::Error::MergeOperator);
49///             }
50///             counter += i64::from_le_bytes(
51///                 (*operand).try_into().expect("checked length"),
52///             );
53///         }
54///
55///         Ok(counter.to_le_bytes().to_vec().into())
56///     }
57/// }
58/// ```
59pub trait MergeOperator: Send + Sync + RefUnwindSafe + 'static {
60    /// Merges operands with an optional base value.
61    ///
62    /// `key` is the user key being merged.
63    ///
64    /// `base_value` is the existing value for the key, or `None` if no base
65    /// value exists (e.g., the key was never written or was deleted). This
66    /// may already be the output of a previous `merge` call (after compaction
67    /// or an earlier read), so implementations must be stable when re-merging.
68    ///
69    /// `operands` contains the merge operand values in ascending sequence
70    /// number order (chronological — oldest first).
71    ///
72    /// Returns the merged value on success.
73    ///
74    /// # Errors
75    ///
76    /// Returns [`crate::Error::MergeOperator`] if the merge fails (e.g., corrupted
77    /// operand data).
78    fn merge(
79        &self,
80        key: &[u8],
81        base_value: Option<&[u8]>,
82        operands: &[&[u8]],
83    ) -> crate::Result<UserValue>;
84}
lsm_tree/merge_operator.rs

lsm_tree/
merge_operator.rs
