-
-
Notifications
You must be signed in to change notification settings - Fork 98
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
How to delete "state". (SPEC-8) #43
Comments
Jira watchers: @erikjohnston @ara4n @richvdh |
After a lot of thought, I've come to the conclusion that for now we can't "delete" state, i.e. remove it from the current state dictionary from POV of federation. This is because the state resolution algorithm assumes that we have a pointer to the current state. So we're left with the idea of tombstoning, i.e. mark the event as having been deleted, but still keep it in the current state dictionary. If we can ever guarantee that we will never see (or accept) an event that will reference another part of the state tree, then we can safely remove the tombstone from the current state dictionary. Currently it is unclear whether we would ever be able to guarantee that. |
The state table is a mapping from The members list is a subset of the state table, i.e. |
Okay, much clearer, thanks. Sorry for being thick/ill, but: "If we can guarantee that we will never see (or accept) an event that will reference another part of the state tree, then we can safely remove the tombstone from the current state dictionary." Why would an event that references "another part of the state tree" impact on our ability to remove the tombstone? Isn't "another part of the state tree" unrelated to our tombstone by definition? -- @ara4n |
If we get a state update that references a different branch of the state tree than the one we attached the tombstone to, then we would need to apply the state resolution algorithm on those two branches to see which one wins. However, if we've removed the tombstone from the state dictionary then when we get the state update we won't know about / have a reference to the tombstoned branch and so can't apply state resolution to both (in practice this would mean that we would blindly accept the update.) |
So I think I've come up with a solution, which basically hinges on the fact the event graph gives us a partial ordering we can rely on. The solution basically involves:
We don't even need tombstones! |
Motivation
Currently, when a user leaves a room they keep an entry in the current state table which is never deleted. For large, old, busy rooms this could easily lead to the current state table being huge as it would contain an event for every use that has ever been in the room.
Since these entries are not used for anything, it would be much more convenient if the act of leaving simply involved removing the corresponding membership entry from the current state.
Problems
The main problem with removing entries from current state is making it work with the state conflict resolution algorithm. The algorithm must have these properties:
Currently, the algorithm works by comparing the current state with the newly proposed state. If they are on separate branches of the tree then the two separate branches are compared.
However, if we have removed the entry from the current state we have nothing to compare any new state events with, and so it is treated as if it is completely new state. Thus by property 2, a deletion can only take effect if there are no other undeleted branches of the state tree, which doesn't really work very well.
(Imported from https://matrix.org/jira/browse/SPEC-8)
(Reported by @erikjohnston)
The text was updated successfully, but these errors were encountered: