"Pulled event failed history check" when backfilling

[richvdh]

Sometimes we fail to backfill events, with warnings like the following:

2022-04-25 12:03:23,359 - synapse.handlers.federation_event - 684 - INFO - GET-415-$t48Htry7uXkIrbBvqFfzMFaYvNNZTjnYpn_Sq7E4b0Y - Processing pulled event <FrozenEventV3 event_id=$t48Htry7uXkIrbBvqFfzMFaYvNNZTjnYpn_Sq7E4b0Y, type=m.room.member, state_key=@2l4dhtu40w:plmatrix.pl, outlier=False>
2022-04-25 12:03:23,370 - synapse.handlers.federation_event - 703 - INFO - GET-415-$t48Htry7uXkIrbBvqFfzMFaYvNNZTjnYpn_Sq7E4b0Y - De-outliering event $t48Htry7uXkIrbBvqFfzMFaYvNNZTjnYpn_Sq7E4b0Y
2022-04-25 12:03:23,373 - synapse.handlers.federation_event - 770 - INFO - GET-415-$t48Htry7uXkIrbBvqFfzMFaYvNNZTjnYpn_Sq7E4b0Y - Event $t48Htry7uXkIrbBvqFfzMFaYvNNZTjnYpn_Sq7E4b0Y is missing prev_events ['$45VO5ImZbpf5oZJB3LDFLX5SUlCfIWVG1F5ixtJSFqg']: calculating state for a backwards extremity
2022-04-25 12:03:23,374 - synapse.handlers.federation_event - 788 - INFO - GET-415-$t48Htry7uXkIrbBvqFfzMFaYvNNZTjnYpn_Sq7E4b0Y - Requesting state after missing prev_event $45VO5ImZbpf5oZJB3LDFLX5SUlCfIWVG1F5ixtJSFqg
2022-04-25 12:03:23,433 - synapse.http.matrixfederationclient - 600 - INFO - GET-415-$t48Htry7uXkIrbBvqFfzMFaYvNNZTjnYpn_Sq7E4b0Y-$45VO5ImZbpf5oZJB3LDFLX5SUlCfIWVG1F5ixtJSFqg - {GET-O-718} [maunium.net] Got response headers: 404 Not Found
2022-04-25 12:03:23,434 - synapse.http.matrixfederationclient - 679 - WARNING - GET-415-$t48Htry7uXkIrbBvqFfzMFaYvNNZTjnYpn_Sq7E4b0Y-$45VO5ImZbpf5oZJB3LDFLX5SUlCfIWVG1F5ixtJSFqg - {GET-O-718} [maunium.net] Request failed: GET matrix://maunium.net/_matrix/federation/v1/state_ids/%21XaqDhxuTIlvldquJaV%3Amatrix.org?event_id=%2445VO5ImZbpf5oZJB3LDFLX5SUlCfIWVG1F5ixtJSFqg: HttpResponseException('404: Not Found')
2022-04-25 12:03:23,434 - synapse.handlers.federation_event - 831 - WARNING - GET-415-$t48Htry7uXkIrbBvqFfzMFaYvNNZTjnYpn_Sq7E4b0Y - Error attempting to resolve state at missing prev_events
2022-04-25 12:03:23,434 - synapse.handlers.federation_event - 720 - WARNING - GET-415-$t48Htry7uXkIrbBvqFfzMFaYvNNZTjnYpn_Sq7E4b0Y - Pulled event $t48Htry7uXkIrbBvqFfzMFaYvNNZTjnYpn_Sq7E4b0Y failed history check.

(this is taken from an attempt to back-paginate in #synapse-dev.)

In this case, $t48Htry7uXkIrbBvqFfzMFaYvNNZTjnYpn_Sq7E4b0Y is an m.room.member event, with a prev_event of $45VO5ImZbpf5oZJB3LDFLX5SUlCfIWVG1F5ixtJSFqg. Evidently, $45V... is a backwards extremity on maunium.net, because maunium.net is (correctly) returning $t48H... from the /backfill request, but is (also correctly) replying with a 404 to a state_ids request for $45V....

We do eventually reply to the /messages request, but without the missing events.

Fundamentally the problem here is that the federation protocol provides no way for us to get the state before a given event (indeed, Synapse does not store that data, though it can often be inferred). Instead we have to ask for the state after the the event's predecessors - which the remote server may not have.

[akoyaxd]

I'm facing the exact same issue.
Is this something, that has to be fixed in Spec or is just something in the implementation?