4 ms·

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

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.
  - puetzk 10y ago
    It does? git merge --strategy xyz means git will invoke git-merge-xyz to do the actual conflict resolution. It comes with a variety of built-in ones (see https://git-scm.com/docs/merge-strategies https://git-scm.com/docs/merge-strategies) but you can write more if you have some special-purpose approach you want to use. Git also has smudge/clean filters if you want to transform your file to a format where line-by-line textual merge is more meaningful And you can use .gitattributes to make certain extensions/folders/file/whatever default to a certain treatment. A good example is https://bitbucket.org/sippey/zippey https://bitbucket.org/sippey/zippey which unpacks zip archives (and hence file formats based on them, like .jar, .docx, etc) to allow the contents within to be tracked in the git repo better. Other custom formats could do something similar...
espadrine 10y ago
To me, there are two separate concerns: intent preservation and coherence. Operations cause a change of state. The sequence of operations that are performed given a user action need to ensure that they will cause a modification of the state of the database in the way intended by the user. Coherence is about maintaining a design. A set of rules are conceived. For each state, it is possible to determine whether the state is valid according to them, and if so, the database is coherent. To maintain coherence, it is possible to deny an operation, therefore breaking user intent. To maintain user intent, it is possible to accept an operation that leads to an invalid state. From what I understand, noms is heavily tilted towards coherence, like git, but unlike git, it doesn't have the social "pull request" aspect, nor a support for running tests. You mention diffing as a plus, but realistically the only use of diffing is to guess intent. Real intent can only be provided by a maximally rich set of operations. Logs of SQL queries, for instance, are more likely to provide insight than a cold diff. For a database that is tilted so far towards maintaining coherence at the expense of user intent, it may be a good idea to compensate by staying close to the operations. Finally, if you decide to tilt towards intent preservation, there are definitely approaches to automate merges, avoiding nagging the user to fix conflicts. The most successful trivial solution remains latest-write-wins, which gives surprisingly good results assuming a high data granularity and a rich set of operations. But unless there is a way to automate coherence validation (which the equivalent in git projects is, I suppose, running the tests), we can only rely on user attention… in which case, relying on the user to fix coherence after the fact on a database that heavily preserves user intent would be pretty much the same. So… do you plan on supporting custom coherence rules? Alternatively, which conflict resolutions are you leaning towards?
- im_down_w_otp 10y ago
  What is "latest" in a situation where you're experiencing concurrent writes?
  - espadrine 10y ago
    Google's Spanner, for instance, relies on their TrueTime design, which requires having a GPS clock and an atomic clock on each datacenter, I believe. Most designs simply rely on NTP or a similar time synchronization system. Another approach is to maintain total order of writes. Assuming some form of consensus protocol to determine write order, the unicity of the order ensures synchronization. That design, however, tends to preserve user intent less. Bitcoin has a form of that.

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.
- puetzk 10y ago
  It does? git merge --strategy xyz means git will invoke git-merge-xyz to do the actual conflict resolution. It comes with a variety of built-in ones (see https://git-scm.com/docs/merge-strategies https://git-scm.com/docs/merge-strategies) but you can write more if you have some special-purpose approach you want to use. Git also has smudge/clean filters if you want to transform your file to a format where line-by-line textual merge is more meaningful And you can use .gitattributes to make certain extensions/folders/file/whatever default to a certain treatment. A good example is https://bitbucket.org/sippey/zippey https://bitbucket.org/sippey/zippey which unpacks zip archives (and hence file formats based on them, like .jar, .docx, etc) to allow the contents within to be tracked in the git repo better. Other custom formats could do something similar...

espadrine 10y ago

To me, there are two separate concerns: intent preservation and coherence. Operations cause a change of state. The sequence of operations that are performed given a user action need to ensure that they will cause a modification of the state of the database in the way intended by the user. Coherence is about maintaining a design. A set of rules are conceived. For each state, it is possible to determine whether the state is valid according to them, and if so, the database is coherent. To maintain coherence, it is possible to deny an operation, therefore breaking user intent. To maintain user intent, it is possible to accept an operation that leads to an invalid state. From what I understand, noms is heavily tilted towards coherence, like git, but unlike git, it doesn't have the social "pull request" aspect, nor a support for running tests. You mention diffing as a plus, but realistically the only use of diffing is to guess intent. Real intent can only be provided by a maximally rich set of operations. Logs of SQL queries, for instance, are more likely to provide insight than a cold diff. For a database that is tilted so far towards maintaining coherence at the expense of user intent, it may be a good idea to compensate by staying close to the operations. Finally, if you decide to tilt towards intent preservation, there are definitely approaches to automate merges, avoiding nagging the user to fix conflicts. The most successful trivial solution remains latest-write-wins, which gives surprisingly good results assuming a high data granularity and a rich set of operations. But unless there is a way to automate coherence validation (which the equivalent in git projects is, I suppose, running the tests), we can only rely on user attention… in which case, relying on the user to fix coherence after the fact on a database that heavily preserves user intent would be pretty much the same. So… do you plan on supporting custom coherence rules? Alternatively, which conflict resolutions are you leaning towards?

im_down_w_otp 10y ago
What is "latest" in a situation where you're experiencing concurrent writes?
- espadrine 10y ago
  Google's Spanner, for instance, relies on their TrueTime design, which requires having a GPS clock and an atomic clock on each datacenter, I believe. Most designs simply rely on NTP or a similar time synchronization system. Another approach is to maintain total order of writes. Assuming some form of consensus protocol to determine write order, the unicity of the order ensures synchronization. That design, however, tends to preserve user intent less. Bitcoin has a form of that.