lib

Core libraries for Radroots
git clone https://radroots.dev/git/lib.git
Log | Files | Refs | README

memory_projection_cache.rs (16889B)


      1 use super::{Error, State, projection_batch};
      2 use crate::{
      3     event::{EventSourceToken, SourceGeneration},
      4     projection::{
      5         ProjectionGeneration, ProjectionHealth, ProjectionId, ProjectionSnapshot,
      6         batch::ProjectionWriteScope,
      7         cache::{
      8             PROJECTION_CACHE_COLLECTION_ROWS_MAX, ProjectionCacheCollection, ProjectionCacheLimits,
      9             ProjectionCacheScope, ProjectionCacheUsage,
     10         },
     11     },
     12 };
     13 use std::{
     14     collections::{BTreeMap, BTreeSet},
     15     ops::Bound::{Excluded, Included, Unbounded},
     16     time::{SystemTime, UNIX_EPOCH},
     17 };
     18 
     19 type Identity = (ProjectionId, ProjectionGeneration);
     20 pub(super) type Snapshots = BTreeMap<(ProjectionId, [u8; 32]), ProjectionSnapshot>;
     21 #[derive(Clone, Default)]
     22 pub(super) struct Cache {
     23     pub(super) limits: Option<ProjectionCacheLimits>,
     24     pub(super) owners: BTreeSet<ProjectionId>,
     25     pub(super) protected: BTreeSet<Identity>,
     26     pub(super) retired: BTreeMap<ProjectionId, BTreeSet<ProjectionGeneration>>,
     27     pub(super) snapshot_order: BTreeSet<(ProjectionId, ProjectionGeneration, u64, [u8; 32])>,
     28     pub(super) value_bytes: u64,
     29     pub(super) owner_time_ms: u64,
     30 }
     31 impl Cache {
     32     pub(super) const fn new() -> Self {
     33         Self {
     34             limits: None,
     35             owners: BTreeSet::new(),
     36             protected: BTreeSet::new(),
     37             retired: BTreeMap::new(),
     38             snapshot_order: BTreeSet::new(),
     39             value_bytes: 0,
     40             owner_time_ms: 0,
     41         }
     42     }
     43     pub(super) fn usage(&self) -> ProjectionCacheUsage {
     44         ProjectionCacheUsage {
     45             value_bytes: self.value_bytes,
     46             protected_generations: self.protected.len() as u64,
     47             legacy_snapshots: self.snapshot_order.len() as u64,
     48         }
     49     }
     50     pub(super) fn check_bytes(&self, previous: u64, next: u64) -> Result<u64, Error> {
     51         let value = self
     52             .value_bytes
     53             .checked_sub(previous)
     54             .and_then(|value| value.checked_add(next))
     55             .ok_or(Error::SpaceInsufficient)?;
     56         if next > previous && self.limits.is_some_and(|limit| value > limit.value_bytes()) {
     57             return Err(Error::SpaceInsufficient);
     58         }
     59         Ok(value)
     60     }
     61     pub(super) fn check_protected(&self, identity: &Identity) -> Result<(), Error> {
     62         if !self.protected.contains(identity)
     63             && self
     64                 .limits
     65                 .is_some_and(|limit| self.protected.len() as u64 >= limit.protected_generations())
     66         {
     67             return Err(Error::SpaceInsufficient);
     68         }
     69         Ok(())
     70     }
     71     pub(super) fn time(&mut self, now: u64) -> u64 {
     72         self.owner_time_ms = self.owner_time_ms.max(now);
     73         self.owner_time_ms
     74     }
     75     pub(super) fn expired(&self, created: u64, now: u64) -> bool {
     76         self.limits
     77             .is_some_and(|limit| created > now || now - created >= limit.legacy_age_ms())
     78     }
     79 }
     80 pub(super) fn now() -> Result<u64, Error> {
     81     u64::try_from(
     82         SystemTime::now()
     83             .duration_since(UNIX_EPOCH)
     84             .map_err(|_| Error::InvalidProjectionTimestamp)?
     85             .as_millis(),
     86     )
     87     .map_err(|_| Error::InvalidProjectionTimestamp)
     88 }
     89 pub(super) fn configure(
     90     state: &mut State,
     91     id: ProjectionId,
     92     limits: ProjectionCacheLimits,
     93     now: u64,
     94 ) -> Result<ProjectionCacheUsage, Error> {
     95     ProjectionId::parse(id.as_str())?;
     96     if state
     97         .projection_cache
     98         .limits
     99         .is_some_and(|existing| existing != limits)
    100     {
    101         return Err(Error::ProjectionRevisionConflict);
    102     }
    103     state.projection_cache.limits = Some(limits);
    104     state.projection_cache.owners.insert(id);
    105     state.projection_cache.time(now);
    106     Ok(state.projection_cache.usage())
    107 }
    108 pub(super) fn fence_owner(
    109     state: &State,
    110     generation: SourceGeneration,
    111     id: &ProjectionId,
    112     source: EventSourceToken,
    113     active: Option<ProjectionGeneration>,
    114 ) -> Result<(), Error> {
    115     ProjectionId::parse(id.as_str())?;
    116     if source != EventSourceToken::new(generation, state.event_mutation_epoch) {
    117         return Err(Error::SourceEpochChanged);
    118     }
    119     if state
    120         .projections
    121         .iter()
    122         .find(|value| value.projection_id() == id)
    123         .map(|value| value.generation())
    124         != active
    125     {
    126         return Err(Error::ProjectionRevisionConflict);
    127     }
    128     Ok(())
    129 }
    130 pub(super) fn retire(
    131     state: &mut State,
    132     source: SourceGeneration,
    133     scope: ProjectionCacheScope,
    134 ) -> Result<ProjectionCacheUsage, Error> {
    135     fence_owner(
    136         state,
    137         source,
    138         scope.projection_id(),
    139         scope.source(),
    140         scope.expected_active(),
    141     )?;
    142     let identity = (scope.projection_id().clone(), scope.generation());
    143     let prior = state.projection_generations.get(&identity);
    144     let configured = state
    145         .projection_cache
    146         .owners
    147         .contains(scope.projection_id());
    148     if !configured {
    149         let legacy = state
    150             .projections
    151             .iter()
    152             .find(|value| value.projection_id() == scope.projection_id());
    153         if scope.expected_active() != Some(scope.generation())
    154             || legacy.is_none_or(|value| {
    155                 value.health() != ProjectionHealth::Invalidated
    156                     || value.active_rebuild().is_some()
    157                     || value
    158                         .checkpoint()
    159                         .and_then(|value| value.source_position())
    160                         .is_some_and(|position| position.generation() != source)
    161             })
    162             || prior.is_some_and(|value| value.phase != projection_batch::Phase::Retired)
    163         {
    164             return Err(Error::ProjectionRevisionConflict);
    165         }
    166     }
    167     if scope.expected_active() == Some(scope.generation()) {
    168         let current = state
    169             .projections
    170             .iter()
    171             .find(|value| value.projection_id() == scope.projection_id())
    172             .ok_or(Error::ProjectionRevisionConflict)?;
    173         if current.health() == ProjectionHealth::Ready
    174             && prior.is_none_or(|value| value.scope.source() == scope.source())
    175         {
    176             return Err(Error::ProjectionRevisionConflict);
    177         }
    178     }
    179     let retired = prior.cloned().unwrap_or(projection_batch::Generation {
    180         scope: ProjectionWriteScope::new(
    181             scope.projection_id().clone(),
    182             scope.generation(),
    183             scope.source(),
    184             None,
    185         )?,
    186         phase: projection_batch::Phase::Retired,
    187         rows: 0,
    188         bytes: 0,
    189     });
    190     state.projection_generations.insert(
    191         identity.clone(),
    192         projection_batch::Generation {
    193             phase: projection_batch::Phase::Retired,
    194             ..retired
    195         },
    196     );
    197     state.projection_cache.protected.remove(&identity);
    198     state
    199         .projection_cache
    200         .retired
    201         .entry(identity.0.clone())
    202         .or_default()
    203         .insert(identity.1);
    204     if configured && scope.expected_active() == Some(scope.generation()) {
    205         state
    206             .projections
    207             .retain(|value| value.projection_id() != scope.projection_id());
    208     }
    209     Ok(state.projection_cache.usage())
    210 }
    211 pub(super) fn collect(
    212     state: &mut State,
    213     source: SourceGeneration,
    214     scope: ProjectionCacheScope,
    215     now: u64,
    216 ) -> Result<ProjectionCacheCollection, Error> {
    217     collect_kind(state, source, scope, now, CollectionKind::Generation)
    218 }
    219 
    220 #[derive(Clone, Copy, Eq, PartialEq)]
    221 pub(super) enum CollectionKind {
    222     Generation,
    223     ObsoleteSnapshots,
    224 }
    225 
    226 pub(super) fn collect_kind(
    227     state: &mut State,
    228     source: SourceGeneration,
    229     scope: ProjectionCacheScope,
    230     now: u64,
    231     kind: CollectionKind,
    232 ) -> Result<ProjectionCacheCollection, Error> {
    233     fence_owner(
    234         state,
    235         source,
    236         scope.projection_id(),
    237         scope.source(),
    238         scope.expected_active(),
    239     )?;
    240     if !state
    241         .projection_cache
    242         .owners
    243         .contains(scope.projection_id())
    244     {
    245         return Err(Error::ProjectionRevisionConflict);
    246     }
    247     let identity = (scope.projection_id().clone(), scope.generation());
    248     let reserved = state
    249         .projection_generations
    250         .get(&identity)
    251         .is_some_and(|value| value.phase != projection_batch::Phase::Retired);
    252     let active = scope.expected_active() == Some(scope.generation());
    253     let snapshot_only = kind == CollectionKind::ObsoleteSnapshots;
    254     if snapshot_only {
    255         let invalidated = active
    256             && state.projections.iter().any(|status| {
    257                 status.projection_id() == scope.projection_id()
    258                     && status.health() == ProjectionHealth::Invalidated
    259                     && status.active_rebuild().is_none()
    260             });
    261         let staging = state
    262             .projection_generations
    263             .get(&identity)
    264             .is_some_and(|value| value.phase == projection_batch::Phase::Staging);
    265         if ((reserved || active) && !invalidated) || staging {
    266             return Err(Error::ProjectionRevisionConflict);
    267         }
    268     }
    269     let protected = !snapshot_only && (active || reserved);
    270     let now = state.projection_cache.owner_time_ms.max(now);
    271     let documents: Vec<_> = if protected || snapshot_only {
    272         Vec::new()
    273     } else {
    274         state
    275             .projection_documents
    276             .range((
    277                 Included((identity.0.clone(), identity.1, String::new())),
    278                 Unbounded,
    279             ))
    280             .take_while(|((id, generation, _), _)| id == &identity.0 && generation == &identity.1)
    281             .take(PROJECTION_CACHE_COLLECTION_ROWS_MAX)
    282             .map(|(key, value)| (key.clone(), value.value().len() as u64))
    283             .collect()
    284     };
    285     let mut snapshots = Vec::new();
    286     let remaining = PROJECTION_CACHE_COLLECTION_ROWS_MAX - documents.len();
    287     for key in state
    288         .projection_cache
    289         .snapshot_order
    290         .range((
    291             Included((identity.0.clone(), identity.1, 0, [0; 32])),
    292             Unbounded,
    293         ))
    294         .take_while(|(id, generation, _, _)| id == &identity.0 && generation == &identity.1)
    295         .take(remaining)
    296     {
    297         let pressure = state.projection_cache.limits.is_some_and(|limit| {
    298             state.projection_snapshots.len() as u64 - snapshots.len() as u64
    299                 > limit.legacy_snapshots()
    300         });
    301         if !protected || pressure || state.projection_cache.expired(key.2, now) {
    302             let value = state
    303                 .projection_snapshots
    304                 .get(&(key.0.clone(), key.3))
    305                 .ok_or(Error::CorruptProjectionRecord)?;
    306             snapshots.push((key.clone(), value.value().len() as u64));
    307         } else {
    308             break;
    309         }
    310     }
    311     if protected {
    312         let start = snapshots.last().filter(|(key, _)| key.2 > now).map_or(
    313             (identity.0.clone(), identity.1, now, [255; 32]),
    314             |(key, _)| key.clone(),
    315         );
    316         for key in state
    317             .projection_cache
    318             .snapshot_order
    319             .range((Excluded(start), Unbounded))
    320             .take_while(|(id, generation, _, _)| id == &identity.0 && generation == &identity.1)
    321             .take(remaining - snapshots.len())
    322         {
    323             let value = state
    324                 .projection_snapshots
    325                 .get(&(key.0.clone(), key.3))
    326                 .ok_or(Error::CorruptProjectionRecord)?;
    327             snapshots.push((key.clone(), value.value().len() as u64));
    328         }
    329     }
    330     let freed = documents
    331         .iter()
    332         .map(|(_, bytes)| *bytes)
    333         .chain(snapshots.iter().map(|(_, bytes)| *bytes))
    334         .try_fold(0u64, |sum, bytes| {
    335             sum.checked_add(bytes).ok_or(Error::CorruptProjectionRecord)
    336         })?;
    337     let value_bytes = state
    338         .projection_cache
    339         .value_bytes
    340         .checked_sub(freed)
    341         .ok_or(Error::CorruptProjectionRecord)?;
    342     let mut removed = (documents.len() + snapshots.len()) as u64;
    343     for (key, _) in documents {
    344         state.projection_documents.remove(&key);
    345     }
    346     for (key, _) in snapshots {
    347         state.projection_cache.snapshot_order.remove(&key);
    348         state.projection_snapshots.remove(&(key.0, key.3));
    349     }
    350     state.projection_cache.value_bytes = value_bytes;
    351     state.projection_cache.time(now);
    352     let document_more = !protected
    353         && !snapshot_only
    354         && state
    355             .projection_documents
    356             .range((
    357                 Included((identity.0.clone(), identity.1, String::new())),
    358                 Unbounded,
    359             ))
    360             .next()
    361             .is_some_and(|((id, generation, _), _)| id == &identity.0 && generation == &identity.1);
    362     let snapshot_more = state
    363         .projection_cache
    364         .snapshot_order
    365         .range((
    366             Included((identity.0.clone(), identity.1, 0, [0; 32])),
    367             Unbounded,
    368         ))
    369         .next()
    370         .is_some_and(|(id, generation, created, _)| {
    371             id == &identity.0
    372                 && generation == &identity.1
    373                 && (!protected
    374                     || state.projection_cache.expired(*created, now)
    375                     || state.projection_cache.limits.is_some_and(|limit| {
    376                         state.projection_snapshots.len() as u64 > limit.legacy_snapshots()
    377                     }))
    378         })
    379         || state
    380             .projection_cache
    381             .snapshot_order
    382             .range((
    383                 Excluded((identity.0.clone(), identity.1, now, [255; 32])),
    384                 Unbounded,
    385             ))
    386             .next()
    387             .is_some_and(|(id, generation, _, _)| id == &identity.0 && generation == &identity.1);
    388     if !protected
    389         && !snapshot_only
    390         && !document_more
    391         && !snapshot_more
    392         && state.projection_generations.contains_key(&identity)
    393         && removed < PROJECTION_CACHE_COLLECTION_ROWS_MAX as u64
    394     {
    395         state.projection_generations.remove(&identity);
    396         if let Some(generations) = state.projection_cache.retired.get_mut(&identity.0) {
    397             generations.remove(&identity.1);
    398             if generations.is_empty() {
    399                 state.projection_cache.retired.remove(&identity.0);
    400             }
    401         }
    402         removed += 1;
    403     }
    404     let registration_more =
    405         !protected && !snapshot_only && state.projection_generations.contains_key(&identity);
    406     Ok(ProjectionCacheCollection {
    407         removed_rows: removed,
    408         removed_value_bytes: freed,
    409         more: document_more || snapshot_more || registration_more,
    410         usage: state.projection_cache.usage(),
    411     })
    412 }
    413 
    414 #[cfg(test)]
    415 mod tests {
    416     use super::*;
    417     use crate::{EventStore, ProjectionStore, memory::MemoryStorage};
    418     use futures_executor::block_on;
    419     #[test]
    420     fn projection_cache_memory_owner_time_age_boundary_rollback_and_future_do_not_extend_lifetime()
    421     {
    422         let generation = SourceGeneration::new([9; 32]).unwrap();
    423         let store = MemoryStorage::new(generation);
    424         let id = ProjectionId::parse("clock_cache").unwrap();
    425         let projection_generation = ProjectionGeneration::new([1; 32]).unwrap();
    426         let created = now().unwrap();
    427         let snapshot =
    428             ProjectionSnapshot::new(id.clone(), [1; 32], projection_generation, created, vec![7])
    429                 .unwrap();
    430         block_on(store.put_projection_snapshot(snapshot.clone())).unwrap();
    431         let limits = ProjectionCacheLimits::new(67_108_864, 2, 32, 1_800_000).unwrap();
    432         block_on(store.configure_projection_cache(id.clone(), limits)).unwrap();
    433         {
    434             let mut state = store.state().unwrap();
    435             assert!(!state.projection_cache.expired(created, created + 1_799_999));
    436             assert!(state.projection_cache.expired(created, created + 1_800_000));
    437             assert!(state.projection_cache.expired(created + 1, created));
    438             assert_eq!(
    439                 state.projection_cache.time(created + 1_800_001),
    440                 created + 1_800_001
    441             );
    442             assert_eq!(
    443                 state.projection_cache.time(created - 1),
    444                 created + 1_800_001
    445             );
    446         }
    447         assert_eq!(
    448             block_on(store.projection_snapshot(id.clone(), [1; 32])).unwrap(),
    449             None
    450         );
    451         block_on(store.put_projection_snapshot(snapshot.clone())).unwrap();
    452         assert_eq!(
    453             block_on(store.projection_snapshot(id.clone(), [1; 32])).unwrap(),
    454             None
    455         );
    456         let source = block_on(store.source_token()).unwrap();
    457         let exact =
    458             ProjectionCacheScope::new(id.clone(), projection_generation, source, None).unwrap();
    459         assert_eq!(
    460             block_on(store.collect_projection_cache(exact))
    461                 .unwrap()
    462                 .removed_rows,
    463             1
    464         );
    465         assert_eq!(
    466             block_on(store.put_projection_snapshot(snapshot)),
    467             Err(Error::ProjectionRevisionConflict)
    468         );
    469     }
    470 }