From 7c5dd6ffb85f208632f7a2018a922b5ef2083c18 Mon Sep 17 00:00:00 2001 From: anoadragon453 Date: Tue, 22 Mar 2022 16:30:53 +0000 Subject: deploy: 6b26536a52f77aa5573b4d2afedae448fac31b7c --- latest/development/room-dag-concepts.html | 66 ++++++++++++++++++++++++------- 1 file changed, 52 insertions(+), 14 deletions(-) (limited to 'latest/development/room-dag-concepts.html') diff --git a/latest/development/room-dag-concepts.html b/latest/development/room-dag-concepts.html index 59cead08ab..183a250718 100644 --- a/latest/development/room-dag-concepts.html +++ b/latest/development/room-dag-concepts.html @@ -99,7 +99,7 @@ @@ -205,24 +205,62 @@ incrementing integer, but backfilled events start with stream_ordering=-1< rather than skipping any that arrived late; whereas if you're looking at a historical section of timeline (i.e. /messages), you want to see the best representation of the state of the room as others were seeing it at the time.

+

Outliers

+

We mark an event as an outlier when we haven't figured out the state for the +room at that point in the DAG yet. They are "floating" events that we haven't +yet correlated to the DAG.

+

Outliers typically arise when we fetch the auth chain or state for a given +event. When that happens, we just grab the events in the state/auth chain, +without calculating the state at those events, or backfilling their +prev_events.

+

So, typically, we won't have the prev_events of an outlier in the database, +(though it's entirely possible that we might have them for some other +reason). Other things that make outliers different from regular events:

+ +

Since outliers are not tied into the DAG, they do not normally form part of the +timeline sent down to clients via /sync or /messages; however there is an +exception:

+

Out-of-band membership events

+

A special case of outlier events are some membership events for federated rooms +that we aren't full members of. For example:

+ +

In all the above cases, we don't have the state for the room, which is why they +are treated as outliers. They are a bit special though, in that they are +proactively sent to clients via /sync.

Forward extremity

-

Most-recent-in-time events in the DAG which are not referenced by any other events' prev_events yet.

-

The forward extremities of a room are used as the prev_events when the next event is sent.

+

Most-recent-in-time events in the DAG which are not referenced by any other +events' prev_events yet. (In this definition, outliers, rejected events, and +soft-failed events don't count.)

+

The forward extremities of a room (or at least, a subset of them, if there are +more than ten) are used as the prev_events when the next event is sent.

+

The "current state" of a room (ie: the state which would be used if we +generated a new event) is, therefore, the resolution of the room states +at each of the forward extremities.

Backward extremity

The current marker of where we have backfilled up to and will generally be the prev_events of the oldest-in-time events we have in the DAG. This gives a starting point when backfilling history.

-

When we persist a non-outlier event, we clear it as a backward extremity and set -all of its prev_events as the new backward extremities if they aren't already -persisted in the events table.

-

Outliers

-

We mark an event as an outlier when we haven't figured out the state for the -room at that point in the DAG yet.

-

We won't necessarily have the prev_events of an outlier in the database, -but it's entirely possible that we might.

-

For example, when we fetch the event auth chain or state for a given event, we -mark all of those claimed auth events as outliers because we haven't done the -state calculation ourself.

+

Note that, unlike forward extremities, we typically don't have any backward +extremity events themselves in the database - or, if we do, they will be "outliers" (see +above). Either way, we don't expect to have the room state at a backward extremity.

+

When we persist a non-outlier event, if it was previously a backward extremity, +we clear it as a backward extremity and set all of its prev_events as the new +backward extremities if they aren't already persisted as non-outliers. This +therefore keeps the backward extremities up-to-date.

State groups

For every non-outlier event we need to know the state at that event. Instead of storing the full state for each event in the DB (i.e. a event_id -> state -- cgit 1.5.1