lsm_tree/
value.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::{key::InternalKey, Slice};
6
7/// User defined key
8pub type UserKey = Slice;
9
10/// User defined data (blob of bytes)
11#[allow(clippy::module_name_repetitions)]
12pub type UserValue = Slice;
13
14/// Sequence number - a monotonically increasing counter
15///
16/// Values with the same seqno are part of the same batch.
17///
18/// A value with a higher sequence number shadows an item with the
19/// same key and lower sequence number.
20/// This enables MVCC.
21///
22/// Stale items are lazily garbage-collected during compaction.
23pub type SeqNo = u64;
24
25/// Value type (regular value or tombstone)
26#[derive(Copy, Clone, Debug, Eq, PartialEq)]
27#[allow(clippy::module_name_repetitions)]
28pub enum ValueType {
29    /// Existing value
30    Value,
31
32    /// Deleted value
33    Tombstone,
34
35    /// "Weak" deletion (a.k.a. `SingleDelete` in `RocksDB`)
36    WeakTombstone,
37}
38
39impl TryFrom<u8> for ValueType {
40    type Error = ();
41
42    fn try_from(value: u8) -> Result<Self, Self::Error> {
43        match value {
44            0 => Ok(Self::Value),
45            1 => Ok(Self::Tombstone),
46            2 => Ok(Self::WeakTombstone),
47            _ => Err(()),
48        }
49    }
50}
51
52impl From<ValueType> for u8 {
53    fn from(value: ValueType) -> Self {
54        match value {
55            ValueType::Value => 0,
56            ValueType::Tombstone => 1,
57            ValueType::WeakTombstone => 2,
58        }
59    }
60}
61
62/// Internal representation of KV pairs
63#[allow(clippy::module_name_repetitions)]
64#[derive(Clone, Eq)]
65pub struct InternalValue {
66    /// Internal key
67    pub key: InternalKey,
68
69    /// User-defined value - an arbitrary byte array
70    ///
71    /// Supports up to 2^32 bytes
72    pub value: UserValue,
73}
74
75impl InternalValue {
76    /// Creates a new [`Value`].
77    ///
78    /// # Panics
79    ///
80    /// Panics if the key length is empty or greater than 2^16, or the value length is greater than 2^32.
81    pub fn new<V: Into<UserValue>>(key: InternalKey, value: V) -> Self {
82        let value = value.into();
83
84        assert!(!key.user_key.is_empty(), "key may not be empty");
85        assert!(
86            u32::try_from(value.len()).is_ok(),
87            "values can be 2^32 bytes in length"
88        );
89
90        Self { key, value }
91    }
92
93    /// Creates a new [`Value`].
94    ///
95    /// # Panics
96    ///
97    /// Panics if the key length is empty or greater than 2^16, or the value length is greater than 2^32.
98    pub fn from_components<K: Into<UserKey>, V: Into<UserValue>>(
99        user_key: K,
100        value: V,
101        seqno: SeqNo,
102        value_type: ValueType,
103    ) -> Self {
104        let key = InternalKey::new(user_key, seqno, value_type);
105        Self::new(key, value)
106    }
107
108    /// Creates a new tombstone.
109    ///
110    /// # Panics
111    ///
112    /// Panics if the key length is empty or greater than 2^16.
113    pub fn new_tombstone<K: Into<UserKey>>(key: K, seqno: u64) -> Self {
114        let key = InternalKey::new(key, seqno, ValueType::Tombstone);
115        Self::new(key, vec![])
116    }
117
118    /// Creates a new weak tombstone.
119    ///
120    /// # Panics
121    ///
122    /// Panics if the key length is empty or greater than 2^16.
123    pub fn new_weak_tombstone<K: Into<UserKey>>(key: K, seqno: u64) -> Self {
124        let key = InternalKey::new(key, seqno, ValueType::WeakTombstone);
125        Self::new(key, vec![])
126    }
127
128    #[doc(hidden)]
129    #[must_use]
130    pub fn is_tombstone(&self) -> bool {
131        self.key.is_tombstone()
132    }
133}
134
135impl PartialEq for InternalValue {
136    fn eq(&self, other: &Self) -> bool {
137        self.key == other.key
138    }
139}
140
141impl Ord for InternalValue {
142    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
143        self.key.cmp(&other.key)
144    }
145}
146
147impl PartialOrd for InternalValue {
148    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
149        Some(self.cmp(other))
150    }
151}
152
153impl std::fmt::Debug for InternalValue {
154    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
155        write!(
156            f,
157            "{:?} => {:?}",
158            self.key,
159            if self.value.len() >= 64 {
160                format!("[ ... {} bytes ]", self.value.len())
161            } else {
162                format!("{:?}", self.value)
163            }
164        )
165    }
166}
167
168#[cfg(test)]
169mod tests {
170    use super::*;
171    use test_log::test;
172
173    #[test]
174    fn pik_cmp_user_key() {
175        let a = InternalKey::new(*b"a", 0, ValueType::Value);
176        let b = InternalKey::new(*b"b", 0, ValueType::Value);
177        assert!(a < b);
178    }
179
180    #[test]
181    fn pik_cmp_seqno() {
182        let a = InternalKey::new(*b"a", 0, ValueType::Value);
183        let b = InternalKey::new(*b"a", 1, ValueType::Value);
184        assert!(a > b);
185    }
186}
lsm_tree/value.rs

lsm_tree/
value.rs
