Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

You don't need a CRDT to build a collaborative experience

zknill.io

Post reply on HN
Print view View original

41–50 of 70 posts

Re: You don't need a CRDT to build a collaborative experience

#41

Post by zknill »

lmm wrote: post #37

> You can’t inspect your model represented by the CRDT without using the CRDT library to decode the blob, and you can’t just store the underlying model state because the CRDT needs its change history also. You’re left with an opaque blob of data in your database. You can’t join on it, you can’t search it, you can’t do much without building extra features around that state blob. So use the CRDT library when building y…

> So use the CRDT library when building your indices?

Yeah, sure, you can build a secondary index over the data. But you're still having to decode the blob and index it. There's no version where you can index the data without using the library to expose the underlying model state (like you could if you weren't using a CRDT).

On locking, yes, it's hard. But it's not the same kind of locking that you'd expect in other parts of a system. You're locking the UI, not the actual data, so it's a tiny bit more forgiving. In general the locks aren't trying to force consistency, instead they are trying to prompt the humans to reduce the chance of conflict happening in the first place. Ofc, you still have to care about the locking, unlocking, disconnection problems, etc.

Here's a decent example/demo you can play around with in multiple windows:

https://examples.ably.dev/component-locking?space=W0V-t5oY6A...

https://ably.com/spaces

Re: You don't need a CRDT to build a collaborative experience

#42

Post by jay-aye-see-key »

josephg wrote: post #32
lewisjoe wrote: post #12

> everyone’s gonna say “but hey, google docs uses operational transform not CRDTs”.. OK yes, but you are not google. Well, google docs works not because they somehow figured out how to converge OT edits with as much precision as CRDTs do, but simply because they have a central server which orders edits anyway and don't need true leader-less convergence. In fact, I agree not many things don't need a CRDT. CRDTs help w…

Yeah. Text based OT is pretty simple to implement, too. It’s about 200 lines of code, plus a simple network protocol. It’s fast and relatively straightforward to code up, and unlike text CRDTs it’s pretty fast by default. I use it as my standard test when trying out a new programming language. It was unexpectedly ugly in go because of go’s lack of enums & unions, and that’s one of the big reasons I never got in to pr…

Operational transforms are one of those interesting technologies I’ve wanted to learn by implementing but haven’t made the time yet. I also didn’t realise it could be implemented in that little code.

Can you recommend any learning resources for implementing an OT? (Ideally typescript, python, or rust)

Re: You don't need a CRDT to build a collaborative experience

#44

Post by zknill »

aboodman wrote: post #40

It's true that a CRDT is often not the right thing for a classic client/server application. But this doesn't mean we should just give up on ux and use locking. There are approaches to multiplayer that are client/server native. By leveraging the authoritative server they can offer features that CRDTs can't, while preserving the great ux. I'm partial to server reconciliation: https://www.gabrielgambetta.com/client-side…

> But this doesn't mean we should just give up on ux

It's a little unfair to describe locking as "[giving] up on UX", especially given some well known collaboration products use it quite successfully; Google Sheets cell locking, Miro element/Text locking, etc.

Ofc, it's going to depend on the scope of what's being locked. These two examples are quite finely scoped element locks.

Re: You don't need a CRDT to build a collaborative experience

#45

Post by jahfer »

jay-aye-see-key wrote: post #42
josephg wrote: post #32

Earlier quoted context omitted.

Yeah. Text based OT is pretty simple to implement, too. It’s about 200 lines of code, plus a simple network protocol. It’s fast and relatively straightforward to code up, and unlike text CRDTs it’s pretty fast by default. I use it as my standard test when trying out a new programming language. It was unexpectedly ugly in go because of go’s lack of enums & unions, and that’s one of the big reasons I never got in to pr…

Operational transforms are one of those interesting technologies I’ve wanted to learn by implementing but haven’t made the time yet. I also didn’t realise it could be implemented in that little code. Can you recommend any learning resources for implementing an OT? (Ideally typescript, python, or rust)

I haven’t explored this space in a while, but I have a couple of examples that could be helpful. A Clojure library of mine [0] has a decent README with some background reading on how to use operational transform.

I also reimplemented it in a surprisingly tiny amount of OCaml [1] which was a fun way to learn that language :)

[0]: https://github.com/jahfer/othello [1]: https://github.com/jahfer/othello-ocaml

Re: You don't need a CRDT to build a collaborative experience

#46

Post by asib »

jitl wrote: post #19
zknill wrote: post #18

Earlier 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…

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

#47

Post by chromatin »

zknill wrote: post #31
chromatin wrote: post #29

We 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 resolut…

How do you handle getting the changes that one client makes onto the other clients? Are you pushing it from the server to the clients with websockets, or waiting for the clients to ask for new info, or waiting for the conflict to happen when someone else tries to make a change, or something else? I'm thinking a lot about keeping server and client data in sync while working on our hopefully-soon-to-be-released LiveSyn…

When the client gets HTTP 409 Conflict, it asks for the current version and presents to the user for manual resolution

Re: You don't need a CRDT to build a collaborative experience

#48

Post by dugmartin »

jay-aye-see-key wrote: post #42
josephg wrote: post #32

Earlier quoted context omitted.

Yeah. Text based OT is pretty simple to implement, too. It’s about 200 lines of code, plus a simple network protocol. It’s fast and relatively straightforward to code up, and unlike text CRDTs it’s pretty fast by default. I use it as my standard test when trying out a new programming language. It was unexpectedly ugly in go because of go’s lack of enums & unions, and that’s one of the big reasons I never got in to pr…

Operational transforms are one of those interesting technologies I’ve wanted to learn by implementing but haven’t made the time yet. I also didn’t realise it could be implemented in that little code. Can you recommend any learning resources for implementing an OT? (Ideally typescript, python, or rust)

This single file shows the entire set of OT transformations (retain, insert, delete):

https://github.com/Operational-Transformation/ot.js/blob/mas...

and this is a good post outlining the basics of OT, from the creator of CodeMirror:

https://marijnhaverbeke.nl/blog/collaborative-editing-cm.htm...

Re: You don't need a CRDT to build a collaborative experience

#49

Post by matlin »

I think the most important part of designing collaborative software, which this touches on a bit, is having a the right granularity and scope of a given change.

Last-writer-wins is only bad when the granularity of what you're editing is too big. E.g. if you're an editor like Figma and each element is a row in a database, a single row is too big. Instead you want attribute level granularity so two users can change the independent properties (like one color and the other size) without bulldozing each other.

The other key thing (that's also a common mistake) is to only consider realtime collaboration. In practice, there's always some delay (maybe just milliseconds but could be be hours or days) in how events propagate so solutions like locking don't work.

The reality is that any client-server system that needs to be highly interactive and robust to unreliable network conditions is undeniably a distributed system and therefore warrants using distributed system solutions like vector clocks, Lamport timestamps, CRDTs, etc.

Last thing is that I think many people only think of operation-based CRDTs when they think about CRDTs. You can (and we have at my company) created a fairly traditional feeling database that relies on a state-based CRDT solution that doesn't need to maintain a log of every operation that has every happened.

So yes, you might not need to reach for a fancy library like Yjs or Automerge, but it's worth understanding how these things thinks basically work because many of them are extremely simple and easy to grok - the complicated parts of Yjs and Automerge are the sophisticated data-structures and algorithms that are pretty much only needed for large document text editing.

Re: You don't need a CRDT to build a collaborative experience

#50

Post by lmm »

zknill wrote: post #41
lmm wrote: post #37

> You can’t inspect your model represented by the CRDT without using the CRDT library to decode the blob, and you can’t just store the underlying model state because the CRDT needs its change history also. You’re left with an opaque blob of data in your database. You can’t join on it, you can’t search it, you can’t do much without building extra features around that state blob. So use the CRDT library when building y…

> So use the CRDT library when building your indices? Yeah, sure, you can build a secondary index over the data. But you're still having to decode the blob and index it. There's no version where you can index the data without using the library to expose the underlying model state (like you could if you weren't using a CRDT). On locking, yes, it's hard. But it's not the same kind of locking that you'd expect in other…

> Yeah, sure, you can build a secondary index over the data. But you're still having to decode the blob and index it. There's no version where you can index the data without using the library to expose the underlying model state (like you could if you weren't using a CRDT).

How's that different from any other datastructure? You're never indexing the raw underlying bytes and you wouldn't want to. Like, sure, if you're using a datastore where indexing is built in then you need to make sure that your datastore understands the datastructures you're using, but that's always a problem that you have. Most of the CRDT infrastructure I've seen has been designed around having a datastore that understands the CRDT and building on top of that.

> On locking, yes, it's hard. But it's not the same kind of locking that you'd expect in other parts of a system. You're locking the UI, not the actual data, so it's a tiny bit more forgiving. In general the locks aren't trying to force consistency, instead they are trying to prompt the humans to reduce the chance of conflict happening in the first place.

I don't think that actually improves matters, it just means more edge cases? Either you have a locking system that's 100% consistent and people can lock each other out and deadlock, or you don't and you end up with lost updates that will be even more infuriating because the user checked whether anyone else was editing and it looked like they weren't.

Post reply on HN