Backfill in the background if we're doing it "just because"

[MadLittleMods]

Backfill in the background if we're doing it "just because"

Fix #15702

I completely acknowledge that a backward extremity later in the DAG, could connect to an unknown branch in the DAG that has events at the depth we're scrolling through but how likely is this to happen? This would be an interesting metric to track (how many events from /backfill actually end up in /messages)

Dev notes

Does this work fine in the scenario where your server just joined the room so there isn't many messages anywhere?

I think this will work fine because there will be backward extremities given you have your join event and other state persisted already. In other words, there will be backwards extremities at a lower depth when you paginate and we will backfill in the foreground so you see history come in as you scrollback.

Tested and there is a backward extremity after you join a federated room so you backfill in the foreground and get messages as you scrollback ✅

(matrix-org/complement#443)

COMPLEMENT_KEEP_BLUEPRINTS="fed.perf_many_messages.hs1" COMPLEMENT_ALWAYS_PRINT_SERVER_LOGS=1 COMPLEMENT_DIR=../complement ./scripts-dev/complement.sh -run TestMessagesOverFederation -p 1

Pull Request Checklist

• Pull request is based on the develop branch
• Pull request includes a changelog file. The entry should:
  • Be a short description of your change which makes sense to users. "Fixed a bug that prevented receiving messages from other servers." instead of "Moved X method from EventStore to EventWorkerStore.".
  • Use markdown where necessary, mostly for code blocks.
  • End with either a period (.) or an exclamation mark (!).
  • Start with a capital letter.
  • Feel free to credit yourself, by adding a sentence "Contributed by @github_username." or "Contributed by [Your Name]." to the end of the entry.
• Pull request includes a sign off
• Code style is correct
  (run the linters)

[reivilibre]

From the linked issue:

I completely acknowledge that a backward extremity later in the DAG, could connect to an unknown branch in the DAG that has events at the depth we're scrolling through but how likely is this to happen?

This sounds like we're taking risks? But the code change includes a comment that seems to point out that we don't use the return value of the function anyway? (Should we remove the return value in that case?)

I am not sure I am in favour of 'assuming too much', as it were, but I'm struggling to appreciate the consequences / whether this will affect this PR

[MadLittleMods]

This sounds like we're taking risks? But the code change includes a comment that seems to point out that we don't use the return value of the function anyway? (Should we remove the return value in that case?)

-- @reivilibre, #15710 (review)

There are two things being conflated here:

The first thing around "risk" is only really just calling out the fact that there is a behavior change here. Before this PR, if there wasn't any backward extremities where we were paginating, we would backfill anyway with the most-recent backward extremities. The exact reason why we did this wasn't specified beyond "in case we do get relevant events" but I assume it was for eventual consistency and just in case we catch a new branch of history that extends back into the place where we are paginating. Now with this PR, we are acknowledging that it's still a possibility that some useful history could come back but we don't need to block the client in this case because it's a best effort thing that could just as easily not return anything relevant since it's unlikely that a random backward extremity will lead to anything relevant to the place we are paginating and impossible in situations where the most-recent backward extremities are so far ahead of where we are paginating. And there really isn't any consequence since next time they scrollback, the history will be there since we still did the work in the background.

The second thing here is the return value of maybe_backfill() which is completely separate. This just signals whether we actually backfilled anything. We've historically not used it for anything since it was introduced. Coincidentally, I am using it in a new PR in order to see if there is anything new that we should go back to the database and ask about. Now that I understand the nuance better with an actual use case, I've updated the comment.

[reivilibre]

I think I'm starting to understand what you are saying a bit; thanks for bearing with me, I don't ever touch backwards extremities so it's an unfamiliar topic for me.

So the root of the issue is that backwards extremities could point to events anywhere in the DAG (we don't know whereabouts they are because we don't have those events locally, which is why they are backwards extremities in the first place).
So when scrolling backwards in the event stream, we technically would have to try and fetch events from backwards extremities 'in case' they might appear in the scrollback window?
But this is not a very common occurrence, so most of the time it's a waste to wait for this to happen before letting the client go on its merry way?

And then the change introduced here means we don't block on that request. In the rare case that it should have produced events in the client's request window, it now won't.

Is that roughly the right idea?

The part I'm missing now is, which of these holds?:

1. when the client scrolls back again, those missed events will be given to it
2. those missed events will only be given to the client if the client repeated the request some point in the future after the background request completed

[MadLittleMods]

And then the change introduced here means we don't block on that request. In the rare case that it should have produced events in the client's request window, it now won't.

Is that roughly the right idea?

This is the main gist to take away 👍

---

So the root of the issue is that backwards extremities could point to events anywhere in the DAG (we don't know whereabouts they are because we don't have those events locally, which is why they are backwards extremities in the first place).

We know approximately where any backward extremity is because we have the successor events persisted (see the backward extremity explanation in the docs). And we first pick from backward extremities that are approximately in range of where we are paginating already. This is all smart and good so far. But if there are no backward extremities at or further back in history than our current pagination position, then we just backfill with the most recent backward extremities (just because).

The backfill with the most recent backward extremities "just because" is the part we're deciding to put in the background now.

We could check whether these most recent backward extremities are "close" as well but it's just extra complexity and lookup time and we could just as easily be missing that single event vs a unknown chain. And maybe we even want to do something different, where we just choose the closest extremities to our window. But the current behavior of most recent extremities does fill in history that other people are most likely to hit first if they scrollback and is a bit simple to think about (although a bit arbitrary).

There is an argument where we might want to remove this logic completely, but I think it serves a good enough purpose to fill in history in rooms that people are visiting often and unstick things so they become eventually consistent.

---

those missed events will only be given to the client if the client repeated the request some point in the future after the background request completed

This is the right answer. Which does mean that clients could miss out on history but that's already the case and one of the reasons I created MSC3871 so we could indicate to clients that there is a gap that they could try refetching.

[reivilibre]

Understandable compromises. That gap suggestion by MSC3871 could well be useful for clients, thanks.

[reivilibre]

Thanks for the answers!

[MadLittleMods]

@reivilibre Thanks for the review and questions to double-check that we're doing this for a sane reason 🦇