Conflict-Free Replicated Data Type (CRDT) is a type of data structure that enables concurrent updates across multiple replicas without the need for coordination between them.
You don't need a CRDT to build a collaborative experience
21–30 of 70 posts
Re: You don't need a CRDT to build a collaborative experience
#22Earlier quoted context omitted.
Are you considering having a CRDT for each text block individually, or moving to a CRDT for the entire data model for a document? Really curious about the design approach here, especially insofar as there's now an external API that the data models need to service!
It’s Complicated (tm), a hybrid of the two. Text content across multiple CRDT enabled blocks may be connected in a single logical CRDT, but the segment visible in any given block is stored in that block object, which maintains our permission system invariants. We’ll still support moving blocks to different pages, so one page may have a few different CRDTs visually interleaved. All the edge cases are very interesting,…
always great hearing your perspective on the notion text engine jake, thanks for taking the time to explain everything!
Re: You don't need a CRDT to build a collaborative experience
#23CRDT is a different paradigm. Ideally we'd use it to replace client-server
Re: You don't need a CRDT to build a collaborative experience
#24For offline first apps, or for applications where very high degree of control for the content is needed (e.g. legal docs) and realtime collaboration isn't that valuable, there is also the option to use 3-way merge instead.
The benefit is that you can even allow the user to resolve conflicts in a satisfactory way.
Another benefit is that the document doesn't even have to be derived from the original, it could go through exports and re-imports and it will still be possible to run a 3-way merge as long as a common base version is declared. This can be especially covnenient for systems that involve e.g. MS Word.
Re: You don't need a CRDT to build a collaborative experience
#25That's not gonna work for real-world projects. Real-world apps often have larger edits than locking individual cells/cards e.g. Move columns or replace large chunks of spreadsheets in Google Sheets, or Ctrl-A to select all and then drag to move.
Also, if you consider latency, locking does not work well because client B might do operations before he/she even acknowledges the lock from client A because of latency.
Re: You don't need a CRDT to build a collaborative experience
#26> Ever-growing state: for CRDTs to work well they need to keep a record of both what exists, and what has been deleted (so that the deletes aren’t accidentally added back in later). This means that CRDT state will continually expand.
I guess a couple things:
It depends on the CRDT. Some CRDTs grow with the number of replicas and others with the number of events.
State-based CRDTs don't need to keep history and don't need causal ordering of messages, but internal bookkeeping grows with the number of replicas. And for large states (like sets and maps), it can be prohibitive to send the state all over the wire for an idempotent merge.
That's why in practice, people implement Op-based CRDTs, which makes the trade: in order to send small ops over the wire, we now need causal ordering of messages. To make sure we can sync with replicas long offline, we keep as much history so that they can catch up.
There are other variations, such as delta-state based CRDTs that send diffs, and merkle CRDTs, which use merkle data structures to calculate diffs and detect concurrency, which have different growth characteristics.
---
As for a growing state: Is this actually a concern for devs that aren't using CRDTs for collaborative text? I can see that being an issue with the amount of changes that can happen.
But outside of that, lots of data don't grow that fast. We all regularly use Git and it keeps a history of everything. Our disks are huge, and having an immutable record is great for lots of things (providing you can access it).
> Opaque state: ...you’re generally left with an opaque blob of binary encoded data.
Most CRDT libraries take a document-orientated angle. It assumes that you can contain the entire "unit of work", like a document, inside of a CRDT. However, if your data is more relational, it doesn't quite fit. And while there's immutable data in a CRDT, I do wish it was more accessible and queryable. In addition, being a binary blob, it's not exactly composable. I think CRDT libraries should be composable with each other.
Re: You don't need a CRDT to build a collaborative experience
#27CRDT is a different paradigm. Ideally we'd use it to replace client-server
I think we can. Following all the implications down the rabbit hole, you end up with a system architecture where there's no front-end, and there's no back-end.
Since CRDTs are still kinda new for most people, the discussion hasn't really gotten there yet.
Re: You don't need a CRDT to build a collaborative experience
#28Earlier quoted context omitted.
So Last-Write-Wins (LWW) basically _is_ a CRDT, but not in the sense that anyone really expects, because they aren't that useful or intention preserving. Especially if the two writes happen in very quick succession / concurrently. LWW becomes useful if you can: a) help humans to see who is doing what on a doc b) reduce the size of the change that is LWW As you've said: > However our LWW texts are individually small -…
You can have a LWW CRDT, but not every LWW is a CRDT. LWW CRDTs generally pick a winner based on causal order which is convergent , the C in CRDT, because every peer receiving the same ops in any order would pick the same winner. Picking a winner based on wall clock time order (as suggested in the article, and implemented by Notion) is not convergent; if peers used that algorithm to apply ops I they would not converg…
I understand what you are saying here in terms of the difference between using wall-clock or causal ordering to determine who 'wins' for LWW. However, both of these strategies seem convergent to me? In any case, all clients will agree on whose changes win.
1. With wall-clock decided by clients, A + B changes will win since C's wall-time is earlier (yes, C could lie, but still would converge).
2. With wall-clock decided by server C will win and everyone will agree.
3. With causal ordering, everyone will agree that A + B won.
2 is not a CRDT since it requires a central server, but I think 1 would still count? Or stated another way: I'm not sure the _convergence_ is what determines if these strategies are CRDTs or not, but rather whether or not this decision making is _distributed_ or not.
Re: You don't need a CRDT to build a collaborative experience
#29We took a super simple (IMO) approach to collaborative editing in my current project:
Each block of text has a version number which must be incremented by one by the client at the time of submission. The database provides conflict prevention by uniqueness constraint which bubbles up to the API code. The frontend is informed of conflict, so that the user can be notified and let the human being perform conflict resolution.
Because most concurrent users are working on different blocks, this works great.
Re: You don't need a CRDT to build a collaborative experience
#30Wrote about something similar a while ago https://hex.tech/blog/a-pragmatic-approach-to-live-collabora...
Using a server to tie break and locking has worked pretty well for us