Hacker News Reader

Comment by rafaelweinstein | Hacker News Reader

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.

View on HN

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 [2] https://github.com/ottypes/json0 [3] https://github.com/josephg/json1

> 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.

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) 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 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...

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?

What is "latest" in a situation where you're experiencing concurrent writes?

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.

Time isn't a reliable resource in this context.

They mention striving to support many contexts. In the demo, they showcase offline editing of a single CSV entry. If the granularity is the atomic types, then a conflict only occurs when the very same field in the very same row is concurrently edited.

Then, the system can show the conflict and offer a default that keeps the operation with the highest timestamp, or if the timestamps are identical, the one with the highest hash.

> which requires having a GPS clock and an atomic clock on each datacenter,

Right. I'll download an open source database, then buy a commercial GPS clock and attach to it.

https://www.amazon.com/Spectracom-1200-033-SECURESYNC-MODULA...

Only $12k for a Spectracom. Granted they are nice.

Well, I guess if it demonstrates anything is one fact -- if even Google needed GPS hardware to provide "latest" in a distributed system, then OP is right. Time in distributed systems is very hard.

> Most designs simply rely on NTP or a similar time synchronization system.

Not sure if "simply" was mean sarcastic or not. If reliability and deletion of user's data is important, and it relies on getting NTP time, I would strongly advice not to use that distributed db system.

Much of this is yet to be designed, but in general, our approach has been to lean towards a relatively layered system. That is to say, that at the lowest level, noms probably won't make a judgement about the trade-off you describe above, but rather provide primitives which allow layers above to more easily take opinionated positions.

In the near-term we'll be paying attention to specific cases that arise, and we'd welcome the opportunity to learn more about those that you may encounter.

Reply on news.ycombinator.com