I’ve been trying to understand yjs and automerge and some other CRDTs lately. Over the last few days I’ve made my own little reference implementation of yjs and automerge, so I could understand how (algorithmically) they’re similar and different. I put both implementations in the same codebase (they only really differ by one function). And the whole thing is only a few hundred lines of code written like this. Its essentially an insertion sort, with a fancy comparator.
My implementation isn’t as as fast as yjs, and its missing lots of important features (like serialization, non-list types, a nice API, etc). And I’m never going to add those features - Kevin is a class act. I’m just pleased with this as a learning + reference tool for implementers. And it is correct - I ran a fuzzer all day simulating 3 peers concurrently inserting random edits and merging. The output matches the official yjs implementation perfectly at every step.
I’ll give a recorded talk in the next week or so about how it works, since there’s some diagrams and explanations which would really help explain what I’ve done here. But if anyone is interested in having a peek, the code + tests and conformance validations are all in this repository: