6 ms·

See also automerge [1], discussed at the end. They are currently working on performance improvements [2]. Quoting from the repo, "automerge is a library of da

See also automerge [1], discussed at the end. They are currently working on performance improvements [2]. Quoting from the repo, "automerge is a library of data structures for building collaborative applications in JavaScript: * You can have a copy of the application state locally on several devices (which may belong to the same user, or to different users). Each user can independently update the application state on their local device, even while offline, and save the state to local disk. * (Similar to git, which allows you to edit files and commit changes offline.) * When a network connection is available, Automerge figures out which changes need to be synced from one device to another, and brings them into the same state. (Similar to git, which lets you push your own changes, and pull changes from other developers, when you are online.) * If the state was changed concurrently on different devices, Automerge automatically merges the changes together cleanly, so that everybody ends up in the same state, and no changes are lost. (Different from git: no merge conflicts to resolve!)" [1] https://github.com/automerge/automerge https://github.com/automerge/automerge [2] https://github.com/automerge/automerge/pull/253 https://github.com/automerge/automerge/pull/253

benrbray 6y ago
See also the PushPin project [3], which uses React+Automerge, along with Capstone [4] [3] https://automerge.github.io/pushpin/ https://automerge.github.io/pushpin/ [4] https://www.inkandswitch.com/capstone-manuscript.html https://www.inkandswitch.com/capstone-manuscript.html
flir 6y ago
So if I change "foo" to "moo" and you change "foo" to "boo", who wins?
- wffurr 6y ago
  Depending on timing, you end up with "mboo" or "bmoo".
  - taeric 6y ago
    So, literally a change nobody wanted? Seems like it would not work in any real sense. I change it to moo and as a line checking something on it. You change it to boo and add a line, as well. Congrats, now neither of our additional lines makes sense... This really feels like a solution in search of problems.
    - heavenlyblue 6y ago
      What do you expect to happen instead?
      - taeric 6y ago
        Things are always sequenced. One will win, and the other will have to redo their change on top. Partially applying the change at the word level just seems way too fraught with false edits. It is already a source of a lot of bugs at the file and project level.
        djur 6y ago
        That is exactly what's happening here -- both deleted the "f", so there's no conflict, and their inserts of "b" and "m" are executed in order.
        taeric 6y ago
        But one person edited the word foo. The other edited a weird that no longer exists. I get why this feels like a clever combination of the edits. But I'm struggling to see how doing this at the character level makes any sense. Consider instead that you could do this at the byte level, with equally off results. At higher levels, this trick sounds useful. But you pick your abstraction height where all conflicts should just go back to the user. So, people edit the same document, but at different paragraphs? Fine. They edit the same paragraph? Almost certainly a problem. No different than code.
- atombender 6y ago
  So this is either represented as a delete followed by an insert (delete one character at offset N, insert "m" at offset N), or as a replace (atomically replace character at offset N with "m"). For an atomic replace operation, CRDT algorithms will solve this by having the last write win. What CRDTs give you here is a guarantee that the order is the same for every participant. So if you're building a collaborative text editor, for example, either everyone will either see "moo" or everyone will see "boo". For a delete + insert, it might not be atomic, in which case only the delete will "conflict". Since you both deleted at the same time, it's not actually a conflict (you both did the same thing), and the result will be either "mboo" or "bmoo". But again, it will the same for everyone.
  - Someone 6y ago
    > either everyone will either see "moo" or everyone will see "boo" That seems in conflict with the claim elsewhere in this discussion that this works offline, too (https://news.ycombinator.com/item?id=23802495 https://news.ycombinator.com/item?id=23802495) I guess everyone will eventually either see “moo” or “boo”?
    - atombender 6y ago
      Right!
  - flir 6y ago
    Interesting. What about the seqeunce "Alice deletes f, Bob replaces f with b, Alice inserts m"? I guess it doesn't matter, as long as all implementations do the same thing. git could easily take an approach like this too, but there are obvious reasons why it doesn't. It feels like the people designing this algorithm believe the text being worked on is less important than source code. I don't see how it's possible. I get Alice's changes, I spend 3 hours working on them, I get Bob's changes. The algorithm might be able to resolve these three sets of changes consistently according to its rules, but I've got no faith that the meaning of the text would survive the process.
    - atombender 6y ago
- amelius 6y ago
  Ideally, you'd get a popup asking you and the other party to reach consensus.
vlovich123 6y ago
It’s hard enough getting your own code to run and work correctly. When would this be a useful development paradigm?
- topicseed 6y ago
  Realtime collaboration on documents (e.g. source code, rich text editing, etc).
  - ickyforce 6y ago
    When I edit code it's broken most of the time. It wouldn't make sense to collaboratively break it in various parts for other people...
    - dkersten 6y ago
      I have done remote pair programming many times though and in that case it’s perfectly ok, because you’re communicating with the other person/people and can let each other know if you will break something. For that use case, I can see this being very useful.
    - IggleSniggle 6y ago
      While you could do real-time collaboration on code edits with this tool (and I've done that with some success via pair coding, where you commit them to git after your shared edits are complete), this tool isn't strictly about code. It's about any shared content at all. Think google docs, but for any data, with offline/online sync. The offline/online sync might not be great for simultaneous edits, but in a shared "project" of say, field research data, the combination offline/online sync and soft-realtime shared documents at any hierarchy level layer is a nice "don't need to think about it generally" approach. I'm not sure which kind of CRDT these are, but since all edits are part of history, as in git, you're not going to lose history if someone DOES inadvertently stomp on someone else's edits.
  - vlovich123 6y ago
    I understand how it's useful for documents. I don't believe source code is anything like a document and thus that mental model doesn't feel useful.
Someone 6y ago
That sounds similar in functionality to the protocol for Google Wave, now Apache Wave, and discontinued in early 2018 (https://en.m.wikipedia.org/wiki/Apache_Wave https://en.m.wikipedia.org/wiki/Apache_Wave) If so, what’s different? Better algorithms, assuming fewer collaborators and/or less frequent updates? Or is my understanding that these are similar in functionality incorrect?
- jahewson 6y ago
  Google Wave’s algorithm is now used by Google Docs, it’s Operational Transformation (OT) [1]. You can approximately view it as a special form of CRDT but the theory underpinning each have separate origins. OT is efficient and fast at real-time editing with a central server, whereas CRDTs are more capable in distributed/p2p scenarios but bring significant overhead as they store a lot of metadata. 1) https://en.m.wikipedia.org/wiki/Operational_transformation https://en.m.wikipedia.org/wiki/Operational_transformation
  - neilk 6y ago
    You seem to be implying that OT requires a central server. OT was designed for peer-to-peer, at least as far as I know. My OT knowledge isn't deep; perhaps in practice, some implementations like Google docs use an authoritative node?
    - liuliu 6y ago
      Interesting. I thought that OT implementations require peers to have at least one authoritative view of the transformations somewhere, and then distribute different operation sequences (after transformed) to different node. That, in simplest way, would imply a central server (otherwise you will have an alternative method to communicate the authoritative view between peers, which sort of defeat the purpose).
    - archagon 6y ago
      My understanding is that most specifications for OT have obscure failure cases if a central server is not used. Some papers have fixed these issues to enable fully P2P OT, but IIRC the resulting ops require similar amounts of metadata per-change as sequence CRDTs.
nojvek 6y ago
What does no merge conflicts to resolve even mean? Isn’t it fundamentally impossible to have both no merge conflicts and have meaningful data. Incase of a conflict you can either keep the most recent change or both changes. But like got keeps both changes with <<<< HEAD and theirs markers the code is now invalid and won’t compile. Suppose both the changes were kept without conflict resolution, now you have two things that may interfere with each other. I’ve had git mess up by trying to do an auto merge and still breaking the logic. So I don’t think there is a golden algorithms. Just a bunch of trade offs like any other problem.
- liuliu 6y ago
  The talk makes it clear, "no conflict" in CRDT sense is that states update, even ordered differently will converge to the same state. For practical sense, it is last-write-win baked in the the CRDT design (you can choose alternatives, but it has to be in the CRDT design, not something pluggable).
- butterisgood 6y ago
  If the merge operation is commutative the order doesn’t matter.
  - ulrikrasmussen 6y ago
    Yes, but the question is whether the semantics is meaningful for the application (e.g. text editing). I can also make string concatenation commutative by generalizing the concept of strings to multisets, but it is not given that this structure is useful for the applications where strings are needed.
    - sitkack 6y ago
      > Yes, but the question is whether the semantics is meaningful for the application (e.g. text editing). CRDTs are building blocks for larger systems. They themselves need to be composed into higher level constructs. I think this is the crux of the CRDT, it assists the application designer in creating an algebra over the domain model such that state can get updated w/o having a single representation of that state space. It pushes that complexity back down, so that we can reason about it in serial code.

benrbray 6y ago

See also the PushPin project [3], which uses React+Automerge, along with Capstone [4] [3] https://automerge.github.io/pushpin/ https://automerge.github.io/pushpin/ [4] https://www.inkandswitch.com/capstone-manuscript.html https://www.inkandswitch.com/capstone-manuscript.html

flir 6y ago

So if I change "foo" to "moo" and you change "foo" to "boo", who wins?

wffurr 6y ago
Depending on timing, you end up with "mboo" or "bmoo".
- taeric 6y ago
  So, literally a change nobody wanted? Seems like it would not work in any real sense. I change it to moo and as a line checking something on it. You change it to boo and add a line, as well. Congrats, now neither of our additional lines makes sense... This really feels like a solution in search of problems.
  - heavenlyblue 6y ago
    What do you expect to happen instead?
    - taeric 6y ago
      Things are always sequenced. One will win, and the other will have to redo their change on top. Partially applying the change at the word level just seems way too fraught with false edits. It is already a source of a lot of bugs at the file and project level.
      - djur 6y ago
        That is exactly what's happening here -- both deleted the "f", so there's no conflict, and their inserts of "b" and "m" are executed in order.
        taeric 6y ago
        But one person edited the word foo. The other edited a weird that no longer exists. I get why this feels like a clever combination of the edits. But I'm struggling to see how doing this at the character level makes any sense. Consider instead that you could do this at the byte level, with equally off results. At higher levels, this trick sounds useful. But you pick your abstraction height where all conflicts should just go back to the user. So, people edit the same document, but at different paragraphs? Fine. They edit the same paragraph? Almost certainly a problem. No different than code.
atombender 6y ago
So this is either represented as a delete followed by an insert (delete one character at offset N, insert "m" at offset N), or as a replace (atomically replace character at offset N with "m"). For an atomic replace operation, CRDT algorithms will solve this by having the last write win. What CRDTs give you here is a guarantee that the order is the same for every participant. So if you're building a collaborative text editor, for example, either everyone will either see "moo" or everyone will see "boo". For a delete + insert, it might not be atomic, in which case only the delete will "conflict". Since you both deleted at the same time, it's not actually a conflict (you both did the same thing), and the result will be either "mboo" or "bmoo". But again, it will the same for everyone.
- Someone 6y ago
  > either everyone will either see "moo" or everyone will see "boo" That seems in conflict with the claim elsewhere in this discussion that this works offline, too (https://news.ycombinator.com/item?id=23802495 https://news.ycombinator.com/item?id=23802495) I guess everyone will eventually either see “moo” or “boo”?
  - atombender 6y ago
    Right!
- flir 6y ago
  Interesting. What about the seqeunce "Alice deletes f, Bob replaces f with b, Alice inserts m"? I guess it doesn't matter, as long as all implementations do the same thing. git could easily take an approach like this too, but there are obvious reasons why it doesn't. It feels like the people designing this algorithm believe the text being worked on is less important than source code. I don't see how it's possible. I get Alice's changes, I spend 3 hours working on them, I get Bob's changes. The algorithm might be able to resolve these three sets of changes consistently according to its rules, but I've got no faith that the meaning of the text would survive the process.
  - atombender 6y ago
amelius 6y ago
Ideally, you'd get a popup asking you and the other party to reach consensus.

vlovich123 6y ago

It’s hard enough getting your own code to run and work correctly. When would this be a useful development paradigm?

topicseed 6y ago
Realtime collaboration on documents (e.g. source code, rich text editing, etc).
- ickyforce 6y ago
  When I edit code it's broken most of the time. It wouldn't make sense to collaboratively break it in various parts for other people...
  - dkersten 6y ago
    I have done remote pair programming many times though and in that case it’s perfectly ok, because you’re communicating with the other person/people and can let each other know if you will break something. For that use case, I can see this being very useful.
  - IggleSniggle 6y ago
    While you could do real-time collaboration on code edits with this tool (and I've done that with some success via pair coding, where you commit them to git after your shared edits are complete), this tool isn't strictly about code. It's about any shared content at all. Think google docs, but for any data, with offline/online sync. The offline/online sync might not be great for simultaneous edits, but in a shared "project" of say, field research data, the combination offline/online sync and soft-realtime shared documents at any hierarchy level layer is a nice "don't need to think about it generally" approach. I'm not sure which kind of CRDT these are, but since all edits are part of history, as in git, you're not going to lose history if someone DOES inadvertently stomp on someone else's edits.
- vlovich123 6y ago
  I understand how it's useful for documents. I don't believe source code is anything like a document and thus that mental model doesn't feel useful.

Someone 6y ago

That sounds similar in functionality to the protocol for Google Wave, now Apache Wave, and discontinued in early 2018 (https://en.m.wikipedia.org/wiki/Apache_Wave https://en.m.wikipedia.org/wiki/Apache_Wave) If so, what’s different? Better algorithms, assuming fewer collaborators and/or less frequent updates? Or is my understanding that these are similar in functionality incorrect?

jahewson 6y ago
Google Wave’s algorithm is now used by Google Docs, it’s Operational Transformation (OT) [1]. You can approximately view it as a special form of CRDT but the theory underpinning each have separate origins. OT is efficient and fast at real-time editing with a central server, whereas CRDTs are more capable in distributed/p2p scenarios but bring significant overhead as they store a lot of metadata. 1) https://en.m.wikipedia.org/wiki/Operational_transformation https://en.m.wikipedia.org/wiki/Operational_transformation
- neilk 6y ago
  You seem to be implying that OT requires a central server. OT was designed for peer-to-peer, at least as far as I know. My OT knowledge isn't deep; perhaps in practice, some implementations like Google docs use an authoritative node?
  - liuliu 6y ago
    Interesting. I thought that OT implementations require peers to have at least one authoritative view of the transformations somewhere, and then distribute different operation sequences (after transformed) to different node. That, in simplest way, would imply a central server (otherwise you will have an alternative method to communicate the authoritative view between peers, which sort of defeat the purpose).
  - archagon 6y ago
    My understanding is that most specifications for OT have obscure failure cases if a central server is not used. Some papers have fixed these issues to enable fully P2P OT, but IIRC the resulting ops require similar amounts of metadata per-change as sequence CRDTs.

nojvek 6y ago

What does no merge conflicts to resolve even mean? Isn’t it fundamentally impossible to have both no merge conflicts and have meaningful data. Incase of a conflict you can either keep the most recent change or both changes. But like got keeps both changes with <<<< HEAD and theirs markers the code is now invalid and won’t compile. Suppose both the changes were kept without conflict resolution, now you have two things that may interfere with each other. I’ve had git mess up by trying to do an auto merge and still breaking the logic. So I don’t think there is a golden algorithms. Just a bunch of trade offs like any other problem.

liuliu 6y ago
The talk makes it clear, "no conflict" in CRDT sense is that states update, even ordered differently will converge to the same state. For practical sense, it is last-write-win baked in the the CRDT design (you can choose alternatives, but it has to be in the CRDT design, not something pluggable).
butterisgood 6y ago
If the merge operation is commutative the order doesn’t matter.
- ulrikrasmussen 6y ago
  Yes, but the question is whether the semantics is meaningful for the application (e.g. text editing). I can also make string concatenation commutative by generalizing the concept of strings to multisets, but it is not given that this structure is useful for the applications where strings are needed.
  - sitkack 6y ago
    > Yes, but the question is whether the semantics is meaningful for the application (e.g. text editing). CRDTs are building blocks for larger systems. They themselves need to be composed into higher level constructs. I think this is the crux of the CRDT, it assists the application designer in creating an algebra over the domain model such that state can get updated w/o having a single representation of that state space. It pushes that complexity back down, so that we can reason about it in serial code.