State delta between two events for more efficient delivery and processing

[matrixbot]

This issue has been migrated from #13618.

---

Spawning from matrix-org/synapse#13356 to make /messages faster which includes backfill

---

It's very inefficient to have to request the full room state (or state_ids) at a given event when we already have the majority of the state locally. For a room like #matrix:matrix.org, /state_ids gives 200k events (77k state_events, 122k auth_events) which by its sheer volume takes the sending server a while assemble a response, send it, and then we have process all of it 😱

It would be nice if we had an endpoint to get only the state that is different from event A to event B (the delta). This way the sending server doesn't have to send as much and we don't have process as many events to find the couple events that we need.

This new endpoint needs some spec thought and a proper MSC but creating an issue here so we can track the idea before that gets created. One potential option is adding some from/to query parameters to the existing /state_ids and /state endpoints.

• GET /_matrix/federation/v1/state_ids/{roomId}?from_event_id=$a&to_event_id=$b
• GET /_matrix/federation/v1/state/{roomId}?from_event_id=$a&to_event_id=$b

It might be good if we could also specify multiple pairs of events to help batch up multiple missing events.

Maybe similar to the existing /get_missing_events endpoint where you can specify earliest_events and latest_events

---

Related issues:

• Handling state_ids responses loads huge amounts of events into memory at once, causing OOMs matrix-org/synapse#6597
• /state_ids is slow to respond matrix-org/synapse#13620

Dev notes

In Synapse, we can use our state_groups to to simplify the diff calculation.

compute_state_delta is used for /sync but is probably of interest as well.

---

(matrix-org/synapse#13586)
https://github.com/matrix-org/synapse/blob/ec44d79775e2b811f733fb4c2195cd5f14fec275/synapse/handlers/federation_event.py#L1035-L1045