Comment by jitl | Hacker News Reader

Comment by jitl | Hacker News Reader

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 / jake@makenotion.com

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

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?

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.

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

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

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…

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

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, like what happens if I use backspace to join a block of CRDT B into block of CRDT A.

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.

always great hearing your perspective on the notion text engine jake, thanks for taking the time to explain everything!

Reply on news.ycombinator.com