Comment by im_down_w_otp | Hacker News Reader

Comment by im_down_w_otp | Hacker News Reader

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

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.

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.

> [...] 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?

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.

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

I think the OP meant "most recently changed", not "most changed" :)

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

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

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

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.

It is just that random if the systems remain isolated for a long time. Since CouchDB requires you to send the last revision number when updating a document, if the systems are are live replicating between themselves, the guy who is hitting the queue more rapidly will be forced to fetch the latest winning revision every time before hitting the queue (that may be a revision from a different guy). This will give him time to think about the revision he just received, perhaps examine the document linked to that revision number, see if everything is place, perhaps merge changes himself manually... all that before updating the document in the database.

This seems to only make sense in the case that I'm sure I've been able to read the most recent writes from all replicas, no?

I feel like there should be some other method to carry on this discussion besides this thread about Noms :-)

> How is, "whoever hits the queue most often" a useful deterministic resolution strategy?

It's a deterministic resolution strategy, and is thus useful.

> I guess it's functionally no worse than wall-clock time or something,

Wall-clock time is not deterministic; therefore it's far worse.

When dealing with distributed systems, deterministic processes are critical. Multiple systems all being right is awesome, but multiple systems being wrong in different ways is a nightmare. :)

Is it deterministic in a way that's useful? From the perspective of the end-user its going to appear random because they don't control the system environment where "highest revision number" can mean something useful to them. In fact, the CouchDB guide even alludes to this when they talk about not relying on this scheme for complex conflict resolution it seems.

Two nodes split. A and B. Say there are 100 updates to A and 500 updates to B. The split heals, the system picks B because 500 > 100, but the write you actually want to dominate is A. The user can't control which replica gets hit more often, or when a split happens, so while this might be deterministic inside the DB it is semantically random from the user's perspective. So the system can make the same choice on all replicas, assuming it can guarantee it has seen all replicas, which I guess allows you to push merging management to each replica instead of requiring an intermediate coordination replica and then re-publishing the merge state to the replicas? So there's a system optimization benefit there.

But consider if the system did pick a winner at random, how would this look any different to the user? The user doesn't necessarily know if A or B should be picked.

Deterministic behavior is really important, but it seems like it really only looks non-random to the end user when deterministically picking a least upper bound for converging a join-semilattice or when all operations on the data are commutative or idempotent doesn't it?

> Is it deterministic in a way that's useful?

Yes, because it allows to maintain a consistent state across distributed nodes.

> From the perspective of the end-user its going to appear random

...but consistent. If every node picks a random revision on conflict, then when multiple clients try to continue editing, they'll end up increasing the conflicts.

> The split heals, the system picks B because 500 > 100, but the write you actually want to dominate is A. The user can't control which replica gets hit more often, or when a split happens, so while this might be deterministic inside the DB it is semantically random from the user's perspective.

Yeah, but what happens if B picks B, and A picks A? Now the write you're looking for is either there or not there, depending on on which node you're talking to.

> how would this look any different to the user?

Everything is going to look random to the user, no?

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

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.

Reply on news.ycombinator.com