Avoid `/backfill` when we already have enough messages to return for a `/messages` response

[MadLittleMods]

Avoid /backfill when we already have enough messages to return for a /messages response

As you can see from the trace, if we were somehow smart enough to know not to /backfill, we would save ourselves 14s from that 16.42s request. In this example, there is only a single new event out of the 100 returned in the /backfill response that is "new" to us and it's one that already has failed pull attempts so we end up skipping it anyway because of expontential backoff. This is definitely a candidate where we didn't need to /backfill!

Full Jaeger trace JSON

Questions

What kind of heuristic can we use to know that we have enough messages to respond to /messages request? In other words, it's fine to have small holes (especially with cases where we've attempted to fill the hole before) but if we're missing a big chunk of history, then we probably should try /backfill.

Perhaps we can look at the depth of the continuous set of messages and if there isn't too big of a gap between them, we can consider it good enough. Maybe potentially still trigger a /backfill in the background so things can become eventually consistent.

[clokep]

I know very little about backfill, so maybe this is a dumb question: do we kick off backfills in the background when we're getting "close" to the end of what we know as a server, or do we wait for it to be requested by a client?

[MadLittleMods]

@clokep We always kick off backfills in the foreground and wait for the result whenever we're at or approaching a backward extremity.

synapse/synapse/handlers/federation.py

Lines 333 to 350 in 874378c

	# If we're approaching an extremity we trigger a backfill, otherwise we
	# no-op.
	#
	# We chose twice the limit here as then clients paginating backwards
	# will send pagination requests that trigger backfill at least twice
	# using the most recent extremity before it gets removed (see below). We
	# chose more than one times the limit in case of failure, but choosing a
	# much larger factor will result in triggering a backfill request much
	# earlier than necessary.
	max_depth_of_backfill_points = sorted_backfill_points[0].depth
	if current_depth - 2 * limit > max_depth_of_backfill_points:
	logger.debug(
	"Not backfilling as we don't need to. %d < %d - 2 * %d",
	max_depth_of_backfill_points,
	current_depth,
	limit,
	)
	return False

The recent PR to process events with previous failed pull attempts is the only background thing introduced so far (#15585).