Roadmap to Automerge 1.0

[ept]

Hi all! I wanted to give an update and invite discussion on our plans to ship a 1.0 version of Automerge. The performance branch has been a work in progress for about a year and a half, and I owe you all some news about getting it merged and released!

The performance branch and data format evolution

Despite its name, the performance branch is not only about improving performance, but also about updating the data formats to something that we can support long-term. One of the key parts of this has been a binary encoding format for changes and documents (#253), which is orders of magnitude more compact than the JSON data format used by the currently released version of Automerge. This binary format is now pretty stable: I made a few more tweaks to it in #296, but beyond that I do not expect further changes.

The binary data format is the primary reason why this work has been happening on a topic branch rather than main. Since this data format is used by collaborators to exchange their edits, and different collaborators may be running different versions of the software, it's important that it is forward and backward compatible. We have been storing up all the breaking data format changes on the performance branch so that when it is released, we only need to perform a one-time migration from JSON to the binary format, and thereafter have no more migrations for hopefully a very long time, if ever. That means getting the fundamentals of the format right before releasing it.

The binary format is carefully designed to be extensible while maintaining compatibility, and so it will allow seamless collaboration across different versions of Automerge. That means we can add features to future versions of Automerge without breaking compatibility. If you are collaborating with users running different app versions, including different versions of Automerge, they will still be able to interoperate.

The plan is to ship this binary format in Automerge 1.0. Now that the format is pretty stable, the time has come to discuss the steps towards getting it released.

What's changing and what's remaining the same

The fundamentals of Automerge will remain unchanged in 1.0:

• The API will remain largely unchanged, except for some tweaks that are detailed in the changelog and below. Automerge will continue to have a JSON data model plus extensions (e.g. relational tables, text, date objects), and Automerge.change() will continue working as-is.
• The fundamental model remains the same: users can edit offline and sync with other collaborators when online again; sync can happen via a server, a peer-to-peer protocol, or any other communication channel. Automerge itself remains just a data structure, with storage and networking provided by associated libraries.
• Unlike other CRDT libraries, Automerge continues to remember the full editing history of a document, unless you explicitly choose to discard history. The binary format allows us to keep all this history at very low cost (see Preview: Automerge binary data format #253). This enables things like powerful undo and revert features, visualising change history, allowing one user to suggest changes that can be accepted or rejected by another user, and more.
• Automerge continues to consist of a frontend and backend, which can run on different threads. The frontend is lightweight and can run on a UI thread, while the backend containing the CRDT logic (which is sometimes expensive) can be on a background thread where it doesn't interfere with UI responsiveness. In future we may even have multiple frontends presenting different views onto a single shared backend, to save memory. However, this threading stuff is optional; it's also fine to do everything on a single thread.

The biggest changes are:

• The compact binary format, as discussed above. We will provide a migration tool to convert any existing Automerge documents to the new format.
• Much improved performance. More on this below.
• Multi-language support! The Rust port of Automerge is closely tracking the performance branch, and we have detailed tests to check interoperability between the JS and Rust implementations. The Rust code compiles to WebAssembly (an almost-drop-in replacement for the JavaScript implementation, providing much better performance) and also to native code that can be used through a C API/FFI (allowing portability e.g. to iOS and Android without requiring a JS runtime). There is already a Swift wrapper for the Rust backend, and eventually I hope we will have wrappers for all mainstream languages and platforms, which will all be able to interoperate. Rust is an ideal language to provide this level of portability.
• Change history is secured through chaining cryptographic hashes, like a Git commit history or a blockchain (except that we use SHA-256 rather than Git's insecure SHA-1). When two users are syncing their changes, if they have the same hashes, then they are guaranteed to be in the same state. This is a much stronger guarantee than algorithms based on vector clocks can provide, where it is possible that two users believe they are in sync, when in fact their states are inconsistent (see discussion in Automerge 1.0 sync protocol #290).
• The undo/redo feature is temporarily removed. Not because it's not important, but to cut scope and help us ship 1.0 sooner. The existing implementation is a hack, and rather than continue supporting that hack, I would rather remove the feature for now, and bring it back in better form in the future. Since we're remembering editing history anyway, we have the freedom to implement arbitrary undo algorithms in the future, even across editing sessions (i.e. you can restart your app, and then undo changes you made before the restart).
• Network protocols for syncing Automerge need to be updated to handle hash chaining (see Automerge 1.0 sync protocol #290). This mostly affects implementers of those network protocols; applications using Automerge can remain largely unchanged.

The Rust and JS implementations

The current JavaScript implementation of Automerge is quite slow and memory-hungry (including the one on the performance branch, despite the name).
The Rust implementation compiled to WebAssembly is a huge improvement; I don't have figures right now, but I expect that switching to wasm will be a good way forward for people who have run into performance problems with the current Automerge. (Update: Orion has posted some benchmark figures comparing the JS and wasm implementations.)

The wasm version is a drop-in replacement on Node.js, and almost a drop-in replacement in web browsers. The only issue is that loading wasm modules on the web is asynchronous (it returns a promise), and so the initialization of Automerge needs to be made async. This will require a small code change for applications. Apart from that, the API remains the same.

For now, our plan is to maintain both the JS and Rust implementations side-by-side as equal partners, and to see how they work out in the wild. If it turns out that Rust+wasm is superior in every way, we may eventually deprecate the JS implementation and move the JS API to be a wrapper around a wasm core. But before doing that we will have to see how they compare in terms of performance, memory use, compatibility, tooling, etc.

On the JS side, I have also been working on performance improvements through new internal data structures for Automerge. This effort is orthogonal to the Rust implementation: in the Rust port, @orionz has been focussing on profiling and optimizing the existing data structures, whereas my experimental new data structures are a more radical rethink, building upon the new binary format. My hope is that, in the same way as the binary format has reduced the storage cost of Automerge documents by orders of magnitude, the new data structures will improve performance by orders of magnitude. In particular, saving and loading large documents to/from disk will become super fast. But the new data structures are not actually working yet! I think I'm getting close, but it's a quite complex research project.

If my new data structures work as well as I hope they will, we will port them over to Rust to gain the additional wasm speed boost. But if they don't work, I don't want this to hold up the release of Automerge 1.0. Hence publishing this roadmap, even though the new data structures remain a point of uncertainty.

What still needs to be done

Here are the main things that I think still need to be done before shipping 1.0:

• API for network sync that deals with hash chaining (Automerge 1.0 sync protocol #290), and coordination with networking and storage libraries for Automerge to ensure it works for everyone.
• Data migration tool to convert existing JSON Automerge documents into the new binary format (Binary format data migration tool #298).
• Complete interoperability between JS and Rust implementations (this is almost done; the main thing missing on the Rust side is full-document compression).
• Detailed specification and documentation of the Automerge data format. This will be an open specification, free for anybody to implement if they can't use the JS or Rust implementation for whatever reason (Specification of binary data format #297).
• Fuzz testing (testing consistency with large numbers of pseudorandomly generated inputs). Even though we already have a solid suite of unit tests with near-complete coverage, this would further help ensure that Automerge is highly reliable (Fuzz testing #299).
• Further performance improvements (hopefully including my new data structures, if I can get them working). Keeping this vague for now, but I have high hopes.

That list is not terribly long — it feels like 1.0 is finally moving within reach! Feedback welcome on any things you think should be added or removed from that list.

In terms of timescale, I expect that we will be shipping at least a release candidate for 1.0 within the first quarter of 2021. Assuming no major issues are found, a definitive release should follow shortly afterwards.

Thank you to all the people who have contributed and are still contributing to this effort! Especially big thanks to @orionz and @alexjg for the excellent Rust implementation, @lightsprint09 for the Swift wrapper, @HerbCaudill and @pvh for Automerge-related libraries and feedback, and many other contributors and community members!

[echarles]

Thx all contributors to this huge effort.

We are tracking for the Jupyter RTC initiative the branches with a wasm javascript client (generated from rust) and a python server (also generated from script). It looks like we are happy with having rust the single source of truth and generating binding in various languages (javascript, python...).

Looking forward to get this merged with as many features as possible. I would say that you could target a Automerge 1.0alpha0 even without all performance improvement. I guess having aligned repository with the master branches is for now the best improvement we could think to.

[alexjg]

This is fantastic, we're so close!

One thing I've been thinking a lot about is interoperability. I think having a formal specification will be an enormous step forward for this but I wonder if it would also be worth having automated compliance tests. This has worked well for other standardisation efforts (e.g the Acid test). I would normally suggest that this could be done after the 1.0 release but here it might actually be convenient to do it as part of the fuzz testing task. If we write the fuzz tests in an implementation independent manner then they can function as compliance tests.

[ept]

I would say that you could target a Automerge 1.0alpha0 even without all performance improvement.

Yes, I think we can do that. But I do think we will want at least #290, #298 and full Rust-JS interop for a first alpha release, otherwise those will be the first things that people get stuck with.

One thing I've been thinking a lot about is interoperability.

Yes, this is very important. I made a start with some JS-wasm interop tests in 3fef7e2 but more are needed. The fuzzer should be able to run against both the JS and the wasm backend, so that should help. The process of writing the format spec will probably also suggest test cases.

[skokenes]

Exciting!

As someone who has an implementation of a network protocol for Automerge, my question is how soon can I access something to test the hash chaining changes? Is that available in the performance branch already, or should I watch #290 ?

[ept]

@skokenes The hash chaining is already implemented on the performance branch and baked into the binary encoding for changes and documents. If you want to see the hashes, you can use decodeChange() to decode a binary change to JSON. However, the API for syncing hash graphs is not yet available; see #290 for that.

[ept]

Okay, I said in January that I hoped to ship a 1.0 preview release in the first quarter of 2021 — which hasn't quite happened, as it's now May. However, we've now completed all the blockers for the preview release and so I'm going to close this issue.

There are still a few things to do before we can ship a stable 1.0 release, which are mentioned above on this issue, and which we are tracking in the 1.0 milestone. In particular, we need a data conversion tool from the old to the new data format, we need more and better documentation, and of course we need to find any bugs that are found.

[hyemmie]

Hello @ept . I understand that this implementation is already deprecated, but I have a question. You mentioned that the undo & redo feature is a hack. Could you clarify what specific aspects you believe are lacking? Are you referring to the limitation that users can only undo their own actions?