[HN Gopher] Lies I was told about collab editing, Part 1: Algori...
___________________________________________________________________
Lies I was told about collab editing, Part 1: Algorithms for
offline editing
Author : antics
Score : 62 points
Date : 2024-12-06 20:22 UTC (2 hours ago)
(HTM) web link (www.moment.dev)
(TXT) w3m dump (www.moment.dev)
| zamalek wrote:
| I think this happens because the mathematical, or causal, or
| entropic, notion of conflicts has been conflated with semantic
| conflicts. In the past I have made the same mistake, though
| inversely and was adamantly informed that I had no clue what I
| was talking about :)
|
| Things get way nastier when you start considering trees, e.g. yJS
| operates on JSON documents. From a UI standpoint (where the UI is
| showing some shallow level and hasn't been expanded to the deeper
| level) users could never even see edits that have been deleted.
|
| I think that the class of CRDTs that preserve conflicts (IIRC
| that is when a register can hold multiple values) hold the most
| promise. Users should then be presented with those conflicts -
| and it could even be completely visual. Being able to scrub
| through history also seems like a viable alternative (allowing
| the user to figure out how a strange thing happened, or how their
| changes disappeared).
| Onavo wrote:
| > _Users should then be presented with those conflicts - and it
| could even be completely visual. Being able to scrub through
| history also seems like a viable alternative_
|
| I think "Git" would be a wonderful name for this type of CRDT.
| drdaeman wrote:
| More like Pijul or Darcs?
|
| Git is popular, but it's not particularly great at conflict
| resolution.
| satvikpendem wrote:
| I mentioned Loro in another comment, but they actually do
| conflict resolution on top of Git trees [0]. Jujutsu is also
| interesting but I'm not sure if they do any conflict
| resolution [1].
|
| [0] https://loro.dev/blog/v1.0#loro-version-controller
|
| [1] https://github.com/martinvonz/jj
| Rygian wrote:
| I would wager that, in general, supporting the notion that
| several different entities are all the authority over a piece of
| data simultaneously and without live coordination is not
| solvable. This is a learned lesson for distributed systems, and
| is readily apparent in the article when considering distributed
| editing of documents. Same goes for dual input in flight cabins,
| parenting, and probably any other disparate example one can think
| of.
| beefnugs wrote:
| It is solvable, but needs more complicated contextual
| information that many people would not want to bother entering
| : "this word i just changed only makes sense if it is apart of
| this whole sentence, which is not necessarily required for the
| whole paragraph..."
|
| And calling this "solvable" is a funny thing to think about,
| since huge portions of the earth think the chaos output of LLMs
| could be anywhere near deciding the final output of computation
| at this point in time
| antics wrote:
| Hi folks! Author here. Happy to answer questions or take
| feedback. I'll be in meetings for an hour or two but I love
| talking about this stuff. :) Here or over email if you prefer,
| alex@moment.dev
| jakevoytko wrote:
| If you keep the offline support, you'll eventually uncover even
| more fun cases. "I started working on this on an airplane where
| the wifi was down. But then decided I didn't like the direction
| it was going and just closed the laptop and took a nap. I spent
| the next few days working on the document on my desktop. Over
| the weekend I opened the doc on my laptop and now all of my
| airplane changes are in the doc and everything is garbled.
| Help, I didn't mean to merge them!"
|
| Git would never automatically mash your local changes in
| without your explicit consent. bzr would never have dreamed of
| it. But things like Google Docs will happily do it.
|
| It's awesome to see all the progress y'all have made! Good luck
| with early access!
| mike_hearn wrote:
| What's the problem with just adopting patch/diff style merging?
| I mean, offline collaborative text editing is a solved problem
| for decades if you're going to phrase it as just a UX
| optimization problem.
| bee_rider wrote:
| The example seems like it would be easier if we'd gone in the
| direction of allowing more complex commands, like vim does.
| Imagine if real editors had been developed for the last 30 years
| or however long, instead of stagnating at vim (which is clearly a
| nice text editor, but it could be nice to have an editor designed
| around writing prose). Maybe neovim will save us. Some day.
|
| Bob's intent is to edit the word color, and inserting a u. But,
| he is limited to just expressing "put u here," which is not at
| all what he wants to _achieve_ it is just a mechanical
| description of what operations need to occur.
|
| Alice's intent is to delete the whole sentence, but she's
| similarly limited to just saying "delete delete deleted delete
| delete..." to a bunch of letters.
|
| Ending up with a u is the obvious dumb result of treating
| language as a pile of characters. The correct behavior is to say:
| because the world Bob has edited no longer exists, his edit is
| clearly nonsense, don't apply it. Which editor does that?
| Rygian wrote:
| Considering that software can only guess the intent if it's not
| declared explicitly, I'm curious what such an "intent
| declaration" language would look like.
| satvikpendem wrote:
| At the limit, it would probably look like an LLM, because
| it's akin to rules-based AI in the '90s vs neural network AI
| today. Expert systems had programmers write many rules in
| order to process information, which is what this "intent
| declaration" language would also be like, users writing many
| rules that would be followed. But this approach didn't work
| because even humans didn't even know all of the rules needed,
| therefore we turned to the statistical approaches of current
| neural network AI.
| robertclaus wrote:
| The most surprising part of this article for someone uninitiated
| like myself is probably that products/algorithms are claiming
| this automatic reconciliation is consistently possible. Maybe
| I've spent too much time resolving code merge conflicts by hand,
| but this seems intuitively obvious to me...
|
| Feels like https://xkcd.com/1831
| williamstein wrote:
| What they claim is that if all editing stops, then after a
| period of time everybody will be looking at the SAME document.
| This is what is meant by "eventual consistency". Achieving this
| in general is indeed a difficult problem, but (some of) these
| algorithms do solve it, though it can be tricky to correctly
| prove that they do. I agree that it is not possible to ensure
| that the document everybody is looking at is what they actually
| wanted it to be. However, there are some options for what
| happens, where some results may be technically correct -- we
| are all looking at the same thing -- but obviously really bad.
| This beautiful talk has some examples:
| https://www.youtube.com/watch?v=x7drE24geUw
| satvikpendem wrote:
| I had an interest in CRDTs for quite a while now, as I like the
| local first philosophy of developing software, that works offline
| in its entirely but can also work online, a sort of progressive
| enhancement [0]. Recently I've been looking into Loro [1] which
| seems like it is able to effectively merge disparate offline text
| edits together, by using some new algorithms that were written
| about last year, such as the Event Graph Walker [2]. I've been
| combining this with ElectricSQL [3], which is a sync engine for
| Postgres. In the past they had their own CRDT right inside
| Postgres which would then sync tables, but they have rewritten
| their product to focus primarily on being a sync engine first and
| perhaps a conflict resolution library second. Therefore, I store
| the Loro changes binary in a table in Postgres as a blob that I
| then sync via Electric to all my clients.
|
| Ultimately though, it is as you and others like @zamalek in this
| thread have said, the mathematical notion of conflict resolution
| might not actually mean anything semantically, therefore it is
| difficult to have long running offline edits merge together
| cohesively; it works with things like Google Docs where the user
| can see what other users have written in real time, which works
| for 99% of use cases, and sometimes I wonder whether one really
| needs such long running offline syncs, as it seems to be a very
| niche goal to target. Short running offline is nice to have and
| even necessary, especially for products one expects to work
| wholly offline, but it is the long term I don't see much value
| in, as in not collaborating online for weeks or months at a time
| but still expecting cohesive edit merges.
|
| [0] https://localfirstweb.dev/
|
| [1] https://loro.dev/
|
| [2] https://loro.dev/docs/advanced/event_graph_walker
|
| [3] https://electric-sql.com/
| refulgentis wrote:
| Alas, Loro fails The Color of Pomegranates test as well. (JSON
| trace, really cool toy they got there:
| https://pastebin.com/6dSDc6Su)
| satvikpendem wrote:
| Yes, it is as I mentioned in my 2nd paragraph, mathematical
| conflict resolution is not semantically relevant for humans
| much of the time. That is why I don't think automated merge
| conflict resolution with no human input can really work, that
| is why Git asks you to resolve merge conflicts before
| committing again. CRDTs can only really help when users edit
| disparate pieces of data, and if editing the same piece of
| data, _some_ set of users need to be there, as in an online
| rather than offline capacity, to facilitate the merges, such
| as in Google Docs where if I edit a sentence with a spelling
| correction and you delete the sentence entirely, I will ask
| you directly what 's up.
|
| Now, what some Git merge software is doing is using LLMs to
| coordinate merges, which I think might be useful to do so in
| plain text editing too, perhaps embedded into these CRDT
| libraries, but fundamentally, there must be _someone_ to
| facilitate merges, whether it be a human agent or an AI one.
| It is impossible to do so with an entirely automated solution
| simply because _the machine does not know the intents of all
| its users_.
| williamstein wrote:
| The text sync algorithm I wrote succeeds at the "The Color of
| Pomegranates" test. See
| https://cocalc.com/wstein/dev/share/files/2024-12-06.md for
| some details of the exact patches. This algorithm, which we
| came up with in 2015, is described at
| https://blog.cocalc.com/2018/10/11/collaborative-
| editing.htm... It's a different approach than that taken by
| Yjs, Automerge, and Egwalker, with signficant pros (and
| cons!) relative to those algorithms. It has been used in
| production in CoCalc for over 8 years, and was also used by
| the recently shutdown Noteable Jupyter notebook project.
| refulgentis wrote:
| This is so, so, sooo good. I've never been brave enough to say it
| out loud, but this is 110% my experience.
|
| I imagine it is somewhat a consequence of the divide between
| engineering and product.
|
| It _can_ resolve all conflicts, and it 's such a holy grail to go
| decentralized / get Google Docs-like editing down to a a package
| in your favorite language. But, in practice, its intractable for
| arbitrary data, even just an arbitrary string.
|
| I do wish there was a formal proof that showed / proved this to
| share in HN discussions re: CRDTs...but hey, this is great! The
| "it left a u" example is simple, intuitive, and with a charitable
| listener, I doubt they'd argue we can't figure out a string
| unambiguously, but we can figure out JSON unmabiguously.
| pvh wrote:
| Mechanical merge algorithms can perform better or worse on
| different kinds of conflicts (the specific example of editing
| deleted text is just one of many edge cases) but in the end no
| CRDT can decide if your merged text is what you _mean_ to say.
|
| We go into a bunch more detail in the Upwelling paper about the
| differences between (what we call) semantic and syntactic
| conflicts in writing: https://inkandswitch.com/upwelling/
|
| Ultimately, my feeling is that serious collaboration is a
| document review problem as much as anything else. That said, this
| is particularly true in journalism and scientific publishing and
| can be mostly ignored for your meeting notes...
|
| Anyway, if you see this comment, thanks for a nice piece of
| writing, Alex. Love to see folks wrestling with these problems.
| antics wrote:
| Hi Peter! Thanks so much for the kind words. I hope you noticed
| that a lot of the article ends up being a motivation for Ink &
| Switch's work, which we call out directly at the end. I am a
| big fan! :)
|
| EDIT: Oh, also I meant to link to Upwelling, but forgot what it
| was called. I settled for a different link instead because it
| was deadline.
| major4x wrote:
| I love this mini article, however, I disagree with the main
| conclusion that collaborative editing is not an algorithmic but a
| UI/UX problem. I think that collaborative editing is a semantic
| problem. To the best of my knowledge (I'm writing this comment
| without much preparation), all SVN/Git algorithms are based on
| UNIX diff (Hunt-Szymanski algorithm). UNIX diff (and patch) is
| purely syntax driven.
|
| Actually, I will make a small deviation here: I think it is a big
| industry/startup/open source project there, in creating a set of
| semantic diff algorithms/implementations. For example, due to my
| present job, I am very interested in collaborative editing of
| electrical circuits, and layouts for PCB and chips. Altium and
| KiCad are trying, for exmaple, to store everything in XML/text
| files and put the text files in Git/SVN and I can tell you a
| botched C++ program is nothing in comparison to a botched and
| malformed electrical circuit. So we need diff tools that "know"
| about a text file, vs rich-text with formatting, vs bitmap vs
| vector image, vs song, vs English text. Anybody want to start an
| open source project (DM me or put a comment here).
|
| Anyhow, thanks to the authors on the great insights and let's
| work on the take home!
| ramon156 wrote:
| Just use git (: (Half joking)
| josephg wrote:
| Hi! Author of Eg-walker & ShareJS here, both of which are
| referenced by this post.
|
| You write this article like you're disagreeing with me - but I
| agree completely with what you've said. I've been saying so on HN
| for years. (Eg, in this comment from 6 years ago[1].)
|
| The way I think about it, the realtime collaborative tools we use
| today make a lot of sense when everyone is online & editing
| together. But when users edit content offline, or in long lived
| branches, you probably want the option to add conflict markers &
| do manual review when merging. (Especially for code.)
|
| Luckily, algorithms like egwalker have access to all the
| information they need to do that. We store character-by-character
| editing traces from all users. And we store _when_ all changes
| happened (in causal order, like a git DAG). This is far more
| information than git has. So it should be very possible to build
| a CRDT which uses this information to detects & mark conflict
| ranges when branches are merged. Then we can allow users to
| manually resolve conflicts.
|
| Algorithmically, this is an interesting problem but it should be
| quite solvable. Just, for some reason, nobody has worked on this
| yet. So, thanks for writing this post and bringing more attention
| to this problem!
|
| If anyone is interested in making a unique and valuable
| contribution to the field, I'd love to see some work on this. Its
| an important piece thats missing in the CRDT ecosystem - simply
| because (as far as I know) nobody has tried to solve it yet. At
| least not for text editing.
|
| [1] Bottom part of this comment:
| https://news.ycombinator.com/item?id=19889174
| antirez wrote:
| Now that there are LLMs available, why is this still a problem?
| You just have to detect the conflicts and show a powerful enough
| LLM the two versions and tell it to do its best job at merging.
| Done.
___________________________________________________________________
(page generated 2024-12-06 23:00 UTC)