[matlin]

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

[btown]

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]

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.

[vlovich123]

I’ve loved learning all your detailed info on CRDT work. Thank you for progressing the field!

Since it stores all the editing events, does this mean that the complexity of opening a document is at least O(N) in terms of number of edits? Or are there interim snapshots / merging / and/or intelligent range computations to reduce the number of edits that need to be processed?

[josephg]

You can just store a snapshot on disk (ie, the raw text) and load that directly. You only ever need to look at historical edits when merging concurrent changes into the local document state. (And thats pretty rare in practice).

Even when that happens, the algorithm only needs to look at operations as far back as the most recent "fork point" between the two branches in order to merge. (And we can compute that fork point in O(n) time - where n is the number of events that have happened since then). Its usually very very fast.

In an application like google docs or a wiki, the browser will usually never need to look at any historical changes at all in order to edit a document.

[vlovich123]

Very clever idea. Thanks for explaining

[benjismith]

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]

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

[riedel]

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