Clarify order of initial vs incremental `/sync`

[MadLittleMods]

Link to problem area:

Spec: https://spec.matrix.org/v1.10/client-server-api/#syncing

Events are ordered in this API according to the arrival time of the event on the homeserver. This can conflict with other APIs which order events based on their partial ordering in the event graph. This can result in duplicate events being received (once per distinct API called). Clients SHOULD de-duplicate events based on the event ID when this happens.

Issue

Spawning from a discussion with @erikjohnston,

The spec clearly states that /sync should return events according to the "arrival time of the event on the homeserver" (stream_ordering). This is not how Synapse has been behaving since the beginning. element-hq/synapse@e2accd7 even claims the following in the commit message:

The sync API often returns events in a topological rather than stream
ordering, e.g. when the user joined the room or on initial sync. When
this happens we can reuse existing pagination storage functions.

Normally, this would just be a spec-compliance problem in Synapse but I think this may be the right way to think about it.

Proposal

For initial /sync, we want to view a historical section of the timeline; to fetch events by topological_ordering (partial ordering in the event graph) (best representation of the room DAG as others were seeing it at the time). This also aligns with the order that /messages returns events in. We should also extend this to any time we're initially returning a room (therefore historical events) to the user (like a newly joined room). This behavior basically results in the same outcome as if no history was sent down /sync and /messages was used instead.

For incremental /sync, we want to get all updates for rooms since the last /sync (regardless if those updates arrived late or happened a while ago in the past); to fetch events by stream_ordering (in the order they were received by the server).

Related issues

• CS API refers to undefined terms stream ordering and topological ordering #1334
• Reduce confusion between topological and stream position tokens (SPEC-268) #125
• Consider changing /messages to use stream ordering for events #852
• MSC4033: Explicit ordering of events for receipts matrix-spec-proposals#4033
  • Clarify if notifications are cleared by stream ordering or topological ordering #1167