5 ms·

CRDTs are often talked about in the same breath as collaborative editing software, but they're useful for much more than that. They really are a theoretical mo

CRDTs are often talked about in the same breath as collaborative editing software, but they're useful for much more than that. They really are a theoretical model of how distributed, convergent, multi-master systems have to work. IE the DT in CRDT could be a whole datastore, not as just an individual document. (Wish I could remember who on HN alerted me to this. I had read the paper but didn't grok the full implications).

adamnemecek 4y ago
Probably something by Martin Kleppmann?
jdvh 4y ago
We're using a single end-to-end encrypted document tree synced with CRDTs for our collaborative task IDE[1]. All data for a team is a single tree (graph really, if you count transclusions) and its kind of magical how simple everything gets when you know all state will sync in a deterministic way between all clients. It doesn't matter whether you drag&drop some object or add a new user, or rename something. It all reduces to a handful of CRDT operations. (We have a central server and the app works offline so the algorithm from the linked article doesn't apply in our case.) [1] https://thymer.com https://thymer.com
- jitl 4y ago
  Are you using Yjs? How are you thinking about scale-up for teams with 100s - 1000s of users?
  - jdvh 4y ago
    We've looked at Yjs but ultimately decided to write our own thing from scratch. Even scale-ups with thousands of users will have people working on different parts of the document tree in practice. The client doesn't need to receive every keystroke for people editing somewhere far away in the document tree. Those updates can be sent in batches every once in a while. If 10.000 people decide to edit the exact same location in a document then performance will degrade. The client will start to lag behind if it can't keep up with the stream of updates (cpu or internet bottleneck) but eventually it will process everything and all clients will end up with the same state. We have two channels. One for state updates (soft real-time) and one for UI hints ("hard" real-time) and other user actions that aren't CRDT mutations.
    - baran1 4y ago
      How did you got end to end encryption working with CRDTs?
newhouseb 4y ago
You might be thinking of this [1] paper? The core idea being if your problem space lends itself to monotonicity (see the paper for a more precise definition than I can give), then you can build a globally consistent database (around a CRDT) where the end-user doesn't need to concern themselves with inconsistent states while consistency is reached. [1] https://arxiv.org/pdf/1901.01930.pdf https://arxiv.org/pdf/1901.01930.pdf
- LAC-Tech 4y ago
  I wasn't clear - by "the paper" I meant the original CRDT paper. I read it, thought I understood it on some level, but had not drawn the dots between the theory and real world problems. Regardless, thanks very much for linking the paper! Right up my alley.
  - sitkack 4y ago
    Marc Shapiro and Nuno Preguiça created CRDTs in 2007. https://pages.lip6.fr/Marc.Shapiro/pubs.html#CRDTs https://pages.lip6.fr/Marc.Shapiro/pubs.html#CRDTs The original paper would be https://hal.inria.fr/inria-00177693/ https://hal.inria.fr/inria-00177693/

adamnemecek 4y ago

Probably something by Martin Kleppmann?

jdvh 4y ago

We're using a single end-to-end encrypted document tree synced with CRDTs for our collaborative task IDE[1]. All data for a team is a single tree (graph really, if you count transclusions) and its kind of magical how simple everything gets when you know all state will sync in a deterministic way between all clients. It doesn't matter whether you drag&drop some object or add a new user, or rename something. It all reduces to a handful of CRDT operations. (We have a central server and the app works offline so the algorithm from the linked article doesn't apply in our case.) [1] https://thymer.com https://thymer.com

jitl 4y ago
Are you using Yjs? How are you thinking about scale-up for teams with 100s - 1000s of users?
- jdvh 4y ago
  We've looked at Yjs but ultimately decided to write our own thing from scratch. Even scale-ups with thousands of users will have people working on different parts of the document tree in practice. The client doesn't need to receive every keystroke for people editing somewhere far away in the document tree. Those updates can be sent in batches every once in a while. If 10.000 people decide to edit the exact same location in a document then performance will degrade. The client will start to lag behind if it can't keep up with the stream of updates (cpu or internet bottleneck) but eventually it will process everything and all clients will end up with the same state. We have two channels. One for state updates (soft real-time) and one for UI hints ("hard" real-time) and other user actions that aren't CRDT mutations.
  - baran1 4y ago
    How did you got end to end encryption working with CRDTs?

newhouseb 4y ago

You might be thinking of this [1] paper? The core idea being if your problem space lends itself to monotonicity (see the paper for a more precise definition than I can give), then you can build a globally consistent database (around a CRDT) where the end-user doesn't need to concern themselves with inconsistent states while consistency is reached. [1] https://arxiv.org/pdf/1901.01930.pdf https://arxiv.org/pdf/1901.01930.pdf

LAC-Tech 4y ago
I wasn't clear - by "the paper" I meant the original CRDT paper. I read it, thought I understood it on some level, but had not drawn the dots between the theory and real world problems. Regardless, thanks very much for linking the paper! Right up my alley.
- sitkack 4y ago
  Marc Shapiro and Nuno Preguiça created CRDTs in 2007. https://pages.lip6.fr/Marc.Shapiro/pubs.html#CRDTs https://pages.lip6.fr/Marc.Shapiro/pubs.html#CRDTs The original paper would be https://hal.inria.fr/inria-00177693/ https://hal.inria.fr/inria-00177693/