element-hq / element-hq/dendrite
Inform syncapi about holes in DAGs
- 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
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