Skip to main content

prolly_store_redb/
lib.rs

1#![doc = include_str!("../README.md")]
2
3use std::collections::{hash_map::Entry, HashMap};
4use std::error::Error as StdError;
5use std::path::Path;
6use std::sync::atomic::{AtomicBool, Ordering};
7use std::sync::Arc;
8
9use ahash::AHashMap;
10use parking_lot::{Mutex, RwLock};
11use redb::{
12    Database, ReadableDatabase, ReadableTable, ReadableTableMetadata, TableDefinition,
13    WriteTransaction,
14};
15
16use prolly::{
17    BatchOp, Cid, Error, IndexedStore, ManifestStore, ManifestStoreScan, ManifestUpdate,
18    NamedRootManifest, NodeStoreScan, RootCondition, RootManifest, RootWrite, Store,
19    TransactionConflict, TransactionNodeWrite, TransactionUpdate, TransactionalStore,
20};
21
22pub use redb::Durability;
23
24const V2_NODES: TableDefinition<&[u8], (u8, &[u8])> = TableDefinition::new("prolly_nodes_v2");
25const NODES: TableDefinition<&[u8], &[u8]> = TableDefinition::new("prolly_nodes");
26const ROOTS: TableDefinition<&[u8], &[u8]> = TableDefinition::new("prolly_roots");
27const HINTS: TableDefinition<(&[u8], &[u8]), &[u8]> = TableDefinition::new("prolly_hints");
28
29const NODE_ENCODING_RAW: u8 = 0;
30const NODE_ENCODING_LZ4: u8 = 1;
31const NODE_ENVELOPE_MAGIC: &[u8; 4] = b"PRN1";
32const NODE_ENVELOPE_HEADER_BYTES: usize = NODE_ENVELOPE_MAGIC.len() + 1;
33const MIN_COMPRESSIBLE_NODE_BYTES: usize = 8 * 1024;
34const DEFAULT_NODE_READ_CACHE_SIZE_BYTES: usize = 128 * 1024 * 1024;
35
36type V2NodeTable<'txn> = redb::Table<'txn, &'static [u8], (u8, &'static [u8])>;
37
38/// Configuration for [`RedbStore`].
39#[derive(Debug, Clone, Copy)]
40pub struct RedbStoreConfig {
41    /// Maximum bytes redb may use for its in-memory page cache.
42    pub cache_size_bytes: usize,
43    /// Durability applied to every committed write transaction.
44    pub durability: Durability,
45}
46
47impl Default for RedbStoreConfig {
48    fn default() -> Self {
49        Self {
50            cache_size_bytes: 1024 * 1024 * 1024,
51            durability: Durability::Immediate,
52        }
53    }
54}
55
56/// Extended adapter options that preserve [`RedbStoreConfig`] compatibility.
57///
58/// Redb's page cache stores encoded database pages, while the node read cache
59/// retains decoded immutable prolly nodes. Their memory budgets are separate.
60#[derive(Debug, Clone, Copy)]
61pub struct RedbStoreOptions {
62    /// Redb database configuration.
63    pub database: RedbStoreConfig,
64    /// Maximum decoded node bytes retained for native shared reads.
65    ///
66    /// Set this to zero to disable retention without changing read semantics.
67    pub node_read_cache_size_bytes: usize,
68    /// Transparently LZ4-compress large nodes when it reduces their size.
69    pub compress_nodes: bool,
70}
71
72impl Default for RedbStoreOptions {
73    fn default() -> Self {
74        Self {
75            database: RedbStoreConfig::default(),
76            node_read_cache_size_bytes: DEFAULT_NODE_READ_CACHE_SIZE_BYTES,
77            compress_nodes: true,
78        }
79    }
80}
81
82struct NodeReadCache {
83    values: AHashMap<Vec<u8>, Arc<[u8]>>,
84    retained_bytes: usize,
85    max_bytes: usize,
86    generation: u64,
87}
88
89impl NodeReadCache {
90    fn new(max_bytes: usize) -> Self {
91        Self {
92            values: AHashMap::new(),
93            retained_bytes: 0,
94            max_bytes,
95            generation: 0,
96        }
97    }
98
99    fn get(&self, key: &[u8]) -> Option<Arc<[u8]>> {
100        self.values.get(key).cloned()
101    }
102
103    fn insert(&mut self, key: &[u8], value: Arc<[u8]>) {
104        if self.max_bytes == 0 || value.len() > self.max_bytes {
105            return;
106        }
107        if let Some(previous) = self.values.remove(key) {
108            self.retained_bytes = self.retained_bytes.saturating_sub(previous.len());
109        }
110        if self.retained_bytes.saturating_add(value.len()) > self.max_bytes {
111            self.values.clear();
112            self.retained_bytes = 0;
113        }
114        self.retained_bytes = self.retained_bytes.saturating_add(value.len());
115        self.values.insert(key.to_vec(), value);
116    }
117
118    fn remove(&mut self, key: &[u8]) {
119        if let Some(value) = self.values.remove(key) {
120            self.retained_bytes = self.retained_bytes.saturating_sub(value.len());
121        }
122    }
123
124    fn invalidate<'a>(&mut self, keys: impl IntoIterator<Item = &'a [u8]>) {
125        self.generation = self.generation.wrapping_add(1);
126        for key in keys {
127            self.remove(key);
128        }
129    }
130}
131
132struct OrderedBatchReadPlan<'a> {
133    unique_keys: Vec<&'a [u8]>,
134    positions: Option<Vec<usize>>,
135}
136
137impl<'a> OrderedBatchReadPlan<'a> {
138    fn new(keys: &[&'a [u8]]) -> Self {
139        let mut unique_indexes = AHashMap::with_capacity(keys.len());
140        let mut unique_keys = Vec::with_capacity(keys.len());
141        let mut positions = None;
142        for key in keys {
143            match unique_indexes.entry(*key) {
144                Entry::Occupied(entry) => positions
145                    .get_or_insert_with(|| (0..unique_keys.len()).collect::<Vec<_>>())
146                    .push(*entry.get()),
147                Entry::Vacant(entry) => {
148                    let index = unique_keys.len();
149                    unique_keys.push(*key);
150                    if let Some(positions) = positions.as_mut() {
151                        positions.push(index);
152                    }
153                    entry.insert(index);
154                }
155            }
156        }
157        Self {
158            unique_keys,
159            positions,
160        }
161    }
162
163    fn unique_keys(&self) -> &[&'a [u8]] {
164        &self.unique_keys
165    }
166
167    fn expand<T: Clone>(&self, values: Vec<Option<T>>) -> Vec<Option<T>> {
168        match &self.positions {
169            Some(positions) => positions
170                .iter()
171                .map(|&index| values[index].clone())
172                .collect(),
173            None => values,
174        }
175    }
176}
177
178/// Error returned by [`RedbStore`] operations.
179#[derive(Debug)]
180pub struct RedbStoreError {
181    message: String,
182    source: Option<Box<dyn StdError + Send + Sync>>,
183}
184
185impl RedbStoreError {
186    fn message(message: impl Into<String>) -> Self {
187        Self {
188            message: message.into(),
189            source: None,
190        }
191    }
192
193    fn with_source(
194        context: impl Into<String>,
195        source: impl StdError + Send + Sync + 'static,
196    ) -> Self {
197        let context = context.into();
198        Self {
199            message: format!("{context}: {source}"),
200            source: Some(Box::new(source)),
201        }
202    }
203}
204
205impl std::fmt::Display for RedbStoreError {
206    fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
207        write!(formatter, "redb store error: {}", self.message)
208    }
209}
210
211impl StdError for RedbStoreError {
212    fn source(&self) -> Option<&(dyn StdError + 'static)> {
213        self.source
214            .as_deref()
215            .map(|source| source as &(dyn StdError + 'static))
216    }
217}
218
219/// Persistent synchronous prolly store backed by redb.
220///
221/// The store keeps nodes, named roots, and advisory hints in separate redb
222/// tables. All mutation methods commit through redb transactions, and strict
223/// prolly transactions atomically validate roots and update nodes and roots.
224pub struct RedbStore {
225    db: Database,
226    durability: Durability,
227    node_read_cache: Mutex<NodeReadCache>,
228    node_read_cache_enabled: bool,
229    node_read_transaction: RwLock<Option<redb::ReadTransaction>>,
230    compress_nodes: bool,
231    v2_nodes_present: AtomicBool,
232}
233
234impl std::fmt::Debug for RedbStore {
235    fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
236        formatter
237            .debug_struct("RedbStore")
238            .field("durability", &self.durability)
239            .field(
240                "node_read_cache_size_bytes",
241                &self.node_read_cache.lock().max_bytes,
242            )
243            .field("compress_nodes", &self.compress_nodes)
244            .field(
245                "v2_nodes_present",
246                &self.v2_nodes_present.load(Ordering::Relaxed),
247            )
248            .finish_non_exhaustive()
249    }
250}
251
252impl RedbStore {
253    /// Open an existing redb database or create one with default settings.
254    pub fn open(path: impl AsRef<Path>) -> Result<Self, RedbStoreError> {
255        Self::open_with_config(path, RedbStoreConfig::default())
256    }
257
258    /// Open an existing redb database or create one with `config`.
259    pub fn open_with_config(
260        path: impl AsRef<Path>,
261        config: RedbStoreConfig,
262    ) -> Result<Self, RedbStoreError> {
263        Self::open_with_options(
264            path,
265            RedbStoreOptions {
266                database: config,
267                ..RedbStoreOptions::default()
268            },
269        )
270    }
271
272    /// Open an existing database or create one with database and adapter tuning.
273    pub fn open_with_options(
274        path: impl AsRef<Path>,
275        options: RedbStoreOptions,
276    ) -> Result<Self, RedbStoreError> {
277        let mut builder = Database::builder();
278        builder.set_cache_size(options.database.cache_size_bytes);
279        let db = builder.create(path.as_ref()).map_err(|error| {
280            RedbStoreError::with_source(
281                format!("failed to open database at {:?}", path.as_ref()),
282                error,
283            )
284        })?;
285        let store = Self {
286            db,
287            durability: options.database.durability,
288            node_read_cache: Mutex::new(NodeReadCache::new(options.node_read_cache_size_bytes)),
289            node_read_cache_enabled: options.node_read_cache_size_bytes != 0,
290            node_read_transaction: RwLock::new(None),
291            compress_nodes: options.compress_nodes,
292            v2_nodes_present: AtomicBool::new(false),
293        };
294        store.initialize_tables()?;
295        Ok(store)
296    }
297
298    /// Reclaim free pages and compact the database file where possible.
299    ///
300    /// Returns `true` when redb performed compaction and `false` when the file
301    /// cannot be compacted further. The store must be mutably borrowed so no
302    /// concurrent operation can begin while redb rewrites the file.
303    pub fn compact(&mut self) -> Result<bool, RedbStoreError> {
304        *self.node_read_transaction.write() = None;
305        self.db
306            .compact()
307            .map_err(|error| RedbStoreError::with_source("failed to compact database", error))
308    }
309
310    fn initialize_tables(&self) -> Result<(), RedbStoreError> {
311        let transaction = self.begin_write("failed to begin table initialization")?;
312        let v2_nodes_present;
313        {
314            let v2_nodes = transaction.open_table(V2_NODES).map_err(|error| {
315                RedbStoreError::with_source("failed to initialize v2 node table", error)
316            })?;
317            v2_nodes_present = !v2_nodes.is_empty().map_err(|error| {
318                RedbStoreError::with_source("failed to inspect v2 node table", error)
319            })?;
320            let _nodes = transaction.open_table(NODES).map_err(|error| {
321                RedbStoreError::with_source("failed to initialize node table", error)
322            })?;
323            let _roots = transaction.open_table(ROOTS).map_err(|error| {
324                RedbStoreError::with_source("failed to initialize root table", error)
325            })?;
326            let _hints = transaction.open_table(HINTS).map_err(|error| {
327                RedbStoreError::with_source("failed to initialize hint table", error)
328            })?;
329        }
330        transaction.commit().map_err(|error| {
331            RedbStoreError::with_source("failed to commit table initialization", error)
332        })?;
333        self.v2_nodes_present
334            .store(v2_nodes_present, Ordering::Relaxed);
335        Ok(())
336    }
337
338    fn begin_write(&self, context: &str) -> Result<WriteTransaction, RedbStoreError> {
339        let mut transaction = self
340            .db
341            .begin_write()
342            .map_err(|error| RedbStoreError::with_source(context, error))?;
343        transaction
344            .set_durability(self.durability)
345            .map_err(|error| {
346                RedbStoreError::with_source("failed to configure transaction durability", error)
347            })?;
348        Ok(transaction)
349    }
350
351    fn open_v2_nodes_for_write<'txn>(
352        &self,
353        transaction: &'txn WriteTransaction,
354        operation: &str,
355    ) -> Result<Option<V2NodeTable<'txn>>, RedbStoreError> {
356        if !self.v2_nodes_present.load(Ordering::Relaxed) {
357            return Ok(None);
358        }
359        transaction.open_table(V2_NODES).map(Some).map_err(|error| {
360            RedbStoreError::with_source(
361                format!("failed to open v2 node table for {operation}"),
362                error,
363            )
364        })
365    }
366
367    fn read_nodes_shared_ordered_unique(
368        &self,
369        keys: &[&[u8]],
370    ) -> Result<Vec<Option<Arc<[u8]>>>, RedbStoreError> {
371        loop {
372            let mut values = vec![None; keys.len()];
373            let mut missing = Vec::new();
374            let read_generation = {
375                let cache = self.node_read_cache.lock();
376                for (position, key) in keys.iter().enumerate() {
377                    match cache.get(key) {
378                        Some(value) => values[position] = Some(value),
379                        None => missing.push((position, *key)),
380                    }
381                }
382                cache.generation
383            };
384            if missing.is_empty() {
385                return Ok(values);
386            }
387
388            self.ensure_node_read_transaction()?;
389            let transaction_guard = self.node_read_transaction.read();
390            let transaction = transaction_guard
391                .as_ref()
392                .expect("node read transaction was initialized");
393            let table = transaction.open_table(NODES).map_err(|error| {
394                RedbStoreError::with_source("failed to open node table for reading", error)
395            })?;
396            let v2 = self
397                .v2_nodes_present
398                .load(Ordering::Relaxed)
399                .then(|| {
400                    transaction.open_table(V2_NODES).map_err(|error| {
401                        RedbStoreError::with_source(
402                            "failed to open v2 node table for reading",
403                            error,
404                        )
405                    })
406                })
407                .transpose()?;
408            if !missing.windows(2).all(|pair| pair[0].1 <= pair[1].1) {
409                missing.sort_unstable_by(|left, right| left.1.cmp(right.1));
410            }
411            let mut loaded_values: Vec<Option<Arc<[u8]>>> = Vec::with_capacity(missing.len());
412            for (_, key) in &missing {
413                let value = if let Some(value) = table
414                    .get(*key)
415                    .map_err(|error| RedbStoreError::with_source("failed to read node", error))?
416                {
417                    Some(Arc::from(decode_stored_node(value.value())?))
418                } else if let Some(value) = v2
419                    .as_ref()
420                    .map(|v2| {
421                        v2.get(*key).map_err(|error| {
422                            RedbStoreError::with_source("failed to read v2 node", error)
423                        })
424                    })
425                    .transpose()?
426                    .flatten()
427                {
428                    let (encoding, bytes) = value.value();
429                    Some(Arc::from(decode_v2_stored_node(encoding, bytes)?))
430                } else {
431                    None
432                };
433                loaded_values.push(value);
434            }
435            drop(v2);
436            drop(table);
437            drop(transaction_guard);
438
439            let mut cache = self.node_read_cache.lock();
440            if cache.generation != read_generation {
441                continue;
442            }
443            for ((position, key), loaded) in missing.into_iter().zip(loaded_values) {
444                if let Some(loaded) = loaded {
445                    cache.insert(key, loaded.clone());
446                    values[position] = Some(loaded);
447                }
448            }
449            return Ok(values);
450        }
451    }
452
453    fn read_nodes_owned_ordered_unique_uncached(
454        &self,
455        keys: &[&[u8]],
456    ) -> Result<Vec<Option<Vec<u8>>>, RedbStoreError> {
457        self.ensure_node_read_transaction()?;
458        let transaction_guard = self.node_read_transaction.read();
459        let transaction = transaction_guard
460            .as_ref()
461            .expect("node read transaction was initialized");
462        let table = transaction.open_table(NODES).map_err(|error| {
463            RedbStoreError::with_source("failed to open node table for reading", error)
464        })?;
465        let v2 = self
466            .v2_nodes_present
467            .load(Ordering::Relaxed)
468            .then(|| {
469                transaction.open_table(V2_NODES).map_err(|error| {
470                    RedbStoreError::with_source("failed to open v2 node table for reading", error)
471                })
472            })
473            .transpose()?;
474        let mut order = (0..keys.len()).collect::<Vec<_>>();
475        if !keys.windows(2).all(|pair| pair[0] <= pair[1]) {
476            order.sort_unstable_by(|&left, &right| keys[left].cmp(keys[right]));
477        }
478        let mut values = vec![None; keys.len()];
479        for index in order {
480            let key = keys[index];
481            values[index] = if let Some(value) = table
482                .get(key)
483                .map_err(|error| RedbStoreError::with_source("failed to read node", error))?
484            {
485                decode_stored_node(value.value()).map(Some)
486            } else if let Some(value) = v2
487                .as_ref()
488                .map(|v2| {
489                    v2.get(key).map_err(|error| {
490                        RedbStoreError::with_source("failed to read v2 node", error)
491                    })
492                })
493                .transpose()?
494                .flatten()
495            {
496                let (encoding, bytes) = value.value();
497                decode_v2_stored_node(encoding, bytes).map(Some)
498            } else {
499                Ok(None)
500            }?;
501        }
502        Ok(values)
503    }
504
505    fn node_read_cache_enabled(&self) -> bool {
506        self.node_read_cache_enabled
507    }
508
509    fn ensure_node_read_transaction(&self) -> Result<(), RedbStoreError> {
510        if self.node_read_transaction.read().is_some() {
511            return Ok(());
512        }
513        let mut retained = self.node_read_transaction.write();
514        if retained.is_none() {
515            *retained = Some(self.db.begin_read().map_err(|error| {
516                RedbStoreError::with_source("failed to begin retained node read transaction", error)
517            })?);
518        }
519        Ok(())
520    }
521
522    fn invalidate_node(&self, key: &[u8]) {
523        *self.node_read_transaction.write() = None;
524        self.node_read_cache.lock().invalidate([key]);
525    }
526
527    fn invalidate_nodes<'a>(&self, keys: impl IntoIterator<Item = &'a [u8]>) {
528        *self.node_read_transaction.write() = None;
529        self.node_read_cache.lock().invalidate(keys);
530    }
531}
532
533impl Store for RedbStore {
534    type Error = RedbStoreError;
535
536    fn get(&self, key: &[u8]) -> Result<Option<Vec<u8>>, Self::Error> {
537        if self.node_read_cache_enabled() {
538            self.get_shared(key)
539                .map(|value| value.map(|value| value.as_ref().to_vec()))
540        } else {
541            self.read_nodes_owned_ordered_unique_uncached(&[key])
542                .map(|mut values| values.pop().flatten())
543        }
544    }
545
546    fn get_shared(&self, key: &[u8]) -> Result<Option<Arc<[u8]>>, Self::Error> {
547        if self.node_read_cache_enabled() {
548            self.read_nodes_shared_ordered_unique(&[key])
549                .map(|mut values| values.pop().flatten())
550        } else {
551            self.read_nodes_owned_ordered_unique_uncached(&[key])
552                .map(|mut values| values.pop().flatten().map(Arc::from))
553        }
554    }
555
556    fn batch_get_shared_ordered_unique(
557        &self,
558        keys: &[&[u8]],
559    ) -> Result<Vec<Option<Arc<[u8]>>>, Self::Error> {
560        if self.node_read_cache_enabled() {
561            self.read_nodes_shared_ordered_unique(keys)
562        } else {
563            self.read_nodes_owned_ordered_unique_uncached(keys)
564                .map(|values| {
565                    values
566                        .into_iter()
567                        .map(|value| value.map(Arc::from))
568                        .collect()
569                })
570        }
571    }
572
573    fn has_native_shared_reads(&self) -> bool {
574        self.node_read_cache_enabled()
575    }
576
577    fn put(&self, key: &[u8], value: &[u8]) -> Result<(), Self::Error> {
578        let transaction = self.begin_write("failed to begin node write transaction")?;
579        {
580            let mut table = transaction.open_table(NODES).map_err(|error| {
581                RedbStoreError::with_source("failed to open node table for writing", error)
582            })?;
583            let mut v2 = self.open_v2_nodes_for_write(&transaction, "writing")?;
584            let mut compression_scratch = Vec::new();
585            insert_stored_node(
586                &mut table,
587                key,
588                value,
589                self.compress_nodes,
590                &mut compression_scratch,
591            )
592            .map_err(|error| RedbStoreError::with_source("failed to write node", error))?;
593            if let Some(v2) = v2.as_mut() {
594                v2.remove(key).map_err(|error| {
595                    RedbStoreError::with_source("failed to remove superseded v2 node", error)
596                })?;
597            }
598        }
599        transaction
600            .commit()
601            .map_err(|error| RedbStoreError::with_source("failed to commit node write", error))?;
602        self.invalidate_node(key);
603        Ok(())
604    }
605
606    fn delete(&self, key: &[u8]) -> Result<(), Self::Error> {
607        let transaction = self.begin_write("failed to begin node delete transaction")?;
608        {
609            let mut table = transaction.open_table(NODES).map_err(|error| {
610                RedbStoreError::with_source("failed to open node table for deletion", error)
611            })?;
612            let mut v2 = self.open_v2_nodes_for_write(&transaction, "deletion")?;
613            table
614                .remove(key)
615                .map_err(|error| RedbStoreError::with_source("failed to delete node", error))?;
616            if let Some(v2) = v2.as_mut() {
617                v2.remove(key).map_err(|error| {
618                    RedbStoreError::with_source("failed to delete v2 node", error)
619                })?;
620            }
621        }
622        transaction.commit().map_err(|error| {
623            RedbStoreError::with_source("failed to commit node deletion", error)
624        })?;
625        self.invalidate_node(key);
626        Ok(())
627    }
628
629    fn batch(&self, ops: &[BatchOp]) -> Result<(), Self::Error> {
630        let transaction = self.begin_write("failed to begin node batch transaction")?;
631        {
632            let mut table = transaction.open_table(NODES).map_err(|error| {
633                RedbStoreError::with_source("failed to open node table for batch", error)
634            })?;
635            let mut v2 = self.open_v2_nodes_for_write(&transaction, "batch")?;
636            let mut compression_scratch = Vec::new();
637            for op in ops {
638                match op {
639                    BatchOp::Upsert { key, value } => {
640                        insert_stored_node(
641                            &mut table,
642                            key,
643                            value,
644                            self.compress_nodes,
645                            &mut compression_scratch,
646                        )
647                        .map_err(|error| {
648                            RedbStoreError::with_source("failed to write node in batch", error)
649                        })?;
650                        if let Some(v2) = v2.as_mut() {
651                            v2.remove(*key).map_err(|error| {
652                                RedbStoreError::with_source(
653                                    "failed to remove superseded v2 node in batch",
654                                    error,
655                                )
656                            })?;
657                        }
658                    }
659                    BatchOp::Delete { key } => {
660                        table.remove(*key).map_err(|error| {
661                            RedbStoreError::with_source("failed to delete node in batch", error)
662                        })?;
663                        if let Some(v2) = v2.as_mut() {
664                            v2.remove(*key).map_err(|error| {
665                                RedbStoreError::with_source(
666                                    "failed to delete v2 node in batch",
667                                    error,
668                                )
669                            })?;
670                        }
671                    }
672                }
673            }
674        }
675        transaction
676            .commit()
677            .map_err(|error| RedbStoreError::with_source("failed to commit node batch", error))?;
678        self.invalidate_nodes(ops.iter().map(|op| match op {
679            BatchOp::Upsert { key, .. } | BatchOp::Delete { key } => *key,
680        }));
681        Ok(())
682    }
683
684    fn batch_get(&self, keys: &[&[u8]]) -> Result<HashMap<Vec<u8>, Vec<u8>>, Self::Error> {
685        let plan = OrderedBatchReadPlan::new(keys);
686        let values = self.batch_get_ordered_unique(plan.unique_keys())?;
687        let mut results = HashMap::with_capacity(plan.unique_keys().len());
688        for (key, value) in plan.unique_keys().iter().zip(values) {
689            if let Some(value) = value {
690                results.insert(key.to_vec(), value);
691            }
692        }
693        Ok(results)
694    }
695
696    fn batch_get_ordered(&self, keys: &[&[u8]]) -> Result<Vec<Option<Vec<u8>>>, Self::Error> {
697        let plan = OrderedBatchReadPlan::new(keys);
698        let values = self.batch_get_ordered_unique(plan.unique_keys())?;
699        Ok(plan.expand(values))
700    }
701
702    fn batch_get_ordered_unique(
703        &self,
704        keys: &[&[u8]],
705    ) -> Result<Vec<Option<Vec<u8>>>, Self::Error> {
706        if self.node_read_cache_enabled() {
707            self.read_nodes_shared_ordered_unique(keys).map(|values| {
708                values
709                    .into_iter()
710                    .map(|value| value.map(|value| value.as_ref().to_vec()))
711                    .collect()
712            })
713        } else {
714            self.read_nodes_owned_ordered_unique_uncached(keys)
715        }
716    }
717
718    fn prefers_batch_reads(&self) -> bool {
719        true
720    }
721
722    fn batch_put(&self, entries: &[(&[u8], &[u8])]) -> Result<(), Self::Error> {
723        let transaction = self.begin_write("failed to begin node batch-put transaction")?;
724        {
725            let mut table = transaction.open_table(NODES).map_err(|error| {
726                RedbStoreError::with_source("failed to open node table for batch put", error)
727            })?;
728            let mut v2 = self.open_v2_nodes_for_write(&transaction, "batch put")?;
729            let mut order = (0..entries.len()).collect::<Vec<_>>();
730            order.sort_by(|&left, &right| entries[left].0.cmp(entries[right].0));
731            let mut compression_scratch = Vec::new();
732            for index in order {
733                let (key, value) = entries[index];
734                insert_stored_node(
735                    &mut table,
736                    key,
737                    value,
738                    self.compress_nodes,
739                    &mut compression_scratch,
740                )
741                .map_err(|error| {
742                    RedbStoreError::with_source("failed to write node in batch put", error)
743                })?;
744                if let Some(v2) = v2.as_mut() {
745                    v2.remove(key).map_err(|error| {
746                        RedbStoreError::with_source(
747                            "failed to remove superseded v2 node in batch put",
748                            error,
749                        )
750                    })?;
751                }
752            }
753        }
754        transaction.commit().map_err(|error| {
755            RedbStoreError::with_source("failed to commit node batch put", error)
756        })?;
757        self.invalidate_nodes(entries.iter().map(|(key, _)| *key));
758        Ok(())
759    }
760
761    fn supports_hints(&self) -> bool {
762        true
763    }
764
765    fn get_hint(&self, namespace: &[u8], key: &[u8]) -> Result<Option<Vec<u8>>, Self::Error> {
766        let transaction = self.db.begin_read().map_err(|error| {
767            RedbStoreError::with_source("failed to begin hint read transaction", error)
768        })?;
769        let table = transaction.open_table(HINTS).map_err(|error| {
770            RedbStoreError::with_source("failed to open hint table for reading", error)
771        })?;
772        table
773            .get((namespace, key))
774            .map(|value| value.map(|guard| guard.value().to_vec()))
775            .map_err(|error| RedbStoreError::with_source("failed to read hint", error))
776    }
777
778    fn put_hint(&self, namespace: &[u8], key: &[u8], value: &[u8]) -> Result<(), Self::Error> {
779        let transaction = self.begin_write("failed to begin hint write transaction")?;
780        {
781            let mut table = transaction.open_table(HINTS).map_err(|error| {
782                RedbStoreError::with_source("failed to open hint table for writing", error)
783            })?;
784            table
785                .insert((namespace, key), value)
786                .map_err(|error| RedbStoreError::with_source("failed to write hint", error))?;
787        }
788        transaction
789            .commit()
790            .map_err(|error| RedbStoreError::with_source("failed to commit hint write", error))
791    }
792
793    fn batch_put_with_hint(
794        &self,
795        entries: &[(&[u8], &[u8])],
796        namespace: &[u8],
797        key: &[u8],
798        value: &[u8],
799    ) -> Result<(), Self::Error> {
800        let transaction = self.begin_write("failed to begin node and hint transaction")?;
801        {
802            let mut nodes = transaction.open_table(NODES).map_err(|error| {
803                RedbStoreError::with_source("failed to open node table for publication", error)
804            })?;
805            let mut v2 = self.open_v2_nodes_for_write(&transaction, "publication")?;
806            let mut hints = transaction.open_table(HINTS).map_err(|error| {
807                RedbStoreError::with_source("failed to open hint table for publication", error)
808            })?;
809            let mut order = (0..entries.len()).collect::<Vec<_>>();
810            order.sort_by(|&left, &right| entries[left].0.cmp(entries[right].0));
811            let mut compression_scratch = Vec::new();
812            for index in order {
813                let (node_key, node_value) = entries[index];
814                insert_stored_node(
815                    &mut nodes,
816                    node_key,
817                    node_value,
818                    self.compress_nodes,
819                    &mut compression_scratch,
820                )
821                .map_err(|error| RedbStoreError::with_source("failed to publish node", error))?;
822                if let Some(v2) = v2.as_mut() {
823                    v2.remove(node_key).map_err(|error| {
824                        RedbStoreError::with_source(
825                            "failed to remove superseded v2 node during publication",
826                            error,
827                        )
828                    })?;
829                }
830            }
831            hints
832                .insert((namespace, key), value)
833                .map_err(|error| RedbStoreError::with_source("failed to publish hint", error))?;
834        }
835        transaction.commit().map_err(|error| {
836            RedbStoreError::with_source("failed to commit node and hint publication", error)
837        })?;
838        self.invalidate_nodes(entries.iter().map(|(key, _)| *key));
839        Ok(())
840    }
841}
842
843impl NodeStoreScan for RedbStore {
844    type Error = RedbStoreError;
845
846    fn list_node_cids(&self) -> Result<Vec<Cid>, Self::Error> {
847        let transaction = self.db.begin_read().map_err(|error| {
848            RedbStoreError::with_source("failed to begin node scan transaction", error)
849        })?;
850        let table = transaction.open_table(NODES).map_err(|error| {
851            RedbStoreError::with_source("failed to open node table for scanning", error)
852        })?;
853        let mut cids = Vec::new();
854        for entry in table
855            .iter()
856            .map_err(|error| RedbStoreError::with_source("failed to iterate node table", error))?
857        {
858            let (key, _) = entry.map_err(|error| {
859                RedbStoreError::with_source("failed to read node scan entry", error)
860            })?;
861            cids.push(cid_from_store_key(key.value())?);
862        }
863        if self.v2_nodes_present.load(Ordering::Relaxed) {
864            let v2 = transaction.open_table(V2_NODES).map_err(|error| {
865                RedbStoreError::with_source("failed to open v2 node table for scanning", error)
866            })?;
867            for entry in v2.iter().map_err(|error| {
868                RedbStoreError::with_source("failed to iterate v2 node table", error)
869            })? {
870                let (key, _) = entry.map_err(|error| {
871                    RedbStoreError::with_source("failed to read v2 node scan entry", error)
872                })?;
873                cids.push(cid_from_store_key(key.value())?);
874            }
875        }
876        cids.sort_by(|left, right| left.as_bytes().cmp(right.as_bytes()));
877        cids.dedup();
878        Ok(cids)
879    }
880}
881
882impl ManifestStore for RedbStore {
883    type Error = RedbStoreError;
884
885    fn get_root(&self, name: &[u8]) -> Result<Option<RootManifest>, Self::Error> {
886        let transaction = self.db.begin_read().map_err(|error| {
887            RedbStoreError::with_source("failed to begin root read transaction", error)
888        })?;
889        let table = transaction.open_table(ROOTS).map_err(|error| {
890            RedbStoreError::with_source("failed to open root table for reading", error)
891        })?;
892        let value = table
893            .get(name)
894            .map_err(|error| RedbStoreError::with_source("failed to read root manifest", error))?;
895        value
896            .map(|guard| decode_root_manifest(guard.value()))
897            .transpose()
898    }
899
900    fn put_root(&self, name: &[u8], manifest: &RootManifest) -> Result<(), Self::Error> {
901        let bytes = encode_root_manifest(manifest)?;
902        let transaction = self.begin_write("failed to begin root write transaction")?;
903        {
904            let mut table = transaction.open_table(ROOTS).map_err(|error| {
905                RedbStoreError::with_source("failed to open root table for writing", error)
906            })?;
907            table.insert(name, bytes.as_slice()).map_err(|error| {
908                RedbStoreError::with_source("failed to write root manifest", error)
909            })?;
910        }
911        transaction
912            .commit()
913            .map_err(|error| RedbStoreError::with_source("failed to commit root write", error))
914    }
915
916    fn delete_root(&self, name: &[u8]) -> Result<(), Self::Error> {
917        let transaction = self.begin_write("failed to begin root delete transaction")?;
918        {
919            let mut table = transaction.open_table(ROOTS).map_err(|error| {
920                RedbStoreError::with_source("failed to open root table for deletion", error)
921            })?;
922            table.remove(name).map_err(|error| {
923                RedbStoreError::with_source("failed to delete root manifest", error)
924            })?;
925        }
926        transaction
927            .commit()
928            .map_err(|error| RedbStoreError::with_source("failed to commit root deletion", error))
929    }
930
931    fn compare_and_swap_root(
932        &self,
933        name: &[u8],
934        expected: Option<&RootManifest>,
935        new: Option<&RootManifest>,
936    ) -> Result<ManifestUpdate, Self::Error> {
937        let new_bytes = new.map(encode_root_manifest).transpose()?;
938        let transaction = self.begin_write("failed to begin root CAS transaction")?;
939        {
940            let mut table = transaction.open_table(ROOTS).map_err(|error| {
941                RedbStoreError::with_source("failed to open root table for CAS", error)
942            })?;
943            let current = {
944                let value = table.get(name).map_err(|error| {
945                    RedbStoreError::with_source("failed to read root during CAS", error)
946                })?;
947                value
948                    .map(|guard| decode_root_manifest(guard.value()))
949                    .transpose()?
950            };
951            if current.as_ref() != expected {
952                return Ok(ManifestUpdate::Conflict { current });
953            }
954            match new_bytes.as_deref() {
955                Some(bytes) => {
956                    table.insert(name, bytes).map_err(|error| {
957                        RedbStoreError::with_source("failed to write root during CAS", error)
958                    })?;
959                }
960                None => {
961                    table.remove(name).map_err(|error| {
962                        RedbStoreError::with_source("failed to delete root during CAS", error)
963                    })?;
964                }
965            }
966        }
967        transaction
968            .commit()
969            .map_err(|error| RedbStoreError::with_source("failed to commit root CAS", error))?;
970        Ok(ManifestUpdate::Applied)
971    }
972}
973
974impl ManifestStoreScan for RedbStore {
975    fn list_roots(&self) -> Result<Vec<NamedRootManifest>, Self::Error> {
976        let transaction = self.db.begin_read().map_err(|error| {
977            RedbStoreError::with_source("failed to begin root scan transaction", error)
978        })?;
979        let table = transaction.open_table(ROOTS).map_err(|error| {
980            RedbStoreError::with_source("failed to open root table for scanning", error)
981        })?;
982        let iterator = table
983            .iter()
984            .map_err(|error| RedbStoreError::with_source("failed to iterate root table", error))?;
985        let mut roots = Vec::new();
986        for entry in iterator {
987            let (name, manifest) = entry.map_err(|error| {
988                RedbStoreError::with_source("failed to read root scan entry", error)
989            })?;
990            roots.push(NamedRootManifest::new(
991                name.value().to_vec(),
992                decode_root_manifest(manifest.value())?,
993            ));
994        }
995        roots.sort_by(|left, right| left.name.cmp(&right.name));
996        Ok(roots)
997    }
998}
999
1000impl TransactionalStore for RedbStore {
1001    fn supports_transactions(&self) -> bool {
1002        true
1003    }
1004
1005    fn commit_transaction(
1006        &self,
1007        node_writes: &[TransactionNodeWrite],
1008        root_conditions: &[RootCondition],
1009        root_writes: &[RootWrite],
1010    ) -> Result<TransactionUpdate, Error> {
1011        let transaction = self
1012            .begin_write("failed to begin strict transaction")
1013            .map_err(store_error)?;
1014        {
1015            let mut nodes = transaction.open_table(NODES).map_err(|error| {
1016                store_error(RedbStoreError::with_source(
1017                    "failed to open node table for strict transaction",
1018                    error,
1019                ))
1020            })?;
1021            let mut v2_nodes = self
1022                .open_v2_nodes_for_write(&transaction, "strict transaction")
1023                .map_err(store_error)?;
1024            let mut roots = transaction.open_table(ROOTS).map_err(|error| {
1025                store_error(RedbStoreError::with_source(
1026                    "failed to open root table for strict transaction",
1027                    error,
1028                ))
1029            })?;
1030
1031            for condition in root_conditions {
1032                let current = {
1033                    let value = roots.get(condition.name.as_slice()).map_err(|error| {
1034                        store_error(RedbStoreError::with_source(
1035                            "failed to read root condition",
1036                            error,
1037                        ))
1038                    })?;
1039                    value
1040                        .map(|guard| decode_root_manifest(guard.value()))
1041                        .transpose()
1042                        .map_err(store_error)?
1043                };
1044                if current != condition.expected {
1045                    return Ok(TransactionUpdate::Conflict(Box::new(
1046                        TransactionConflict::new(
1047                            condition.name.clone(),
1048                            condition.expected.clone(),
1049                            current,
1050                        ),
1051                    )));
1052                }
1053            }
1054
1055            let mut compression_scratch = Vec::new();
1056            for write in node_writes {
1057                match write {
1058                    TransactionNodeWrite::Upsert { key, value } => {
1059                        insert_stored_node(
1060                            &mut nodes,
1061                            key.as_slice(),
1062                            value,
1063                            self.compress_nodes,
1064                            &mut compression_scratch,
1065                        )
1066                        .map_err(|error| {
1067                            store_error(RedbStoreError::with_source(
1068                                "failed to write node in strict transaction",
1069                                error,
1070                            ))
1071                        })?;
1072                        if let Some(v2_nodes) = v2_nodes.as_mut() {
1073                            v2_nodes.remove(key.as_slice()).map_err(|error| {
1074                                store_error(RedbStoreError::with_source(
1075                                    "failed to remove superseded v2 node in strict transaction",
1076                                    error,
1077                                ))
1078                            })?;
1079                        }
1080                    }
1081                    TransactionNodeWrite::Delete { key } => {
1082                        nodes.remove(key.as_slice()).map_err(|error| {
1083                            store_error(RedbStoreError::with_source(
1084                                "failed to delete node in strict transaction",
1085                                error,
1086                            ))
1087                        })?;
1088                        if let Some(v2_nodes) = v2_nodes.as_mut() {
1089                            v2_nodes.remove(key.as_slice()).map_err(|error| {
1090                                store_error(RedbStoreError::with_source(
1091                                    "failed to delete v2 node in strict transaction",
1092                                    error,
1093                                ))
1094                            })?;
1095                        }
1096                    }
1097                }
1098            }
1099
1100            for write in root_writes {
1101                match write {
1102                    RootWrite::Put { name, manifest } => {
1103                        let bytes = encode_root_manifest(manifest).map_err(store_error)?;
1104                        roots
1105                            .insert(name.as_slice(), bytes.as_slice())
1106                            .map_err(|error| {
1107                                store_error(RedbStoreError::with_source(
1108                                    "failed to write root in strict transaction",
1109                                    error,
1110                                ))
1111                            })?;
1112                    }
1113                    RootWrite::Delete { name } => {
1114                        roots.remove(name.as_slice()).map_err(|error| {
1115                            store_error(RedbStoreError::with_source(
1116                                "failed to delete root in strict transaction",
1117                                error,
1118                            ))
1119                        })?;
1120                    }
1121                }
1122            }
1123        }
1124        transaction.commit().map_err(|error| {
1125            store_error(RedbStoreError::with_source(
1126                "failed to commit strict transaction",
1127                error,
1128            ))
1129        })?;
1130        self.invalidate_nodes(node_writes.iter().map(|write| match write {
1131            TransactionNodeWrite::Upsert { key, .. } | TransactionNodeWrite::Delete { key } => {
1132                key.as_slice()
1133            }
1134        }));
1135        Ok(TransactionUpdate::Applied {
1136            nodes_written: node_writes.len(),
1137            roots_written: root_writes.len(),
1138        })
1139    }
1140}
1141
1142impl IndexedStore for RedbStore {}
1143
1144fn cid_from_store_key(key: &[u8]) -> Result<Cid, RedbStoreError> {
1145    let bytes: [u8; 32] = key.try_into().map_err(|_| {
1146        RedbStoreError::message(format!(
1147            "node key has invalid CID length {}, expected 32",
1148            key.len()
1149        ))
1150    })?;
1151    Ok(Cid(bytes))
1152}
1153
1154fn insert_stored_node(
1155    table: &mut redb::Table<'_, &[u8], &[u8]>,
1156    key: &[u8],
1157    node: &[u8],
1158    compress: bool,
1159    scratch: &mut Vec<u8>,
1160) -> redb::Result {
1161    if compress && node.len() >= MIN_COMPRESSIBLE_NODE_BYTES && node.len() <= u32::MAX as usize {
1162        let compressed_header_bytes = NODE_ENVELOPE_HEADER_BYTES + 4;
1163        let maximum =
1164            compressed_header_bytes + lz4_flex::block::get_maximum_output_size(node.len());
1165        scratch.clear();
1166        scratch.resize(maximum, 0);
1167        scratch[..NODE_ENVELOPE_MAGIC.len()].copy_from_slice(NODE_ENVELOPE_MAGIC);
1168        scratch[NODE_ENVELOPE_MAGIC.len()] = NODE_ENCODING_LZ4;
1169        scratch[NODE_ENVELOPE_HEADER_BYTES..compressed_header_bytes]
1170            .copy_from_slice(&(node.len() as u32).to_le_bytes());
1171        let compressed_len =
1172            lz4_flex::block::compress_into(node, &mut scratch[compressed_header_bytes..])
1173                .expect("maximum LZ4 output size is sufficient");
1174        let stored_len = compressed_header_bytes + compressed_len;
1175        if stored_len < NODE_ENVELOPE_HEADER_BYTES + node.len() {
1176            scratch.truncate(stored_len);
1177            table.insert(key, scratch.as_slice())?;
1178            return Ok(());
1179        }
1180    }
1181
1182    let mut stored = table.insert_reserve(key, NODE_ENVELOPE_HEADER_BYTES + node.len())?;
1183    let stored = stored.as_mut();
1184    stored[..NODE_ENVELOPE_MAGIC.len()].copy_from_slice(NODE_ENVELOPE_MAGIC);
1185    stored[NODE_ENVELOPE_MAGIC.len()] = NODE_ENCODING_RAW;
1186    stored[NODE_ENVELOPE_HEADER_BYTES..].copy_from_slice(node);
1187    Ok(())
1188}
1189
1190fn decode_stored_node(stored: &[u8]) -> Result<Vec<u8>, RedbStoreError> {
1191    let Some(envelope) = stored.strip_prefix(NODE_ENVELOPE_MAGIC) else {
1192        return Ok(stored.to_vec());
1193    };
1194    let (&encoding, node) = envelope
1195        .split_first()
1196        .ok_or_else(|| RedbStoreError::message("stored node is missing its encoding byte"))?;
1197    match encoding {
1198        NODE_ENCODING_RAW => Ok(node.to_vec()),
1199        NODE_ENCODING_LZ4 => lz4_flex::decompress_size_prepended(node)
1200            .map_err(|error| RedbStoreError::with_source("failed to decompress node", error)),
1201        other => Err(RedbStoreError::message(format!(
1202            "unsupported node encoding {other}"
1203        ))),
1204    }
1205}
1206
1207fn decode_v2_stored_node(encoding: u8, node: &[u8]) -> Result<Vec<u8>, RedbStoreError> {
1208    match encoding {
1209        NODE_ENCODING_RAW => Ok(node.to_vec()),
1210        NODE_ENCODING_LZ4 => lz4_flex::decompress_size_prepended(node)
1211            .map_err(|error| RedbStoreError::with_source("failed to decompress v2 node", error)),
1212        other => Err(RedbStoreError::message(format!(
1213            "unsupported v2 node encoding {other}"
1214        ))),
1215    }
1216}
1217
1218fn encode_root_manifest(manifest: &RootManifest) -> Result<Vec<u8>, RedbStoreError> {
1219    manifest
1220        .to_bytes()
1221        .map_err(|error| RedbStoreError::with_source("failed to encode root manifest", error))
1222}
1223
1224fn decode_root_manifest(bytes: &[u8]) -> Result<RootManifest, RedbStoreError> {
1225    RootManifest::from_bytes(bytes)
1226        .map_err(|error| RedbStoreError::with_source("failed to decode root manifest", error))
1227}
1228
1229fn store_error(error: RedbStoreError) -> Error {
1230    Error::Store(Box::new(error))
1231}