`/state_ids` is slow to respond

This issue has been migrated from [#13620](https://github.com/matrix-org/synapse/issues/13620).

---

`/state_ids` is slow to respond. The 99th percentile is almost solidly above 10s (we can't tell how high), and 5s for the 75th percentile 🐢. Seems like this should be much faster since we just need to dump out what we have in the database (simplification).

Being slow at `/state_ids` means slowing down `/messages` whenever we backfill and need to figure out the state at an event.

https://grafana.matrix.org/d/dYoRgTgVz/messages-timing?orgId=1&from=1661359694721&to=1661381294721&viewPanel=197

---

As an example for `#matrix:matrix.org`, `/state_ids` took 30s for this endpoint to respond. We don't know what `t2bot.io` is doing but chances are we can improve things for the whole federation:

Because `matrix.org` is also slow to respond and we can actually trace it:

(also, what's that mystery gap at the end after we encode the JSON response (`encode_json_response`)?) (update: see https://github.com/element-hq/synapse/issues/17722)

Related to:

- https://github.com/matrix-org/synapse/issues/13246
- https://github.com/matrix-org/synapse/issues/6597

### Rate limiter

We could gain an easy ~1s, by tuning the rate limiter to not sleep as much if our servers can handle it.

https://grafana.matrix.org/d/dYoRgTgVz/messages-timing?orgId=1&from=1661358785681&to=1661380385682&viewPanel=204

### Using less `/state_ids`

Might be better if we could work with less state events every time `/state_ids` is called so it might be nice to have a way to get the delta between two events (the unknown event and the event where your server already has state), see https://github.com/matrix-org/synapse/issues/13618