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
74
75
76
77
78
79
80
81
82
83
84
// SPDX-License-Identifier: Apache-2.0
// Copyright (c) 2024-present, fjall-rs
// Copyright (c) 2026-present, Structured World Foundation
use crate::UserValue;
use std::panic::RefUnwindSafe;
/// A user-defined merge operator for commutative LSM operations.
///
/// Merge operators enable efficient read-modify-write operations by storing
/// partial updates (operands) that are lazily combined during reads and
/// compaction, avoiding the need for explicit read-modify-write cycles.
///
/// # Implementor contract
///
/// The merge function must be **deterministic and stable across multiple
/// passes**. The `base_value` may itself be the result of a previous merge
/// (e.g., from compaction or an earlier read resolution) rather than the
/// original stored value. Repeated merging must produce identical bytes
/// for the same logical state.
///
/// # Examples
///
/// A simple counter merge operator that sums integer operands:
///
/// ```
/// use lsm_tree::{MergeOperator, UserValue};
///
/// struct CounterMerge;
///
/// impl MergeOperator for CounterMerge {
/// fn merge(
/// &self,
/// _key: &[u8],
/// base_value: Option<&[u8]>,
/// operands: &[&[u8]],
/// ) -> lsm_tree::Result<UserValue> {
/// let mut counter: i64 = match base_value {
/// Some(bytes) if bytes.len() == 8 => i64::from_le_bytes(
/// bytes.try_into().expect("checked length"),
/// ),
/// Some(_) => return Err(lsm_tree::Error::MergeOperator),
/// None => 0,
/// };
///
/// for operand in operands {
/// if operand.len() != 8 {
/// return Err(lsm_tree::Error::MergeOperator);
/// }
/// counter += i64::from_le_bytes(
/// (*operand).try_into().expect("checked length"),
/// );
/// }
///
/// Ok(counter.to_le_bytes().to_vec().into())
/// }
/// }
/// ```
pub trait MergeOperator: Send + Sync + RefUnwindSafe + 'static {
/// Merges operands with an optional base value.
///
/// `key` is the user key being merged.
///
/// `base_value` is the existing value for the key, or `None` if no base
/// value exists (e.g., the key was never written or was deleted). This
/// may already be the output of a previous `merge` call (after compaction
/// or an earlier read), so implementations must be stable when re-merging.
///
/// `operands` contains the merge operand values in ascending sequence
/// number order (chronological — oldest first).
///
/// Returns the merged value on success.
///
/// # Errors
///
/// Returns [`crate::Error::MergeOperator`] if the merge fails (e.g., corrupted
/// operand data).
fn merge(
&self,
key: &[u8],
base_value: Option<&[u8]>,
operands: &[&[u8]],
) -> crate::Result<UserValue>;
}