Skip to main content

tuwunel_service/rooms/timeline/
backfill.rs

1//! Retrieves older room history from federation and inserts validated events.
2//!
3//! Candidate servers are selected from trusted and room-related origins, while
4//! remote timestamp claims are checked against the ingested event. Backfilled
5//! events receive negative stream counts so they sort before normal history.
6
7use std::{collections::HashSet, iter::once, num::NonZeroUsize};
8
9use futures::{
10	FutureExt, StreamExt, TryFutureExt,
11	future::{join, try_join, try_join4},
12};
13use rand::seq::SliceRandom;
14use ruma::{
15	CanonicalJsonObject, EventId, MilliSecondsSinceUnixEpoch, OwnedEventId, RoomId, ServerName,
16	api::Direction, events::TimelineEventType,
17};
18use serde::Deserialize;
19use serde_json::value::RawValue as RawJsonValue;
20use tuwunel_core::{
21	Err, Result, at, debug, debug_warn, implement, is_false,
22	utils::{
23		BoolExt, IterStream, ReadyExt,
24		future::{BoolExt as FutureBoolExt, TryExtExt},
25	},
26	validated, warn,
27};
28use tuwunel_database::Json;
29use tuwunel_matrix::{
30	PduEvent,
31	event::Event,
32	pdu::{PduCount, PduId, RawPduId},
33};
34
35use super::{ExtractBody, bias_count};
36use crate::{
37	federation::Candidates,
38	fetcher::{Op, Opts},
39	rooms::state_accessor::plain_text_topic,
40};
41
42/// Events requested per backfill batch.
43const BACKFILL_LIMIT: NonZeroUsize = NonZeroUsize::new(100).unwrap();
44
45const BACKFILL_ATTEMPT_LIMIT: NonZeroUsize = NonZeroUsize::new(5).unwrap();
46
47const BACKFILL_BATCH_ATTEMPTS: usize = 3;
48
49/// The `event_id` and timestamp parsed back out of an [`Op::TimestampToEvent`]
50/// fetch outcome.
51#[derive(Deserialize)]
52struct TimestampHit {
53	event_id: OwnedEventId,
54	origin_server_ts: MilliSecondsSinceUnixEpoch,
55}
56
57/// Attempts federation backfill when a request reaches local history's edge.
58///
59/// Backfill is skipped after the create event and for effectively empty rooms
60/// that are not world-readable. No candidate, a remote fetch failure, or an
61/// empty accepted chunk is treated as a successful best-effort outcome.
62#[implement(super::Service)]
63#[tracing::instrument(name = "backfill", level = "debug", skip(self))]
64pub async fn backfill_if_required(&self, room_id: &RoomId, from: PduCount) -> Result {
65	let (first_pdu_count, first_pdu) = self.first_item_in_room(room_id).await?;
66
67	if first_pdu_count < from {
68		return Ok(());
69	}
70
71	// No backfill required, reached the end.
72	if *first_pdu.event_type() == TimelineEventType::RoomCreate {
73		return Ok(());
74	}
75
76	let empty_room = self
77		.services
78		.state_cache
79		.room_joined_count(room_id)
80		.map_ok_or(true, |count| count <= 1);
81
82	let not_world_readable = self
83		.services
84		.state_accessor
85		.is_world_readable(room_id)
86		.map(is_false!());
87
88	// Room is empty (1 user or none), there is no one that can backfill
89	if empty_room.and(not_world_readable).await {
90		return Ok(());
91	}
92
93	let mut eligible = self.backfill_candidates(room_id).await;
94
95	let no_backfill = || {
96		warn!(%room_id, "No servers could backfill, but backfill was needed");
97		Ok(())
98	};
99
100	// Empty here, rather than deferring to the fetcher, keeps backfill scoped to
101	// the authoritative servers; the fetcher would otherwise fall back to the
102	// room's whole population.
103	if eligible.is_empty() {
104		return no_backfill();
105	}
106
107	for _ in 0..BACKFILL_BATCH_ATTEMPTS {
108		let opts = Opts::new(Op::Backfill, room_id.to_owned())
109			.event_id(first_pdu.event_id().to_owned())
110			.candidates(eligible.iter().cloned())
111			.attempt_limit(BACKFILL_ATTEMPT_LIMIT)
112			.backfill_limit(BACKFILL_LIMIT);
113
114		let Ok(outcome) = self.services.fetcher.fetch(opts).await else {
115			return no_backfill();
116		};
117
118		let pdus: Vec<Box<RawJsonValue>> = serde_json::from_slice(&outcome.bytes)?;
119		let batch_size = pdus.len();
120		let prepended = pdus
121			.into_iter()
122			.stream()
123			.fold(0_usize, async |prepended, pdu| {
124				let inserted = self
125					.backfill_pdu(room_id, &outcome.origin, pdu)
126					.await
127					.inspect_err(|e| debug_warn!(%room_id, %e, "Failed to add backfilled pdu"))
128					.unwrap_or(false);
129
130				prepended.saturating_add(usize::from(inserted))
131			})
132			.await;
133
134		debug!(
135			%room_id,
136			origin = %outcome.origin,
137			batch_size,
138			prepended,
139			"Processed backfill response",
140		);
141
142		if prepended > 0 {
143			return Ok(());
144		}
145
146		eligible.retain(|server| server != &outcome.origin);
147		if eligible.is_empty() {
148			break;
149		}
150	}
151
152	warn!(%room_id, "Backfill was required but prepended no events");
153	Ok(())
154}
155
156#[implement(super::Service)]
157async fn backfill_candidates(&self, room_id: &RoomId) -> Candidates {
158	let canonical_alias = self
159		.services
160		.state_accessor
161		.get_canonical_alias(room_id);
162
163	let power_levels = self
164		.services
165		.state_accessor
166		.get_power_levels(room_id);
167
168	let (canonical_alias, power_levels) = join(canonical_alias, power_levels).await;
169
170	let power_servers = power_levels
171		.iter()
172		.flat_map(|power| {
173			power
174				.rules
175				.privileged_creators
176				.iter()
177				.flat_map(|creators| creators.iter())
178		})
179		.chain(power_levels.iter().flat_map(|power| {
180			power
181				.users
182				.iter()
183				.filter_map(|(user_id, level)| level.gt(&power.users_default).then_some(user_id))
184		}))
185		.filter_map(|user_id| {
186			self.services
187				.globals
188				.user_is_local(user_id)
189				.is_false()
190				.then_some(user_id.server_name())
191		})
192		.collect::<HashSet<_>>();
193
194	let power_servers = {
195		let mut vec: Vec<_> = power_servers
196			.into_iter()
197			.map(ToOwned::to_owned)
198			.collect();
199
200		vec.shuffle(&mut rand::rng());
201		vec.into_iter().stream()
202	};
203
204	let canonical_room_alias_server = once(canonical_alias)
205		.filter_map(Result::ok)
206		.map(|alias| alias.server_name().to_owned())
207		.stream();
208
209	let trusted_servers = self
210		.services
211		.server
212		.config
213		.federation
214		.keys
215		.trusted_servers
216		.iter()
217		.map(ToOwned::to_owned)
218		.stream();
219
220	power_servers
221		.chain(canonical_room_alias_server)
222		.chain(trusted_servers)
223		.ready_filter(|server_name| !self.services.globals.server_is_ours(server_name))
224		.filter_map(async |server_name| {
225			self.services
226				.state_cache
227				.server_in_room(&server_name, room_id)
228				.await
229				.then_some(server_name)
230		})
231		.collect()
232		.await
233}
234
235#[implement(super::Service)]
236/// Finds the nearest event to a timestamp with a federation fallback.
237///
238/// The local answer is retained unless a closer remote claim can be ingested.
239/// The ingested event must belong to this room and its actual timestamp must
240/// remain on the requested side of the query.
241pub async fn get_event_id_near_ts_with_fallback(
242	&self,
243	room_id: &RoomId,
244	ts: MilliSecondsSinceUnixEpoch,
245	dir: Direction,
246) -> Result<(MilliSecondsSinceUnixEpoch, OwnedEventId)> {
247	let local = self.get_event_id_near_ts(room_id, ts, dir).await;
248
249	let federate = match &local {
250		| Err(_) => true,
251		| Ok((_, event_id)) =>
252			dir == Direction::Forward && self.is_start_edge_hit(room_id, event_id).await,
253	};
254
255	if !federate {
256		return local;
257	}
258
259	let candidates = self.backfill_candidates(room_id).await;
260
261	if candidates.is_empty() {
262		return local;
263	}
264
265	let opts = Opts::new(Op::TimestampToEvent, room_id.to_owned())
266		.ts(ts)
267		.dir(dir)
268		.candidates(candidates)
269		.checks(false);
270
271	let Ok(outcome) = self.services.fetcher.fetch(opts).await else {
272		return local;
273	};
274
275	let Ok(TimestampHit { event_id, origin_server_ts }) = serde_json::from_slice(&outcome.bytes)
276	else {
277		return local;
278	};
279
280	if let Ok((local_ts, local_id)) = &local
281		&& !nearer(dir, origin_server_ts, *local_ts)
282	{
283		return Ok((*local_ts, local_id.clone()));
284	}
285
286	// Fail closed: an un-ingested event can't be visibility-checked, so keep local.
287	let Ok(pdu) = self
288		.backfill_event(room_id, &event_id, &outcome.origin)
289		.inspect_err(|e| debug_warn!(%room_id, error = ?e, "timestamp fallback backfill failed"))
290		.await
291	else {
292		return local;
293	};
294
295	let actual_ts = pdu.origin_server_ts();
296	let matches_direction = match dir {
297		| Direction::Forward => actual_ts >= ts,
298		| Direction::Backward => actual_ts <= ts,
299	};
300
301	if actual_ts != origin_server_ts || !matches_direction {
302		debug_warn!(
303			%room_id,
304			%event_id,
305			?dir,
306			?ts,
307			?origin_server_ts,
308			?actual_ts,
309			"timestamp fallback claim was inconsistent with the ingested event"
310		);
311		return local;
312	}
313
314	Ok((actual_ts, event_id))
315}
316
317#[implement(super::Service)]
318async fn is_start_edge_hit(&self, room_id: &RoomId, event_id: &EventId) -> bool {
319	self.first_item_in_room(room_id)
320		.await
321		.is_ok_and(|(_, first)| {
322			*first.event_type() != TimelineEventType::RoomCreate && first.event_id() == event_id
323		})
324}
325
326fn nearer(dir: Direction, a: MilliSecondsSinceUnixEpoch, b: MilliSecondsSinceUnixEpoch) -> bool {
327	match dir {
328		| Direction::Forward => a < b,
329		| Direction::Backward => a > b,
330	}
331}
332
333#[implement(super::Service)]
334async fn backfill_event(
335	&self,
336	room_id: &RoomId,
337	event_id: &EventId,
338	origin: &ServerName,
339) -> Result<PduEvent> {
340	let opts = Opts::new(Op::Backfill, room_id.to_owned())
341		.event_id(event_id.to_owned())
342		.candidates([origin.to_owned()])
343		.backfill_limit(BACKFILL_LIMIT);
344
345	let outcome = self.services.fetcher.fetch(opts).await?;
346
347	let pdus: Vec<Box<RawJsonValue>> = serde_json::from_slice(&outcome.bytes)?;
348
349	let ingestion = pdus
350		.into_iter()
351		.stream()
352		.fold(Ok(()), async |prior, pdu| {
353			let current = self
354				.backfill_pdu(room_id, &outcome.origin, pdu)
355				.map_ok(|_| ())
356				.inspect_err(
357					|e| debug_warn!(%room_id, error = ?e, "Failed to add backfilled pdu"),
358				)
359				.await;
360
361			prior.and(current)
362		})
363		.await;
364
365	match self.get_pdu_count(event_id).await {
366		| Err(error) => ingestion.and(Err(error)),
367		| Ok(_) => {
368			let pdu = self.get_pdu(event_id).await?;
369
370			if pdu.room_id() != room_id {
371				return Err!(Request(NotFound(
372					"Timestamp fallback target belongs to another room."
373				)));
374			}
375
376			Ok(pdu)
377		},
378	}
379}
380
381/// Fetches one remote event and persists it through the backfill path.
382///
383/// Fetcher checks are disabled only for retrieval; `backfill_pdu`
384/// performs signature, hash, and authorization validation. An event already
385/// accepted completes successfully without another insertion, while a stored
386/// outlier is still validated and promoted.
387#[implement(super::Service)]
388#[tracing::instrument(skip(self), level = "debug")]
389pub async fn fetch_remote_event(&self, room_id: &RoomId, event_id: &EventId) -> Result {
390	let opts = Opts::new(Op::Event, room_id.to_owned())
391		.event_id(event_id.to_owned())
392		.checks(false);
393
394	let outcome = self.services.fetcher.fetch(opts).await?;
395
396	let pdu: Box<RawJsonValue> = serde_json::from_slice(&outcome.bytes)?;
397
398	self.backfill_pdu(room_id, &outcome.origin, pdu)
399		.await?;
400
401	Ok(())
402}
403
404/// Validates and inserts one remotely supplied event as backfilled history.
405///
406/// An already accepted duplicate returns `false` without insertion. A new event
407/// or stored outlier receives a negative backfill count, moves to accepted
408/// storage, updates its timestamp and ID indexes, and adds searchable message
409/// or topic content.
410#[implement(super::Service)]
411#[tracing::instrument(skip(self, pdu), level = "debug")]
412pub async fn backfill_pdu(
413	&self,
414	room_id: &RoomId,
415	origin: &ServerName,
416	pdu: Box<RawJsonValue>,
417) -> Result<bool> {
418	let parsed = self
419		.services
420		.event_handler
421		.parse_incoming_pdu(&pdu);
422
423	// Lock so we cannot backfill the same pdu twice at the same time
424	let mutex_lock = self
425		.services
426		.event_handler
427		.mutex_federation
428		.lock(room_id)
429		.map(Ok);
430
431	let ((_, event_id, value), mutex_lock) = try_join(parsed, mutex_lock).await?;
432
433	let existed = self
434		.services
435		.event_handler
436		.handle_incoming_pdu(origin, room_id, &event_id, value, false)
437		.await?
438		.map(at!(1))
439		.is_some_and(is_false!());
440
441	// Bail if the PDU already exists; a duplicate insertion is not good.
442	if existed {
443		return Ok(false);
444	}
445
446	let pdu = self.get_pdu(&event_id);
447
448	let value = self.get_pdu_json(&event_id);
449
450	let shortroomid = self.services.short.get_shortroomid(room_id);
451
452	let insert_lock = self.mutex_insert.lock(room_id).map(Ok);
453
454	let (pdu, value, shortroomid, insert_lock) =
455		try_join4(pdu, value, shortroomid, insert_lock).await?;
456
457	// A pdu_id is not returned from handle_incoming_pdu() when accepting a new
458	// event on this codepath. The pdu_id is instead created here in ℤ−
459	let count = self.services.globals.next_count();
460	let count: i64 = (*count).try_into()?;
461	let pdu_id: RawPduId = PduId {
462		shortroomid,
463		count: PduCount::Backfilled(validated!(0 - count)),
464	}
465	.into();
466
467	// Insert pdu
468	self.prepend_backfill_pdu(
469		&pdu_id,
470		room_id,
471		&event_id,
472		u64::from(pdu.origin_server_ts),
473		&value,
474	);
475	drop(insert_lock);
476
477	match pdu.kind {
478		| TimelineEventType::RoomMessage => {
479			if let Ok(ExtractBody { body: Some(body) }) = pdu.get_content() {
480				self.services
481					.search
482					.index_pdu(shortroomid, &pdu_id, &body);
483			}
484		},
485		| TimelineEventType::RoomTopic =>
486			if let Some(topic) = pdu.get_content().ok().and_then(plain_text_topic) {
487				self.services
488					.search
489					.index_pdu(shortroomid, &pdu_id, &topic);
490			},
491		| _ => {},
492	}
493
494	drop(mutex_lock);
495
496	debug!("Prepended backfill pdu");
497	Ok(true)
498}
499
500#[implement(super::Service)]
501fn prepend_backfill_pdu(
502	&self,
503	pdu_id: &RawPduId,
504	room_id: &RoomId,
505	event_id: &EventId,
506	origin_server_ts: u64,
507	json: &CanonicalJsonObject,
508) {
509	let mut txn = self.db.db.txn();
510
511	txn.raw_put(&self.db.pduid_pdu, pdu_id, Json(json));
512	txn.insert_raw(&self.db.eventid_pduid, event_id, pdu_id);
513	txn.del_raw(&self.db.eventid_outlierpdu, event_id);
514
515	let count_key = bias_count(pdu_id.count());
516	let key = (room_id, origin_server_ts, count_key);
517	txn.put_raw(&self.db.roomid_tscount_pducount, key, pdu_id.count());
518
519	txn.execute();
520}