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 }