Hacker News Reader

Comment by eptcyka | Hacker News Reader

The specific case of an edit to a line being applied to a different line than what it was intended for because a previous change deleted said line is exactly what CRDTs rectify. I'm not referring to merge conflicts per say, or that the final document will make human sense. But CRDTs will prevent changesets from different participats from being applied in the worst possible way. And there will be no data loss.

View on HN

You’re misunderstanding what I’m saying.

Original document has a list of instructions. The first instruction says “delete line 3”. User 1 offline deletes line 3. User 2 updates the instructions so that step 1 says “delete line 4”. Merged result when user 1 comes back online: step 1 says “delete line 4” and line 3 is deleted with the users none the wiser about what happened unless they double check the merged result. Physically the result is merged consistently but logically the end result of the document is not what was intended.

That's why relative positions are not used in CRDTs in the absolute sense. Entities are added via IDs and operations are recorded via IDs. If user one deletes line 3 and user 2 deletes line 4, user one will see lines 1, 2 and 5 and onwards. The commands that are captured by CRDTs only operate on the state of the document as the user sees it at the time, their own changes might be overwritten later during a merge, but their changes won't interfere with parts they were not destined to interfere with.

You seem to still not be getting it. Here’s the original online document:

> 1. Please delete line 3.

> 2. Blank line

> 3. This is line 3

> 4. This is line 4.

User 1 is accessing the document offline, sees the instruction on line 1 and changes their local copy to:

> 1. Please delete line 3

> 2. Blank line

> 3. This is line 4

User 2 concurrently changes the document to update the instruction:

> 1. Please delete line 4

> 2. Blank line

> 3. This is line 3

> 4. This is line 4

When user 1 & user 2 merge their documents, they’ll get:

> 1. Please delete line 4

> 2. Blank line

> 3. This is line 4

You can also split this into two documents with a similar effect (one contains instructions, the other contents). The point is that it’s not about how changes are represented. It’s that the logical and semantic structure isn’t represented in the CRDT and thus while some eventually consistent result is attained by all nodes, the logical and semantic structure may end up broken. That’s why you generally don’t see CRDTs for code editors - the merge conflicts still need to be resolved by hand and doing it automatically can result in worse and harder to understand results than normal.

For certain scenarios there will be conflicts, take a boolean value. Client A sets it and client B unsets it. There can only be one winner.

But that might be a benefit from the proposed log sync, because these conflicting situations can be shown and marked for human review in the UI. Each step of change is well documented and the history can fully be reviewed.

Note that in the example I gave there’s not even a conflict to notice. You just have meta instructions telling you what to do within a document. You apply those instructions offline but in the mean time your meta instructions are updated online. You come back and synchronize your changes but there’s nothing that suggests your offline sync against the meta instructions was stale so your edits are applied based on stale meta instructions resulting in a logically undesirable result.

This is basically a TOCTOU race in a distributed context and CRDTs do not magically solve this problem because it’s not solvable. That’s why we have PAXOS and RAFT to do such things and why many many papers have been written trying to solve the Byzantine generals problem in constrained scenarios with well defined criteria.

> And there will be no data loss.

CRDT's can absolutely lose data!

Not when the log is append-only.

Yes, and CRDT's can absolutely lose data. That's the point that should be delivered across when someone claims they can't. Nobody needs to be warned that if you save endless data then you could save all data.

Reply on news.ycombinator.com