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#[derive(Debug, Clone, Copy)]
40pub struct RedbStoreConfig {
41 pub cache_size_bytes: usize,
43 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#[derive(Debug, Clone, Copy)]
61pub struct RedbStoreOptions {
62 pub database: RedbStoreConfig,
64 pub node_read_cache_size_bytes: usize,
68 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#[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
219pub 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 pub fn open(path: impl AsRef<Path>) -> Result<Self, RedbStoreError> {
255 Self::open_with_config(path, RedbStoreConfig::default())
256 }
257
258 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 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 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}