What are you working on these days?
I’m all over the place at the moment, but one topic keeps standing out – working on CRDTs. If you don’t know this crazy arsed geek acronym, it stands for Conflict-free Replicated Data Types, and it’s a means to enable eventually consistent data replication – “sync” in a word, or the “lots of sync” that comes with interactive collaboration. CRDTs evolved out of the world of Google Docs (and examples before that, but everyone seems to know of Google Docs) that provides a way for multiple people to interactively collaborate on a document, seeing what each other was typing at the same time. My first experiences with anything like this date back to SubEthaEdit (which is still out there and available), and a browser-based thing called EtherPad, used extensively in the early, early days of OpenStack conferences.
A few of years ago, a friend asked for a bit of help with a programming project that sent me down the rabbit hole of “Okay, how does this stuff actually work?”. While doing that research, I found the article by Alexei Baboulevitch (from march 2018) Data Laced with History: Causal Trees & Operational CRDTs. It’s a brutally dense article, but goes into depth that I hadn’t seen earlier. After reading it (and re-reading it, multiple times) some of it sunk in. Alexei even made source code available (written in Swift 4). At the time, the code my friend was working in was C++, so I helped port some of those concepts into a C++ implementation. (Yes, I was an absolute glutton for punishment).
Since then, I found several places that I wanted to use the same techniques, but there wasn’t much in terms of Swift native libraries available, and surprisingly little conversation about it. More recently, the topic has popped up on a couple of places – Objc.io did a series introducing the basic concepts on Swift Talk #294: CRDTs – Introduction (a really well done introduction). And I found thread on the Swift Forums about that was (more or less) talking about proposals for standard types that might fit into the Swift standard library. I’d also be remiss if I didn’t point out the walk-through article Replicating Types with Swift at AppDecentral, which has great code examples on GitHub as well.
Most of the “interesting” heavy lifting in advancing the state of the art was primarily being done in the browser space (aka Javascript first), which is pretty heavily dominated by two really good projects: Automerge and Yjs. Around 2021 both started tackling ports of the core algorithms into the Rust language, prodded a bit by I think by the post 5000x faster CRDTs: An Adventure in Optimization, who makes some really compelling points.
I did find some swift-native CRDT implementations – but what had been done wasn’t as deep as I’d like, and didn’t support features that I wanted to use. One of them (bluk/CRDT) was close, but constrained such that you had to pass the entire history of the data structure in order to make it work effectively. I’d learned enough that I could make a variant that did what I was after, so I created my own CRDT library (heckj/CRDT). The most meaningful difference is that my version was a delta-CRDT. That’s a fancy way of saying “You don’t need to send the entire history of a data structure, only the “recent bits since you last looked” in order to sync things up. It’s darned useful optimization given how CRDTs trade off memory for the ability to be eventually consistent. So if you don’t have to transfer the “whole history”, it’s a win.
In truth, I did the “easy parts” version – enough to have something out there that I could use and build on. But there’s several areas where my current implementation is weak. Martin Kleppmann has a great set of slides and a video explaining the intricacies on these weak areas called CRDTs: The Hard Parts. If you’re in to implementation details, I recommend watching that video. Martin’s a good speaker, and a prolific researching in the CRDT space. Oh – and he’s fairly deeply involved in one of those Javascript libraries I mentioned earlier: Automerge. The TLDR of that talk are that “just having eventually consistent data” can still end up with a seriously shitty user experience. (He says it more politely). There’s some things you can do to solve for that better user experience – so that the end result is not only “eventually consistent” (a baseline requirement for CRDTs), but is also more in line with “what a user expects”. Unsurprisingly, these additions come with a bit of complexity.
I looked at implementing that complexity in my heckj/CRDT library, and so far I’ve held off. Instead, I went and looked at getting involved in potentially using either Automerge or Yjs in Swift through the lens of those Rust language rewrite efforts. And that’s where I’m at currently – helping out and collaborating a bit with Aidar Nugmanoff, who’s establishing the Swift language bindings over the Yrs (the Rust-based rewrite of Yjs by Bartosz Sypytkowski). That effort, by the way, was the source for my recently popular article: Creating an XCFramework.
If you’re interested in the algorithms, Bartosz has a whole series of blog posts that beautifully outline how Yrs tackles their implementation of the CRDT algorithm “YATA”. I seriously thought about implementing the YATA algorithms (which I liked a bit better than RGA from an academic perspective) in my CRDT library, and I might still do so down the road.
Both Automerge and Yjs have very well established communities around them, so it seemed like a bigger win to be able end up with something that was cross-platform AND cross-language compatible. So for now, Aidar is doing the heavy lifting for a Swift front-end to Y-CRDT, and I’m helping out. The extended Y-CRDT dev team (which cover quite a variety of languages: Python, Ruby, Rust, Javascript, WASM, etc) is fun to collaborate with, and has been very welcoming. For my part, I’d love to have an end-result that works both in iOS and macOS and is binary-compatible with existing platforms, and I’m learning a lot along the way.
Automerge had earlier swift bindings, but they were awkward as all get out to use. (I contributed documentation to that effort a while back.) I think they took that as “lessons learned” and put that feedback into their own Rust-port/rewrite effort. Automerge just released their 2.0 – which I suspect solidifies their Rust implementation to the point they could re-create new Swift language bindings, at least I’m hoping that’s the case.
If you want to see what Aidar and I are up to (its definitely a work-in-progress right now), the Y-CRDT swift language bindings work is being done as open-source work at https://github.com/y-crdt/y-uniffi. Right now everything is in a single repository, but that’ll need to expand out a bit in order to effectively support the layers of Swift packages that we’re planning. We’ll have one layer which is the Rust side of this exposed through the Mozilla supported tooling UniFFI, and another which is all in Swift providing the Swift idiomatic interfaces. In the meantime, I’m getting a deeper-than-anticipated introduction to the Rust language.
For now, I’m helping the Y-CRDT project rather than re-implementing the bits on my own. It feels like there’s more of a win that way. Last year, about this time, I was fiddling with a library that was a ghetto-simple version of what Apple released as the (amazing) Swift Charts. To be honest, I wouldn’t be entirely surprised if Apple again published something like a CRDT library – at least for their own platforms. They’re clearly already using the technology in some of their apps: Notes at first, and I’d almost be willing to bet it’s being used in the “Collaborate with…” stuff that was released for the Pages, Keynote, and Numbers last year.
Circling back to my own library
There is more work that I’d like to do within heckj/CRDT, even outside of the complex lifting to support really effective user experiences in collaborative string editing (let alone collaborate editing of attributed strings). So for now, I’m also getting the benefit of seeing how other folks are building atop core CRDT libraries, and getting more familiar with the considerations and choices that brings.
There’s some interesting “quirks” to using CRDTs that any low-level library expects you to manage: the algorithms can provide “unexpected” results if you don’t correctly identify different instances that are collaborating. Without the correct identity assertion above it, the CRDT algorithm is unable to achieve the “consistent” part of eventually consistent. In academic terms, most CRDT algorithms are very susceptible to “byzantine attacks”, although that term seems an unfair label to the ancient empire.
For the use case of “syncing between my own iPhone, mac, and iPad” – you need to come up with a means to uniquely identify where you’re syncing from for the corner case where you make different, conflicting changes on different devices that are disconnected from each other and then later, sync them up. The algorithms frequently use a technique such as “last-write-wins”, but if you have two change histories that report that they’re the exact same instance, there’s no easy way to get a consistent end-result.
There’s a use case that Automerge (and Martin) focus on called Local-first, one part of which is entirely skipping the whole “hosted service middleman” thing. That leads to either peer-to-peer interactive sessions to collaborate, or transferring files that maintain their own history – so you can sync up any time down the road, and it’s still ultimately consistent. There’s a whole encoding scheme that Martin Kleppmann pioneered that compresses the history-overhead data so that a document that has “1MB” of text in it doesn’t end up with a “20MB” file representing that data and all its changes. That’s one of the topics he talks about in his CRDT: The Hard Parts presentation. That’s not something I’ve enabled in my own library, but it’s an obvious addition I’d like to make.
The other use case is real-time collaborative editing – whether that’s editing text or something else. The whole idea of authenticated edits and allowing collaborators, or not, is not something that the raw, underlying CRDT libraries really support. I want to look a bit more in depth as to potential ways of tackling that, and supporting “inviting someone to collaborate”. There’s also a whole space of “what does this library look like as idiomatic swift” and “how composable is it” – both of which I don’t have solid answers to.
Getting back into doing work with CRDTs was inspired by Distributed Actors in Swift, released last year, and which looks like a super-interest substrate to support sync, collaboration, and more. The examples from last year’s WWDC (Tic Tac Fish) included a a Bonjour-based actor implementation as well as a WebSocket example – and it’s all just been stewing in my rear brain since.
Rhonabwy 