Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

An Interactive Intro to CRDTs (2023)

jakelazaroff.com

Post reply on HN
Print view View original

31–36 of 36 posts

Re: An Interactive Intro to CRDTs (2023)

#31

Post by GermanJablo »

aguacaterojo wrote: post #11

I've spent a lot of time studying CRDTs & order theory in the last year & will publish an article too. Local-first apps are not easy to build, complex data structures (say, calendar repetitions with exceptions) become harder to model. Everything must converge automatically while clients can branch off. In general, you don't really get to compact tombstones meaningfully without consensus so you really are pushing at l…

The tombstone problem is exactly why I built DocNode. You're right that you can't compact them without consensus, so DocNode just doesn't create them. It assumes a server decides the order, which is already the case in 99% of collaborative apps. The result: a doc stays the same size whether it was edited once or a thousand times. Yjs for the same doc grows every time someone types, pastes, or undoes. Check it out: https://docukit.dev

Re: An Interactive Intro to CRDTs (2023)

#32

Post by fellowniusmonk »

josephg wrote: post #26
fellowniusmonk wrote: post #24

Earlier quoted context omitted.

Thank you for your work. Diamond Types is probably my favorite piece of programming, transliterating the algo for line edits for a situation where I needed a a different algo for the line management itself, is probably the most rewarding deep dive on a algorithm I've ever done.

I’m glad you enjoyed it! What did you build?

Effectively a distributed ~OS that hands off between browser and cloud using websocket presence.

So its like the human facing side of an OS where time, space (structure) and minds are all the only first class types and any apps exist as apptributes on the data itself.

It's basically a document editor, cal, feed, chat app, etc. in one interface where temporal search and retrieve is built in.

Re: An Interactive Intro to CRDTs (2023)

#33

Post by laalshaitaan »

The "central server is usually right" framing holds until you hit cases where ordering matters and latency is non-negotiable. We ran into this building conversation stores for AI agents where concurrent turns need to converge without a strict lock - last-write-wins breaks fast when two agents update shared state mid-session. Hybrid approach: OT for the ordered log, CRDT-style semantics for ephemeral state. Not elegant but it works.

Re: An Interactive Intro to CRDTs (2023)

#34

Post by josephg »

lifty wrote: post #29
josephg wrote: post #28

Earlier quoted context omitted.

Interesting! Do you mind explaining the idea in more detail?

As far as I understand, libraries like Automerge use the Merkle DAG to encode a document as an immutable bundle of state changes aka operation log + the causal ordering which enables conflict free merging between multiple peers. The final document is reconstructed by combining the state transitions. So the Merkle DAG is both the state and the causal relationship between mutations which allows the merge "magic". Proll…

Those are lovely data structures and I know about them. But how are you planning on using those data structures? What CRDT are you building?

You might also be interested in Alex Good's Beelay algorithm: https://www.youtube.com/watch?v=neRuBAPAsE0

Re: An Interactive Intro to CRDTs (2023)

#35

Post by lifty »

josephg wrote: post #34
lifty wrote: post #29

Earlier quoted context omitted.

As far as I understand, libraries like Automerge use the Merkle DAG to encode a document as an immutable bundle of state changes aka operation log + the causal ordering which enables conflict free merging between multiple peers. The final document is reconstructed by combining the state transitions. So the Merkle DAG is both the state and the causal relationship between mutations which allows the merge "magic". Proll…

Those are lovely data structures and I know about them. But how are you planning on using those data structures? What CRDT are you building? You might also be interested in Alex Good's Beelay algorithm: https://www.youtube.com/watch?v=neRuBAPAsE0

Prolly trees can act as CRDTs if you have a merge function that always merges and doesn’t block.

So my initial comment merely tried to make the point that there is a design space where you’re not stuck with the tradeoff of carrying the full Merkle DAG history just to be able to reconstruct the latest version of your document.

Thanks for the video, will check it out!

Re: An Interactive Intro to CRDTs (2023)

#36

Post by [deleted] »

josephg wrote: post #26
fellowniusmonk wrote: post #24

Earlier quoted context omitted.

Thank you for your work. Diamond Types is probably my favorite piece of programming, transliterating the algo for line edits for a situation where I needed a a different algo for the line management itself, is probably the most rewarding deep dive on a algorithm I've ever done.

I’m glad you enjoyed it! What did you build?

[deleted]
Post reply on HN