8 ms·

GC I can see a shape of solution for since you can use something like a per-object DVVset to determine the minimum set of unresolved histories required to avoid

GC I can see a shape of solution for since you can use something like a per-object DVVset to determine the minimum set of unresolved histories required to avoid losing data during conflicts while not unnecessarily ballooning the size of the dataset. However, the inner-object conflict-resolution problem seems a lot harder to solve given that there's no obvious join-semilattice for arbitrary fields/data. Can you discuss what conflict-resolution strategies you're working on for auto-resolution and/or what metadata you intend to provide to the end-user in the event that you're going to punt resolution to them to handle? Given this is supposed to be for collaborative workloads, the conflict-resolution issue seems to be a cornerstone. Git handles this by inserting sibling sections into the documents and forcing the end-user to manually deal with fixing problems, which is often fraught with pain and peril, and doesn't seem like a strategy that would work for something that's a database (as opposed to something that's a workflow).

svckr 10y ago
> [...] forcing the end-user to manually deal with fixing problems, which is often fraught with pain and peril, and doesn't seem like a strategy that would work for something that's a database (as opposed to something that's a workflow). Isn't that what (for example) CouchDB does? I believe the reasoning is that conflict resolution is often application specific, so why not deal with it in the application?
- fiatjaf 10y ago
  In case of conflicts, CouchDB assumes the most modified branch of the document (i.e., the document with the higher revision number) is the winner. You can resolve the conflict by choosing a different branch/revision manually, but you can also choose to not do anything.
  - im_down_w_otp 10y ago
    Really? That's nearly undifferentiated from just picking one at random. How is, "whoever hits the queue most often" a useful deterministic resolution strategy? I mean I guess it's functionally no worse than wall-clock time or something, but still kinda funny. :-)
    - carterehsmith 10y ago
      I think the OP meant "most recently changed", not "most changed" :)
      - im_down_w_otp 10y ago
        I don't think so. Though "most recently changed" is pretty useless too. They won't be synchronized in a distributed system, and even on a single machine if it's setup to use something like NTP, then the time won't be monotonically increasing since the clock-sync mechanism can move time both forward and backward. Having now looked at it out of curiousity... http://guide.couchdb.org/draft/conflicts.html http://guide.couchdb.org/draft/conflicts.html "Each revision includes a list of previous revisions. The revision with the longest revision history list becomes the winning revision. If they are the same, the _rev values are compared in ASCII sort order, and the highest wins. So, in our example, 2-de0ea16f8621cbac506d23a0fbbde08a beats 2-7c971bb974251ae8541b8fe045964219." Weird.
      - fiatjaf 10y ago
        No, I meant "most changed". I don't see how this could be better for a deterministic approach. The recommendations are always that the developer must implement a saner way to resolve the conflicts. In the CouchDB world, however, I have the impression that conflict resolution is ignored most of times, so we are left with this. (I say this based on what I do, other people's code I read on the internet and the concerns of the CouchDB core developers about educating users and developers to setup saner conflict resolution approaches themselves.)
    - rdtsc 10y ago
      It is not random. It is consitently picking the same document on all servers that have seen the same changes. By default it picks the one with the most changes. That consintency ("the same" part is very important) it means if you replicate and bring in some conflicts, both sides will show the same state. So you won't randomly after replicating A to B, and B to A see document 1 as the winner on A but 2 on B. They'll both pick 1 or 2. So both would settle on the same state. Also it doesn't delete or remove conflicting siblings, it is very good about not doing that to user data. Users only know exactly how to solve particular conflicts.
  - rdtsc 10y ago
    Yes, it picks a winner, which it show on all machines (so all machines that have seen same changes will pick the same winner). But it also keeps conflicts around, so users who care about them can correctly resolve them. Sometimes the winner it picks is not what the users want, That could surprising, but it is correct because it really is a user-level conflicts. (Now, user may very well at a timestamp field to the document, hope ntp works well and resolve the conflicts if they appear based on that, but CouchDB tries not to make such assumption on behalf of the user).
- im_down_w_otp 10y ago
  Riak does this when not using CRDT data types, but the problem is often that there's no clear application or user way to deal with this either most of the time because it requires an awful lot of context in order to make a good decision. Using the same example of how Git deals with this. Think about times you've gone through a merge conflict process on a chunk of conflicting code where you don't really have any knowledge or context for why the other stuff that's not yours is even there, and say you don't have a way to collaborate with the other developer or someone in leadership to make sense of those parallel efforts. You can only make sane decisions about complex conflict resolution when you have a lot... a lot... of surrounding context and intent. You need extra metadata, and the underlying system needs to expose that to you. That system being your engineering process, manager, co-worker or in this case that system being the database. Hence my interest in how they're intending to expose this set of concerns to the user.
rafaelweinstein 10y ago
This is a question that we've gotten quite a bit. It's our view that there's no magic solution to conflicts. There are logical conflicts in the real world that must be arbitrated. That said, it's a surprisingly basic thing, but just knowing what changed from party (a) and party (b)'s perspective (relative to their most recently agreed-upon state) is somewhat rare or ad-hoc in existing systems. In noms, you can directly compute exactly how state diverged and apply whatever resolution strategy is suitable. We have plans for applying default conflict resolution for changes to data-types that - in many cases - will be correct, but in the end, there's no avoiding that correctness can only be defined within a given specific domain.
- josephg 10y ago
  I've played with this problem on and off over the last few years. ShareDB[1] is powered by JSON OT[2], in which each change describes the meaning behind what you're trying to do. (For example, 'increment counter' is different from 'change counter from 2 to 3'. They look the same, but behave differently in the case of conflicts). Just knowing what changed often isn't enough to do proper resolution. I've spent years on and off playing with a better, faster, stronger version of the JSON OT code[1] which also supports arbitrary object reparenting. You run into problems where you really want conflicts as well. For example, given {x:{}, y:{}} user A moves x into y, and user B moves y into x. There's no good solution to resolving this without more information or conflict markers & humans. Doing this in a P2P setting is hard & interesting. Very cool stuff though! [1] https://github.com/share/sharedb https://github.com/share/sharedb [2] https://github.com/ottypes/json0 https://github.com/ottypes/json0 [3] https://github.com/josephg/json1 https://github.com/josephg/json1
  - adekok 10y ago
    > Just knowing what changed often isn't enough to do proper resolution. This is why my git commit logs are sometimes: perl -p -i -e 's/FOO/BAR/g' $(find src -name "*.[ch]" -print) Having a "high level" description of what changed makes manual merges easier. I wish git had conflict resolution like this. Treating data as an arbitrary sequence of bits is general and correct. Treating data as having a particular format can be useful, too.

svckr 10y ago

> [...] forcing the end-user to manually deal with fixing problems, which is often fraught with pain and peril, and doesn't seem like a strategy that would work for something that's a database (as opposed to something that's a workflow). Isn't that what (for example) CouchDB does? I believe the reasoning is that conflict resolution is often application specific, so why not deal with it in the application?

fiatjaf 10y ago
In case of conflicts, CouchDB assumes the most modified branch of the document (i.e., the document with the higher revision number) is the winner. You can resolve the conflict by choosing a different branch/revision manually, but you can also choose to not do anything.
- im_down_w_otp 10y ago
  Really? That's nearly undifferentiated from just picking one at random. How is, "whoever hits the queue most often" a useful deterministic resolution strategy? I mean I guess it's functionally no worse than wall-clock time or something, but still kinda funny. :-)
  - carterehsmith 10y ago
    I think the OP meant "most recently changed", not "most changed" :)
    - im_down_w_otp 10y ago
      I don't think so. Though "most recently changed" is pretty useless too. They won't be synchronized in a distributed system, and even on a single machine if it's setup to use something like NTP, then the time won't be monotonically increasing since the clock-sync mechanism can move time both forward and backward. Having now looked at it out of curiousity... http://guide.couchdb.org/draft/conflicts.html http://guide.couchdb.org/draft/conflicts.html "Each revision includes a list of previous revisions. The revision with the longest revision history list becomes the winning revision. If they are the same, the _rev values are compared in ASCII sort order, and the highest wins. So, in our example, 2-de0ea16f8621cbac506d23a0fbbde08a beats 2-7c971bb974251ae8541b8fe045964219." Weird.
    - fiatjaf 10y ago
      No, I meant "most changed". I don't see how this could be better for a deterministic approach. The recommendations are always that the developer must implement a saner way to resolve the conflicts. In the CouchDB world, however, I have the impression that conflict resolution is ignored most of times, so we are left with this. (I say this based on what I do, other people's code I read on the internet and the concerns of the CouchDB core developers about educating users and developers to setup saner conflict resolution approaches themselves.)
  - rdtsc 10y ago
    It is not random. It is consitently picking the same document on all servers that have seen the same changes. By default it picks the one with the most changes. That consintency ("the same" part is very important) it means if you replicate and bring in some conflicts, both sides will show the same state. So you won't randomly after replicating A to B, and B to A see document 1 as the winner on A but 2 on B. They'll both pick 1 or 2. So both would settle on the same state. Also it doesn't delete or remove conflicting siblings, it is very good about not doing that to user data. Users only know exactly how to solve particular conflicts.
- rdtsc 10y ago
  Yes, it picks a winner, which it show on all machines (so all machines that have seen same changes will pick the same winner). But it also keeps conflicts around, so users who care about them can correctly resolve them. Sometimes the winner it picks is not what the users want, That could surprising, but it is correct because it really is a user-level conflicts. (Now, user may very well at a timestamp field to the document, hope ntp works well and resolve the conflicts if they appear based on that, but CouchDB tries not to make such assumption on behalf of the user).
im_down_w_otp 10y ago
Riak does this when not using CRDT data types, but the problem is often that there's no clear application or user way to deal with this either most of the time because it requires an awful lot of context in order to make a good decision. Using the same example of how Git deals with this. Think about times you've gone through a merge conflict process on a chunk of conflicting code where you don't really have any knowledge or context for why the other stuff that's not yours is even there, and say you don't have a way to collaborate with the other developer or someone in leadership to make sense of those parallel efforts. You can only make sane decisions about complex conflict resolution when you have a lot... a lot... of surrounding context and intent. You need extra metadata, and the underlying system needs to expose that to you. That system being your engineering process, manager, co-worker or in this case that system being the database. Hence my interest in how they're intending to expose this set of concerns to the user.

rafaelweinstein 10y ago

This is a question that we've gotten quite a bit. It's our view that there's no magic solution to conflicts. There are logical conflicts in the real world that must be arbitrated. That said, it's a surprisingly basic thing, but just knowing what changed from party (a) and party (b)'s perspective (relative to their most recently agreed-upon state) is somewhat rare or ad-hoc in existing systems. In noms, you can directly compute exactly how state diverged and apply whatever resolution strategy is suitable. We have plans for applying default conflict resolution for changes to data-types that - in many cases - will be correct, but in the end, there's no avoiding that correctness can only be defined within a given specific domain.

josephg 10y ago
I've played with this problem on and off over the last few years. ShareDB[1] is powered by JSON OT[2], in which each change describes the meaning behind what you're trying to do. (For example, 'increment counter' is different from 'change counter from 2 to 3'. They look the same, but behave differently in the case of conflicts). Just knowing what changed often isn't enough to do proper resolution. I've spent years on and off playing with a better, faster, stronger version of the JSON OT code[1] which also supports arbitrary object reparenting. You run into problems where you really want conflicts as well. For example, given {x:{}, y:{}} user A moves x into y, and user B moves y into x. There's no good solution to resolving this without more information or conflict markers & humans. Doing this in a P2P setting is hard & interesting. Very cool stuff though! [1] https://github.com/share/sharedb https://github.com/share/sharedb [2] https://github.com/ottypes/json0 https://github.com/ottypes/json0 [3] https://github.com/josephg/json1 https://github.com/josephg/json1
- adekok 10y ago
  > Just knowing what changed often isn't enough to do proper resolution. This is why my git commit logs are sometimes: perl -p -i -e 's/FOO/BAR/g' $(find src -name "*.[ch]" -print) Having a "high level" description of what changed makes manual merges easier. I wish git had conflict resolution like this. Treating data as an arbitrary sequence of bits is general and correct. Treating data as having a particular format can be useful, too.