Show HN: Operational transform for realtime collaborative editing in JS/Flow • Hacker News Board

Re: Show HN: Operational transform for realtime collaborative editing in JS/Flow

#11

Post by akanet » Sat, Dec 31, 2016, 10:23 AM UTC

c0da wrote: post #3

theaustinseven wrote: post #2

This is cool! I've been working on something similar in Go, but I haven't spent much time on it recently. Is this a purely front-end application, or is there a server associated with it?

Thanks! My implementation is currently front-end only. Here's the code that simulates all the client/server communication: https://github.com/cricklet/blue-ot.js/blob/master/js/ot/orc... It shouldn't be too hard to take that and put it in an actual client/server architecture. The client needs to have a way to send local operations to the server (this can just be an endpoint on the server) and the server needs a way t…

I'm going to try to implement this in my app. I use Firebase/Firepad for true p2p OT but it's become cumbersome. Do you have additional thoughts about communication channel implementation?

Re: Show HN: Operational transform for realtime collaborative editing in JS/Flow

#12

Post by devdoomari » Sat, Dec 31, 2016, 10:53 AM UTC

tmail21 wrote: post #6

The basic problem with OT (and current "real-time" collaborative editing approaches) is that they can only achieve eventual consistency. While this sounds great, eventual consistency DOES NOT mean semantic consistency. This rules it out for many applications where semantic correctness is important. Even for simple text documents you can get eventually correct but semantically incorrect results. For example, consider…

I can't think of a CRDT / anything that can handle your example...

but wouldn't this be somewhat (*not 100%) mitigated with UI? (e.g. showing carret positions + time-agos of different users, asking user(s) to resolve a conflict, etc.)

Re: Show HN: Operational transform for realtime collaborative editing in JS/Flow

#13

Post by tmail21 » Sat, Dec 31, 2016, 5:52 PM UTC

theaustinseven wrote: post #10

tmail21 wrote: post #6

The basic problem with OT (and current "real-time" collaborative editing approaches) is that they can only achieve eventual consistency. While this sounds great, eventual consistency DOES NOT mean semantic consistency. This rules it out for many applications where semantic correctness is important. Even for simple text documents you can get eventually correct but semantically incorrect results. For example, consider…

I would expect that if an editor makes a change, their change should be preserved. There is no general case where you can decide which edit to keep, because in some cases(like the one you presented) people are editing the exact same sentence, but far more often people will not make edits to the same small part at the same time(at least in the real world). This makes OT very practical since generally the eventual cons…

It is fairly trivial to construct an example where editors are editing _different_ sentences and OT takes two locally semantically correct states and converges to a semantically incorrect (but grammatically correct) state.

I think OT and other "real-time" collaborative editors are practical if you are willing to (or your use case can) live with "silent semantic errors".

The greater the document "interconnectivity" (eg, paragraph A is semantically related to paragraph C), the greater the likelihood of having far-flung silent semantic errors.

For documents like spreadsheets this is very obvious because you start getting nonsensical results and (hopefully) errors very quickly. For Word-like documents, the errors are "silent" and thus much more insidious.

My point was that that is an element of OT which many users don't realize.

With regards to predictability, I would not call the results of OT predictable from a user's perspective. It is predictable in the narrow sense that for a sequence of arrival of operations AT THE SERVER it is predictable.

However, it is impossible for a user to predict how their local operations will interleave at the server with other users' local operations. For all practical purposes the converged result is unpredictable from the user's perspective.

The only property which one can confidently assert with OT is eventual consistency.

Re: Show HN: Operational transform for realtime collaborative editing in JS/Flow

#14

Post by tmail21 » Sat, Dec 31, 2016, 6:05 PM UTC

devdoomari wrote: post #12

tmail21 wrote: post #6

The basic problem with OT (and current "real-time" collaborative editing approaches) is that they can only achieve eventual consistency. While this sounds great, eventual consistency DOES NOT mean semantic consistency. This rules it out for many applications where semantic correctness is important. Even for simple text documents you can get eventually correct but semantically incorrect results. For example, consider…

I can't think of a CRDT / anything that can handle your example... but wouldn't this be somewhat (*not 100%) mitigated with UI? (e.g. showing carret positions + time-agos of different users, asking user(s) to resolve a conflict, etc.)

Yes, this problem could be mitigated somewhat by showing caret positions. But this method is very reliant on the users paying extremely close attention. It does not work at all when the silent semantic errors are caused by "far flung" edits, where you don't even see the other caret because it is "off screen" for you.

Asking users to resolve a conflict is not possible, because the whole idea of OT is to have no-conflict merges and would have no idea where the conflicts are.

Re: Show HN: Operational transform for realtime collaborative editing in JS/Flow

#15

Post by tmail21 » Sat, Dec 31, 2016, 6:37 PM UTC

willyk wrote: post #7

tmail21 wrote: post #6

The basic problem with OT (and current "real-time" collaborative editing approaches) is that they can only achieve eventual consistency. While this sounds great, eventual consistency DOES NOT mean semantic consistency. This rules it out for many applications where semantic correctness is important. Even for simple text documents you can get eventually correct but semantically incorrect results. For example, consider…

Thanks for the thoughtful post. What do you see as the next best alternative approach to OT?

If one absolutely wants real-time collaborative editing then the only (long-term) solution I see is something like a deep learning solution that continuously semantically analyzes the merged state for semantic errors. In a particular problem domain this might be 5-10 years out. In the general case, this starts to approach the level of difficulty of AGI and hence who knows when that'll happen :)

Some practical solutions are that the document starts out in a 'real-time collaborative editing' phase. After this phase is over, the document moves to a 'review' phase where the document is reviewed for semantic errors and those errors are fixed using a 'non-real-time' approach.

The only way I see at this time to avoid silent semantic errors in the first place are non-real-time approaches.

The best practices here are optimistic locking/leasing of "semantically-connected regions" (could be defined as a paragraph, document, multi-docset, worksheet, slide etc.) along with semantically useful diffs (diffs that are meaningful for an end user) for conflicts.

You could say that this is the approach taken by version control systems like git, where the semantically-connected region is the File/Document.

Semantically useful diffs for anything other than text documents is a non-trivial problem in itself. But is still more tractable than avoiding or detecting silent semantic errors with OT.

Re: Show HN: Operational transform for realtime collaborative editing in JS/Flow

#16

Post by theaustinseven » Sat, Dec 31, 2016, 9:04 PM UTC

tmail21 wrote: post #13

theaustinseven wrote: post #10

Earlier quoted context omitted.

I would expect that if an editor makes a change, their change should be preserved. There is no general case where you can decide which edit to keep, because in some cases(like the one you presented) people are editing the exact same sentence, but far more often people will not make edits to the same small part at the same time(at least in the real world). This makes OT very practical since generally the eventual cons…

It is fairly trivial to construct an example where editors are editing _different_ sentences and OT takes two locally semantically correct states and converges to a semantically incorrect (but grammatically correct) state. I think OT and other "real-time" collaborative editors are practical if you are willing to (or your use case can) live with "silent semantic errors". The greater the document "interconnectivity" (e…

Yeah, I guess I see what you are trying to say. I just want to clarify when I say predictable, I mean that given a set of operations. No matter the order they come in, the results will be the same. This makes OT powerful in that everyone just needs the operations eventually in order to have a consistent document. The only middle ground that I could see that would allow predictability in the document, and help mitigate these silent errors would be to notify users of when they have both edited the same range before consistency was reached. This would catch "almost" any case that I think you are talking about, although would of course miss the situations in which semantic errors arise due to errors in very different parts of the document(e.g. referencing a figure 2.1, while someone changes that figure to 2.2), but these errors can still easily arise with a single editor, and so are not really unique to OT. I do think that it would be nice to have a solution to that problem though...