Live data from Hacker News

Collaborative text editing with Eg-Walker: Better, faster, smaller

arxiv.org

11–20 of 32 posts

Re: Collaborative text editing with Eg-Walker: Better, faster, smaller

#11
post #2

Seph (author) also has a reference implementation in Typescript: https://github.com/josephg/eg-walker-reference I've stated before that I think the main thing holding back collaborative text / sequence CRDTs is integration with a production database. Eg-walker looks interesting because it might lend itself to be integrated into a database because the operations are immutable and only appended. However, to demonstrate…

There was a recent thread about the 2001 post that afaik eventually lead to this paper (diamond types is the rust implementation): https://news.ycombinator.com/item?id=41372833

Re: Collaborative text editing with Eg-Walker: Better, faster, smaller

#12
post #2

Seph (author) also has a reference implementation in Typescript: https://github.com/josephg/eg-walker-reference I've stated before that I think the main thing holding back collaborative text / sequence CRDTs is integration with a production database. Eg-walker looks interesting because it might lend itself to be integrated into a database because the operations are immutable and only appended. However, to demonstrate…

This seems to be a holy grail, to be honest! Super-simple database representations with barely any processing required on the "write path," instant startup, minimal memory requirements on both server and client without a need for CRDT data structures to be in memory, none of the O(n^2) complexity of OT. In fact, if I'm interpreting it correctly, it should be straightforward to get this working in a serverless environment without any notion of session fixation, nor active documents needing to be kept in memory.

I can see this completely reshaping the landscape of what's possible with collaborative documents!

Re: Collaborative text editing with Eg-Walker: Better, faster, smaller

#13

Joseph explains the algorithm on YouTube too: https://www.youtube.com/watch?v=rjbEG7COj7o It's great work, combining the best of OT and CRDTs.

I find the formulation in the abstract slightly confusing. As far as I understand EG-Walker is a CRDT, an operation-based one.

Author here. It’s kinda both a crdt and an operational transform system.

It’s a crdt in that all peers share & replicate the set of all editing events. (A grow-only set crdt if we’re being precise). Peers can use those editing events to generate the document state at any point in time, merge changes and so on.

But the editing events themselves are stored and expressed in their “original” form (unlike existing CRDTs, which need a prepare function). That means lower memory usage during use.

The replying / merging process itself is kind of a batch operational transform algorithm. It works by building a normal crdt state object in memory in order to transform the events so they can be replayed. In that sense, it’s an OT system. (But one which transforms by using a crdt, like Yjs, internally within each peer).

I don’t know if that clarifies things. Feel free to ask more questions!

Re: Collaborative text editing with Eg-Walker: Better, faster, smaller

#14
post #12
post #2

Seph (author) also has a reference implementation in Typescript: https://github.com/josephg/eg-walker-reference I've stated before that I think the main thing holding back collaborative text / sequence CRDTs is integration with a production database. Eg-walker looks interesting because it might lend itself to be integrated into a database because the operations are immutable and only appended. However, to demonstrate…

This seems to be a holy grail, to be honest! Super-simple database representations with barely any processing required on the "write path," instant startup, minimal memory requirements on both server and client without a need for CRDT data structures to be in memory, none of the O(n^2) complexity of OT. In fact, if I'm interpreting it correctly, it should be straightforward to get this working in a serverless environ…

Author here. Thanks! Yeah this is my hope too.

Egwalker has one other advantage here: the data format will be stable and consistent. With CRDTs, every different crdt algorithm (Yjs, automerge/rga, fugue, etc) actually stores different fields on disk. So if someone figure out a new way to make text editing work better, we need to rip up our file formats and network protocols.

Egwalker just stores the editing events in their original form. (Eg insert “a” at position 100). It uses a crdt implementation in memory to merge concurrent changes (and everyone needs to use the same crdt algorithm for convergence). But the network protocol and file format is stable no matter what algorithm you use.

Re: Collaborative text editing with Eg-Walker: Better, faster, smaller

#15
post #2

Seph (author) also has a reference implementation in Typescript: https://github.com/josephg/eg-walker-reference I've stated before that I think the main thing holding back collaborative text / sequence CRDTs is integration with a production database. Eg-walker looks interesting because it might lend itself to be integrated into a database because the operations are immutable and only appended. However, to demonstrate…

Awesome, I'm been following Seph's work for many years! Always thoughtful and well-executed. Probably the most prolific and insightful engineer in the "collaborative text editing" universe. I use ShareDB every day, which originated from Seph's excellent work on OT algorithms. Good stuff!

Good to hear it’s still in use! That’s very kind.

Re: Collaborative text editing with Eg-Walker: Better, faster, smaller

#16
post #13

Earlier quoted context omitted.

I find the formulation in the abstract slightly confusing. As far as I understand EG-Walker is a CRDT, an operation-based one.

Author here. It’s kinda both a crdt and an operational transform system. It’s a crdt in that all peers share & replicate the set of all editing events. (A grow-only set crdt if we’re being precise). Peers can use those editing events to generate the document state at any point in time, merge changes and so on. But the editing events themselves are stored and expressed in their “original” form (unlike existing CRDTs,…

Let me see if I understand this correctly:

CRDTs take an editor event such as "insert at position X" and turns it into something a concrete operation like "insert to the right of node Y created by client C" which is then sent. This makes it super easy to apply concurrent operations since they have a direct reference to where they're located. However, it also means that you know have to keep track of these nodes. All of the nodes that has ever existed is present at all times, and deletion is handled as a state flag which marks it as hidden.

OTs take an editor event such as "insert at position X" and keeps it like that. Whenever a concurrent event is received it then tries to "rebase" it (i.e. patch that event) so that it makes sense on top of the current events. However, this (1) can be quite finicky to get right and (2) it is based on there being One True Order of Events (i.e. a server).

This approach takes an editor event such as "insert at position X" and keeps it like that. When applied, it can be inserted into an "ever-growing list of atoms with state flag". However, in this algorithm the data structure is actually capable of representing two different versions at the same time: A current version and a final version. This is handled by there being two state flags instead of one: Every node has a "current state = exists/deleted" and "final state = exists/deleted".

This gives us the power of doing a "soft undo" (which is called "retreat" in the paper): We can take our own latest event which we've applied, revert the effect on the current version, while still keeping the final version the same. We're handling this very similar to CRDTs: We keep all the nodes at all time, we're just using state flags to keep track of whether it exists or not.

This is useful when we observe a concurrent event. This event have references to positions which are valid in the context of its parent. If we "retreat" of all of our events until we reach the parent, we then have a data structure which represents the text at that point. We can now apply the "insert at position Y"-events which we received by interpreting "Y" in terms of the current version. After we've applied all of those events we can then look at the final version and this now actually contains the combined result of both changes!

And here comes the nice part: Since the events themselves are always on the form "insert at position X" it means that we can choose another representation of applying them. For instance, if we know that there are no concurrent events that are happening, we might as well apply them directly on a string without bothering with the whole "current/final dual data structure".

Re: Collaborative text editing with Eg-Walker: Better, faster, smaller

#17
post #16
post #13

Earlier quoted context omitted.

Author here. It’s kinda both a crdt and an operational transform system. It’s a crdt in that all peers share & replicate the set of all editing events. (A grow-only set crdt if we’re being precise). Peers can use those editing events to generate the document state at any point in time, merge changes and so on. But the editing events themselves are stored and expressed in their “original” form (unlike existing CRDTs,…

Let me see if I understand this correctly: CRDTs take an editor event such as "insert at position X" and turns it into something a concrete operation like "insert to the right of node Y created by client C" which is then sent. This makes it super easy to apply concurrent operations since they have a direct reference to where they're located. However, it also means that you know have to keep track of these nodes. All…

First paragraph: yes, exactly.

> OTs take an event..

This is how the early Jupiter OT works, yes. And most OT systems work like this. But there are also some papers on more recent OT systems which can work with more than 2 peers. Unfortunately, many of these systems have turned out to have convergence bugs and/or they are O(n^2). For our paper one of our example datasets takes tens of milliseconds to replay with CRDTs and egwalker but an hour of time with OT!

> the data structure is capable of representing two different versions…

With egwalker it’s important to distinguish between two different data structures. There’s a grow only set of original editing events. This is persisted to disk and replicated over the network. Then while actually replaying events or merging, we generate a second, temporary, in memory data structure which resembles a normal CRDT. (Except with an extra state field on each item like you said). This crdt state object isn’t persisted. It’s usually discarded as soon as the merge (transform) operation is complete. One big advantage of this approach is that this data structure does not need to represent all items ever inserted. Just the concurrent items, back to the most recent common branch. So it’s usually tiny. And that allows history to be pruned - which CRDTs typically don’t allow.

But yes, everything else is right!

Re: Collaborative text editing with Eg-Walker: Better, faster, smaller

#18

Do collaborative whiteboard like software use the same algorithms, or are there more suitable algorithms for picture collaborations?

There’s usually more suitable algorithms for picture collaborations.

Text is hard because it’s a list of characters, and when items are inserted and deleted the operations change the index of all subsequent elements.

Usually, editing a digital whiteboard is much simpler.

Re: Collaborative text editing with Eg-Walker: Better, faster, smaller

#19
post #17
post #16

Earlier quoted context omitted.

Let me see if I understand this correctly: CRDTs take an editor event such as "insert at position X" and turns it into something a concrete operation like "insert to the right of node Y created by client C" which is then sent. This makes it super easy to apply concurrent operations since they have a direct reference to where they're located. However, it also means that you know have to keep track of these nodes. All…

First paragraph: yes, exactly. > OTs take an event.. This is how the early Jupiter OT works, yes. And most OT systems work like this. But there are also some papers on more recent OT systems which can work with more than 2 peers. Unfortunately, many of these systems have turned out to have convergence bugs and/or they are O(n^2). For our paper one of our example datasets takes tens of milliseconds to replay with CRDT…

This is probably a question about classic CRDTs as much as eg-walker:

Do all possible topological sorts of the event graph result in the same final consensus document? If yes how do we know that, and if no, how do they resolve the order in which each branch is applied?

Re: Collaborative text editing with Eg-Walker: Better, faster, smaller

#20
Saw the YouTube video when it was first posted, and it could be a great match for a new project I have in mind.

Is there a practical implementation yet that supports not just strings, but also lists and maps?

Would be great to see it integrated into yjs / y-crdt.

Post reply on HN