memory_visibility_index.rs (13384B)
1 use super::State; 2 use crate::event::{AdmissionStage, EventId}; 3 use crate::{ 4 Error, 5 event::{ 6 EventSourceToken, SourceGeneration, VisibilityEventMetadata, VisibilityIndexBounds, 7 VisibilityIndexProgress, 8 }, 9 }; 10 use std::collections::{BTreeMap, BTreeSet}; 11 12 #[derive(Clone, Default)] 13 pub(super) struct Index { 14 cursor: Option<Cursor>, 15 pub(super) ready: bool, 16 pub(super) events: BTreeMap<u64, VisibilityEventMetadata>, 17 pub(super) visible: BTreeSet<u64>, 18 pub(super) ids: BTreeMap<EventId, u64>, 19 pub(super) verified: u64, 20 heads: BTreeMap<Vec<u8>, u64>, 21 address_heads: BTreeMap<String, u64>, 22 deletion_events: BTreeSet<(EventId, [u8; 32])>, 23 deletion_addresses: BTreeMap<(String, [u8; 32]), u64>, 24 pending: BTreeSet<(u8, Vec<u8>)>, 25 } 26 27 #[derive(Clone, Copy)] 28 struct Cursor { 29 target: u64, 30 backfill: u64, 31 replay_epoch: u64, 32 } 33 34 impl Index { 35 pub(super) const fn new() -> Self { 36 Self { 37 cursor: Some(Cursor { 38 target: 0, 39 backfill: 0, 40 replay_epoch: 0, 41 }), 42 ready: true, 43 events: BTreeMap::new(), 44 visible: BTreeSet::new(), 45 ids: BTreeMap::new(), 46 verified: 0, 47 heads: BTreeMap::new(), 48 address_heads: BTreeMap::new(), 49 deletion_events: BTreeSet::new(), 50 deletion_addresses: BTreeMap::new(), 51 pending: BTreeSet::new(), 52 } 53 } 54 55 fn refresh(&mut self, position: u64) { 56 let Some(event) = self.events.get(&position) else { 57 return; 58 }; 59 let head = event 60 .head_coordinate 61 .as_ref() 62 .is_none_or(|key| self.heads.get(key) == Some(&position)); 63 let deleted = !event.deletion_request 64 && (self 65 .deletion_events 66 .contains(&(event.event_id, event.author)) 67 || event 68 .deletion_coordinate 69 .as_ref() 70 .is_some_and(|coordinate| { 71 self.deletion_addresses 72 .get(&(coordinate.clone(), event.author)) 73 .is_some_and(|time| *time >= event.created_at) 74 })); 75 if event.stage == AdmissionStage::Visible && !event.ephemeral && head && !deleted { 76 self.visible.insert(position); 77 } else { 78 self.visible.remove(&position); 79 } 80 } 81 82 fn put(&mut self, position: u64, event: VisibilityEventMetadata) { 83 let previously_verified = self 84 .events 85 .get(&position) 86 .is_some_and(|old| old.stage != AdmissionStage::Raw); 87 if !previously_verified && event.stage != AdmissionStage::Raw { 88 self.verified += 1; 89 } 90 self.ids.insert(event.event_id, position); 91 for target in &event.event_targets { 92 self.deletion_events.insert((*target, event.author)); 93 self.pending.insert((0, target.as_bytes().to_vec())); 94 } 95 for coordinate in &event.address_targets { 96 self.deletion_addresses 97 .entry((coordinate.clone(), event.author)) 98 .and_modify(|time| *time = (*time).max(event.created_at)) 99 .or_insert(event.created_at); 100 self.pending.insert((1, coordinate.as_bytes().to_vec())); 101 } 102 let old_head = event 103 .head_coordinate 104 .as_ref() 105 .and_then(|key| self.heads.get(key)) 106 .copied(); 107 let replace = old_head.is_none_or(|old| { 108 self.events.get(&old).is_some_and(|current| { 109 event.created_at > current.created_at 110 || (event.created_at == current.created_at && event.event_id < current.event_id) 111 }) 112 }); 113 if let Some(key) = &event.head_coordinate 114 && replace 115 { 116 self.heads.insert(key.clone(), position); 117 if let Some(old) = old_head.and_then(|old| self.events.get(&old)) 118 && let Some(address) = &old.deletion_coordinate 119 { 120 self.address_heads.remove(address); 121 } 122 if let Some(address) = &event.deletion_coordinate { 123 self.address_heads.insert(address.clone(), position); 124 } 125 } 126 self.events.insert(position, event); 127 if replace && let Some(old) = old_head { 128 self.refresh(old); 129 } 130 self.refresh(position); 131 } 132 133 fn drain(&mut self, maximum: u16, charged: &mut u64, byte_limit: u64) -> Result<u16, Error> { 134 let mut processed = 0; 135 while processed < maximum { 136 let Some((kind, key)) = self.pending.first() else { 137 break; 138 }; 139 let charge = charged 140 .checked_add(4096 + 16 * key.len() as u64) 141 .ok_or(Error::SpaceInsufficient)?; 142 if charge > byte_limit { 143 break; 144 } 145 let position = if *kind == 0 { 146 let id = EventId::from_bytes( 147 key.as_slice() 148 .try_into() 149 .map_err(|_| Error::CorruptStoredEvent)?, 150 ); 151 self.ids.get(&id).copied() 152 } else { 153 let address = std::str::from_utf8(key).map_err(|_| Error::CorruptStoredEvent)?; 154 self.address_heads.get(address).copied() 155 }; 156 self.pending.pop_first(); 157 if let Some(position) = position { 158 self.refresh(position); 159 } 160 *charged = charge; 161 processed += 1; 162 } 163 Ok(processed) 164 } 165 } 166 167 pub(super) fn prepare( 168 generation: SourceGeneration, 169 state: &mut State, 170 bounds: VisibilityIndexBounds, 171 ) -> Result<VisibilityIndexProgress, Error> { 172 let mut charged = 4096 + u64::from(bounds.rows()) * 128; 173 if charged > bounds.bytes() { 174 return Err(Error::SpaceInsufficient); 175 } 176 let sequence = u64::try_from(state.events.len()).map_err(|_| Error::CorruptStoredEvent)?; 177 let mut cursor = state.visibility_index.cursor.unwrap_or(Cursor { 178 target: sequence, 179 backfill: 0, 180 replay_epoch: state.event_mutation_epoch, 181 }); 182 let building = cursor.backfill < cursor.target; 183 let positions = if !state.visibility_index.pending.is_empty() { 184 Vec::new() 185 } else if building { 186 ((cursor.backfill + 1)..=cursor.target) 187 .take(usize::from(bounds.rows())) 188 .collect::<Vec<_>>() 189 } else { 190 state 191 .event_changes 192 .range(( 193 std::ops::Bound::Excluded(cursor.replay_epoch), 194 std::ops::Bound::Unbounded, 195 )) 196 .take(usize::from(bounds.rows())) 197 .map(|(_, sequence)| *sequence) 198 .collect() 199 }; 200 let mut prepared = Vec::new(); 201 for position in positions { 202 let entry = state 203 .events 204 .get(usize::try_from(position - 1).map_err(|_| Error::CorruptStoredEvent)?) 205 .ok_or(Error::CorruptStoredEvent)?; 206 let bytes = u64::try_from(entry.admission.event().raw_json().len()) 207 .map_err(|_| Error::SpaceInsufficient)?; 208 let next_charge = charged 209 .checked_add(VisibilityIndexBounds::charge(bytes)?) 210 .ok_or(Error::SpaceInsufficient)?; 211 if next_charge > bounds.bytes() { 212 if prepared.is_empty() { 213 return Err(Error::SpaceInsufficient); 214 } 215 break; 216 } 217 let metadata = 218 VisibilityEventMetadata::from_event(entry.admission.event(), entry.admission.stage())?; 219 prepared.push((position, metadata)); 220 charged = next_charge; 221 if building { 222 cursor.backfill = position; 223 } else { 224 cursor.replay_epoch = entry.last_mutation_epoch; 225 } 226 } 227 let pending = state 228 .event_changes 229 .range(( 230 std::ops::Bound::Excluded(cursor.replay_epoch), 231 std::ops::Bound::Unbounded, 232 )) 233 .next() 234 .is_some(); 235 let source_complete = cursor.backfill == cursor.target && !pending; 236 if source_complete { 237 cursor.replay_epoch = state.event_mutation_epoch; 238 } 239 let processed = u16::try_from(prepared.len()).map_err(|_| Error::CorruptStoredEvent)?; 240 for (position, event) in prepared { 241 state.visibility_index.put(position, event); 242 } 243 let keys = 244 state 245 .visibility_index 246 .drain(bounds.rows() - processed, &mut charged, bounds.bytes())?; 247 if processed == 0 && keys == 0 && !state.visibility_index.pending.is_empty() { 248 return Err(Error::SpaceInsufficient); 249 } 250 let complete = source_complete && state.visibility_index.pending.is_empty(); 251 if complete && state.visibility_index.events.len() != state.events.len() { 252 return Err(Error::CorruptStoredEvent); 253 } 254 state.visibility_index.cursor = Some(cursor); 255 state.visibility_index.ready = complete; 256 Ok(VisibilityIndexProgress::new( 257 EventSourceToken::new(generation, state.event_mutation_epoch), 258 cursor.backfill, 259 cursor.replay_epoch, 260 processed, 261 charged, 262 complete, 263 ) 264 .with_processed_keys(keys)) 265 } 266 267 #[cfg(test)] 268 mod tests { 269 use super::*; 270 use crate::{EventStore, memory::MemoryStorage}; 271 use futures_executor::block_on; 272 use radroots_event::{SignedEvent, wire::Nip01EventWire}; 273 use radroots_transport::{ 274 Target, TransportId, 275 source::{EventProvenance, ObservedEvent}, 276 }; 277 278 fn admission(content: &str, time: u64) -> crate::event::EventAdmission { 279 let mut wire = Nip01EventWire { 280 id: "0".repeat(64), 281 pubkey: "585591529da0bab31b3b1b1f986611cf5f435dca84f978c89ee8a40cca7103df".to_owned(), 282 created_at: time, 283 kind: 0, 284 tags: vec![], 285 content: content.to_owned(), 286 sig: "42".repeat(64), 287 extra: Default::default(), 288 }; 289 wire.id = wire.computed_event_id().unwrap().to_hex(); 290 let raw = serde_json::to_string(&wire).unwrap(); 291 let event = SignedEvent::from_wire_verified_id(wire, raw).unwrap(); 292 let target = Target::nostr_relay("wss://relay.example").unwrap(); 293 crate::event::EventAdmission::raw(ObservedEvent::new( 294 event, 295 EventProvenance::new(TransportId::NOSTR, target.fingerprint().clone(), 100).unwrap(), 296 )) 297 } 298 299 #[test] 300 fn memory_visibility_index_retains_backfill_and_refuses_oversized_rows_without_partial_state() { 301 let generation = SourceGeneration::new([82; 32]).unwrap(); 302 let storage = MemoryStorage::new(generation); 303 storage.state().unwrap().visibility_index = Index::default(); 304 let first = admission("first", 10); 305 block_on(storage.admit(first.clone())).unwrap(); 306 block_on(storage.admit(admission("second", 20))).unwrap(); 307 let bounds = VisibilityIndexBounds::new(1, 16 * 1024 * 1024).unwrap(); 308 let part = block_on(storage.maintain_visibility(bounds)).unwrap(); 309 assert_eq!(part.source_sequence(), 1); 310 assert!(!part.is_complete()); 311 block_on(storage.admit(admission("third", 30))).unwrap(); 312 let next = block_on(storage.maintain_visibility(bounds)).unwrap(); 313 assert_eq!(next.source_sequence(), 2); 314 assert!(!next.is_complete()); 315 assert!( 316 block_on(storage.maintain_visibility(bounds)) 317 .unwrap() 318 .is_complete() 319 ); 320 assert_eq!(storage.state().unwrap().visibility_index.events.len(), 3); 321 block_on(storage.admit(first)).unwrap(); 322 assert_eq!( 323 block_on(storage.maintain_visibility(bounds)) 324 .unwrap() 325 .processed_rows(), 326 0 327 ); 328 // Exercise explicit maintenance of an already dirty index. Ordinary 329 // ready-index admission is separately covered by indexed-read parity. 330 storage.state().unwrap().visibility_index.ready = false; 331 block_on(storage.admit(admission(&"x".repeat(1000), 40))).unwrap(); 332 assert_eq!( 333 block_on(storage.maintain_visibility(VisibilityIndexBounds::new(1, 10000).unwrap())), 334 Err(Error::SpaceInsufficient) 335 ); 336 assert_eq!(storage.state().unwrap().visibility_index.events.len(), 3); 337 assert!(!storage.state().unwrap().visibility_index.ready); 338 assert!( 339 block_on(storage.maintain_visibility(bounds)) 340 .unwrap() 341 .is_complete() 342 ); 343 } 344 345 #[test] 346 fn memory_visibility_index_empty_source_has_a_real_zero_epoch_fence() { 347 let generation = SourceGeneration::new([83; 32]).unwrap(); 348 let storage = MemoryStorage::new(generation); 349 let progress = block_on( 350 storage.maintain_visibility(VisibilityIndexBounds::new(64, 16 * 1024 * 1024).unwrap()), 351 ) 352 .unwrap(); 353 assert!(progress.is_complete()); 354 assert_eq!(progress.token(), EventSourceToken::new(generation, 0)); 355 assert_eq!(progress.processed_rows(), 0); 356 assert!(storage.state().unwrap().visibility_index.events.is_empty()); 357 } 358 }