News for hackers. Stuff that matters.
Re:You don't need a CRDT to build a collaborative experience by jitl on Thursday November 16, 2023 @12:08PM (#38292180)
I agree broadly with the article’s position but I think locks are more harmful than helpful. When I was a Quip user (2018) it was super frustrating to get locked out of a paragraph because someone’s cursor idled there. Instead just allow LWW overwrites. If users have contention and your sync & presence is fast, they’ll figure it out pretty quick, and at most lose 1-2 keystrokes, or one drag gesture, or one color pick.

Notion is “collaborative” and we don’t use a CRDT for text, it’s all last-write-wins decided by the server. However our LWW texts are individually small - one block/paragraph in size - and adding/moving/removing blocks is intention-preserving if not perfectly convergent.

As the article says, the downside for LWW is that “offline” / async collaboration isn’t so great. That’s why we’re working on switching to CRDT for our texts. If you’re interested in bringing CRDTs to a product with a lot of users, consider joining Notion’s Docs team - https://boards.greenhouse.io/notion/jobs/5602426003 / @jitl on Twitter / [email protected]

Re:You don't need a CRDT to build a collaborative experience by zknill on Thursday November 16, 2023 @12:37PM (#38292682)
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 - one block/paragraph in size

This is really important, because by reducing the size of the individual element that any single user is updating you can also reduce the chance of conflicts. With a small amount of contextual feedback (like the notion icon next to the block) a lot of the problem cases are just avoided.

Clearly locking and updating the entire document would be terrible, but if you can do it on a small enough scope that others can change other elements, it can work really well.

(If you've worked on the notion things you're describing then I'm sure you know this better than I do, but just spelling it out really clearly.)

Re:You don't need a CRDT to build a collaborative experience by jitl on Thursday November 16, 2023 @01:04PM (#38293078)
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 converge to the same state. Instead you need an authority (your server) to essentially pick an arbitrary order of ops and clients just have to deal with it.

A practical example is to consider three users (A, B, C) working on a document.

1. A, B, C start online working together.

2. C goes offline

3. A, B stay online, and make 100s of changes.

4. C makes a few changes while offline (not sent to other peers yet)

5. C comes back online and sends their changes to (the server / other peers).

In wall-clock LWW, C's changes will overwrite A & B's changes, even though A & B have done a lot more work.

In a causal ordering CRDT implementing LWW, C's changes will "lose" to A & B's changes, since they were actually made "earlier" in causal ordering.

> Clearly locking and updating the entire document would be terrible, but if you can do it on a small enough scope that others can change other elements, it can work really well.

I'm sure good UX is possible with locks, but I haven't used one yet for document editing. I'm still traumatized from Quip which did per-paragraph (per block?) locking and was really annoying. Eventually they added an unlock button next to the block so anyone could "steal" the lock at will due to all the user complaints, but at that point, why put it in at all?

Re:You don't need a CRDT to build a collaborative experience by maclockard on Thursday November 16, 2023 @02:54PM (#38294560)
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 by asib on Thursday November 16, 2023 @05:25PM (#38296490)
> ...based on causal order which is convergent, the C in CRDT...

Doesn't the C stand for conflict-free? I suppose both are kind of getting at the same idea though.

Re:You don't need a CRDT to build a collaborative experience by mweidner on Saturday November 18, 2023 @11:31AM (#38321276)
Early papers (e.g. https://inria.hal.science/inria-00555588) use C=Convergent for state-based CRDTs and C=Commutative for op-based CRDTs. Nowadays it is usually C=Conflict-free for all variants (e.g. https://en.wikipedia.org/wiki/CRDT).

You could add to the confusion by using C=Collaborative. (I personally prefer "collaborative data structures" for the more general concept of data structures that can be edited on multiple devices; CRDT is a mouthful and now also a buzzword.)

Re:You don't need a CRDT to build a collaborative experience by btown on Thursday November 16, 2023 @12:15PM (#38292299)
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!
Re:You don't need a CRDT to build a collaborative experience by jitl on Thursday November 16, 2023 @12:22PM (#38292439)
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.

API consumers are unaffected. Likely we’ll support API updates of text as best-effort diff-match-patch of the text on our side applied as CRDT ops.

Re:You don't need a CRDT to build a collaborative experience by npunt on Thursday November 16, 2023 @01:51PM (#38293685)
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 by Summerbud on Thursday November 16, 2023 @09:01PM (#38298360)
I feel the same in the paragraph. But in some situation it seems rational

Figma still limits you from editing the component if someone is on it. And Figjam did that too. In my mind, this is a good practice in the realm of collaborative design. Because it will be very messy if a single component obeys the last-write-win rule

Re:You don't need a CRDT to build a collaborative experience by ccorcos on Thursday November 16, 2023 @11:21PM (#38299534)
I agree!

If people clobber each others updates by typing at the same time in the same input, at least they can understand what happened.

That’s much better than not being able to do something because someone left their cursor on something and walked away…