It's been an intense couple of weeks, but we're coming out of it with more clarity than ever on the future direction of Memo. We're entering a new phase of the project where we distill the research of the last few months into a usable form. Thanks for your patience with the radio silence the last couple of weeks.
Our previous vision for Memo was to store the full operational history for the repository in a global database, so that each file's full history would be available in a single structure dating back to its creation. This would essentially duplicate the role of Git as a content tracker for the repository, but with a much more fine-grained resolution. It may eventually make sense to build a global operation index to enable advanced features and analysis, but I don't think it makes sense to conceive of such an index as an independent version control system. For async collaboration, CRDTs probably won't offer enough advantages to induce people to switch away from Git. Even if we managed to build such a system, it would always need to interoperate with Git. So we may as well embrace that reality and build on top of Git. We can then focus on the area where CRDTs have their greatest strength: real-time collaboration and recording the fine-grained edits that occur between Git commits.
Augmenting Git is definitely something I've considered in the past, but it's finally becoming clearer how we can achieve it. We will start by packaging the previous months' work into a library that is similar to teletype-crdt. With Teletype, you work with individual buffers. Each local edit returns one or more operations to apply on remote replicas, and applying remote operations returns a diff that describes the impact of those operations on the local replica. Memo will expand the scope of this abstraction from individual buffers to the working tree, but it won't represent the full state of this tree in the form of operations. Instead, we'll exploit the fact that Git commits provide a common synchronization point. The library will expect any data that's committed to the Git repository to be supplied separately from the operations.
By making the CRDT representation sparse and leaning on Git to synchronize the bulk of the working tree, we reduce the memory footprint of the CRDT to the point where it can reasonably be kept resident in memory. This also bounds the bandwidth required to replicate the full structure, which obviates the need for complex partial data fetching schemes that we were considering previously. This in turn greatly simplifies backend infrastructure. Because a sparse representation should always be small enough to fully reconstruct from raw operations on the client, server side infrastructure shouldn't need to process operations in any way other than simply storing them based on the identifier of the patch to which they apply.
One big obstacle to making this patch-based representation work is undo. In teletype-crdt, we implement undo by associating every operation with a counter. If an operation's undo counter is odd, we consider the operation to be undone and therefore invisible. If the operation's undo counter is even, we consider the operation to be visible. If two users undo or redo the same operation concurrently, they'll both assign its undo count to the same number, which preserves both users' intentions of undoing the operation and avoids their actions doubling up or cancelling each other out, which could occur in some other schemes. However, implementing undo in this way comes with a cost, which is that in order for me to undo an operation that is present in my local history, I need to rely on that operation being present in the history of all of my collaborators. This approach to undo combines poorly with resetting to an empty CRDT on each commit, because it forces everyone to clear their undo stack after committing since there won't be any way to refer to prior operations in order to update their undo counters.
This felt like a show-stopper to me until I had a conversation with @jeffrafter about his team's experience using teletype-crdt in Tiny. I don't have a perfect understanding of the details of their approach, but they essentially bypass Teletype's built-in undo system and maintain their own history on each client independently of the CRDT. When a user performs an undo, they simply apply its to the current CRDT and broadcast it as a new operation. When I asked about some of the more diabolical concurrency scenarios that the counters were designed to eliminate, Jeff simply replied that it's working for them in practice.
Inspired by their experience, I have a hunch that we can implement undo similarly in our library. For each buffer, we can maintain two CRDTs. One will serve as a local non-linear history that allows us to understand the effects of undoing operations that aren't the most recent change to the buffer. We'll perform undos against this local history first, then apply their affects to a CRDT that starts at the most recent commit. This will generate remote operations we know can be cleanly applied by all participants. The local history can be retained across several commits and even be stored locally. By fetching operations from previous commits, we could even construct such a history for clients that are new to the collaboration.
We need to be able to refer to files in a universal way, but with this hybrid approach, only new files are assigned identifiers by operations. This stumped us for a bit, until an obvious solution occurred to us. The set of paths in the base Git commit is the same for every replica, so we can sort these paths lexicographically and assign each an identifier based on its position in this fixed order. Internally, file identifiers are a Rust enum with two possible variants, Base, which wraps a u64, and New, which wraps a local timestamp generated on the replica that created the file.
By being agnostic to plumbing and building a library that operates purely in terms of operations and data, this software should be useful in a broader array of applications. We plan to distribute a WebAssembly version to enable collaboration in browser-based environments, along with a native executable that can talk to editors and synchronize our CRDT with an underlying file system like we originally envisioned. The operations can serve as a kind of common real-time collaboration protocol. As long as an application can send and receive operations and feed them into this library, it should be capable of real-time collaboration with other applications.
In light of these shifts in our thinking, I've updated the Memo README to reflect the current state of the world. Some details about the implementation have been dropped, but I plan to reintroduce them over time as our implementation stabilizes. At some point soon, it may make sense to again pull Memo out into its own repository that is separate from Xray. If that happens, I'll keep everyone posted here.