11 ms·
Automerge: JSON-like data structure for building collaborative apps
- bringtheaction 9y ago> If the state was concurrently changed 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! This is impossible unless there are significant restrictions on what kind of operations are possible. If I have a bag of 15 apples, and I take 10 of those apples at the same time as somebody else takes more than five apples then we have a merge conflict right there because we can't end up with a negative amount of apples in the bag.
- kba 9y agoThen there'd be a negative amount of apples. It's not impossible if you disregard context. There is nothing new about doing things like this, OT and CRDT have existed for ages. Check out ShareDB (https://github.com/share/sharedb https://github.com/share/sharedb) or Webstrates (https://webstrates.net/ https://webstrates.net/) (based on ShareDB). In Webstrates, we don't have merge conflicts that need to be resolved and there are never any practical synchronization issues. The server orders the operation and if you try to delete something that's already been deleted, then we just ignore your operation. Also quite courageous to say something is impossible when you have the code that does it right in front of you. ;-)
- KirinDave 9y agoI think when we say "impossible" we mean "well sure any old thing is possible but there are hard limits on what's consistent and sane." I will go read the docs in more detail but what you've just describes sounds pretty awful. Perhaps it's more just you being glib about non-cooperative actors in an environment that expects cooperatuon, but an "available balance" abstractions are a pretty reasonable thing to ask for, if only to encode natural numbers.
- kba 9y agoI'm not one to dictate how technologies like these are to be used, but all I can say is that in the almost two years I've been working on Webstrates – a collaborative system using a very similar technology – this has not been an issue. But surely, if you allow malicious actors to modify your document, then that's your problem right there.
- pvh 9y agoShareDB looks quite interesting. We wanted similar capabilities but without a central authority, thus automerge was born.
- kba 9y agoWe've been wanting to try a CRDT-based implementation with Webstrates for some time, but haven't found a suitable implementation, so this looks very promising! Any particular reason why you choose CRDT over OT?
- pvh 9y agoI'm told OT gets very complicated, and I hoped a good CRDT would be general-purpose enough to cover a variety of applications and domains. Also, I like not needing a central server to coordinate action. Would love to compare notes -- feel free to reach out to me on twitter at the same nick.
- imtringued 9y agoIt's still impossible in the general case. You merely proved him right. Limiting yourself to OTs and CRDTs is a signficant restriction.
- kba 9y agoWhy is that a restriction? You can make any changes to the JSON you wish, you just have to use their API.
- kaoD 9y agoIt's right there in the README: > The only case Automerge cannot handle automatically, because there is no well-defined resolution, is when users concurrently update the same property in the same object (or, similarly, the same index in the same list). In this case, Automerge arbitrarily picks one of the concurrently written values as the "winner": https://github.com/automerge/automerge#conflicting-changes https://github.com/automerge/automerge#conflicting-changes
- sli 9y agoMerge conflicts are handled transparently and seemingly indeterminately? Yikes.
- kba 9y agoThis isn't for a banking system, this is for building collaborative apps. If you press "A" and your friend press "B" into a Google Docs document at the same time, you also don't know if the document is going to read "AB" or "BA". In practice, this is not an issue.
- nolok 9y agoWell, so much for "no changes are lost", instead it should be "one of the change is lost, and you can't know which one until it's done ! Suprise !!!"
- amelius 9y agoAnother problem is this. Let's say there is a counter that is at value 100. I increment the counter. Simultaneously another user increments the counter, so the stable value should be 102. However, a operation-agnostic "merging" approach like described here can never catch that, and sets the final value to 101.
- insomniacity 9y agoAs I understand it, CRDTs don’t work on atomic types you might use in normal code - they work on larger structures where the problem has been solved. Wikipedia has some examples: https://en.m.wikipedia.org/wiki/Conflict-free_replicated_data_type https://en.m.wikipedia.org/wiki/Conflict-free_replicated_dat...
- kba 9y agoMy experience is with OT, so I can't speak for CRDT, but I can imagine it's similar. With OT, you send a na[1] (number add) operation, so this would work fine. Indeed, if you treat the number as a string, then you have a problem. [1]: https://github.com/ottypes/json0#summary-of-operations https://github.com/ottypes/json0#summary-of-operations
- taeric 9y agoThis doesn't compose with all operations. One users adds and another user multiplies, for example. That is to say, not all operations are associative. I bet you can run really far with this general idea. But there is no panacea.
- kba 9y agoYou're absolutely right, but I'd also never suggest a collaborative system for anything critical. As I've said earlier in this thread: If you're in a Google Docs document with a buddy and you write "A" and he writes "B" at the same time, you also don't know whether that'll show up as "AB" or "BA". In practice, this isn't an issue.
- 9y ago
- amelius 9y agoYet another problem is access-control: what if a user is allowed to access only part of the data-structure? And what if you'd want to encode access rules in the data-structure itself?
- k__ 9y agoWhen I learned one thing about collaborative apps, it's that there is no automerge that works for all use-cases. Couchdb does it the right way, it simply keeps all versions and lets the application logic decide which is the "one true state".
- jimpick 9y agoAutomerge is very similar. If there are conflicts, it returns a _conflicts property on the object so you can retrieve the other conflicting alternatives so the application logic can write another change if it wants to use a different alternative than the one that was automatically chosen.
- aeorgnoieang 9y agoI'm confused. What's the point of `_conflicts` property if conflicts are automatically merged? The linked project README, and even the CRDT Wikipedia page, seem to claim that conflicts are avoided, whereas, at least in my mind, these are more like strategies to automatically privilege one version in the event of a conflict.
- zachallaun 9y agoFrom my reading of the docs, Automerge will arbitrarily pick a "winning" document in the case of a conflict, but guarantees that the same winner will be chosen if the merge were to occur, for instance, in a different order: // Pretend doc1 and doc2 are already Automerge objects let doc1 = { x: 1 } let doc2 = { x: 2 } // x will be either 1 or 2 (arbitrarily chosen), but // res1 will always == res2 regardless of choice let res1 = Automerge.merge(doc1, doc2) let res2 = Automerge.merge(doc2, doc1) res1 == res2 // true However, there may be cases where you want to manually resolve conflicts, and if that is the case, the `_conflicts` property is there so that you can undo whatever merge occurred automatically and set the "winner" yourself.
- bb88 9y agoThe more interesting case is when you have the following: doc1 = { 'a': {'b': {'c': ... }}} doc2 = {} So one has been deleted entirely and the other has modified some attribute deep down inside of it. If you always have to check and resolve conflicts yourself, then it's not really useful.
- billconan 9y agoHow does this compared to differential synchronization used by google drive? https://neil.fraser.name/writing/sync/ https://neil.fraser.name/writing/sync/
- toomim 9y agoI love Differential Synchronization. Howevr, Google Drive doesn't use it. More specifically, by Google Drive, I assume you mean Google Docs. And Google Docs doesn't use diffsync, it uses OT.
- billconan 9y agoWhat's OT? why doesn't google docs use DS? Who uses DS? What's the best choice of making something similar to google docs' co-edit feature?
- deleted 9y ago[deleted]
- eindiran 9y agoWRT "What's OT?": https://en.wikipedia.org/wiki/Operational_transformation https://en.wikipedia.org/wiki/Operational_transformation The wiki article includes information that should answer your last question as well.
- billconan 9y agoI found this page informative and interesting https://operational-transformation.github.io/visualization.html https://operational-transformation.github.io/visualization.h... it has a live visualization of the OT algorithm
- eindiran 9y agoThe live visualization was a lot of fun to play around with.
- 9y ago
- benjaminjackman 9y agoDoes anyone have any experience and can offer a suggestion on javascript libraries that will handle text editing (like google docs or etherpad) and which can be dropped into a site and which aren't locked into a particular service or backend? I.e. basically something like this but for text?
- ZitchDog 9y agohttps://github.com/automerge/automerge#text-editing-support https://github.com/automerge/automerge#text-editing-support
- jimpick 9y agoProsemirror is another option that has the editor bits implemented. http://prosemirror.net/examples/collab/#edit-Example http://prosemirror.net/examples/collab/#edit-Example
- houshuang 9y ago[ShareDB](https://github.com/share/sharedb https://github.com/share/sharedb) is the most commonly used, we use it extensively - also has bindings to rich text or code editors. [Y-js](http://y-js.org/ http://y-js.org/) is a more academic project, also based on CRDTs I think.
- skrebbel 9y agoWow! I really, really like this because the goal appears to be to expose CRDTs in a developer-friendly way. I truly believe that well-designed CRDTs are the future for a lot of distributed systems problems, but they've been a bit hard to get into for people who just want to solve problems and not read 10 papers first. The only thing I miss here is a clear spec of the CRDT itself so that people could implement compatible versions in other languages.
- imoldfella 9y agoI imagine it is based on the author's earlier paper? https://arxiv.org/abs/1608.03960 https://arxiv.org/abs/1608.03960 I haven't compared them though.
- teej 9y agoIt’s not the same as the paper for performance reasons. This is noted in the github README. Martin said on Software Engineering Daily late last year that Automerge was three orders of magnitude faster than his published version of the JSON CRDT. This is my second time highly recommending a Software Engineering Daily podcast with Martin Kleppman on it. He is really smart and able to break down really complex topics in a way that's easy to understand. If you've never heard of CRDTs before, have a listen - https://softwareengineeringdaily.com/2017/12/08/decentralized-objects-with-martin-kleppman/ https://softwareengineeringdaily.com/2017/12/08/decentralize...
- biztos 9y agoConflict-free Replicated Data Type[0], for anyone else who didn't know what CRDT means. [0]: https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type https://en.wikipedia.org/wiki/Conflict-free_replicated_data_...
- skrebbel 9y agoYes, thanks!
- vanderZwan 9y ago
- maelito 9y agoSo this is to paths (keys and indexes) in a JSON object what git is to lines in a text file ? Could git be configured with a different diff algorithm to have this functionality, or is it too tied to lines ?
- deleted 9y ago[deleted]
- avian 9y agoSeveral years ago I made jsonmerge, a Python library for merging standard JSON structures. The rules for resolving conflicts are encoded in a standard JSON schema document that is extended with some (non-standard) keywords. https://github.com/avian2/jsonmerge https://github.com/avian2/jsonmerge https://www.tablix.org/~avian/blog/articles/talks/tomaz_solc_jsonmerge.pdf https://www.tablix.org/~avian/blog/articles/talks/tomaz_solc...
- trjordan 9y agoThis is cool! I've been thinking about this a lot in a similar domain (JSON / YAML for configuration), and I've come to the conclusion that anything approaching manual merge is pretty much the worst thing ever. The domain I'm specifically thinking of is managing routing rules, like nginx configs or control-plane configs for Envoy. It's really tempting to simplify it down to a config file, then you version-control it, then you get merge conflicts, and all of a sudden a bad merge makes 10% of your services unroutable. Which is hilariously bad. Having an auto-merge for those sort of configs seems like the only reasonable way to do it. Escalating conflicts up, from easy merge, to trying an automatic strategy, to surfacing conflicts to the user in a domain-specific way, seems like the only way to do it!
- davidw 9y agoThis is pretty interesting. I've seen similar problems at various places I've worked, and having a library that uses a CRDT to solve it is a winning proposition.
- jpsim 9y agoVery similar to Realm (also syncing CRDTs), though this seems more lightweight and works in client-side web apps. https://realm.io https://realm.io
- kuon 9y agoMy experience with collaborative sync is that it is really application specific. Most of the time, I used a dumb store (just storing all versions) and had the app decide of the logic to produce the current state. But, this library looks nice, and I'm sure it can fit some use cases.
- whoisjuan 9y agoThis is how you're supposed to write documentation. Excellent descriptions, explanations and examples.
- superasn 9y agoThis would work great with Firebase too. I remember writing a collaborative document editor similar to Google docs and the "document" was basically JSON with nodes for headlines, paragraphs, etc that multiple users could edit in real time. That time I just used to write the whole JSON to firebase (with flock like locking) and it was really bad but since it was just a weekend project I didn't care much at that time. Bet a library like this could have saved me a lot of headache.
- softwarelimits 9y agoThank you very much for the publication, may I ask a few questions: * How to integrate this with a decent pagination library? * How to integrate this with vue.js? * How does this compare to http://y-js.org http://y-js.org ? * How does this compare to http://gun.js.org http://gun.js.org ? Thanks for your attention!
- paulddraper 9y agoThis looks great, depending on the nature of the "collaborative app". E.g. perhaps the most popular collaborative app is Google Docs. This would be a terrible choice for Google Docs, as it doesn't have specialized transforms for text editing/formatting (which turn out to be rather challenging).
- namuol 9y agoTo change the state, you can use the regular JavaScript array mutation methods such as push(). Internally, Automerge translates this mutable API call into an update of the immutable state object. Note that we must pass in doc1, and get back an updated object which we assign to the same variable doc1. The original document object is not modified. Hmm. I like having the _option_ to use mutations to describe changes to the document, but in many cases I would actually prefer to use pure functions. Can I just return a new document with the necessary changes? I don't see any such examples in the docs here.
- wenc 9y agoWorth noting is the fact that this does not require a central transformation server unlike Google Docs' OT approach. This means you can sync peer-to-peer without an Internet connection if say you have a Bluetooth connection between your phone and your laptop on an airplane. Martin Kleppmann explains CRDT in detail in an episode of Software Engineering Daily. https://softwareengineeringdaily.com/2017/12/08/decentralized-objects-with-martin-kleppman/ https://softwareengineeringdaily.com/2017/12/08/decentralize...
- danbruc 9y agoCRDTs can provide an elegant solution to some problems but they are not powerful enough to be used as a general tool. If you change the title of your task card on two different devices, there is not much you can do to automatically merge those changes besides using some simplistic policy like last write wins which will not yield the desired result in general. CRDTs require the operations on them to commute or equivalently that state changes are monotonic. If your application fits those constraints you can probably build a quite elegant solution but unfortunately that is the exception rather than the norm, most operations are not commutative. EDIT: This was meant to be a reply to [1] instead of a top-level comment. [1] https://news.ycombinator.com/item?id=16310656 https://news.ycombinator.com/item?id=16310656
- pvh 9y agoIn fact, one of the purposes of this project was to test exactly what it was like to use a Trello-like tool implemented this way. What happens is that humans have intuitive coordination systems and tend to fix the same problems. In other words, if the card title is "rename auotmerge" then both of us are likely to change it the same way, or at least either resolution is fine. In the event of a conflict we flag the multi-value in the UI so that a human user can decide if they care. Where this approach shines is in domains where it helps avoid conflicts rather than resolving them. Naively adding replies to a comment thread might result in collisions or misordered comments across nodes of a distributed team. Automerge captures enough metadata from the operations created by users that changes "tend" to merge well. I realize this is an argument not from first principles but from experience. We weren't able to find examples of other people building web applications with quite this approach (though we would love to hear from them if they are out there) and so the question was "will this feel alright?" Apparently it does. If you find this result provocative, I would encourage you to challenge it by attempting to build something with automerge and letting us know how it goes. I believe it will work well in applications where all user operations can always commute to produce a subjectively reasonable result. To make that concrete, a bank account is a poor domain to model with a tool like this, but a shared drawing is much better.
- danbruc 9y ago
- nmca 9y agoThis seems to be Martin Kleppman's work - worth noting that his book, "Designing data intensive applications" is also very good :)
- wehriam 9y agoI've been working on Observed-Remove Map and Set implementations that replicate the native Javascript API, as well as versions that use IPFS PubSub for synchronization. * https://github.com/wehriam/observed-remove https://github.com/wehriam/observed-remove * https://github.com/wehriam/ipfs-observed-remove https://github.com/wehriam/ipfs-observed-remove The inherent tradeoffs can be challenging to explain. For example in these implementations, there are caching constraints on certain delete operations. Automerge looks fantastic, and I look forward to more progress in the space.
- avodonosov 9y agoThe description contradicts itself: > Different from git: no merge conflicts to resolve! But later: > The only case Automerge cannot handle automatically, because there is no well-defined resolution, is when users concurrently update the same property in the same object (or, similarly, the same index in the same list). In this case, Automerge arbitrarily picks one of the concurrently written values as the "winner": ... > Although only one of the concurrently written values shows up in the object, the other values are not lost. They are merely relegated to a _conflicts object
- kadenshep 9y agoSooooooo >git merge --strategy-option=theirs
- molikto 9y agoI am planning to doing the same thing, but using OT.
- molikto 9y agoMy idea about conflicts is, since OT is a centralized protocol, the server can refuse some conflicts and let user to resolve it. Another thing I don't like about CRDT is for text editing, it requires a uuid for each char you type. this is a huge waste of memory and disk imho. on the other hand OT requires no metadata
- 1zael 9y agoCan't wait to try this.
- zeandcode 9y agoRecently I created jkt library for my NodeJs project. https://github.com/slaveofcode/jkt https://github.com/slaveofcode/jkt