3 ms·

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

by zknill 3y ago

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

jitl 3y ago
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?
- maclockard 3y ago
  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.
- deleted 3y ago
  [deleted]
- asib 3y ago
  > ...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.
  - mweidner 3y ago
    Early papers (e.g. https://inria.hal.science/inria-00555588 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 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.)

by zknill 3y ago

jitl 3y ago

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?

maclockard 3y ago
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.
deleted 3y ago
[deleted]
asib 3y ago
> ...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.
- mweidner 3y ago
  Early papers (e.g. https://inria.hal.science/inria-00555588 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 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.)