Making Eg-walker even faster

Eg-walker is a collaborative text editing algorithm first published in 2024. It totally shifted how we thought about what we initially assumed was an inherent tradeoff between the two dominant families of collaborative text editing algorithms: OT and CRDT.

OT is generally fast in the simple sequential merge case but can blow up when merging large numbers of concurrent operations (for example if someone goes offline, makes a bunch of edits, and comes back to the document).¹

CRDTs are generally fast to merge large numbers of concurrent operations but keep a ridiculous amount of metadata overhead (IDs for every character typed and tombstones for every character deleted) and are usually slow to load/open a saved document.

Eg-walker tries to combine the best of both worlds by constructing an event graph of plain index-based operations, applying sequential edits directly, and only building up CRDT-like state temporarily to merge concurrent ones.

In this blog post, I introduce eg-strider, a set of improvements on top of Eg-walker that result in significantly better performance on every measurable axis (merge time, reopen time, peak memory, memory at rest, and snapshot size).

The intuition behind Eg-walker

To talk about eg-strider though, we must first understand Eg-walker.

At a high level, we record an event graph of operations. Each operation is either an ins(idx, text) or a del(idx, len), where the index is relative to the document text as its author saw it. We group linear (non-branching) sections of consecutive operations into runs.

Looking at the event graph, we can pretty easily tell where history is linear and where it is concurrent.

The graph becomes non-linear when peers make edits to the document concurrently. Here, we mean the causal definition of concurrency, denoted $a\parallel b$, where it does not mean simultaneous, but rather that neither event knew about the other when it was made. In real life, this usually happens when a peer goes offline and continues making edits.

Linear case

One of Eg-walker’s key observations is that when history is linear, no merge needs to happen and we can simply apply it to the document as the indices of the operations are already relative to the correct document state. It is important that the linear case is cheap as this regime dominates in the vast majority of traces.

Concurrent case

In the concurrent merge case, we start from the end of the last linear run and track a list of records that describes every character inserted and deleted so far in the merge.

We look at these records through two views:

1. The effect view is the set containing every operation we’ve merged so far.
2. The prepare view is the set containing only the operations that the document was composed of as of the operation’s creation. This, for example, excludes any operations that were concurrent with it or happened after it.

Rebasing an operation can be thought of as transforming an operation’s prepare view index into its effect view index.

For each operation, the steps are as follows:

1. Move the prepare view to be accurate as of that operation. In paper terminology, we retreat (hide) events that aren’t in this view and advance (show) ones that are.
2. If the operation is:
   • an insert, we find the position at that operation’s prepare index and insert a new record. If a concurrent insert happened at the same position, we tie-break the insert index in the list of records using a deterministic rule (usually by the unique ID of the peer).
   • a delete, we mark the record at its prepare index as deleted. If a concurrent delete already removed it, there’s nothing left to delete and so the operation is a no-op.
3. We find the index of that record in the effect view and use that as the transformed index.

Applying this to all operations creates a ‘rebased’ list of operations. Note that this list is the only output retained as a result of the merge, and the records can be thrown away as soon as the merge reaches the next linear section. This means that the records and the views over them are purely ephemeral merge metadata that do not need to be kept in steady state.

Where the gains come from

You can’t make the computer faster. You can only make it do less work.

Joseph Gentle, 5000x faster CRDTs: An Adventure in Optimization

Now, equipped with a good understanding of Eg-walker, let’s turn to the main ideas eg-strider uses to improve upon it.

Faster text operations

In the linear case there’s nothing to merge, so applying the operations to the text is a large share of the merge time.

diamond-types applies every transformed operation to a rope. On every operation, the rope does a bunch of pointer-chasing from the top of its skip list to find the node holding a given index, copies the inserted text in twice (once into its write buffer, then into the rope), and shuffles text around inside a node to make room. This turns out to be redundant work when merging operations in bulk as we only care about the end result.

Instead, eg-strider builds the text with a reverse piece table with a finger. The intuition here is two-fold:

1. By traversing the operations in reverse order, we know exactly where each insert is going to end up in the final document or whether it gets deleted. Surviving text gets copied straight to its spot exactly once and deleted text is never copied at all.
2. Finding each piece for the index is relatively cheap if we start our search from the last piece we touched. Edits tend to land near each other which keeps the average search distance low.

On paper, the piece table seems like it would have significantly worse indexing performance (operating in $O(n)$ to locate a piece given the index instead of $O(\log n)$ to locate a node given the index).

The main win here is not in the asymptotic behavior but rather the pragmatic constant factors. The piece table is tiny. Each piece is 8 bytes, and across all of the traces they never take up more than about 50 KB which means all of the pieces fit in L1/L2 cache on most modern processors. A short linear walk over memory already in cache will almost always beat a logarithmic one that needs to chase pointers all over the heap!

Looking at the numbers, building the text using the reverse piece table is 2–7× faster than diamond-types’ rope on the same operations. It’s most noticeable in editing traces with a lot of churn (where only a small fraction of the characters typed end up in the final document).

Maximizing cheap work

As we know from above, the linear merge case is the cheap path as each operation just gets applied to the text directly. Eg-walker has a very conservative rule for what can go through the fast path and only assumes that linear sections qualify.

One important observation we exploit is that in most real editing traces, concurrent edits land in different parts of the document (people collaborating tend to avoid working on the same thing). These non-overlapping concurrent operations can actually use a much simpler merge algorithm: if an operation’s span doesn’t overlap with any span touched by the concurrent events, its index can just shift by the net change in document length of the concurrent operations before it.

We only fall back to the CRDT when an operation lands inside one of those textually conflicting spans or when the concurrent range is very large. As neither happens often, we get to take the cheap path for most concurrent edits too.

Making common work faster

Work that happens often in the hot path (like lookups) matters a surprising amount.

For example, in the fallback CRDT case, finding the record for an operation happens frequently because of retreating and advancing the prepare view. As such, records have two ways to index them:

• by position in a view
• by operation

diamond-types makes the second index a B-tree whose entries point at the same leaves. Since operations within a concurrent range are numbered consecutively, we can make it a flat array instead. This turns record lookup from $O(\log n)$ to $O(1)$. With this change, traces that fall back to the CRDT merge about 4–6× faster.

Saving work

Incremental planning

Before merging, Eg-walker needs to know which parts of the history conflict. diamond-types works this out on every merge by walking back through the graph to the last point where the graph was linear. On concurrent traces, this planning takes about half of its merge time.

eg-strider instead keeps the runs and their causality metadata up to date as events are appended. This costs a little extra work and memory on every append but shaves off a significant amount of time. With incremental planning, merging the concurrent traces is about 1.7–1.8× faster, and merging a single new edit (the common online edit case) is hundreds of times faster than planning from scratch each time.

Lazy document opening

Another speed trick is to make reopening a serialized document lazy. Most libraries (with the exception of Loro) put the whole event graph or operation log into the document and read all of it on open, which is very expensive. Instead, we can split the file into sections that are selectively unpacked as needed:

• header: which peers are in the document, the number of events and characters, the frontier of the event graph, where each part of the history starts in the file.
• text: the document text as of the frontier.
• history: the event graph and operations in parts cut where the history is linear (keeping concurrent regions whole), aiming for about 32k events in the newest part and doubling the target for each part before it.

This allows eg-strider to only read the header and text before being ready to apply an edit which makes reopening about 25× faster than reading the whole file.

Smaller structs and file compression

We save on memory by keeping our structs small and packing data as a struct of arrays rather than an array of structs. Each run of operations is represented with 16 bytes whereas diamond-types uses 64, and the event graph itself is a few arrays of 4-byte numbers rather than a 72-byte struct per run. This helps us fit more per cache line and avoids unnecessary struct padding (see What Every Programmer Should Know About Memory and Practical Data-Oriented Design). Together, this cuts the memory a document holds at steady state by more than half.

Finally, we make file sizes smaller by compressing the text and history sections of the document with zstd, where diamond-types only compresses the inserted text with LZ4. This makes our files about 3.7× smaller than they would be uncompressed, and about 1.3–4.1× smaller than diamond-types’ file format.

A note on measurement

The Eg-walker paper measures merge time as the time it takes to merge a set of operations that are already in the event graph. Since some of eg-strider’s wins come from moving bookkeeping work out of the merge and into appending, measuring only merge time would be slightly deceptive, so our merge times include appending the operations as well.

All measurements are the median of 100 runs, with each library cycling through all of the traces in turn so we aren’t accidentally measuring the CPU’s branch predictor overfitting a single trace.

Caveats & Conclusion

eg-strider is a research project. Like the Eg-walker paper, it assumes that replicas aren’t Byzantine and that every event is valid (following the Eg-walker paper’s C.1 definition), so it doesn’t check its input (and thus even a single invalid event can make it panic).

In practice, any real usage is bound to have buggy clients that look Byzantine and each library handles this to differing extents. Yjs, Loro and Automerge validate what they receive while diamond-types checks what it decodes but panics on out-of-range positions (like eg-strider). If we wanted to add this kind of fault tolerance, a natural home for these checks would be in a server sitting in front of eg-strider, much like how client-server OT algorithms validate operations centrally.²

That said, I still think these ideas are broadly portable to real-world implementations. My hope is that this blog post taught you something :)

Source is open and MIT licensed on GitHub.

Footnotes

1. Normally, people also argue that OT is hard to implement correctly. However, this is generally only true in the peer-to-peer case, where the transform functions need to satisfy both TP1 and TP2, and not in the centralized server case, which only needs TP1. ↩

2. A sketch of what this could look like: the server accepts or rejects every event and fixes one canonical order but unlike OT it never transforms operations for clients, as each client still runs Eg-walker itself. The server first checks structure: the replica comes from the authenticated session, sequence numbers are contiguous (so IDs can’t be forged), parents are events it already has in ascending order, etc. Accepted events are appended in arrival order and broadcast and a client whose event is rejected just resyncs from the server’s snapshot as in OT. ↩