Comment by ragnese
5 years ago
> Is it realistic to think hundreds of people can edit a document in real time at the same time and come up with something coherent?
And here's the thing: Can 100 people edit a document, even in theory, and have it make sense? I think the answer is "no," with or without technology.
I'm sure there are other uses for these data structures, but shared editing is always the example I read about.
Ultimately I think the answer is “it depends” but the issue is that there is usually document structure which is mot visible in the data structure itself. For example imagine getting 100 people to fill out a row on a spreadsheet about their preferences for some things or their availability on certain dates. If each person simultaneously tries to fill in the third row of the spreadsheet (after the headings and the author), then a spreadsheet CRDT probably would suck at merging the edits. But if you had a CRDT for the underlying structure of this specific document you could probably merge the changes (eg sort the set of rows alphabetically by name and do something else if multiple documents have rows keyed by the same name).
It depends how big the document is, i.e. what is the density of users per page. If it's a 100 page document and the 100 users are all working on different sections, then it could easily be possible.
I just don't remotely see a use case for this. Real-time human collaboration in general fails at a scale much smaller than this, and not because of the tools available.
JoeDocs[1] could be a useful project to track related to this - the Coronavirus Tech Handbook[2] amongst other collaborative documents is now hosted by their service.
They utilize the same YJS[3] library mentioned in the article this thread discusses, and their GitHub repos include some useful working demonstration application code.
[1] - https://joedocs.com/
[2] - https://coronavirustechhandbook.com/
[3] - https://docs.yjs.dev/
A question I always have is if CDRTs solve some problem with collaborative editing, then can git's merge algorithm be rewritten to use CDRTs and benefit from it somehow?
Somehow I think the answer is no. There is a reason we still have to manually drop down to a diff editor to resolve certain kinds of conflicts after many decades.
I think a better question is “what if merges were more well behaved,” where “well behaved” means they have nice properties like associativity and having the minimal amount of conflict without auto-resolving any cases that should actually be a conflict.
The problem with using a CRDT is the CR part: there are generally merge conflicts in version control for a reason. If your data type isn’t “state of the repo with no conflicts” or “history of the repo and current state with no conflicts” but something like “history of the repo and current state including conflicts from unresolved merges” then maybe that would work but it feels pretty complicated to explain and not very different from regular git. Also note that you need history to correctly merge (if you do a 3-way merge of a history of a file of “add line foo; delete line foo” with a history of “add line foo; delete line foo; add line foo” and common ancestor “add line foo”, you should end with a history equal to the second one I described. But if you only look at the files you will probably end up deleting foo)
See also: darcs and pijul.
It's perfectly CR to encode a merge conflict as another type of data in the CRDT lattice.
For documents, you might represent this as a merged document, with merge conflict markup inside the merged document - similar to using version control and getting a merge conflict.
Also similar to version control, the merge conflict can be a form of data where a valid CRDT operation is for a user to resolve the conflict. When that resolution is merged with other users, unless there's a conflict in the conflict-resolution, everyone sees the merge conflict go away.
Another valid CRDT operation is when a user modifies their version of the document in the region of the merge conflict prior to seeing the conflict, and broadcasts their edit. Then the merge conflict itself would update to absorb the valid change. In some cases, it might even disappear.
In principle, you can build a whole workflow stack on top of this concept, with sign-offs and reviews, just as with version control. I have no idea how well it would behave in practice.
The answer is no, but unlike git, crdts make a choice for you, and all nodes get convergent consistency. The problem heretofore with crdts is that those choices have not been sane. I think there are a recent crop of crdts that are "95% sane" and honestly that's probably good enough. There is an argument that optimal human choices will never be reconciliable with commutativity, which I totally buy, but I think there is also an argument for "let not the perfect be the enemy of the awesome". And having made a choice, even if it's not optimal, is a much firmer ground to build upon than blocking on leaving a merge conflict undecided.
Git mostly treats merging as a line oriented diff problem. Even though you can specify language aware diffing in theory it doesn't seem to buy you much in practice (based on my experience with the C# language-aware diff).
It wouldn't make much sense to me to just plug a text CRDT in place of a standard text diff. CRDTs like automerge are capable of representing more complex tree structures however and if you squint you can sort of imagine a world where merging source code edits was done at something more like the AST level rather than as lines of text.
I've had some ugly merge conflicts that were a mix of actual code changes and formatting changes which git diffs tend not to be much help with. A system that really understood the semantic structure of the code should in theory be able to handle those a lot better.
IDEs have powerful refactoring support these days like renaming class members but source control is ignorant of those things. One can imagine a more integrated system that could understand a rename as a distinct operation and have no trouble merging a rename with an actual code change that touched some code that referenced the renamed thing in many situations. Manual review would probably still be necessary but the automated merge could get it right a much higher percentage of the time.
For specific use cases where the data format is not plain-text and or is formatted as json (e.g. Jupyter notebooks, rich text editing like ProseMirror), I can see CRDTs being used to automatically merge files and retain consistency. Two things though:
1. this doesn't require modifying git's merge algorithm itself; just having custom merge drivers built on top.
2. Is using more space (edit history of CRDTs vs a regular json document) worth it for automatic merging?
Depends on what kind of document we’re talking about I.e. how the grammar captures the domain model. Eg: A shared ledger in the case of digital currencies, or the linux source code being worked on remotely by many people are exactly examples of such documents.
Maybe if your "document" is the Encyclopedia Britannica? Wikipedia has hundreds of editors working at once, but that only really works because it's broken up into millions of smaller parts that don't interact much.
I meant this to be my takeaway. The data structure is nice. And I suspect it is a perfect fit for some use cases. I question the use case of shared editing. Not just the solution, but the use case.