ADR: Simplified Sliding Sync

Issue #1741.

At the highest level, sliding sync works by the client being able to filter which rooms they are interested in having updates from (instead of the server fetching every possible room update) using “lists” and “subscriptions”. If none of the filtered rooms have any update, then long-polling starts by the server holding that connection until new data arises.

Terminology Note: In the following document, the Matrix mechanism “Simplified Sliding Sync” (MSC4186) is referred to as “Sync v4”. Code implementations, structs, and database schemas related to this mechanism will use the syncv4 identifier.

Author: Pierre

Co-Authors: Michael Schleicher, Flori Ava Star Weber

Resources

Here are some resources useful to understand simplified sliding sync:

• MSC4186: Simplified Sliding Sync
• A talk about simplified sliding sync
• MSC3575: Sliding Sync (aka Sync v3)

These are Synapse code-parts implementing Sync v4:

• Session Storage
• Session tables: migrations 87 to 93
• Handler
• Types

These are the MSCs defining extensions:

• ToDevice
• Account Data.
• Receipts.
• E2EE.

Acceptance Criteria

This ADR must provide an answer to the following problems:

• How events flow from the room server to the client (via the client server)
• How wakeups are handled for long polling requests
• How connections/sessions are stored/resumed
• How to handle the “sync config” somewhat efficiently
• How this relates to legacy sync and what aspects can be shared

Solution

Storage

In Sync v4, a session is tied to its (user, device, connection id) triplet.

Here is an overview of all the various database tables involved:

erDiagram
  direction LR

  SYNCV4_CONNECTIONS {
    BIGINT nid PK

    BIGINT device_nid FK

    STRING connection_id

    TIMESTAMP last_used_at
  }

  SYNCV4_POSITIONS {
    BIGINT nid PK

    BIGINT connection_nid FK

    BIGINT prev_position_nid FK
  }

  SYNCV4_ROOM_CONFIGS {
    BIGINT nid PK

    BIGINT position_nid FK
    BIGINT room_nid FK

    BIGINT required_state_nid FK

    INT timeline_limit
  }

  SYNCV4_REQUIRED_STATES {
    BIGINT nid PK

    BIGINT connection_nid FK

    JSON required_states
  }

  SYNCV4_ROOM_STREAMS {
    BIGINT nid PK
    BIGINT position_nid FK
    BIGINT room_nid FK

    STREAM_TYPE stream_type

    BIGINT up_to_stream_id
  }

  SYNCV4_CONNECTIONS ||--|{ SYNCV4_POSITIONS: "stores"
  SYNCV4_ROOM_CONFIGS }o--|| SYNCV4_POSITIONS: "full per-room accumulated config"
  SYNCV4_REQUIRED_STATES }o--|| SYNCV4_CONNECTIONS: "deduped per connection"
  SYNCV4_ROOM_STREAMS ||--|{ SYNCV4_POSITIONS: "stores"
  SYNCV4_ROOM_CONFIGS }o--|| SYNCV4_REQUIRED_STATES: "points at deduped list"

Tip

Required states are stored separately so that they can be de-duplicated (i.e. multiple room configs pointing to the same required states table entry).

Note

For the syncv4_rooms_streams, the various streams are:

• events: The highest events.stream_id that has already been sent back to the client.
• receipts: The highest read_receipts.stream_id that has already been sent back to the client.
• todevice: The highest todevice_messages.stream_id that has already been sent back to the client.
• user_keys: The highest user_keys.stream_id that has already been sent back to the client.
• room_account_data: The highest room_account_data.stream_id that has already been sent back to the client.
• global_account_data: The highest global_account_data.stream_id that has already been sent back to the client.

CREATE TABLE syncv4_connections (
  nid BIGINT GENERATED BY DEFAULT AS IDENTITY PRIMARY KEY,

  user_nid int NOT NULL REFERENCES users(nid),
  device_nid int NOT NULL REFERENCES devices(nid),
  -- Connection ID set by the client, can be null.
  conn_id TEXT,

  last_used_at timestamp with time zone NOT NULL DEFAULT now(),

  UNIQUE NULLS NOT DISTINCT(user_id, device_nid, conn_id)
);

CREATE TABLE syncv4_positions (
  nid bigint GENERATED BY DEFAULT AS IDENTITY PRIMARY KEY,

  -- Link to Sync v4 connections/sessions
  connection_nid bigint NOT NULL REFERENCES syncv4_connections(nid) ON DELETE SET NULL,
);

-- The various streams we have in our system
CREATE TYPE stream_type AS ENUM (
  'events',
  'receipts',
  'todevice',
  'user_keys',
  'room_account_data',
  'global_account_data'
);

CREATE TABLE syncv4_rooms_streams (
  position_nid bigint NOT NULL REFERENCES syncv4_positions(nid) ON DELETE CASCADE,

  -- Name of the stream this applies to
  stream_type STREAM_TYPE NOT NULL,

  -- Up to where we have already sent down this stream
  up_to_stream_id bigint,
);

CREATE TABLE syncv4_required_states (
  nid bigint GENERATED BY DEFAULT AS IDENTITY PRIMARY KEY,

  connection_nid bigint NOT NULL REFERENCES syncv4_connections(nid) ON DELETE CASCADE,

  -- The list of `(event_type, state_key)` tuples that were already sent
  required_states JSON[] NOT NULL, -- FIXME: JSON array, or just JSON object ?
);

At the highest level, the general course of actions that happens for every sync request is:

1. Figure out where we are in the session.
2. We get the server’s current stream IDs, this will be the response’s pos.
3. Identify which rooms are filtered in by the request’s config.
4. Check if there is data eligible between the stored room streams and the current server’s streams.
   1. If not, enter long-polling and do notified sync.
5. If yes, generate the response, and advance the individual rooms streams.
6. Answer, setting the pos to the current server’s stream.

The rest of this document should help understanding each of these steps.

Handling Sessions and Positions

Clients are supposed to start by sending a first request without any pos set, and then to, in each request, set the pos to whatever was the last response’s value, like so:

sequenceDiagram

  participant Client
  participant Server

  Note over Client,Server: Initial request should have an empty pos
  Client->>Server: Request 1: pos=None
  Server->>Client: Response: pos=1

  Note over Client,Server: Second request should use the last response's pos
  Client->>Server: Request 2: pos=1
  Server->>Client: Response: pos=2

When receiving a new request, we can construct the (User ID, Device ID, Connection ID) tuple and check in our database to tell in which situation we are:

• Not present: We now need to look at the request’s pos.
  • pos is empty: The user is starting a session, we simply handle that request, and store its state.
  • pos is not empty: We send back a 400 - M_UNKNOWN_POS to the user so that they start a new session with an empty pos.
• Present: We now check which pos we got, based on our stored ones.
  • Last response’s one: We can now assume the client correctly received the previous response. We need to combine the room configs and respond with the response of this combined request. After having answered, we store a new entry for it.
  • Penultimate response’s one: It’s either a duplication, or a cancelled+resent request. We answer to the new request, and we store the new response’s one (See forking).
  • Any other value: It is invalid, we send back a 400 - M_UNKNOWN_POS.

Here is the same decision tree as a diagram:

stateDiagram-v2

checkConn: Check for an entry for this session in our storage
checkPosConn: Check if the **pos** field of the request is set
checkPosNoConn: Check if the **pos** field of the request is set

newSession: New session
resetSession: Session reset
comparePos: Compare with the **pos** we have in storage

redoRequest: Retried position
nextRequest: Next linear position
invalidPos: Answer with <br/>400 - M_UNKNOWN_POS

%% Tree root
[*] --> checkConn: We receive a request

%% First level
checkConn --> checkPosNoConn: No
checkConn --> checkPosConn: Yes

%% Second level - Left
checkPosNoConn --> newSession: No
checkPosNoConn --> invalidPos: Yes

%% Second level - Right
checkPosConn --> resetSession: No
checkPosConn --> comparePos: Yes

%% Second level Right - Sublevel
comparePos --> nextRequest: Equal to last response's new one
comparePos --> redoRequest: Equal to penultimate response's one
comparePos --> invalidPos: Equal to any other value

%% Links to output
newSession --> [*]: New connection with a first position
invalidPos --> [*]
resetSession --> [*]: Delete all positions in session and store first one
nextRequest --> [*]: Store new position, delete penultimate one
redoRequest --> [*]: New forked position

Handling Retries (Aka Forking)

Here is a scenario that will happen, and hence that we have to be able to handle:

1. Client sends the sync request with pos=2 -> We answer it and store the one with next_pos=3
2. Client re-sends again the sync request with pos=2 -> We answer it and store the one with next_pos=3'
3. We receive either pos=3 or pos=3' -> We answer it, delete the now irrelevant one, and store the one with next_pos=4

Note

The solution we come up with needs to work even if the two pos=2 requests hit different sync server instances (i.e. multi-tenancy support).

This is why the syncv4_positions table is shaped this way:

erDiagram
  SYNCV4_POSITIONS {
    BIGINT pos PK
    BIGINT connection_nid FK
    BIGINT prev_position FK
  }

Or in SQL:

CREATE TABLE syncv4_positions (
  -- Auto-incremented unique ID. Part of the `pos` token.
  pos BIGINT NOT NULL AUTO_INCREMENT,

  -- Link to the connection this response belongs to.
  connection_nid BIGINT NOT NULL REFERENCES syncv4_connections(nid),

  -- Self-referencing link to the previous position.
  prev_position BIGINT REFERENCES syncv4_positions(pos) ON DELETE CASCADE
);

And now, how the above scenario plays:

sequenceDiagram
    participant C as Client
    participant CS1 as Client API #35;1
    participant CS2 as Client API #35;2
    participant DB as Database

    C->>CS1: sync (pos=2)
    CS1->>DB: SELECT <CONNECTION_STATE> WHERE syncv4_positions.pos = 2
    Note over DB: DELETE syncv4_positions.prev_position deletes pos=1 here
    DB-->>CS1: per-connection state
    CS1->>CS1: diff vs live room state
    CS1->>DB: INSERT new position (copy data from pos=2)
    DB-->>CS1: pos=3
    CS1-->>C: next_pos=3

    Note over C,DB: Response lost in transit -> Client redoes request with pos=2
    C->>CS2: sync (pos=2) [retry]
    CS2->>DB: SELECT <CONNECTION_STATE> WHERE syncv4_positions.pos = 2
    Note over DB: DELETE syncv4_positions.prev_position deletes nothing this time.
    DB-->>CS2: same per-connection state
    CS2->>CS2: diff vs live room state
    CS2->>DB: INSERT new position (copy data from pos=2)
    DB-->>CS2: pos=3'
    CS2-->>C: next_pos=3'

    NOTE over C,DB: There are now 3 states stored: pos=2, pos=3 and pos=3'

    C->>CS1: sync (pos=3) [client decides to go with pos=3]
    CS1->>DB: SELECT <CONNECTION_STATE> WHERE syncv4_positions.pos = 3

    Note over DB: DELETE syncv4_positions.prev_position deletes pos=2 and pos=3' thanks to cascading.

    DB-->>CS1: per-connection state
    CS1->>CS1: diff vs live room state
    CS1->>DB: INSERT new position (copy data from pos=3)
    DB-->>CS1: pos=4
    CS1-->>C: next_pos=4

Filtering & Activity Ordering

Within sliding sync, a few per-room values are needed to either compute responses, or satisfy filters. These values would very quickly become too costly to compute on each sync request and as such should be stored in pre-populated tables. This section describes such tables, the values they hold, and what is their usage during synchronization.

• syncv4_rooms_info: Stores whether rooms are encrypted or not, and which space they are part of. This is used to satisfy the is_encrypted and spaces filters.

  SQL declaration

  CREATE TABLE syncv4_rooms_info (
    -- The room this entry belongs to.
    room_nid int NOT NULL REFERENCES rooms.nid,
  
    -- Whether this room has a `m.room.encryption` event.
    is_encrypted bool NOT NULL DEFAULT FALSE,
  
    -- The list of **joined** space rooms that contain a
    -- `m.space.child` state event referring to this room.
    spaces TEXT[]
  );
  

• syncv4_max_rooms_streams: This table stores two variables (per room):

  • The highest room event’s stream ID. This is used to compute rooms activity ordering.
  • The highest room bump event’s stream ID. This is used to compute responses bump_stamp field.
  SQL declaration

  CREATE TABLE syncv4_max_room_streams (
    -- The room this entry belongs to.
    room_nid int NOT NULL REFERENCES rooms.nid,
  
    -- Stream ID of the latest event of the room.
    max_event_stream_id bigint NOT NULL,
  
    -- Stream ID of the latest **bump** state event of the room.
    max_bump_event_stream_id bigint NOT NULL,
  );
  

  Note

  When constructing responses, we should sort rooms by their highest bump event stream ID and convert these to their sorted indexes (instead of leaking the actual stream_id of events). As an example, this list of room’s max_bump_event_stream_id: [12, 4, 8, 14, 33] is sorted as [33, 14, 12, 8, 4] (most recent activity first) and then the response’s rooms will get their bump_stamp respectively set to 5, 4, 3, 2 and 1.

Tracking Rooms States

This section will go into details explaining how table syncv4_room_streams works. Here is its declaration:

CREATE TABLE syncv4_room_streams (
  -- Link to the room
  room_nid NOT NULL REFERENCES rooms(nid),

  -- The stream this applies to (e.g. `events` or `receipts`, etc)
  stream_type STREAM_TYPE NOT NULL,

  -- Either `PREVIOUSLY` or `LIVE`
  room_status ROOM_STATUS NOT NULL,

  -- The stream ID up to which this room was last synced. Set when `room_status = PREVIOUSLY`.
  stream_id BIGINT
)

A room status of LIVE means it is up to date with the given sync-token event_stream_position, and a room status of PREVIOUSLY(stream_id) means it was synced up to the stored stream_id.

Now, take the following three rooms, and their respective events. In our scenario, we will sync at events F and I (an initial sync occurred at event A before). The sync at event F will filter in rooms 1 and 2, and the sync at event F will filter in rooms 2 and 3.

flowchart LR
  %% Nodes colors
  classDef blackOutline stroke:#000000,stroke-width:2px
  classDef greenOutline stroke:#00f000,stroke-width:2px
  classDef blueOutline stroke:#0000ff,stroke-width:2px

  %% Room #1 events
  subgraph R1 ["**Room 1**"]
    B@{ shape: circle, class: blue }
    class B blueOutline

    G@{ shape: circle }
    class G blueOutline
  end

  %% Room #2 events
  subgraph R2 ["**Room 2**"]
    C@{ shape: circle }
    class C blueOutline

    D@{ shape: circle }
    class D blueOutline

    I@{ shape: dbl-circ, label: "**I**" }
    class I greenOutline
  end

  %% Room #3 events
  subgraph R3 ["**Room 3**"]
    A@{ shape: dbl-circ, label: "**A**" }
    class A blackOutline

    E@{ shape: circle }
    class E greenOutline

    F@{ shape: circle }
    class F greenOutline

    H@{ shape: dbl-circ, label: "**H**" }
    class H greenOutline
  end

  A --> B
  B --> C
  C --> D
  D --> E
  E --> F
  F --> G
  G --> H
  H --> I

Here is what would be the respective entries for each room in the syncv4_room_streams (for the ‘events’ stream_type):

Tip

Notice how, if we sync again at event I, we won’t need to write anything to the database, as each room is still LIVE. This is intended as to make “syncing nothing” as cheap as possible.

And for each sync request what happens:

• @H (rooms 1 and 2): For each room, the server’s current stream ID (which is H) is higher than the room’s current highest stream ID (respectively G and D). We therefore return the latest timeline_limit events (down to at most pos’s value which is A here) in each room to be responded with (so events [B, C, D, G]), and set the room as being live with the response’s next-pos (i.e. here H). We also store that room 3 has fallen behind from LIVE to PREVIOUSLY(A).
• @I (rooms 2 and 3): For each room, the server’s current stream ID (which is I) is higher or equal than the room’s current highest stream ID (respectively I and H). We therefore return the latest timeline_limit events (down to at most pos’s value which is H here) in each room to be responded with (so events [E, F, H, I]) and set the rooms as being live with the response’s next-pos (i.e. here I).

Sync Token and pos

Sync v4 still requires us to have a sync_token in order to a) handle extensions, and b) tell which rooms are eligible to be in a response. Additionally, we also need to get the new pos value that will be used to tell what is the current connection state and what has already been sent through it.

1. Wrapping: We wrap the existing sync token with the new connection position token like so: ss_<SYNC_TOKEN>_<POSITION_ID>. Which in turn gives: ss_s_<EVENT_POS>_<TODEVICE_POS>_<ACCOUNT_DATA_POS>_<USER_KEYS_POS>_<READ_RECEIPTS_POS>_<POSITION_ID>

2. Prefixing: We prefix the existing sync token with the connection position ID (this is what Synapse chose btw) like so: <POSITION_ID>/<SYNC_TOKEN>. Which in turn gives: <POSITION_ID>/s_<EVENT_POS>_<TODEVICE_POS>_<ACCOUNT_DATA_POS>_<USER_KEYS_POS>_<READ_RECEIPTS_POS>

Notified Sync

Similarly to normal sync, sliding sync must support long-polling requests. As a reminder: these consist in clients specifying a timeout in their requests, and us having to watch if we have new data for them for as long as this timeout lasts before giving up.

In order to do so, a first initial bad idea would be to be busy looping on the database before finally, sometimes, get a little data to send back. Here is instead an hopefully better design for it.

First, each of the handler that produces synchronizable data will also publish NATS notification payloads related to newly written data, and on their dedicated subjects:

flowchart LR
    %% Services
    RS[Roomserver]
    acc[Account Data Handlers]
    e2ee[E2EE Keys Handlers]
    receipts[Receipts Handlers]
    ToDev[ToDevice Messages Handler]

    %% Actors
    SYNC[Sync Endpoint]
    Client

    RS -- events.<ROOM_ID> --> SYNC
    acc -- account.<USER_ID> --> SYNC
    e2ee -- e2ee_keys.<USER_ID>.<TYPE> --> SYNC
    receipts -- receipts.<ROOM_ID> --> SYNC
    ToDev -- todevice.<USER_ID> --> SYNC

    Client -- GET /sync long poll --> SYNC
    SYNC -- response --> Client

Tip

I suggest that we change the existing federation output topic to the new roomserver one, so that a single NATS message can be used to both federate and sync new events.

These notifications need to contain just enough data for the sync endpoint to be able to determine, based on the evaluated sync configuration, if the new data would be returned by the ongoing request:

Caution

FIXME: Do we need to self-contain messages here ? I do not see the benefit of doing so, and I see the downside of increased payload sizes, but maybe some of y’all have other opinion on this.

enum NotificationSubjectType {
    Events,
    AccountData,
    E2EEKeys,
    Receipts,
    ToDeviceMessage,
}

enum E2eeActionType {
    OneTimeKeysCount,
    DeviceLists,
    UnusedFallbackKeysTypes,
}

/// (de)serializes as `<user_id>.<e2ee_action>`
struct E2eeKeysSubject {
    user_id: OwnedUserId,
    e2ee_action: E2eeActionType,
}

enum Subject {
    Events(OwnedRoomId),
    AccountData(OwnedUserId),
    E2eeKeys(E2eeKeysSubject),
    Receipts(OwnedRoomId),
    ToDevice(OwnedUserId),
}

struct NotificationSubject {
    notification_type: NotificationSubjectType,
    subject: Subject,
}

enum E2eeNotificationContent {
    OneTimeKeysCount(usize),
    DeviceLists {
        changed: Vec<OwnedUserId>,
        left: Vec<OwnedUserId>,
    },
    UnusedFallbackKeysTypes(Vec<OneTimeKeyAlgorithm>),
}

enum NotificationContent {
    Events(StreamId),
    AccountData {
        stream_id: StreamId,
        room_id: Option<OwnedRoomId>,
    },
    E2eeKeys(E2eeNotificationContent),
    Receipts(StreamId),
    ToDevice(StreamId),
}

Then, ongoing long-polling sync endpoints would just fetch, from the database, the result for their sync request, knowing they should now find some eligible data thanks to the notification they saw pass by.

Note

The only change we would need to do with this plan is that we need to store a single stream ID per user to track changes to their e2ee keys. This stream ID however would not need to use the complicated double-lock stream ID mechanism, and instead a simple SELECT FOR UPDATE query would give us what we need. Note that once implemented and proven to work, we should be able to extend this mechanism to all the other user-scoped data (i.e. todevice messages and account data).

Further Work

These are stuff to go look back at once we are done implementing the above solution. They contribute to us having a final clean version over a proof of concept one.

Optimisations

The proposed solution here is heavily based on Synapse implementation of Sync v4. However, I stripped many optimisation tricks that they did, but that we might want to consider in the future:

• Decide if want to delegate populating syncv4_joined_rooms to a background job instead of it being updated (and hence awaited) in actual handlers.
• Other pre-populated table: sliding_sync_connection_lazy_members: This table would contain the membership status of every user in regards to every room. This would greatly decrease the cost of computing lazy membership as well as shared encrypted rooms for the E2EE keys changes extension.
• Add a configurable UPDATE_LAST_USED_INTERVAL that prevents syncv4_connections.last_used_at column to be updated on every single sync request.
• Introduce some cache mechanisms

Expired Sessions Cleanup

The above session storage could obviously clutter our server’s database, especially since there is no way to tell if a session is over (i.e. the client will start a new one in that connection the next time they sync) or not (i.e. the client will just use the latest pos we gave them in their next sync request). This is why we might decide later on to run a scheduled task, or to implement an admin feature to remove sessions based on relevant criteria (e.g. last_used_at > 7 days, etc). The good news is that these deletion simply need to happen on the syncv4_connections table, and will trickle down deleting all the other entries that are linked to these sessions.

Tip

We should also configure a UPDATE_LAST_USED_INTERVAL on our server that determines how often we’ll update syncv4_connections.last_used_at to avoid updating on every single sync request.

Rejecting Too-Big Requests

The Security considerations section of the MSC states:

Servers MAY decide to expire the sync connection if the generated response on an incremental request is likely very large or expensive to compute.

We could therefore define an algorithm and a bunch of metrics that will make us detect that a request’s configuration will result in too-big of a response and we therefore decide not to fulfill it but instead expire its associated session (by simply removing the session from our storage).

I however think this is to be determined after having fully implemented Sync v4, so that we can benchmark relevant such metrics. This also need to be fully configurable so that administrators can tune them, and so that we can provide different relevant defaults for different deployments (Cloud, Raspberry Pi, single server, etc).

We should nonetheless define a few defaults for these limits, just to prevent nuisance:

• MAX_TIMELINE_LIMIT: 100
• MAX_ROOMS: 50

Tip

We should consider adding a list of metrics to be computable from the get go as part of the implementation’s acceptance criteria, so that we can later on reflect on this problem.

Implementation TODOs

This is just a small list of stuff that I have noticed whilst reading the MSCs, and that we should not forget to do when actually implementing Sync v4.

• Limit the number of connections per user’s device

  As mentioned in the MSC’s Security considerations section:

  Servers SHOULD limit the amount of data that they store per-user to guard against resource consumption, e.g. limiting the number of connections a device can have active. This protects against malicious clients creating large numbers of connections that get persisted to the database.

  This means we should first get the number of known sessions for each (user_id, device_id, conn_id) before creating and storing a new one when being requested to. Note that we can always decide on a policy for what happens when a device reached the maximum number of connections (e.g. delete the oldest one).

• URL to use for Sync v4

  The unstable URL for Simplified Sliding Sync is /_matrix/client/unstable/org.matrix.simplified_msc3575/sync. Nothing special to do about this, but writing it here will avoid having to look it up time and time again.

• Version flag for Sync v4

  The flag to set in /_matrix/client/versions to indicate that we support Sync v4 is org.matrix.simplified_msc3575.

• Expired sessions response

  The spec specifies that we have to answer with a 400 - Bad Request HTTP status code and a M_UNKNOWN_POS Matrix error code when sessions are expired. See Expired sessions cleanup for when this can happen.