element-hq / element-hq/dendrite

Inform syncapi about holes in DAGs

Open
#1,006 2 comments 0 reactions 0 assignees View on GitHub
C-Roomserver C-Sync-API T-Defect X-Needs-Discussion
Dominant language
Go
Stars
965
Forks
101
PR merge metrics
No merged PRs in 30d

Description

*This issue was originally created by [**@kegsay**](https://github.com/kegsay) at .*

### Problem context

Servers send other servers events. These events have `prev_events`. It's possible for a receiving server to be missing those `prev_events`, creating a hole in the DAG (aka an outlier). In an attempt to fill this hole, there's the API `/get_missing_events` which takes the `latest` event IDs and the `earliest` event IDs and gives you events walking back from `latest` and ignoring anything in `earliest` (don't be conned into thinking it returns events "between" the two lists, it doesn't have to in the case of forks).

In the happy case:
- We receive a transaction with events whose `prev_events` we do not recognise.
- We request them via `/get_missing_events` and the returned events fill in the hole in the DAG.
- We process those missing events and then the event from the transaction.
- We return 200 OK to the transaction.

If we cannot obtain the `prev_events`, we can request the `/state` of the room at the event and continue on.

There are many bad cases:
- The server may be missing the `prev_events` or the requesting server [may not be allowed to see those events](https://github.com/matrix-org/synapse/issues/3466).
- The server [may lie](https://github.com/matrix-org/synapse/blob/229eb81498b0fe1da81e9b5b333a0285acde9446/synapse/handlers/federation.py#L313:L318) and say they do not know the prev_event, forcing the server to hit `/state` which then lies about the entire room state.

We can try to [guard against](https://github.com/matrix-org/synapse/pull/3456) lies by forcing the server who sent us the event to cough up the prev_events or else their transaction will be rejected.

In addition, the client needs to be informed of a new hole in the DAG, or else they will never hit `/messages` (and hence backfill) the hole, resulting in a gap in message history e.g due to lost connectivity on the server (this is exacerbated for p2p nodes). We need to send a limited sync to reset the client in this scenario.

Contributor guide

Open the contributing guide

Research direction

Start by tracing how federation handles /get_missing_events and /state, how missing prev_events create DAG holes, and how clients access history through /messages. The issue does not name Dendrite files or tests; done means informing the client through a limited sync so it can reset and discover the hole.

Written by the indexing model from the issue text.

Assessment

Tech stack
go
Domain
backend-api-design, distributed-systems
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.