tuwunel_service/rooms/state_compressor/
mod.rs1use std::{
8 collections::{BTreeSet, HashMap},
9 fmt::{Debug, Write},
10 sync::{Arc, Mutex},
11};
12
13use async_trait::async_trait;
14use futures::{Stream, StreamExt};
15use lru_cache::LruCache;
16use ruma::{EventId, RoomId};
17use tuwunel_core::{
18 Result,
19 arrayvec::ArrayVec,
20 at, checked, err, expected, implement, utils,
21 utils::{bytes, math::usize_from_f64, stream::IterStream},
22};
23use tuwunel_database::{Map, Txn};
24
25use crate::rooms::short::{ShortEventId, ShortId, ShortStateHash, ShortStateKey};
26
27pub struct Service {
33 pub stateinfo_cache: Mutex<StateInfoLruCache>,
35 db: Data,
36 services: Arc<crate::services::OnceServices>,
37}
38
39struct Data {
40 shortstatehash_statediff: Arc<Map>,
41}
42
43#[derive(Clone)]
49pub(crate) struct StateDiff {
50 pub(crate) parent: Option<ShortStateHash>,
52
53 pub(crate) added: Arc<CompressedState>,
55
56 pub(crate) removed: Arc<CompressedState>,
58}
59
60#[derive(Clone, Default)]
65pub struct ShortStateInfo {
66 pub shortstatehash: ShortStateHash,
68
69 pub full_state: Arc<CompressedState>,
71
72 pub added: Arc<CompressedState>,
74
75 pub removed: Arc<CompressedState>,
77}
78
79#[derive(Clone, Default)]
84pub struct HashSetCompressStateEvent {
85 pub shortstatehash: ShortStateHash,
87
88 pub added: Arc<CompressedState>,
90
91 pub removed: Arc<CompressedState>,
93}
94
95type StateInfoLruCache = LruCache<ShortStateHash, ShortStateInfoVec>;
96type ShortStateInfoVec = Vec<ShortStateInfo>;
97type ParentStatesVec = Vec<ShortStateInfo>;
98
99pub type CompressedState = BTreeSet<CompressedStateEvent>;
104
105pub type CompressedStateEvent = [u8; 2 * size_of::<ShortId>()];
110
111#[async_trait]
112impl crate::Service for Service {
113 fn build(args: &crate::Args<'_>) -> Result<Arc<Self>> {
114 let config = &args.server.config;
115 let cache_capacity =
116 f64::from(config.cache.stateinfo_capacity) * config.cache.capacity_modifier;
117
118 Ok(Arc::new(Self {
119 stateinfo_cache: LruCache::new(usize_from_f64(cache_capacity)?).into(),
120 db: Data {
121 shortstatehash_statediff: args.db["shortstatehash_statediff"].clone(),
122 },
123 services: args.services.clone(),
124 }))
125 }
126
127 async fn memory_usage(&self, out: &mut (dyn Write + Send)) -> Result {
128 let (cache_len, ents) = {
129 let cache = self.stateinfo_cache.lock().expect("locked");
130 let ents = cache
131 .iter()
132 .map(at!(1))
133 .flat_map(|vec| vec.iter())
134 .fold(HashMap::new(), |mut ents, ssi| {
135 for cs in &[&ssi.added, &ssi.removed, &ssi.full_state] {
136 ents.insert(Arc::as_ptr(cs), compressed_state_size(cs));
137 }
138
139 ents
140 });
141
142 (cache.len(), ents)
143 };
144
145 let ents_len = ents.len();
146 let bytes = ents
147 .values()
148 .copied()
149 .fold(0_usize, usize::saturating_add);
150
151 let bytes = bytes::pretty(bytes);
152 writeln!(out, "- stateinfo_cache: {cache_len} entries, {ents_len} states ({bytes})")?;
153
154 Ok(())
155 }
156
157 async fn clear_cache(&self) {
158 self.stateinfo_cache
159 .lock()
160 .expect("locked")
161 .clear();
162 }
163
164 fn name(&self) -> &str { crate::service::make_name(std::module_path!()) }
165}
166
167#[implement(Service)]
173#[tracing::instrument(name = "load", level = "debug", skip(self))]
174pub async fn load_shortstatehash_info(
175 &self,
176 shortstatehash: ShortStateHash,
177) -> Result<ShortStateInfoVec> {
178 if let Some(r) = self
179 .stateinfo_cache
180 .lock()?
181 .get_mut(&shortstatehash)
182 {
183 return Ok(r.clone());
184 }
185
186 let stack = self
187 .new_shortstatehash_info(shortstatehash)
188 .await?;
189
190 self.cache_shortstatehash_info(shortstatehash, stack.clone())
191 .await?;
192
193 Ok(stack)
194}
195
196#[implement(Service)]
200#[tracing::instrument(
201 name = "cache",
202 level = "debug",
203 skip_all,
204 fields(
205 ?shortstatehash,
206 stack = stack.len(),
207 ),
208 )]
209async fn cache_shortstatehash_info(
210 &self,
211 shortstatehash: ShortStateHash,
212 stack: ShortStateInfoVec,
213) -> Result {
214 self.stateinfo_cache
215 .lock()?
216 .insert(shortstatehash, stack);
217
218 Ok(())
219}
220
221#[implement(Service)]
222async fn new_shortstatehash_info(
223 &self,
224 shortstatehash: ShortStateHash,
225) -> Result<ShortStateInfoVec> {
226 let StateDiff { parent, added, removed } = self.get_statediff(shortstatehash).await?;
227
228 let Some(parent) = parent else {
229 return Ok(vec![ShortStateInfo {
230 shortstatehash,
231 full_state: added.clone(),
232 added,
233 removed,
234 }]);
235 };
236
237 let mut stack = Box::pin(self.load_shortstatehash_info(parent)).await?; let top = stack.last().expect("at least one frame");
240
241 let mut full_state = (*top.full_state).clone();
242 full_state.extend(added.iter().copied());
243
244 let removed = (*removed).clone();
245 for r in &removed {
246 full_state.remove(r);
247 }
248
249 stack.push(ShortStateInfo {
250 shortstatehash,
251 added,
252 removed: Arc::new(removed),
253 full_state: Arc::new(full_state),
254 });
255
256 Ok(stack)
257}
258
259#[implement(Service)]
264pub fn compress_state_events<'a, I>(
265 &'a self,
266 state: I,
267) -> impl Stream<Item = CompressedStateEvent> + Send + 'a
268where
269 I: Iterator<Item = (&'a ShortStateKey, &'a EventId)> + Clone + Debug + Send + 'a,
270{
271 let event_ids = state.clone().map(at!(1));
272
273 let short_event_ids = self
274 .services
275 .short
276 .multi_get_or_create_shorteventid(event_ids);
277
278 state
279 .stream()
280 .map(at!(0))
281 .zip(short_event_ids)
282 .map(|(shortstatekey, shorteventid)| compress_state_event(*shortstatekey, shorteventid))
283}
284
285#[implement(Service)]
289pub async fn compress_state_event(
290 &self,
291 shortstatekey: ShortStateKey,
292 event_id: &EventId,
293) -> CompressedStateEvent {
294 let shorteventid = self
295 .services
296 .short
297 .get_or_create_shorteventid(event_id)
298 .await;
299
300 compress_state_event(shortstatekey, shorteventid)
301}
302
303#[implement(Service)]
309pub fn save_state_from_diff(
310 &self,
311 txn: &mut Txn,
312 shortstatehash: ShortStateHash,
313 statediffnew: Arc<CompressedState>,
314 statediffremoved: Arc<CompressedState>,
315 diff_to_sibling: usize,
316 mut parent_states: ParentStatesVec,
317) -> Result {
318 let statediffnew_len = statediffnew.len();
319 let statediffremoved_len = statediffremoved.len();
320 let diffsum = checked!(statediffnew_len + statediffremoved_len)?;
321
322 if parent_states.len() > 3 {
323 let parent = parent_states
326 .pop()
327 .expect("parent must have a state");
328
329 let mut parent_new = (*parent.added).clone();
330 let mut parent_removed = (*parent.removed).clone();
331
332 for removed in statediffremoved.iter() {
333 if !parent_new.remove(removed) {
334 parent_removed.insert(*removed);
336 }
337 }
340
341 for new in statediffnew.iter() {
342 if !parent_removed.remove(new) {
343 parent_new.insert(*new);
345 }
346 }
349
350 self.save_state_from_diff(
351 txn,
352 shortstatehash,
353 Arc::new(parent_new),
354 Arc::new(parent_removed),
355 diffsum,
356 parent_states,
357 )?;
358
359 return Ok(());
360 }
361
362 if parent_states.is_empty() {
363 self.save_statediff(txn, shortstatehash, &StateDiff {
365 parent: None,
366 added: statediffnew,
367 removed: statediffremoved,
368 });
369
370 return Ok(());
371 }
372
373 let parent = parent_states
378 .pop()
379 .expect("parent must have a state");
380
381 let parent_added_len = parent.added.len();
382 let parent_removed_len = parent.removed.len();
383 let parent_diff = checked!(parent_added_len + parent_removed_len)?;
384
385 if checked!(diffsum * diffsum)? >= checked!(2 * diff_to_sibling * parent_diff)? {
386 let mut parent_new = (*parent.added).clone();
388 let mut parent_removed = (*parent.removed).clone();
389
390 for removed in statediffremoved.iter() {
391 if !parent_new.remove(removed) {
392 parent_removed.insert(*removed);
394 }
395 }
398
399 for new in statediffnew.iter() {
400 if !parent_removed.remove(new) {
401 parent_new.insert(*new);
403 }
404 }
407
408 self.save_state_from_diff(
409 txn,
410 shortstatehash,
411 Arc::new(parent_new),
412 Arc::new(parent_removed),
413 diffsum,
414 parent_states,
415 )?;
416 } else {
417 self.save_statediff(txn, shortstatehash, &StateDiff {
419 parent: Some(parent.shortstatehash),
420 added: statediffnew,
421 removed: statediffremoved,
422 });
423 }
424
425 Ok(())
426}
427
428#[implement(Service)]
434#[tracing::instrument(skip(self, new_state_ids_compressed), level = "debug")]
435pub async fn save_state(
436 &self,
437 room_id: &RoomId,
438 new_state_ids_compressed: Arc<CompressedState>,
439) -> Result<HashSetCompressStateEvent> {
440 let previous_shortstatehash = self
441 .services
442 .state
443 .get_room_shortstatehash(room_id)
444 .await
445 .ok();
446
447 let state_hash = utils::calculate_hash(
448 new_state_ids_compressed
449 .iter()
450 .map(|bytes| &bytes[..]),
451 );
452
453 let existing_shortstatehash = self
454 .services
455 .short
456 .get_shortstatehash(&state_hash)
457 .await
458 .ok();
459
460 if let Some(new_shortstatehash) = existing_shortstatehash
461 .filter(|&new_shortstatehash| previous_shortstatehash.eq(&Some(new_shortstatehash)))
462 {
463 return Ok(HashSetCompressStateEvent {
464 shortstatehash: new_shortstatehash,
465 ..Default::default()
466 });
467 }
468
469 let states_parents = if let Some(p) = previous_shortstatehash {
470 self.load_shortstatehash_info(p)
471 .await
472 .unwrap_or_default()
473 } else {
474 ShortStateInfoVec::new()
475 };
476
477 let (statediffnew, statediffremoved) = if let Some(parent_stateinfo) = states_parents.last() {
478 let statediffnew: CompressedState = new_state_ids_compressed
479 .difference(&parent_stateinfo.full_state)
480 .copied()
481 .collect();
482
483 let statediffremoved: CompressedState = parent_stateinfo
484 .full_state
485 .difference(&new_state_ids_compressed)
486 .copied()
487 .collect();
488
489 (Arc::new(statediffnew), Arc::new(statediffremoved))
490 } else {
491 (new_state_ids_compressed, Arc::new(CompressedState::new()))
492 };
493
494 let new_shortstatehash = if let Some(new_shortstatehash) = existing_shortstatehash {
495 new_shortstatehash
496 } else {
497 self.services
498 .short
499 .get_or_create_shortstatehash(&state_hash, |txn, shortstatehash| {
500 self.save_state_from_diff(
501 txn,
502 shortstatehash,
503 statediffnew.clone(),
504 statediffremoved.clone(),
505 2, states_parents,
507 )
508 })
509 .await?
510 .0
511 };
512
513 Ok(HashSetCompressStateEvent {
514 shortstatehash: new_shortstatehash,
515 added: statediffnew,
516 removed: statediffremoved,
517 })
518}
519
520#[implement(Service)]
529#[tracing::instrument(skip(self), level = "debug", name = "get")]
530pub(crate) async fn get_statediff(&self, shortstatehash: ShortStateHash) -> Result<StateDiff> {
531 const BUFSIZE: usize = size_of::<ShortStateHash>();
532 const STRIDE: usize = size_of::<ShortStateHash>();
533
534 let value = self
535 .db
536 .shortstatehash_statediff
537 .aqry::<BUFSIZE, _>(&shortstatehash)
538 .await
539 .map_err(|e| {
540 err!(Database("Failed to find StateDiff from short {shortstatehash:?}: {e}"))
541 })?;
542
543 let parent = utils::u64_from_bytes(&value[0..size_of::<u64>()])
544 .ok()
545 .take_if(|parent| *parent != 0);
546
547 debug_assert!(value.len().is_multiple_of(STRIDE), "value not aligned to stride");
548 let _num_values = value.len() / STRIDE;
549
550 let mut add_mode = true;
551 let mut added = CompressedState::new();
552 let mut removed = CompressedState::new();
553
554 let mut i = STRIDE;
555 while let Some(v) = value.get(i..expected!(i + 2 * STRIDE)) {
556 if add_mode && v.starts_with(&0_u64.to_be_bytes()) {
557 add_mode = false;
558 i = expected!(i + STRIDE);
559 continue;
560 }
561 if add_mode {
562 added.insert(v.try_into()?);
563 } else {
564 removed.insert(v.try_into()?);
565 }
566 i = expected!(i + 2 * STRIDE);
567 }
568
569 Ok(StateDiff {
570 parent,
571 added: Arc::new(added),
572 removed: Arc::new(removed),
573 })
574}
575
576#[implement(Service)]
582pub(crate) fn save_statediff(
583 &self,
584 txn: &mut Txn,
585 shortstatehash: ShortStateHash,
586 diff: &StateDiff,
587) {
588 let event_count = diff
589 .added
590 .len()
591 .saturating_add(diff.removed.len());
592
593 let event_bytes = event_count.saturating_mul(size_of::<CompressedStateEvent>());
594 let separator_bytes =
595 usize::from(!diff.removed.is_empty()).saturating_mul(size_of::<ShortStateHash>());
596
597 let capacity = size_of::<ShortStateHash>()
598 .saturating_add(event_bytes)
599 .saturating_add(separator_bytes);
600
601 let parent = diff.parent.unwrap_or(0_u64);
602 let mut value = Vec::<u8>::with_capacity(capacity);
603 value.extend_from_slice(&parent.to_be_bytes());
604
605 for new in diff.added.iter() {
606 value.extend_from_slice(&new[..]);
607 }
608
609 if !diff.removed.is_empty() {
610 value.extend_from_slice(&0_u64.to_be_bytes());
611 for removed in diff.removed.iter() {
612 value.extend_from_slice(&removed[..]);
613 }
614 }
615
616 txn.insert_raw(&self.db.shortstatehash_statediff, shortstatehash.to_be_bytes(), value);
617}
618
619#[inline]
623#[must_use]
624pub(crate) fn compress_state_event(
625 shortstatekey: ShortStateKey,
626 shorteventid: ShortEventId,
627) -> CompressedStateEvent {
628 const SIZE: usize = size_of::<CompressedStateEvent>();
629
630 let mut v = ArrayVec::<u8, SIZE>::new();
631 v.extend(shortstatekey.to_be_bytes());
632 v.extend(shorteventid.to_be_bytes());
633 v.as_ref()
634 .try_into()
635 .expect("failed to create CompressedStateEvent")
636}
637
638#[inline]
642#[must_use]
643pub(crate) fn parse_compressed_state_event(
644 compressed_event: CompressedStateEvent,
645) -> (ShortStateKey, ShortEventId) {
646 use utils::u64_from_u8;
647
648 let shortstatekey = u64_from_u8(&compressed_event[0..size_of::<ShortStateKey>()]);
649 let shorteventid = u64_from_u8(&compressed_event[size_of::<ShortStateKey>()..]);
650
651 (shortstatekey, shorteventid)
652}
653
654#[inline]
655fn compressed_state_size(compressed_state: &CompressedState) -> usize {
656 compressed_state
657 .len()
658 .checked_mul(size_of::<CompressedStateEvent>())
659 .expect("CompressedState size overflow")
660}