[HN Gopher] Collaborative text editing with Eg-Walker: Better, f...
___________________________________________________________________
Collaborative text editing with Eg-Walker: Better, faster, smaller
Author : czx111331
Score : 134 points
Date : 2024-09-27 12:53 UTC (10 hours ago)
(HTM) web link (arxiv.org)
(TXT) w3m dump (arxiv.org)
| matlin wrote:
| 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 the effectiveness of
| these algorithms library authors (see Yjs, DiamondTypes, etc)
| build stand-alone data structures (usually specialized search
| trees) that most databases already provide.
|
| Personally, I've been trying to adapt a Piece Table[1] to be
| collaborative and stored in Triplit[2] which runs on both client
| and server and already implements logical clocks but I might see
| how well I can adapt this algorithm instead!
|
| 1. https://en.wikipedia.org/wiki/Piece_table 2.
| https://github.com/aspen-cloud/triplit
| benjismith wrote:
| 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!
| josephg wrote:
| Good to hear it's still in use! That's very kind.
| riedel wrote:
| 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
| btown wrote:
| 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!
| josephg wrote:
| 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.
| 1attice wrote:
| s/e.g./EG/
| deathanatos wrote:
| s/e.g./Eg/, which is how the paper stylizes it?
| canadiantim wrote:
| Looks like amazing work, congrats!! Excited to see
| implementations in the wild, definitely would be keen to play
| around with.
| eclectic29 wrote:
| If Martin Kleppmann is the author I know this stuff will be worth
| watching out for.
| britannio wrote:
| 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.
| auggierose wrote:
| I find the formulation in the abstract slightly confusing. As
| far as I understand EG-Walker _is_ a CRDT, an operation-based
| one.
| josephg wrote:
| 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!
| judofyr wrote:
| 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".
| abdullahkhalids wrote:
| Do collaborative whiteboard like software use the same
| algorithms, or are there more suitable algorithms for picture
| collaborations?
___________________________________________________________________
(page generated 2024-09-27 23:00 UTC)