1mod fingerprint;
10mod last;
11
12use std::cmp::Ordering;
13use std::sync::Arc;
14
15use uqa_core::memory::{BudgetedVec, MemoryReservation};
16
17use crate::read_control::StorageReadControl;
18
19use super::{
20 CommitSequence, PreparedRecordWrite, PrivateRecordSnapshot, RecordVersion, ScannedRecord,
21 SharedRecordValue, VersionResult,
22};
23
24#[derive(Clone, Copy)]
25pub struct BorrowedRecord<'a> {
26 pub revision: Option<CommitSequence>,
27 pub value: Option<&'a [u8]>,
28}
29
30#[derive(Clone, Copy, Debug, PartialEq, Eq)]
32pub struct RecordMetadata {
33 pub revision: Option<CommitSequence>,
34 pub live: bool,
35}
36
37#[derive(Clone, Copy, Debug, PartialEq, Eq)]
39pub struct VisibleRecordRevision {
40 database: super::DatabaseId,
41 committed: Option<CommitSequence>,
42 private: Option<super::PrivateRecordRevision>,
43}
44
45impl VisibleRecordRevision {
46 pub(crate) fn committed(self, database: super::DatabaseId) -> Option<CommitSequence> {
47 (self.database == database && self.private.is_none())
48 .then_some(self.committed)
49 .flatten()
50 }
51
52 pub(crate) fn committed_sequence(self) -> Option<CommitSequence> {
54 self.committed
55 }
56
57 pub(crate) fn database(self) -> super::DatabaseId {
58 self.database
59 }
60
61 pub fn is_private(self) -> bool {
62 self.private.is_some()
63 }
64}
65
66impl From<BorrowedRecord<'_>> for RecordMetadata {
67 fn from(record: BorrowedRecord<'_>) -> Self {
68 Self {
69 revision: record.revision,
70 live: record.value.is_some(),
71 }
72 }
73}
74
75pub type RecordValueVisitor<'a> = dyn FnMut(Option<BorrowedRecord<'_>>) -> VersionResult<()> + 'a;
76pub type RecordPointVisitor<'a> =
77 dyn FnMut(&[u8], Option<BorrowedRecord<'_>>) -> VersionResult<bool> + 'a;
78pub type RecordKeyIterator<'a> = dyn Iterator<Item = VersionResult<BudgetedVec<u8>>> + 'a;
79pub type RecordScanVisitor<'a> = dyn FnMut(&[u8], BorrowedRecord<'_>) -> VersionResult<bool> + 'a;
80pub type RecordKeyVisitor<'a> = dyn FnMut(&[u8], RecordMetadata) -> VersionResult<bool> + 'a;
81
82pub trait CommittedRecordSnapshot: Send + Sync {
84 fn sequence(&self) -> CommitSequence;
85
86 fn reclamation_epoch(&self) -> Option<u64> {
88 None
89 }
90
91 fn provider_snapshot(&self) -> Option<&dyn std::any::Any> {
93 None
94 }
95
96 fn commit_monitor(&self) -> Option<u64> {
98 None
99 }
100
101 fn adopt_commit_monitor(&self, _monitor: u64) -> bool {
103 false
104 }
105
106 fn metadata(
108 &self,
109 key: &[u8],
110 control: &StorageReadControl,
111 ) -> VersionResult<Option<RecordMetadata>> {
112 let mut found = None;
113 self.visit_value(key, control, &mut |record| {
114 found = record.map(Into::into);
115 Ok(())
116 })?;
117 Ok(found)
118 }
119
120 fn visit_keys(
122 &self,
123 prefix: &[u8],
124 after: Option<&[u8]>,
125 limit: usize,
126 control: &StorageReadControl,
127 visit: &mut RecordKeyVisitor<'_>,
128 ) -> VersionResult<()> {
129 self.visit_prefix(prefix, after, limit, control, &mut |key, record| {
130 visit(key, record.into())
131 })
132 }
133
134 fn visit_last_key(
136 &self,
137 prefix: &[u8],
138 before: Option<&[u8]>,
139 control: &StorageReadControl,
140 visit: &mut RecordKeyVisitor<'_>,
141 ) -> VersionResult<()> {
142 last::by_scan(self, prefix, before, control, visit)
143 }
144
145 fn get(
147 &self,
148 key: &[u8],
149 control: &StorageReadControl,
150 ) -> VersionResult<Option<RecordVersion<SharedRecordValue>>>;
151
152 fn scan(
154 &self,
155 prefix: &[u8],
156 after: Option<&[u8]>,
157 limit: usize,
158 control: &StorageReadControl,
159 ) -> VersionResult<BudgetedVec<ScannedRecord>>;
160
161 fn visit_value(
163 &self,
164 key: &[u8],
165 control: &StorageReadControl,
166 visit: &mut RecordValueVisitor<'_>,
167 ) -> VersionResult<()> {
168 let record = self.get(key, control)?;
169 visit(record.as_ref().map(|record| BorrowedRecord {
170 revision: Some(record.sequence()),
171 value: record.value().map(|value| &***value),
172 }))?;
173 control.cancellation().check()?;
174 Ok(())
175 }
176
177 fn visit_value_bounded(
179 &self,
180 _key: &[u8],
181 _max_bytes: usize,
182 control: &StorageReadControl,
183 _visit: &mut RecordValueVisitor<'_>,
184 ) -> VersionResult<()> {
185 control.check()?;
186 Err(crate::StorageBackendError::Other(
187 "size-bounded committed record reads are not supported".into(),
188 )
189 .into())
190 }
191
192 fn visit_values(
194 &self,
195 keys: &mut RecordKeyIterator<'_>,
196 control: &StorageReadControl,
197 visit: &mut RecordPointVisitor<'_>,
198 ) -> VersionResult<()> {
199 loop {
200 control.check()?;
201 let Some(key) = keys.next() else {
202 return Ok(());
203 };
204 let key = key?;
205 let mut more = true;
206 self.visit_value(&key, control, &mut |record| {
207 more = visit(&key, record)?;
208 Ok(())
209 })?;
210 control.check()?;
211 if !more {
212 return Ok(());
213 }
214 }
215 }
216
217 fn visit_prefix(
219 &self,
220 prefix: &[u8],
221 after: Option<&[u8]>,
222 limit: usize,
223 control: &StorageReadControl,
224 visit: &mut RecordScanVisitor<'_>,
225 ) -> VersionResult<()> {
226 control.cancellation().check()?;
227 let mut cursor: Option<BudgetedVec<u8>> = None;
228 let mut remaining = limit;
229 while remaining != 0 {
230 let mut page = self.scan(
231 prefix,
232 cursor.as_deref().or(after),
233 remaining.min(64),
234 control,
235 )?;
236 if page.is_empty() {
237 break;
238 }
239 for record in page.iter() {
240 control.cancellation().check()?;
241 if !visit(
242 &record.key,
243 BorrowedRecord {
244 revision: Some(record.version.sequence()),
245 value: record.version.value().map(|value| &***value),
246 },
247 )? {
248 control.cancellation().check()?;
249 return Ok(());
250 }
251 remaining -= 1;
252 }
253 cursor = page.pop().map(|record| record.key);
254 }
255 control.cancellation().check()?;
256 Ok(())
257 }
258}
259
260struct RetainedSnapshot<T> {
261 snapshot: T,
262 _memory: MemoryReservation,
263}
264
265pub fn retain_record_snapshot<T: CommittedRecordSnapshot + 'static>(
267 snapshot: T,
268 control: &StorageReadControl,
269) -> VersionResult<Arc<dyn CommittedRecordSnapshot>> {
270 control.cancellation().check()?;
271 let memory = control
272 .memory()
273 .reserve(std::mem::size_of::<RetainedSnapshot<T>>())?;
274 Ok(Arc::new(RetainedSnapshot {
275 snapshot,
276 _memory: memory,
277 }))
278}
279
280impl<T: CommittedRecordSnapshot> CommittedRecordSnapshot for RetainedSnapshot<T> {
281 fn sequence(&self) -> CommitSequence {
282 self.snapshot.sequence()
283 }
284 fn reclamation_epoch(&self) -> Option<u64> {
285 self.snapshot.reclamation_epoch()
286 }
287 fn provider_snapshot(&self) -> Option<&dyn std::any::Any> {
288 self.snapshot.provider_snapshot()
289 }
290 fn commit_monitor(&self) -> Option<u64> {
291 self.snapshot.commit_monitor()
292 }
293 fn adopt_commit_monitor(&self, monitor: u64) -> bool {
294 self.snapshot.adopt_commit_monitor(monitor)
295 }
296 fn visit_last_key(
297 &self,
298 prefix: &[u8],
299 before: Option<&[u8]>,
300 control: &StorageReadControl,
301 visit: &mut RecordKeyVisitor<'_>,
302 ) -> VersionResult<()> {
303 self.snapshot.visit_last_key(prefix, before, control, visit)
304 }
305 fn metadata(
306 &self,
307 key: &[u8],
308 control: &StorageReadControl,
309 ) -> VersionResult<Option<RecordMetadata>> {
310 self.snapshot.metadata(key, control)
311 }
312 fn visit_keys(
313 &self,
314 prefix: &[u8],
315 after: Option<&[u8]>,
316 limit: usize,
317 control: &StorageReadControl,
318 visit: &mut RecordKeyVisitor<'_>,
319 ) -> VersionResult<()> {
320 self.snapshot
321 .visit_keys(prefix, after, limit, control, visit)
322 }
323 fn get(
324 &self,
325 key: &[u8],
326 control: &StorageReadControl,
327 ) -> VersionResult<Option<RecordVersion<SharedRecordValue>>> {
328 self.snapshot.get(key, control)
329 }
330 fn scan(
331 &self,
332 prefix: &[u8],
333 after: Option<&[u8]>,
334 limit: usize,
335 control: &StorageReadControl,
336 ) -> VersionResult<BudgetedVec<ScannedRecord>> {
337 self.snapshot.scan(prefix, after, limit, control)
338 }
339 fn visit_value(
340 &self,
341 key: &[u8],
342 control: &StorageReadControl,
343 visit: &mut RecordValueVisitor<'_>,
344 ) -> VersionResult<()> {
345 self.snapshot.visit_value(key, control, visit)
346 }
347 fn visit_values(
348 &self,
349 keys: &mut RecordKeyIterator<'_>,
350 control: &StorageReadControl,
351 visit: &mut RecordPointVisitor<'_>,
352 ) -> VersionResult<()> {
353 self.snapshot.visit_values(keys, control, visit)
354 }
355 fn visit_value_bounded(
356 &self,
357 key: &[u8],
358 max_bytes: usize,
359 control: &StorageReadControl,
360 visit: &mut RecordValueVisitor<'_>,
361 ) -> VersionResult<()> {
362 self.snapshot
363 .visit_value_bounded(key, max_bytes, control, visit)
364 }
365 fn visit_prefix(
366 &self,
367 prefix: &[u8],
368 after: Option<&[u8]>,
369 limit: usize,
370 control: &StorageReadControl,
371 visit: &mut RecordScanVisitor<'_>,
372 ) -> VersionResult<()> {
373 self.snapshot
374 .visit_prefix(prefix, after, limit, control, visit)
375 }
376}
377
378pub struct VisibleRecord {
380 original: Option<CommitSequence>,
381 value: Option<SharedRecordValue>,
382 private: bool,
383}
384
385impl VisibleRecord {
386 pub fn original_revision(&self) -> Option<CommitSequence> {
387 self.original
388 }
389
390 pub fn value(&self) -> Option<&[u8]> {
391 self.value.as_ref().map(|value| &***value)
392 }
393
394 pub fn is_private(&self) -> bool {
395 self.private
396 }
397
398 fn committed(version: RecordVersion<SharedRecordValue>) -> Self {
399 let (sequence, value) = version.into_parts();
400 Self {
401 original: Some(sequence),
402 value,
403 private: false,
404 }
405 }
406
407 fn private(write: &PreparedRecordWrite) -> Self {
408 Self {
409 original: write.expected(),
410 value: write.shared_value(),
411 private: true,
412 }
413 }
414}
415
416pub struct ScannedVisibleRecord {
417 pub key: BudgetedVec<u8>,
418 pub record: VisibleRecord,
419}
420
421pub struct MergedRecordSnapshot {
423 committed: Arc<dyn CommittedRecordSnapshot>,
424 private: PrivateRecordSnapshot,
425 serializable: Option<super::SerializableReadContext>,
426}
427
428impl MergedRecordSnapshot {
429 pub(in crate::mvcc) fn retained_source(
430 &self,
431 key: &[u8],
432 control: &StorageReadControl,
433 ) -> VersionResult<Option<Arc<dyn crate::key_value::KeyValueRead + Send + Sync>>> {
434 self.private.retained_source(key, control)
435 }
436
437 pub fn record_revision(
439 &self,
440 database: super::DatabaseId,
441 key: &[u8],
442 control: &StorageReadControl,
443 ) -> VersionResult<Option<VisibleRecordRevision>> {
444 control.check()?;
445 let Some(metadata) = self.metadata(key, control)?.filter(|record| record.live) else {
446 control.check()?;
447 return Ok(None);
448 };
449 let private = self.private_keys(key, None, 1, control)?;
450 let private = private
451 .first()
452 .filter(|record| record.key() == key)
453 .map(super::PrivateRecordKey::revision);
454 control.check()?;
455 Ok(Some(VisibleRecordRevision {
456 database,
457 committed: metadata.revision,
458 private,
459 }))
460 }
461
462 pub fn try_clone(&self) -> VersionResult<Self> {
464 Ok(Self {
465 committed: Arc::clone(&self.committed),
466 private: self.private.try_clone()?,
467 serializable: self.serializable.clone(),
468 })
469 }
470
471 pub fn new(
472 committed: Arc<dyn CommittedRecordSnapshot>,
473 private: PrivateRecordSnapshot,
474 ) -> Self {
475 Self {
476 committed,
477 private,
478 serializable: None,
479 }
480 }
481
482 pub(crate) fn with_serializable(
483 mut self,
484 context: Option<super::SerializableReadContext>,
485 ) -> Self {
486 self.serializable = context;
487 self
488 }
489
490 pub fn serializable(&self) -> Option<&super::SerializableReadContext> {
492 self.serializable.as_ref()
493 }
494
495 pub fn sequence(&self) -> CommitSequence {
496 self.committed.sequence()
497 }
498
499 pub fn private_revision(&self) -> Option<super::PrivateRecordRevision> {
501 self.private.revision()
502 }
503
504 pub fn committed(&self) -> &dyn CommittedRecordSnapshot {
506 self.committed.as_ref()
507 }
508
509 pub(super) fn retain_committed(&self) -> Arc<dyn CommittedRecordSnapshot> {
510 Arc::clone(&self.committed)
511 }
512
513 pub fn private_keys(
515 &self,
516 prefix: &[u8],
517 after: Option<&[u8]>,
518 limit: usize,
519 control: &StorageReadControl,
520 ) -> VersionResult<BudgetedVec<super::PrivateRecordKey>> {
521 self.private.scan_keys(prefix, after, limit, control)
522 }
523
524 pub fn visit_value(
525 &self,
526 key: &[u8],
527 control: &StorageReadControl,
528 visit: &mut RecordValueVisitor<'_>,
529 ) -> VersionResult<()> {
530 if let Some(write) = self.private.get(key, control)? {
531 visit(Some(BorrowedRecord {
532 revision: write.expected(),
533 value: write.value(),
534 }))?;
535 control.cancellation().check()?;
536 return Ok(());
537 }
538 self.committed.visit_value(key, control, visit)
539 }
540
541 pub fn visit_values(
543 &self,
544 keys: &mut RecordKeyIterator<'_>,
545 control: &StorageReadControl,
546 visit: &mut RecordPointVisitor<'_>,
547 ) -> VersionResult<()> {
548 if self.private_revision().is_none() {
549 return self.committed.visit_values(keys, control, visit);
550 }
551 loop {
552 control.check()?;
553 let Some(key) = keys.next() else {
554 return Ok(());
555 };
556 let key = key?;
557 let mut more = true;
558 self.visit_value(&key, control, &mut |record| {
559 more = visit(&key, record)?;
560 Ok(())
561 })?;
562 control.check()?;
563 if !more {
564 return Ok(());
565 }
566 }
567 }
568
569 pub fn visit_value_bounded(
571 &self,
572 key: &[u8],
573 max_bytes: usize,
574 control: &StorageReadControl,
575 visit: &mut RecordValueVisitor<'_>,
576 ) -> VersionResult<()> {
577 control.check()?;
578 if let Some(write) = self.private.get(key, control)? {
579 if let Some(value) = write.value() {
580 control.check_value_size(value.len(), max_bytes)?;
581 }
582 visit(Some(BorrowedRecord {
583 revision: write.expected(),
584 value: write.value(),
585 }))?;
586 control.check()?;
587 return Ok(());
588 }
589 self.committed
590 .visit_value_bounded(key, max_bytes, control, visit)
591 }
592
593 pub fn visit_prefix(
594 &self,
595 prefix: &[u8],
596 after: Option<&[u8]>,
597 limit: usize,
598 control: &StorageReadControl,
599 visit: &mut RecordScanVisitor<'_>,
600 ) -> VersionResult<()> {
601 self.private.visit_merged::<super::projection::Values>(
602 &*self.committed,
603 prefix,
604 after,
605 limit,
606 control,
607 visit,
608 )
609 }
610
611 pub fn metadata(
612 &self,
613 key: &[u8],
614 control: &StorageReadControl,
615 ) -> VersionResult<Option<RecordMetadata>> {
616 if let Some(write) = self.private.get(key, control)? {
617 return Ok(Some(RecordMetadata {
618 revision: write.expected(),
619 live: write.value().is_some(),
620 }));
621 }
622 self.committed.metadata(key, control)
623 }
624
625 pub fn visit_keys(
626 &self,
627 prefix: &[u8],
628 after: Option<&[u8]>,
629 limit: usize,
630 control: &StorageReadControl,
631 visit: &mut RecordKeyVisitor<'_>,
632 ) -> VersionResult<()> {
633 self.private.visit_merged::<super::projection::Keys>(
634 &*self.committed,
635 prefix,
636 after,
637 limit,
638 control,
639 visit,
640 )
641 }
642
643 pub fn has_private_change(
645 &self,
646 key: &[u8],
647 control: &StorageReadControl,
648 ) -> VersionResult<bool> {
649 Ok(self.private.get(key, control)?.is_some())
650 }
651
652 pub fn get(
653 &self,
654 key: &[u8],
655 control: &StorageReadControl,
656 ) -> VersionResult<Option<VisibleRecord>> {
657 if let Some(write) = self.private.get(key, control)? {
658 return Ok(Some(VisibleRecord::private(&write)));
659 }
660 Ok(self
661 .committed
662 .get(key, control)?
663 .map(VisibleRecord::committed))
664 }
665
666 pub fn scan(
668 &self,
669 prefix: &[u8],
670 after: Option<&[u8]>,
671 limit: usize,
672 control: &StorageReadControl,
673 ) -> VersionResult<BudgetedVec<ScannedVisibleRecord>> {
674 control.cancellation().check()?;
675 let mut result = BudgetedVec::new(control.memory());
676 if limit == 0 {
677 return Ok(result);
678 }
679 let (committed, _committed_memory) = self
680 .committed
681 .scan(prefix, after, limit, control)?
682 .into_parts();
683 let (private, _private_memory) = self
684 .private
685 .scan(prefix, after, limit, control)?
686 .into_parts();
687 let mut committed = committed.into_iter().peekable();
688 let mut private = private.into_iter().peekable();
689 while result.len() < limit {
690 control.cancellation().check()?;
691 let order = match (committed.peek(), private.peek()) {
692 (Some(committed), Some(private)) => committed.key.as_ref().cmp(private.key()),
693 (Some(_), None) => Ordering::Less,
694 (None, Some(_)) => Ordering::Greater,
695 (None, None) => break,
696 };
697 let record = match order {
698 Ordering::Less => {
699 let committed = committed.next().expect("peeked committed record");
700 ScannedVisibleRecord {
701 key: committed.key,
702 record: VisibleRecord::committed(committed.version),
703 }
704 }
705 Ordering::Equal => {
706 let committed = committed.next().expect("peeked committed record");
707 let private = private.next().expect("peeked private record");
708 ScannedVisibleRecord {
709 key: committed.key,
710 record: VisibleRecord::private(&private),
711 }
712 }
713 Ordering::Greater => {
714 let private = private.next().expect("peeked private record");
715 let mut key = BudgetedVec::new(control.memory());
716 key.extend_from_slice(private.key())?;
717 ScannedVisibleRecord {
718 key,
719 record: VisibleRecord::private(&private),
720 }
721 }
722 };
723 result.push(record)?;
724 }
725 Ok(result)
726 }
727}