Room deletion (and purging) does not always send a leave down sync to clients

[Half-Shot]

Related to #18464

Problem

Room deletion (v2, and possibly v1) will purge the room upon deletion. It will first send a bunch of kick events, which are intended to go to clients to let them know to remove the room from their room list. The problem is however immediately after sending these the room is purged from the database so unless you are federated or happened to be syncing exactly as the leave was sent, you will miss the leave event. The leave events are purged along with the room itself.

Subsequent syncs made after the room is purged never include the leave event, so any clients that did not sync will be stuck with broken state.

Proposed solution

Synapse should generate synthetic leave events for users with devices that existed at the point in time the room was alive. Rather than relying on events in the room which may be purged, the homeserver should keep a mapping of user, device and room_id of deleted rooms that can be popped as the device syncs to ensure they see a leave down the sync in all cases. This minimises the retention of data onto the server with the bare minimum required to execute the leaves, without leaving any metadata.

To keep in mind that quite like device messages, these rows could hang around forever if devices do not sync so a sensible cleanup period should be incorporated (perhaps a month, or so) where these rows are purged anyway.

[anoadragon453]

I don't think you need to track device IDs. Devices will already tell you whether they have yet to see the room be purged as they are passing the events stream ordering in their sync token.

All one needs to store in a new deleted_rooms_users table is:

CREATE TABLE deleted_rooms_users (
    last_event_stream_ordering BIGINT PRIMARY KEY,
    room_id TEXT NOT NULL,
    user_id TEXT NOT NULL
);

where last_event_stream_ordering is the stream ordering of the final event in the room from the perspective of your homeserver.

We need to ensure to cover the edge case of a user who leaves a room before it is purged, but then tries to /sync after the purge with a since token that's before their leave. Right now, they wouldn't see the leave event as it's been purged.

So when purging a room, not only do you need to create a row in deleted_rooms_users for all the users that were joined to the room at the time, but all local users who have ever been in the room.

[Half-Shot]

I don't think you need to track device IDs. Devices will already tell you whether they have yet to see the room be purged as they are passing the events stream ordering in their sync token.

I suppose it comes down to how long we want to keep these entries around for? I suspect it's not going to add up to many bytes to hold these memberships in the database, but it would certainly mean we now store memberships even after you delete a room.

The device tracking would allow us to start deleting these rows as they are no longer needed as we can track which devices still need to see a leave, and eventually expire the data naturally. However, it is A) More work B) breaks the contract on /sync where syncing with the same token twice would not produce the same result.

We would also probably want a retention period on this information in general so the membership lists don't hang around for years, long after they are presumably useful?