Yjs in 200LOC: I made a tiny reference implementation

Hi everyone!

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:

3 Likes

Such a cool thing to do! Thanks for sharing these learning materials! Finally a small proper CRDT implementation. For sure, this is gonna be super useful to many people.

Looking forward to the talk!

1 Like

Sepsh talked about this in a recent webinar: https://braid.org/meeting-10 Definitely worth a listen if you want to have a better understanding of CRDTs / how Yjs works.