Skip to main content

tuwunel_service/rooms/state_compressor/
mod.rs

1//! Encodes room state snapshots as compact parent-linked deltas.
2//!
3//! Each state entry combines a short state key with a short event ID in a
4//! fixed-width record. Reconstructed parent chains are cached to make repeated
5//! state resolution inexpensive while bounding persistent diff depth.
6
7use 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
27/// Persists, reconstructs, and caches compressed room state snapshots.
28///
29/// New snapshots are stored as bounded delta chains and flattened when their
30/// depth or relative size becomes inefficient. Cached chain entries include
31/// both each frame's delta and its fully materialized state.
32pub struct Service {
33	/// Reconstructed state chains keyed by their requested short state hash.
34	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/// One state as a delta against a parent state.
44///
45/// `added` and `removed` are the compressed entries this state adds to and
46/// removes from its parent chain's accumulation; a `None` parent makes
47/// `added` the full state.
48#[derive(Clone)]
49pub(crate) struct StateDiff {
50	/// Parent snapshot against which this delta is applied, if any.
51	pub(crate) parent: Option<ShortStateHash>,
52
53	/// Compressed entries added to the parent snapshot.
54	pub(crate) added: Arc<CompressedState>,
55
56	/// Compressed entries removed from the parent snapshot.
57	pub(crate) removed: Arc<CompressedState>,
58}
59
60/// Describes one materialized frame in a compressed state chain.
61///
62/// Frames are ordered from the root snapshot toward the requested snapshot.
63/// Each frame retains its local delta alongside the resulting full state.
64#[derive(Clone, Default)]
65pub struct ShortStateInfo {
66	/// Short hash identifying this state frame.
67	pub shortstatehash: ShortStateHash,
68
69	/// Fully materialized state after applying this frame.
70	pub full_state: Arc<CompressedState>,
71
72	/// Entries added by this frame relative to its parent.
73	pub added: Arc<CompressedState>,
74
75	/// Entries removed by this frame relative to its parent.
76	pub removed: Arc<CompressedState>,
77}
78
79/// Reports a saved snapshot and its change from the room's previous state.
80///
81/// An unchanged snapshot reuses its short hash and returns empty added and
82/// removed sets.
83#[derive(Clone, Default)]
84pub struct HashSetCompressStateEvent {
85	/// Short hash identifying the saved snapshot.
86	pub shortstatehash: ShortStateHash,
87
88	/// Entries present only in the saved snapshot.
89	pub added: Arc<CompressedState>,
90
91	/// Entries present only in the previous snapshot.
92	pub removed: Arc<CompressedState>,
93}
94
95type StateInfoLruCache = LruCache<ShortStateHash, ShortStateInfoVec>;
96type ShortStateInfoVec = Vec<ShortStateInfo>;
97type ParentStatesVec = Vec<ShortStateInfo>;
98
99/// Ordered set of compressed state-key and event-ID pairs.
100///
101/// Ordering makes hashing, differences, and persistent serialization
102/// deterministic for the same logical state.
103pub type CompressedState = BTreeSet<CompressedStateEvent>;
104
105/// Fixed-width encoding of one short state key and short event ID.
106///
107/// The first eight big-endian bytes hold the state key and the remaining eight
108/// hold the event ID.
109pub 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/// Loads and materializes the parent chain for a short state hash.
168///
169/// The returned frames are ordered root-first and include each frame's full
170/// state plus its added and removed entries. A previously reconstructed chain
171/// is returned from the LRU cache.
172#[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/// Caches a reconstructed state chain under its requested short hash.
197///
198/// Lock poisoning is reported without modifying the cache.
199#[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?; // recursion cycle
238
239	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/// Compresses a stream of state-key and event-ID pairs.
260///
261/// Missing short event IDs are allocated as the returned stream is polled, and
262/// each result packs both short IDs into the fixed-width representation.
263#[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/// Compresses one state key and event ID into its fixed-width representation.
286///
287/// A short event ID is allocated first when the event has not been seen.
288#[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/// Stages a compressed state delta under a new short state hash.
304///
305/// The caller-owned transaction receives the row but is not executed here.
306/// Chains deeper than three parent frames, or deltas too large relative to
307/// their parent, are recursively flattened into an earlier layer.
308#[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		// Number of layers
324		// To many layers, we have to go deeper
325		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				// It was not added in the parent and we removed it
335				parent_removed.insert(*removed);
336			}
337			// Else it was added in the parent and we removed it again. We
338			// can forget this change
339		}
340
341		for new in statediffnew.iter() {
342			if !parent_removed.remove(new) {
343				// It was not touched in the parent and we added it
344				parent_new.insert(*new);
345			}
346			// Else it was removed in the parent and we added it again. We
347			// can forget this change
348		}
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		// There is no parent layer, create a new state
364		self.save_statediff(txn, shortstatehash, &StateDiff {
365			parent: None,
366			added: statediffnew,
367			removed: statediffremoved,
368		});
369
370		return Ok(());
371	}
372
373	// Else we have two options.
374	// 1. We add the current diff on top of the parent layer.
375	// 2. We replace a layer above
376
377	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		// Diff too big, we replace above layer(s)
387		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				// It was not added in the parent and we removed it
393				parent_removed.insert(*removed);
394			}
395			// Else it was added in the parent and we removed it again. We
396			// can forget this change
397		}
398
399		for new in statediffnew.iter() {
400			if !parent_removed.remove(new) {
401				// It was not touched in the parent and we added it
402				parent_new.insert(*new);
403			}
404			// Else it was removed in the parent and we added it again. We
405			// can forget this change
406		}
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		// Diff small enough, we add diff as layer on top of parent
418		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/// Saves a complete compressed snapshot and reports its previous-state delta.
429///
430/// An existing content hash is reused; otherwise the short hash and delta row
431/// are created together. Failure to reconstruct the previous chain is treated
432/// as an absent parent, while an exactly unchanged snapshot returns empty sets.
433#[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, // every state change is 2 event changes on average
506					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/// Reads one state's delta row into its typed form.
521///
522/// Rows round-trip through [`save_statediff`], the pair being the only
523/// codec for the statediff encoding.
524///
525/// # Panics
526///
527/// Panics if a stored delta row is shorter than its eight-byte parent prefix.
528#[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/// Serializes one state's delta into the caller's transaction.
577///
578/// Added and removed entries are emitted in sorted set order. The removed run
579/// follows an all-zero sentinel only when it is nonempty, and this method does
580/// not execute the transaction.
581#[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/// Packs a short state key and short event ID into one compressed record.
620///
621/// Both IDs use big-endian encoding so byte ordering follows numeric ordering.
622#[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/// Unpacks a compressed state record into its two short IDs.
639///
640/// This is the inverse of [`compress_state_event`].
641#[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}