Message Pagination Tokens

Issue: #187

Matrix rooms are represented as DAGs of events. But making a good UI for that is quite difficult, so the spec requires that we linearize the events. However, the spec doesn’t require us to do this in a specific manner, so this ADR specifies how we decided to implement a consistent linearization in Arminius.

This ADR starts by presenting the necessary background around how federation and DAGs work in Matrix, and how it complicates message ordering.

We then describe the approaches taken by Synapse and Dendrite, and the Stitched Ordering proposal recently made by Andy Balaam and Rich van der Hoof, the tradeoffs of these different implementations, and suggestions for what we should do in Arminius.

Goal

Our goal is to find some ordering, which we can use for every endpoint visible to the client, such that any pair of messages will always appear in the same order. Matrix clients request ordered lists of messages with the following (non-deprecated) endpoints:

• GET /_matrix/client/v3/sync
• GET /_matrix/client/v3/rooms/{roomId}/messages
• GET /_matrix/client/v1/rooms/{roomId}/relations/{eventId}
• GET /_matrix/client/v1/rooms/{roomId}/relations/{eventId}/{relType}
• GET /_matrix/client/v3/rooms/{roomId}/context/{eventId}

Note

This ADR only concerns the ordering events, as returned to the client. Internal representation of events, and the server-server API, remains unchanged.

Background

Matrix Federation

Matrix is a federated protocol, designed for availability and partition tolerance. This means that Matrix should continue working when other homeservers are unreachable, and that when the other homeservers again become reachable the federation should self-repair. This self-repair should not only consist in allowing future messages to be federated after a longer net-split, but any divergent conversations which happened in the meantime must also be reconciled into a coherent history, visible to all users.

The way that this is achieved is by maintaining room history, not as a linear list of events, but as a graph. When adding a new message to the graph, it’s added as a child of all previous leaf events. By giving up on the requirement that all matrix homeservers agree to one ordering of the messages in a room, we allow homeservers to accept messages from clients, even if one or all of the other homeservers in a room are currently down.

Example

Adrian, Bartholemew, and Cedric are discussing how to spend their evening. But after Bartholemew suggests the theatre, Adrian’s homeserver loses its internet connection.

graph LR
    E1("Adrian: Hey folks, what are we doing tonight?")
     --> E2("Bartholemew: We could go to the theatre")
     --> E3("Cedric: Which theatre?");

    E2 --> E4("Adrian: Theatre is dead.")

This does not preclude either Cedric or Adrian from posting messages in the chat, however. Since the homeservers do not have to agree on the ordering of messages in the chat, each homeserver can continue adding messages to the chat, even without talking to the other homeservers. The new messages are simply both appended as children to the last event the homeservers know about, which for both new messages is Bartholemew’s message. When the connection to Adrian’s homeserver is restored, the homeservers exchange the messages they missed in the meantime. This results in Bartholemew’s message having two children.

Warning

Netsplit can last an arbitrarily long time. In practice this means that any homeserver can append elements as children of any other event in the DAG.

Backfills and Federation Transactions

The two major ways Matrix homeservers learn about events on other homeservers is through federation transactions, and backfills. Whenever a user on a homeserver sends a message, the homeserver is supposed to include this message in federation transactions to all other homeservers in the room.

But homeservers can also request events from other homeservers. If a homeserver was down for a long time, or hasn’t been in the room since it was created and is therefore missing events, homeservers can use endpoints such as /GET /_matrix/federation/v1/backfill/{roomId} to retrieve old messages.

Topological Ordering

As mentioned Matrix rooms are represented as Directed Acyclic Graphs (DAG). Creating a topological ordering of a Matrix room consists of putting all the events into a list, ordered such that if event \(a\) is an ancestor of \(b\) in the DAG, then \(a\) MUST come before \(b\) in the list.

Depending on how complicated the DAG gets, there can be an unbounded amount of different valid topological orderings for a given DAG.

Showing the user a topologically ordered list of events is desirable, as human conversations generally follow causality. An event that is a descendant of some other event in the DAG may be in reply to it, and should therefore be shown afterwards.

Stream Order

The stream order is the order in which the events arrive at our homeserver. The matrix protocol presents absolutely no guarantees in which order events will arrive at our homeserver, and therefore, this is a really bad ordering from a user perspective.

Synapse does actually order responses to /sync solely by the stream ordering, the argument being that any new non-backfilled event to your homeserver should be visible to the user. In order for backfilled events not to show up as new in the timeline, backfilled events get a stream ID starting at -1 and counting down.

Depth

Each event in a DAG will have a depth. The depth is a positive integer. The depth of the root event (m.room.create) will be one. For any other event, the depth will be the maximum height of any parent event plus one.

While the federation spec does specify that other homeservers should send the depth of an events they provide, we generally cannot trust this field to be correct, since this leads to a long series of security issues.

Synapse and Dendrite

I looked a bit at what Synapse and Dendrite are doing. They both order events in the /messages API by the depth. If two events have the same depth, they break ties by stream order. For the /sync API, they order events solely by the stream order, to make sure that new events, excluding the backfilled ones, are always shown to the user as soon as the homeserver receives them.

The best documentation of how this works is found in Synapse

Backfilling events is simply appending events to the events table, computing the depth based on their parents, and setting the stream ID, in reverse order (starting from -1, going down).

Example

Consider the following event graph, which we have created on the blue homeserver:

graph LR
    E1(Event 1
    depth=1,stream_id = 1)
    --> E2(Event 2
    depth=2,stream_id = 2)
    --> E3(Event 3
    depth=3,stream_id = 3)
    --> E4(Event 4
    depth=4,stream_id = 4)
    --> E5(Event 5
    depth=5,stream_id = 5);

We are very happy right now, because our DAG is a timeline without any extra effort whatsoever! But then the orange homeserver, from which we were partitioned from for a while, comes back online. In their first federation request after coming back online, they send us a branch of conversation, which is also a child of event 2:

graph LR
    E1(Event 1
    depth=1,stream_id = 1)
    --> E2(Event 2
    depth=2,stream_id = 2)
    --> E3(Event 3
    depth=3,stream_id = 3)
    --> E4(Event 4
    depth=4,stream_id = 4)
    --> E5(Event 5
    depth=5,stream_id = 5);

    E2 --> E6(Event 6
    depth=3,stream_id = 6):::hs2
   --> E7(Event 7
  depth=4,stream_id = 7):::hs2;

classDef hs2 fill:#f96;

When we then linearize the events, by ordering them by depth and breaking ties by the stream order, and we get the timeline:

graph LR
    E1(Event 1
    depth=1,stream_id = 1)
    --> E2(Event 2
    depth=2,stream_id = 2)
    --> E3(Event 3
    depth=3,stream_id = 3)
    --> E6(Event 6
    depth=3,stream_id = 6):::hs2
    --> E4(Event 4
    depth=4,stream_id = 4)
    --> E7(Event 7
    depth=4,stream_id = 7):::hs2
    --> E5(Event 5
    depth=5,stream_id = 5);


classDef hs2 fill:#f96;

Stitched Ordering

There isn’t really a good notion in the spec of what the ordering of messages is supposed to be. Synapse has two inconsistent orderings, the one from /sync, and the one from /messages. Rich van der Hoff and Andy Balaam have been looking into a solution, and recently came up with Stitched Ordering.

Here, an order on events and gaps is maintained, with gaps being “ghost events” we know exist, but do not have synchronized to our homeserver. New events are always inserted at the end of the order, with the exception of when it matches a gap, at which point the new event is inserted into the gap. When several events are received as part of a federation transaction, we can also put them next to each other. So our example would look like this:

graph LR
    E1(Event 1)
    --> E2(Event 2)
    --> E3(Event 3)
    --> E4(Event 4)
    --> E5(Event 5)
    --> E6(Event 6):::hs2
    --> E7(Event 7):::hs2;


classDef hs2 fill:#f96;

Stitched ordering is designed to be compatible with the design goals of the /sync ordering as described in the Synapse and Dendrite section, specifically in showing newly federated (non-backfilled) events as soon as possible to the client. But in order to achieve this, they sacrifice the topological ordering property. As Matrix provides no guarantees to the order in which events are delivered as part of federation transactions, we can receive an event, which is an ancestor of all events known to our homeserver, as part of a federation transaction. This event, Stitched Ordering would simply place at the end, making stitched ordering non-topological.

Warning

This ADR does not contain a complete description of stitched ordering. Much of the following will not make sense if you read the description of stitched ordering linked above.

Message Pagination Token Format

The message pagination token can simply be the nid of the last event in the response to a pagination API, as the order doesn’t change based on when the user starts paginating. In the next request to the pagination API, when the user sends us an event nid as a token, we return the range starting at, but not including the event referred to by the pagination token. Backpaging into the linear order would then be:

SELECT
    event_json
FROM
    events
    JOIN stitched_ordering ON events.nid = stitched_ordering.event_nid
WHERE
    stitched_ordering.order < (SELECT order FROM stitched_ordering WHERE event_id = $1)
    AND events.visible
LIMIT 10;

Interactions with /sync

According to the stitched ordering MSC, the /sync endpoint should also be using the linear ordering. For our implementation, the stream ID will live on, as a way to tell the client API which subset of events in the database should be looked on when constructing responses to /sync.

Let \(R\) be the set of all messages in a room.

When we get a set of messages \(M \subseteq R\), which all have a stream_id greater than since, we recursively construct the sync response for this room \(S\) as the set of messages where:

1. \(m \in M\) and there is no other message in the room with a higher linear_order
2. \(m \in M\) and there exists a message \(m’ \in S\) such that \(m < m’\) but there is no message \(m’’ \in R\) such that \(m < m’’ < m’\).

This guarantees that the ordering provided by /sync is consistent with the linear ordering, but only shows new events in the timeline, not backfilled ones, which is the same behaviour as Synapse and Dendrite currently provide.

Note

Stitched Ordering does not result in other branches of events being lost from /sync. In the stitched ordering example above, the distinct branch of conversation is put after the existing events in the timeline, ensuring that future calls to /sync will learn of the new events in the timeline.

Only backfilled events, which fill out gaps we have passed by in the conversation, will not be sent to clients.

Possible Problems

Topological Ordering

The ordering used in Synapse and Dendrite is topological. However, to maintain a correct topological ordering you have to, for every new event you have, know a full path from your new event to the ordering you’re maintaining.

The three solutions for this are basically:

• Give up on making events visible to the user as soon as you receive them. When you receive an orphan event, fetch the entire ancestry, until you reach an event in your local copy of the DAG.
• Give up on having a consistent ordering. When you receive a new event, you make a guess to where an event may fit in, but you may move the event later when you find out your guess was wrong.
• Give up on having a topological ordering of history. Instead of making sure that we know where new events fit in the ordering, put new events at the end. (Stitched Ordering)

A previous version of this ADR used the first solution. But since when recovering from a fork the amount of messages between the leaves of the fork, which we receive over federation, and the fork point is unbounded, we would potentially have to fetch a lot of messages that a user does not care about, before fetching the last 50 messages from the other branch. And these 50 messages may very well be the messages the user looks at to figure out that they do not care about the rest.

Note however, that to order a new event linearly, we only need to have one parent of the new event in our ordering, because it being a descendant of an element in our ordering is enough evidence that it is not an unknown ancestor of our ordering. So backfilling events does not stop us from receiving or sending new messages, but can be done in the background.

Slow Backfill

graph LR
E1(Event 1)
-->E2(Event 2)
-->E3(Event 3)
-->E4(Event 4);

E2-->E6@{ shape: braces, label: "Evil predecessors"}
-->E7(Evil Event);

In the above DAG, we have a pleasant conversation in Event 1 through 4. However, an evil homeserver has sent us “Evil Event”, which references an unknown number of events, between it and some point in our DAG.

In the stitched ordering, we would have:

graph LR
E1(Event 1)
-->E2(Event 2)
-->E6@{ shape: braces, label: "Gap: Evil predecessors"}
-->E7(Evil Event)
-->E3(Event 3)
-->E4(Event 4);

Fetching the Evil Predecessors will take a very long time. So what should our homeserver do, when a client asks for the message history before message 3? The two options, without touching the matrix spec are:

1. Ignore the gap/fetch messages in the background, and return Evil Event, Event 2 and the predecessors of event 2 first (This is what is suggested by the Stitched Ordering MSC)
2. Don’t return from the /messages call, until we get all the Evil Predecessors from some other homeserver.

The gaps draft MSC should also be noted. This MSC modifies the client API, letting us return information about known gaps in the timeline to clients. But that is not as relevant right now, since no clients support it.

For now, and for our first implementation of the /messages endpoint, I would simply want to, when asked for three predecessors of Event 3, to return Event 1, Event 2, Evil Event, ignoring the gap. The gap could, possibly, be fetched in the background, such that subsequent calls to /messages would contain the evil predecessors.

Overeager Backfill

No matter which ordering we decide, there is a possible attack in not configuring a rate-limit for outgoing backfill requests. If a malicious homeserver sent an event, with a lot of prev_events, it could make our homeserver DOS third homeservers, by sending too many backfill requests. Therefore, outgoing backfill requests should be rate-limited in some manner.

Conclusion

For a design of message ordering, we need to make three decisions, which have been outlined in the following tables:

Handling Orphan Events

As discussed in Potential Problem: Topological Ordering, when receiving an event that we cannot trace back to an ancestor in our existing DAG, we have three options:

Moving events around in the ordering is, in my opinion, a non-starter. It will inevitably mess up client expectations, and gives a bad impression to the user.

A lot of people in the Matrix community seem to have very strong opinions that a homeserver should show incoming (non-backfilled) messages as soon as possible, and would therefore prefer #3. For most chat applications, however I think #2 is far more reasonable.

I suggest making a homeserver that serves both use cases well. We implement #2, with a configurable amount of “effort” put in before giving up, and reverting to #3. When a new event is received, we try for (a number between 0 and infinite) minutes to get the full lineage of the event before adding it to the ordering. If we fail, we make a guess, and put it at the end, like the Stitched Ordering MSC suggests. If the Stitched Ordering MSC ever got merged, and we stuck with #2, it still wouldn’t look like, from the outside, as if we broke the spec. It would just look like federation transactions were delayed a lot.

Displaying Gaps

When a user requests a part of the timeline, but we know we have a gap in this part of the DAG, we need to pick between the three approaches:

Since the first option is a potential security issue, and the third one isn’t in the Matrix spec yet, I suggest we go with the second one.

An objection may be that it is easy to miss events. But since backfilled events in Synapse and Dendrite are also just put in the middle of the timeline, with no notification of the user done, and I’ve never personally had a problem with it, I think it’s fine.

Ordering of Events in /messages

Suggested Approach

For the three comparison tables above, I suggest we go with “Wait until full lineage of event is available”, “Backfill in background, letting user scroll on”, and “Stitched Ordering”.

To implement the stitched ordering in SQL, I suggest we use a lexicographic ordering key for our events.

Appendix: Storing Lists in Postgres with Sublinear Insertion

Warning

The version of the algorithm described here is outdated. A better design was found while implementing. For an up-to-date description of the ordering, see the rustdoc

The only feasible way to store a list in postgres, where we can insert events at any point in the list without having to renumber all subsequent elements, is by doing lexicographic ordering on a column.

Of course we could also be storing a linked list, requiring us to only update the predecessor and the successor element when inserting a new one. But this would make reading from the database prohibitively expensive.

The solution to this is to use a lexicographic ordering key. Lexicographic ordering is exactly the same way you order stuff in a dictionary. If you have two words “apple” and “angle”, and want to know which word should come first, you compare the first letter. Whatever word has the smallest first letter, is the smallest word. If both words have the same first letter, you continue until you find two different letters. In our example, we find that the second letter of each word is different. Since “n” is smaller than “p”, we now know that “angle” is smaller than “apple”.

If we have two words, where one is a shorter version of the other one, such as “tree” and “treeness”, the shorter word is smallest.

Let’s apply this principle to storing an ordered grocery list in postgresql. We would create the schema:

CREATE TABLE grocery_list (
  item TEXT PRIMARY KEY,
  ordering BIGINT[] NOT NULL
)

where items on our grocery list are just strings, stores as TEXT in postgresql, and our ordering is an array of bigints.

To create our initial shopping list, we execute some SQL statements:

INSERT INTO grocery_list (item, ordering)
    VALUES ('apple','{1}'),
    ('pear','{2}'),
    ('banana', '{3}');

If we want to insert rye bread directly after “pear”, we can do

INSERT INTO grocery_list (item, ordering) VALUES ('rye bread', '{2, 1}');

This would give us the grocery list:

If we then want to insert “potatoes” directly after “pear”, but before “rye bread”, we can do:

INSERT INTO grocery_list (item, ordering) VALUES ('potatoes', '{2, 0}');

This would give us the grocery list:

Algorithm

Given a list \(L \in \mathbb{N}^*\), to find an unoccupied space directly after any item \(\mathbf{a}\), we can use the following algorithm:

1. Let \(\mathbf{a’} = (a_1, a_2, \dots, a_n + 1)\) be a new ordering key, the same as \(\mathbf{a}\) but with the last item incremented by one. If \(\mathbf{a’} \not \in L\), return \(\mathbf{a’}\)
2. Otherwise, there is already an element directly after \(\mathbf{a}\), and we have to expand the list to insert our new element between \(\mathbf{a}\) and \(\mathbf{a’}\). Let \(\mathbf{a’‘} =(a_1, a_2, \dots a_n, 1)\) be \(\mathbf{a}\), with a one appended. If \(\mathbf{a’‘} \not \in L\), return \(\mathbf{a’’}\)
3. If \(\mathbf{a’‘} \in L\), then we let \(\mathbf{a’‘’}\) be \((a_1, a_2, \dots, a_n, x)\), where \(x\) is the largest integer \(<1\) such that \(\mathbf{a’‘’} \not \in L\).

Given a list \(L\) constructed using this algorithm, if you use the algorithm to insert a new element \(\mathbf{d}\) directly after \(\mathbf{b}\), there will be no element \(\mathbf{c} \in L’\) such that \(\mathbf{b} < \mathbf{c} < \mathbf{d}\).

Proof

Let \(\mathbf{d}\) be our new element inserted directly after \(\mathbf{b}\), and assume there exists an element \(\mathbf{c}\) such that \(\mathbf{b} < \mathbf{c} < \mathbf{d}\).

• If \(\mathbf{d}\) was created using rule 1, then in order for \(\mathbf{c}\) to be \(\mathbf{b} < \mathbf{c} < \mathbf{d}\), it must be the case that \(\mathbf{c}\) has the form \((b_1, b_2, \dots, b_n, x)\), and must therefore have been inserted using rule 2 or 3 after \(\mathbf{a}\). But rules 2 and 3 only would apply if \(\mathbf{d} \in L\) was already in the list, leading to a contradiction.

• If \(\mathbf{d}\) was created using rule 2, then \(\mathbf{c}\) must have the form \((a_1, a_2, \dots, a_n, x)\), where \(x\) is less than one. But that rule would only apply if \(\mathbf{D} \in L\), leading to a contradiction.

• If \(\mathbf{d}\) was created using rule 3, then \(\mathbb{d}\) must have the form \((a_1, a_2, \dots, a_n, x_d)\) \(\mathbf{c}\) must have the form \((a_1, a_2, \dots, a_n, x_c)\), where \(x_c < x_d\) is less than one. But since \(x_d\) was the highest possible integer, before \(x_c\) was in the list, this is a contradiction.

Defragmentation

The ordering key does not have to grow indefinitely. If the ordering key we can always renumber all the elements in our list, to only use length-one ordering keys.

An example (non-performant, only meant for demonstration) SQL query could be:

UPDATE
    grocery_list l
SET
    ordering = ARRAY[l2.seqnum]
FROM (
    SELECT
        l2.*,
        row_number() OVER (ORDER BY ordering) AS seqnum
    FROM
        grocery_list l2) l2
WHERE
    l2.item = l.item;

This SQL query would take the list:

and rewrite it to: