I was wrong. CRDTs are the future - Seph / Joseph Gentle (26 Sept, 2020)
former Google Wave developer picks up on CRDTs
made a test based on automerge in Rust to benchmark (github)
I still wasn’t completely convinced by the speed argument, so I made a simple proof of concept CRDT implementation in Rust using a B-tree using ideas from automerge and benchmarked it. Its missing features (deleting characters, conflicts). But it can handle 6 million edits per second. (Each iteration does 2000 edits to an empty document by an alternating pair of users, and that takes 330µs. So, 6.06 million inserts / second). So that means we’ve made CRDTs good enough that the difference in speed between CRDTs and OT is smaller than the speed difference between Rust and Javascript.
All these improvements have been “coming soon” in automerge’s performance branch for a really long time now. But automerge isn’t the only decent CRDT out there. Y.js works well and kicks the pants off automerge’s current implementation in the Y.js benchmarks. Its missing some features I want, but its generally easier to fix an implementation than invent a new algorithm.
[snip]
I mourn all the work I’ve done on OT over the years. But OT is no longer fits into the vision I have for the future. CRDTs would let us remake Wave, but simpler and better. And they would let us write software that treats users as digital citizens, not a digital serfs. And that matters.
I should have pushed this much harder in-house. I think we could have been launched 2-3 years ago. The number of times I heard oh data can conflict so it’s impossible, we need total order serialization and linearization, etc. would drive anyone nuts. We live and learn though.
If only we knew the answers before we know the answers!
Speaking for myself there, you’ve made some great calls David and that’s why this project is getting there. You’ve done an amazing job. Thanks for showing us how.
Don’t be hard on yourself. You have implemented and are testing stuff (inside a frankly revolutionary framework) that really smart people who have worked on this specific problem for a decade and more are just coming around to. You’ve kept a vision, updated the tech as real world testing showed the limits of other approaches, and made the hard calls. No regrets, don’t look back.
Read the article. It often seems that these CRDT experts are quite aligned with the vision of Safe Network. Do they know that Safe Network project exists? Would they be willing to contribute? (If that is necessary / desired at this point.)
Yes some of them do, when we have more proof points then we will reach out to more of them. We are working on a critical datatype to hold network section membership and that needs to be byzantine fault-tolerant. We have 2 impls right now, both look to work, so a nice place.
The great thing here is we can fully test the data, no need for the network to exist. Then we test the messages and a huge part of the codebase is in a state we can be sure is correct. So simplifies testing as much as it simplifies the codebase. Intersting counter to crdt though is the link @JPL posted Workers Durable Objects Beta: A New Approach to Stateful Serverless I see their point, but not sure I agree with the conclusion. It feels like these durable objects maintain all state forever (like crdt with tombstones). It’s very intersting to see this progress though.
I shared the link to Maidsafe’s Github repository crdt_tree in the comments a few times and received some responses if anybody wants to join in the conversation.
A while back I encountered the following retrospective of an effort to use CRDT in xi (an editor with a backend written in Rust) for collaborative editing. I don’t know much about the subject, but it seems to me it could be an interesting read: https://github.com/xi-editor/xi-editor/issues/1187#issuecomment-491473599
