reddb_engine/storage/btree/
value_layout.rs

1//! Large-value layout for B-tree leaf cells (slice E of PRD #662).
2//!
3//! Wires the standalone slice modules together at the write/read boundary:
4//!
5//! - [`value_codec`] (slice A, #698) decides whether the bytes are worth
6//!   compressing.
7//! - [`OverflowChain`] (slice B, #699) owns the chain of dedicated overflow
8//!   pages.
9//! - `reddb-file` pins the persisted two-bit `(pointer, compressed)` cell
10//!   shape and pointer payload encoding.
11//!
12//! The function entry points are [`encode`] and [`decode`]. They persist
13//! opaque cell bytes whose on-disk shape is owned by `reddb-file`.
14//!
15//! Decision ladder applied by [`encode`]:
16//!
17//! 1. `value.len() > MAX_VALUE_SIZE` → [`ValueLayoutError::ValueTooLarge`]
18//!    (no allocation, no LZ4 work).
19//! 2. `value.len() <= COMPRESSION_THRESHOLD` → inline raw.
20//! 3. Else try LZ4. If the selected raw/compressed bytes fit the native
21//!    leaf's `OVERFLOW_THRESHOLD` → inline with the matching flag.
22//! 4. Else spill via [`OverflowChain`], storing only the pointer in the
23//!    leaf cell.
24//!
25//! Per ADR 0025 (overflow chain MVCC) the chain identity is anchored at
26//! the leaf cell, so this slice does not add any WAL records of its own
27//! — the overflow page writes go through the existing pager path.
28
29use crate::storage::overflow::{OverflowChain, OverflowError};
30use crate::storage::page_store::PageStore;
31use reddb_file::vector_value_codec as value_codec;
32use reddb_file::BTreeValueCell;
33
34/// Encoded values up to this size share a native leaf, raw or compressed.
35/// Larger values spill via [`OverflowChain`] (ADR 0023).
36pub const OVERFLOW_THRESHOLD: usize = reddb_file::BTREE_VALUE_OVERFLOW_THRESHOLD;
37
38/// Preserve compression above the established 1-KiB raw fast path.
39pub const COMPRESSION_THRESHOLD: usize = reddb_file::BTREE_VALUE_COMPRESSION_THRESHOLD;
40
41/// Hard upper bound on logical value size. Values above this are
42/// rejected before any LZ4 or overflow work runs.
43/// 2^28 = 256 MiB per ADR 0023.
44pub const MAX_VALUE_SIZE: usize = reddb_file::BTREE_VALUE_MAX_SIZE;
45
46/// Total stored bytes for a pointer cell — flag byte + payload.
47pub const POINTER_CELL_LEN: usize = reddb_file::BTREE_VALUE_POINTER_CELL_LEN;
48
49/// Errors returned by [`encode`] and [`decode`].
50#[derive(Debug)]
51pub enum ValueLayoutError {
52    /// Logical value length exceeds [`MAX_VALUE_SIZE`].
53    ValueTooLarge(usize),
54    /// Stored cell flag byte sets a reserved bit.
55    UnknownFlag(u8),
56    /// Stored bytes ended before the expected pointer payload.
57    TruncatedPointer { got: usize },
58    /// LZ4 decode failed.
59    Codec(value_codec::ValueCodecError),
60    /// Overflow chain operation failed.
61    Overflow(OverflowError),
62    /// Decode scratch plus output would exceed the read's memory allowance.
63    ReadLimitExceeded {
64        required_bytes: usize,
65        limit_bytes: usize,
66    },
67}
68
69impl std::fmt::Display for ValueLayoutError {
70    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
71        match self {
72            Self::ValueTooLarge(n) => {
73                write!(f, "value too large: {} bytes (max {})", n, MAX_VALUE_SIZE)
74            }
75            Self::UnknownFlag(b) => write!(f, "unknown leaf-cell flag byte: 0b{:08b}", b),
76            Self::TruncatedPointer { got } => {
77                write!(
78                    f,
79                    "pointer cell truncated: need {} bytes after flag, got {}",
80                    POINTER_CELL_LEN - 1,
81                    got
82                )
83            }
84            Self::Codec(e) => write!(f, "value codec: {}", e),
85            Self::Overflow(e) => write!(f, "overflow chain: {}", e),
86            Self::ReadLimitExceeded {
87                required_bytes,
88                limit_bytes,
89            } => write!(
90                f,
91                "read needs {required_bytes} bytes over read memory limit {limit_bytes}"
92            ),
93        }
94    }
95}
96
97impl std::error::Error for ValueLayoutError {}
98
99impl From<value_codec::ValueCodecError> for ValueLayoutError {
100    fn from(e: value_codec::ValueCodecError) -> Self {
101        Self::Codec(e)
102    }
103}
104
105impl From<reddb_file::BTreeValueCellError> for ValueLayoutError {
106    fn from(e: reddb_file::BTreeValueCellError) -> Self {
107        match e {
108            reddb_file::BTreeValueCellError::UnknownFlag(flag) => Self::UnknownFlag(flag),
109            reddb_file::BTreeValueCellError::TruncatedPointer { got } => {
110                Self::TruncatedPointer { got }
111            }
112        }
113    }
114}
115
116impl From<OverflowError> for ValueLayoutError {
117    fn from(e: OverflowError) -> Self {
118        Self::Overflow(e)
119    }
120}
121
122/// Encode only when the result fits in a leaf, without allocating pages.
123pub(crate) fn encode_inline_without_pages(
124    value: &[u8],
125) -> Result<Option<Vec<u8>>, ValueLayoutError> {
126    if value.len() > MAX_VALUE_SIZE {
127        return Err(ValueLayoutError::ValueTooLarge(value.len()));
128    }
129    if value.len() <= COMPRESSION_THRESHOLD {
130        return Ok(Some(reddb_file::encode_btree_inline_raw(value)));
131    }
132    let (flag, bytes) = value_codec::encode(value);
133    if bytes.len() <= OVERFLOW_THRESHOLD {
134        return Ok(Some(match flag {
135            value_codec::ValueFlag::Raw => reddb_file::encode_btree_inline_raw(&bytes),
136            value_codec::ValueFlag::Lz4 => reddb_file::encode_btree_inline_compressed(&bytes),
137        }));
138    }
139    Ok(None)
140}
141
142/// Apply the decision ladder and return the bytes the B-tree should
143/// persist in the leaf cell value slot. May allocate overflow pages
144/// through `pager`.
145pub fn encode<P: PageStore>(pager: &P, value: &[u8]) -> Result<Vec<u8>, ValueLayoutError> {
146    if value.len() > MAX_VALUE_SIZE {
147        return Err(ValueLayoutError::ValueTooLarge(value.len()));
148    }
149
150    // Step 1: small values short-circuit to inline raw. No LZ4 work, no
151    // overflow allocation — preserves the legacy hot path for tiny
152    // values like entity IDs or short JSON.
153    if value.len() <= COMPRESSION_THRESHOLD {
154        return Ok(reddb_file::encode_btree_inline_raw(value));
155    }
156
157    // Step 2: above the threshold, try LZ4. The codec returns Raw when
158    // compression would not shrink the input.
159    let (codec_flag, codec_bytes) = value_codec::encode(value);
160
161    // Step 3: share leaf space for either selected representation. Keep the
162    // previous compression trigger even when a medium raw value now fits.
163    if codec_bytes.len() <= OVERFLOW_THRESHOLD {
164        return Ok(match codec_flag {
165            value_codec::ValueFlag::Raw => reddb_file::encode_btree_inline_raw(&codec_bytes),
166            value_codec::ValueFlag::Lz4 => reddb_file::encode_btree_inline_compressed(&codec_bytes),
167        });
168    }
169
170    // Step 4: spill. We always store the bytes the codec produced —
171    // either Lz4 (with its 4-byte length header) so the reader can
172    // round-trip via the same codec, or Raw bytes when compression
173    // failed to shrink.
174    let is_compressed = codec_flag == value_codec::ValueFlag::Lz4;
175    let chain = OverflowChain::new(pager);
176    let (head, total_len) = chain.store(&codec_bytes)?;
177
178    Ok(reddb_file::encode_btree_pointer(
179        head,
180        total_len,
181        is_compressed,
182    ))
183}
184
185/// Inspect leaf-cell flags, follow the pointer if any, concatenate the
186/// chain, decode if compressed, return the materialised value.
187pub fn decode<P: PageStore>(pager: &P, stored: &[u8]) -> Result<Vec<u8>, ValueLayoutError> {
188    decode_with_budget(pager, stored, usize::MAX)
189}
190
191/// Bound allocations before reading an overflow chain or expanding compressed bytes.
192/// Compressed overflow retains both the encoded chain and its decoded output.
193pub fn decode_with_budget<P: PageStore>(
194    pager: &P,
195    stored: &[u8],
196    limit_bytes: usize,
197) -> Result<Vec<u8>, ValueLayoutError> {
198    match reddb_file::decode_btree_value_cell(stored)? {
199        BTreeValueCell::Pointer {
200            is_compressed,
201            head_page_id,
202            total_len,
203        } => {
204            let encoded_bytes = usize::try_from(total_len)
205                .map_err(|_| ValueLayoutError::ValueTooLarge(usize::MAX))?;
206            check_read_budget(encoded_bytes, limit_bytes)?;
207            let chain = OverflowChain::new(pager);
208            let chain_bytes = chain.read(head_page_id, total_len)?;
209            if is_compressed {
210                let decoded_bytes = compressed_output_bytes(&chain_bytes)?;
211                check_read_budget(encoded_bytes.saturating_add(decoded_bytes), limit_bytes)?;
212                Ok(value_codec::decode(
213                    value_codec::ValueFlag::Lz4,
214                    &chain_bytes,
215                )?)
216            } else {
217                Ok(chain_bytes)
218            }
219        }
220        BTreeValueCell::Inline {
221            is_compressed,
222            payload,
223        } => {
224            let decoded_bytes = if is_compressed {
225                compressed_output_bytes(payload)?
226            } else {
227                payload.len()
228            };
229            check_read_budget(decoded_bytes, limit_bytes)?;
230            Ok(reddb_file::decode_btree_inline_payload(
231                is_compressed,
232                payload,
233            )?)
234        }
235    }
236}
237
238fn compressed_output_bytes(bytes: &[u8]) -> Result<usize, ValueLayoutError> {
239    value_codec::decoded_length(value_codec::ValueFlag::Lz4, bytes).map_err(ValueLayoutError::Codec)
240}
241
242fn check_read_budget(required_bytes: usize, limit_bytes: usize) -> Result<(), ValueLayoutError> {
243    if required_bytes > limit_bytes {
244        return Err(ValueLayoutError::ReadLimitExceeded {
245            required_bytes,
246            limit_bytes,
247        });
248    }
249    Ok(())
250}
251
252/// Return the head overflow page id when `stored` represents a pointer
253/// cell, else `None`. Returns `None` for inline (raw or compressed)
254/// cells and for empty/malformed cells. Callers use this from the
255/// B-tree delete and shrinking-update paths (slice F of PRD #662) to
256/// free the chain before the leaf cell goes away.
257pub fn pointer_head(stored: &[u8]) -> Option<u32> {
258    reddb_file::btree_value_pointer_head(stored)
259}
260
261/// `true` when [`encode`] would emit a spill pointer for a value of
262/// this length (without actually spilling). Used by the leaf-fit check
263/// in `bulk_insert_sorted` to size cells before allocation.
264#[inline]
265#[allow(dead_code)]
266pub fn projected_cell_len(input: &[u8]) -> usize {
267    let codec_len = value_codec::would_encode_to(input);
268    reddb_file::btree_projected_cell_len(input.len(), codec_len)
269}
reddb_engine/storage/btree/value_layout.rs

reddb_engine/storage/btree/
value_layout.rs
