Events with lots of prev_events make backfill very slow

[matrixbot]

This issue has been migrated from #13677.

---

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).