lib

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

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 }