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

21–30 of 36 posts

Re: An Interactive Intro to CRDTs (2023)

#21

Post by josephg »

aguacaterojo wrote: post #17
josephg wrote: post #14

Earlier quoted context omitted.

> In general, you don't really get to compact tombstones meaningfully without consensus so you really are pushing at least remnants of the entire log around to each client indefinitely. This is often much less of a problem in practice than people think. Git repositories also grow without bound, but nobody seems to really notice or care. For diamond types (my library), I lz4 compress the text content itself within the…

The man himself. Yeah agreed you guys have solved it. It is more a misfired crud dev instinct for me that sees it as wasteful. Just a different paradigm and not big in practice. I've got eg-walker & Diamond Types in my reading/youtube backlog. Diamond Types went further down the backlog because of "wip" on the repo! I will look into Antimatter too.

> It is more a misfired crud dev instinct for me that sees it as wasteful.

You're not alone. Lots of people bring this up. And it can be a real problem for some applications, if they store ephemeral data (like mouse cursor positions) within the CRDT itself.

Re: An Interactive Intro to CRDTs (2023)

#22

Post by josephg »

rudi-c wrote: post #18
josephg wrote: post #14

Earlier quoted context omitted.

> In general, you don't really get to compact tombstones meaningfully without consensus so you really are pushing at least remnants of the entire log around to each client indefinitely. This is often much less of a problem in practice than people think. Git repositories also grow without bound, but nobody seems to really notice or care. For diamond types (my library), I lz4 compress the text content itself within the…

re: git repositories That's partly because repositories rarely need to be cloned in their entirety. As such, even when you need to do it and it's a couple hundreds mb taking a few minutes, it's tolerated. In situations where a document needs to be cold loaded often, the size of the document is felt more acutely. Figma has a notion of GC-ing tombstones. But the tombstones in questions aren't even something that get cr…

> even when you need to do it and it's a couple hundreds mb taking a few minutes, it's tolerated.

Well written CRDTs should grow slower than git repositories.

> In situations where a document needs to be cold loaded often, the size of the document is felt more acutely.

With eg-walker (and similar algorithms) you can usually just load and store the native document snapshot at the current point-in-time, and work with that. And by that I mean, just the actual json or text or whatever that the application is interacting with.

Many current apps will first download an entire automerge document (with full history), then using the automerge API to fetch the data. Instead, using eg-walker and similar approaches, you can just download 2 things:

- Current state (eg a single string for a text file, or raw JSON for other kinds of data) alongside the current version

- History. This can be as detailed & go as far back as you want. If you download the full history (with data), you can reconstruct the document at any point in time. If you only download the metadata, you can't go back in time. But you can merge changes. You need history to merge changes. But you only need access to history metadata, and only as far back as the fork point with what you're merging.

If you're working online (eg figma), you can just download history lazily.

For client/server editing, in most cases you don't need any history at all. You can just fetch the current document snapshot (eg a text or json object). And users can start editing immediately. It only gets fancy when you try to merge concurrent changes. But thats quite rare in practice.

Re: An Interactive Intro to CRDTs (2023)

#23

Post by rudi-c »

josephg wrote: post #22
rudi-c wrote: post #18

Earlier quoted context omitted.

re: git repositories That's partly because repositories rarely need to be cloned in their entirety. As such, even when you need to do it and it's a couple hundreds mb taking a few minutes, it's tolerated. In situations where a document needs to be cold loaded often, the size of the document is felt more acutely. Figma has a notion of GC-ing tombstones. But the tombstones in questions aren't even something that get cr…

> even when you need to do it and it's a couple hundreds mb taking a few minutes, it's tolerated. Well written CRDTs should grow slower than git repositories. > In situations where a document needs to be cold loaded often, the size of the document is felt more acutely. With eg-walker (and similar algorithms) you can usually just load and store the native document snapshot at the current point-in-time, and work with t…

> If you're working online (eg figma), you can just download history lazily.

You can download the history lazily, that's a special case of incrementally loading the document.

If the history is only history, then sure. But I was understanding that we were talking about something that may need to be referenced but can eventually be GCed (e.g. tombstones-style). Then lazy loading makes user operations that need to reference that data go from synchronous operations to asynchronous operations. This is a massive jump in complexity. Incrementally loading data is not the hard part. The hard part is how product features need to be built on the assumption that the data is incrementally loaded.

Something that not all collaborative apps will care about, but Figma certainly did, is the concept that the client may go offline with unsynced changes for an indefinite amount of time. So the tombstones may need to be referenced by new-looking old changes, which increases the likelihood of hitting "almost-never" edge cases by quite a bit.

Re: An Interactive Intro to CRDTs (2023)

#24

Post by fellowniusmonk »

josephg wrote: post #22
rudi-c wrote: post #18

Earlier quoted context omitted.

re: git repositories That's partly because repositories rarely need to be cloned in their entirety. As such, even when you need to do it and it's a couple hundreds mb taking a few minutes, it's tolerated. In situations where a document needs to be cold loaded often, the size of the document is felt more acutely. Figma has a notion of GC-ing tombstones. But the tombstones in questions aren't even something that get cr…

> even when you need to do it and it's a couple hundreds mb taking a few minutes, it's tolerated. Well written CRDTs should grow slower than git repositories. > In situations where a document needs to be cold loaded often, the size of the document is felt more acutely. With eg-walker (and similar algorithms) you can usually just load and store the native document snapshot at the current point-in-time, and work with t…

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.

Re: An Interactive Intro to CRDTs (2023)

#25

Post by lifty »

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…

Regarding the growing log in CRDTs, it doesn't have to be that way. Most of these popular CRDT libs use Merkle DAG only to build up the log of the changes. But there is a better way, you can combine a Merkle DAG for ordering + prolly trees for storing the actual state of the data. That gives you total ordering, an easy way to prune old data when you choose to, and an easy way to sync. Look into fireproof for how this is combined.

Regarding distributed schemas, I agree, there's a lot of complexity there but it's worth looking into projects like https://www.inkandswitch.com/cambria/ and https://github.com/grafana/thema, which try to solve the problem. It's a young space though. If anyone else knows about similar projects or efforts, please let me know. Very interested in the space.

Re: An Interactive Intro to CRDTs (2023)

#26

Post by josephg »

fellowniusmonk wrote: post #24
josephg wrote: post #22

Earlier quoted context omitted.

> even when you need to do it and it's a couple hundreds mb taking a few minutes, it's tolerated. Well written CRDTs should grow slower than git repositories. > In situations where a document needs to be cold loaded often, the size of the document is felt more acutely. With eg-walker (and similar algorithms) you can usually just load and store the native document snapshot at the current point-in-time, and work with t…

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?

Re: An Interactive Intro to CRDTs (2023)

#27

Post by josephg »

rudi-c wrote: post #23
josephg wrote: post #22

Earlier quoted context omitted.

> even when you need to do it and it's a couple hundreds mb taking a few minutes, it's tolerated. Well written CRDTs should grow slower than git repositories. > In situations where a document needs to be cold loaded often, the size of the document is felt more acutely. With eg-walker (and similar algorithms) you can usually just load and store the native document snapshot at the current point-in-time, and work with t…

> If you're working online (eg figma), you can just download history lazily. You can download the history lazily, that's a special case of incrementally loading the document. If the history is only history, then sure. But I was understanding that we were talking about something that may need to be referenced but can eventually be GCed (e.g. tombstones-style). Then lazy loading makes user operations that need to refer…

> But I was understanding that we were talking about something that may need to be referenced but can eventually be GCed (e.g. tombstones-style)

Yeah my point is that this is only a limitation of certain types of CRDTs. Automerge and Yjs both suffer from this.

However, it’s not a requirement for anything built on egwalker. Or generally any CRDTs in the pure operation log style. Egwalker (and by extension, loro and diamond types) can generate and broadcast edits synchronously. Even without any history loaded.

Re: An Interactive Intro to CRDTs (2023)

#28

Post by josephg »

lifty wrote: post #25
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…

Regarding the growing log in CRDTs, it doesn't have to be that way. Most of these popular CRDT libs use Merkle DAG only to build up the log of the changes. But there is a better way, you can combine a Merkle DAG for ordering + prolly trees for storing the actual state of the data. That gives you total ordering, an easy way to prune old data when you choose to, and an easy way to sync. Look into fireproof for how this…

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

Re: An Interactive Intro to CRDTs (2023)

#29

Post by lifty »

josephg wrote: post #28
lifty wrote: post #25

Earlier quoted context omitted.

Regarding the growing log in CRDTs, it doesn't have to be that way. Most of these popular CRDT libs use Merkle DAG only to build up the log of the changes. But there is a better way, you can combine a Merkle DAG for ordering + prolly trees for storing the actual state of the data. That gives you total ordering, an easy way to prune old data when you choose to, and an easy way to sync. Look into fireproof for how this…

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".

Prolly trees allow you to store history independent data which is trivial to sync, diff and merge, regardless of insert order, merge order or originating peer. A Merkle DAG layered on top of prolly trees (event reference prolly tree roots) gives you causality so that peers can agree on a common view of history. So it's very useful because you can check integrity and travel in time, but you can keep as much of it as you want, because it's not necessary for constructing the current state. Prolly trees give you the current state and the easy syncing, diff,merge. So you can truncate the history as needed for your use case.

For a production ready implementation of prolly trees you can check Dolt. For a combination of Merkle DAG (https://github.com/storacha/pail) and prolly trees you can check https://github.com/fireproof-storage/fireproof

Re: An Interactive Intro to CRDTs (2023)

#30

Post by davexunit »

anematode wrote: post #2

Enjoyed the article! As someone who's worked on bits of collaborative software (and is currently helping build one at work), I'd caution people from using CRDTs in general. A central server is the right tool for the job in most cases; there are certain things that are difficult to handle with CRDTs, like permissions and acquiring locks on objects. Edit: I had an excerpt here which I completely misread. Sorry.

Permissions can be handled with capability systems. Keyhive [0] is the furthest along on this. I've also made my own prototype [1] showing how certificate capabilities can be composed with CRDTs.

[0] https://www.inkandswitch.com/keyhive/notebook/

[1] https://spritely.institute/news/composing-capability-securit...

Post reply on HN