Events with lots of prev_events make backfill very slow

[richvdh]

I tried to do a backfill in Matrix HQ, and as part as the received events, I received $k59mE1_NBJs-JP4QTza2N7VMahvLp_GlvoYLcJ821s8. This event has 20 prev_events, almost none of which I have in my db.

For each of those 20 events, we then request the full state of the room (taking 24 seconds), and then have to request a lot more individual events for the state or auth_chain. Many of those events get requested each time, because their signing keys have expired, or have been invalidated, so it is impossible to find a good copy of the event (see #13676). This whole process takes at least a minute for each of the 19 missing prev_events.

The whole /messages request took 1787 seconds (nearly 30 minutes).

[MadLittleMods]

Another culprit is the org.matrix.dummy_event's which Synapse automatically puts in the DAG to resolve outstanding/dangling forward extremities when there are more than 5 in the room. Since they have many disparate prev_events, it takes forever to get the state for each prev_event and persist.