Comment by hinkley
5 years ago
A question that's been in my mind for a while is why Version Control and Collaborative Editing work at such cross purposes with each other when they are essentially solving the same problem? The biggest difference is that one works interactively and the other favors a CLI. Beyond that, how much of the distinction is artificial?
In particular I've been wondering about the space between CRDTs and the 'theory of patches' such as we discussed with Pijul the other day.
I have a collaborative editing project that's been sitting in my in-box for a long time now because I don't want to write my own edit history code and existing tools don't have enough ability to reason about the contents as structured data. The target audience is technology-averse, so no 'dancing bears' are going to interest them. It's not enough for it to work, it has to work very well.
As it stands today, version control and collaborative editing do not solve the same problem. Version control deals with large chunks of changes at a time. I don't even particularly want a version control system that stored every single keystroke made in source code. [1] Collaborative editing deals with keystroke-by-keystroke updates. By the standard of collaborative editing, even a single line source control commit is a big change.
The problem spaces are quite different. Problems that emerge on a minute-by-minute basis in collaborative editing emerge on a week-by-week basis in source control, and when the problems emerge in the latter, they tend to be much larger (because you can build up a much bigger merge conflict on a routine basis with the big chunks you're making).
Yes, it's true that if you squint hard, it looks like version control is a subset of collaborative editing, but I'd be really hesitant to, say, try to start a start-up based on that observation, because even if we take for the sake of argument that it's a good idea to use the same underlying data structures, the UI affordances you're going to need to navigate the problem space are going to be very different, and some of the obvious ways of trying to "fix" that would be awful, e.g., yes, you could give me a "collaborative space" where I see what everybody's doing in their code in real time... but it's a feature, not a bug, that when I'm working on a feature I'm isolated from what everyone else is doing at that exact moment. When I run the compiler and it errors out, it's really, really nice to have a good idea that it's my change that produced that result.
(I'm aware that collaborative editing also has the "I was offline for a week and here's a bunch of conflicts", but I'm thinking in terms of UI paradigms. That's not the common case for most/all collaborative editing systems.)
[1]: Not saying the only solution is the one we had now. A magic genie that watched over the code and made commits for you at exactly the right level of granularity would be great, so you'd never lose any useful context. But key-by-key isn't that level of granularity.
Version control is collaborative editing. Synchronizing on every key stroke is real-time collaborative editing. That's nice if you're working on a overlapping data at the same time. In code this does not happen so often because code repositories tend to be large.
Git does not work well for text because we have not figured out a nice format for text yet that developers and other people both enjoy. Developers want to stick to plain text as their format because we have so far failed to create nice tools and formats for structured data. Perhaps these affordances can appear thanks to a popularization of real-time collaborative editing.
Nobody is using "collaborative editing" to mean the sort of thing we've been doing with source control for decades, even if the plain English meaning of the component words seems like it might match that. We wouldn't have needed a new category term if "collaborative editing" didn't have the new element of real-time sharing.
3 replies →
One of the reasons we compartmentalize code is so that people can work on unrelated features without tripping over each other at every turn.
The bits where they don't interact also don't conflict. The bits where they do, look a lot more like collaborative editing.
They're also the spots where merges usually go wrong.
I've been on systems where multiple developers were trying to develop on the same system at once. I've also seen teams trying to do it systematically. It scales basically to two developers, sitting across from each other. Three, again, physically colocated, on a good day. Even if they're working on completely separate tasks, you hit "compile" and it's a complete mystery what's going to happen. It's not even stable if you do nothing and just hit "compile" again.
Beyond that it's insane. You do not want that in your version control system, as something built in, working all the time, across your entire team. It would be a massive anti-feature that would nuke your product.
Again, anyone thinking this sounds like a totally awesome idea, I strongly encourage you to try out the simple version, availablbe right now, of just "five or six people editing the same source code checkout" right now, before betting a start up on it. I guarantee a complete lack of desire to productize the result if you try it for a week or two.
4 replies →
Around 6-7 years ago we started a collaborative editing project for prezi.com. The problem basically boiled down to concurrent editing of a big DOM-like data-structure. We looked at the little literature that was available at the time including OT and CRDTs, but quickly realized that none of the existing approaches were mature enough for our needs. All of them were stuck at "text editing", but we needed to edit these big object DAGs.
So we ended up essentially implementing what you laid out, an in-memory revision control system, although using a bit more formal methods to reason about divergence/convergence of clients. The most basic operation was the "diamond merge": given operation x:A->B, y:A->C, construct x':C->D, y':B->D such that x' . y == y' . x It also had to satisfy certain other algebraic laws, notably diamond composition, which allowed us to compose these merging operations whenever we wanted, guaranteeing that the clients will eventually converge to the same data state. It was quite neat! Shame that it's all proprietary.
Good old days. I remember, the most pesky operation was implementing a good undo-redo algorithm, it's quite tricky, even once you add inverses.
It wasn't around at the time, but tree operations (with object reparenting) is increasingly supported by OT systems now:
https://github.com/ottypes/json1/
(Designed to be used with sharedb or similar.)
Strong agree.
There's a next level of VCS forming on the horizon, in some combination of CRDTs, patch theory, and grammar-aware diffing.
Which should also learn from fossil, and consider metadata such as issues and surrounding discussions to be a part of the repo.
A really robust solution would also be aware of dependencies and build systems, and even deployment: I see these as all fundamentally related, and connected to versioning in a way that should be reflected and tracked through software.
If you look into Bazel (build system), you start getting to the point where everything including dependencies, build system, and deployments can be defined as "source" code and ideally should be treated as a first class software
Cloud based code environments are starting to merge this. Github Code Spaces for one are starting this. I don't know if they use Operational Transaction (OT) or Conflict-Free Replicated Data Types (CRDT) but they are repo backed. I assume it is just using Github diffing tools in the repos and maybe OT/CRDT in live sessions over WebRTC or similar.
Much of real-time collaboration goes back to networking and real-time networking used in distributed multi-user systems like games, where simulations need to sync on a server. In games though, Dead Reckoning [2] is used as well as interpolation and extrapolation in prediction, much of it can be slightly different for instance with physics/effect, but messages that are important to all like scores or game start/end are reliably synced and determined on the server.
[1] https://visualstudio.microsoft.com/services/github-codespace...
[2] https://www.gamasutra.com/view/feature/131638/dead_reckoning...
I wonder if there is a way to describe change sets as a mathematical curve and achieve something like the rewind-ability within Planetary Annihilation https://www.forrestthewoods.com/blog/tech_of_planetary_annih... which seems to be an smoother alternative to dead-reckoning that bakes the history into it a bit better.
Author of the blog post here. I totally agree with you.
People think of OT / CRDT as realtime algorithms for realtime collaborative editing because they're always programmed and used that way. But the conflict resolution approach doesn't have to merge everything as-is. You could build a CRDT or OT system that generated VCS-style conflicts if concurrent edits happen on the same line of code. To make it a valid OT / CRDT algorithm the main constraint is just that every peer needs to resolve conflicts the same way. (So if I merge your changes or you merge my changes, we end up with identical document states). It would be easier to implement using OT because you only have to consider the interaction between two peers. But I think its definitely doable in a CRDT as well.
I think having something that seamlessly worked in both pair programming setups and with git style feature branches & merging would be fantastic.
I have a lot of thoughts about this and would be happy to talk more about it with folks in this space.
I've approached this problem from a different angle. I thought one could embrace the possibility of several truths. In my solution a truth lives in what I call a layer. Different layers can then be projected together in different stacks. Instead of using feature branches/toggles one can change the stack by adding/removing/reordering layers. One can also handle localized content this way, which was the original use case before the idea mutated.
I also thought one could differ between two different kinds of conflicts. I call them simultaneities and disagreements. Simultaneities happen when concurrent changes happen and could be handled by CRDTS for example. Disagreements are conflicts between layers.
The idea is then that you can choose to work in the same layer as someone else, if you are working close. You can also "shield" yourself from changes in other layers by working in a different layer. If you want to detect a disagreement between your layer and a layer someone else is working on, you project your layer on top of that layer.
Even though I believe in these ideas I don't know how to get other people interested in them. It might be that they are flawed in an obvious way not apparent to me.
What would it take to make someone of your caliber curious?
Sounds like a cool idea! There's some UX flows I'm not entirely clear on, but there's some novel ideas buried in here that I haven't seen anyone talk about before, which CRDTs would enable.
> What would it take to make someone of your caliber curious?
Talk about it more! Write a blog post describing the use cases and how it would work. Make UI mockups. Talk about what problems exist today that your idea would solve. Hop on to the automerge slack channel (linked from the automerge github repo) and show us.
And if you want to, build it. You don't need anyone's permission to make useful software.
My understanding may be flawed, but as far as I know you can think of an OT log and a git log as being similar. Each party generates deltas to the data structure that are recorded in the log, and when these parallel histories meet they must be merged. OT merges without involving the user, which sometimes leads it to discard changes. Git merges like that if it can, but when something must be discarded it asks the user. It is the interactive merging and deep ability to navigate and edit the log of changes that makes git so command-liney.
Not intending to nit-pick, but Git doesn't store the content as deltas. Each commit is the snapshot of the entirety of the codebase at that point in time.
Conceptually, yes, but under the hood, Git actually does store content as deltas:
https://git-scm.com/book/en/v2/Git-Internals-Packfiles
2 replies →
line-oriented data formats vs everything else. Why ? Because of "patching theory". If you don't understand the the data describes objects and doesn't have line-by-line semantics, it is hard to get merges correct.
Version control works wonders with line-oriented stuff, which covers more or less every programming language in existence.
It doesn't do so well with non-line-oriented structured formats such as XML (not sure how JSON or TOML) fits in here).
Given that collaborative editing typically works with non-line-oriented data formats, you can see the issue, I think.
That's what I refer to as "grammar-aware diffing" in the sibling comment, and it's one of the low-hanging fruits here.
Even git allows for pluggable diffing, and doesn't force line orientation. What's missing is the concept of moving something, as distinct from deleting lines/chunks and then inserting lines/chunks which just happen to be the same.
This is not a problem which CRDTs have, to put it mildly. I believe pijul understands it as well. A lot of this stuff is right out on the cutting edge, and as it matures it will become practical to connect the edges, such as a CRDT which collaborates with a parser to produce grammar-aware patches which are automagically fed to pijul or something like it.
This comes with a host of problems, mostly that we're not used to dealing with a history which has this level of granularity, most of which we don't want to see, most of the time. But they would be nice problems to have.
Some of "We" depend on sub-line diff highlighting during code reviews in order to reason about refactors and adding/removing arguments from function signatures.
That this is generally a feature of the diff tool and not the version control is a bit disappointing.