search

oddsdk / ts-odd

An SDK for building apps with decentralized identity and storage.
https://odd.dev/
Apache License 2.0
179 stars 24 forks source link

WNFS Conflict Resolution #163

Open expede opened 3 years ago

expede commented 3 years ago

NB: Feature requests will only be considered if they solve a pain

Summary

Problem

Concurrent updates across devices can cause data loss by:

  1. Dropping history (overwriting revisions)
  2. Forgetting files in the latest generation when reconciling with new data

There is a server-side conflict detection portion of this, but the front end needs to know how to reconcile changes first.

Impact

Sometimes users loose recent changes or files

Solution

"Rebase" changes of the local WNFS on top of a remote source of truth at a conflict point.

This means being able to "pop off" the changes since the last common CID, and place them on top of the latest CID from the single source of truth.

The one wrinkle is that we don't want to loose any new files, so this needs to add any missing links back to the new CID head, and propagate those through the history. If you recall this image:

Screen Shot 2021-01-12 at 9 35 08 PM

We're keeping the blue boxes (new files), but adjusting the blue lines to point to all existing files at the previous step.

Not that this does not include sub-file merging. We cannot understand their content structure ahead of time, and even then it often goes awry. Complete individual files can be overwritten, and we keep the history if they want the old copy or to do manual merging of the inner contents.

matheus23 commented 3 years ago

There is a server-side conflict detection portion of this, but the front end needs to know how to reconcile changes first.

I think there's value in implementing the server-side portion of this without implementing the front-end change reconciling in webnative. E.g. I could already implement conflict resolution on the app layer in flatmate if the server-side portion existed!

At the moment I can't do this, as any .publish call might overwrite any changes made by anyone else. So I'd need some kind of .publishIfTheServerAgreesWithMeThatTheMostRecentStateWas(cid). :smile:

expede commented 3 years ago

There is a server-side conflict detection portion of this, but the front end needs to know how to reconcile changes first.

I think there's value in implementing the server-side portion of this without implementing the front-end change reconciling in webnative. E.g. I could already implement conflict resolution on the app layer in flatmate if the server-side portion existed!

At the moment I can't do this, as any .publish call might overwrite any changes made by anyone else. So I'd need some kind of .publishIfTheServerAgreesWithMeThatTheMostRecentStateWas(cid). 😄

Right, or you could ask for the latest head before you apply your changes with the GET /user/data/{username} endpoint

You'll need to do the reconciliation in either case. Just knowing that you're behind only gets you so far, you still need WNFS to merge the changes, or to do them yourself manually. Having the remote block you from pushing breaks everything unless you know how to make a proper WNFS rebase, which is equivalent to building this feature in the FE.

matheus23 commented 3 years ago

Right, or you could ask for the latest head before you apply your changes with the GET /user/data/{username} endpoint

That's my plan for now. It just leaves an uneasy feeling as two concurrent GET + PATCH requests can race each other.

jeffgca commented 2 years ago

@appcypher @matheus23 is this going into rs-winfs?

appcypher commented 2 years ago

@appcypher @matheus23 is this going into rs-winfs?

I believe so. This sounds very much like the file tree merge issue that is expected to be solved at some point in the future.

matheus23 commented 2 years ago

is this going into rs-winfs?

Yes it is! Also reminds me to retract what I said previously:

Right, or you could ask for the latest head before you apply your changes with the GET /user/data/{username} endpoint

That's my plan for now. It just leaves an uneasy feeling as two concurrent GET + PATCH requests can race each other.

I don't think that's an issue! We don't actually need atomic writes to the head pointer! It's the magic of CRDTs. If you accidentally race with someone else, you'll be able to figure that out on your next data root fetch and be able to fix the issues that came because of that. Yay immutable history and merkle clocks! :P