7 ms·

Anything CRDT (conflict free replicated datatypes: https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type https://en.wikipedia.org/wiki/Conflict-free_

Anything CRDT (conflict free replicated datatypes: https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type https://en.wikipedia.org/wiki/Conflict-free_replicated_data_...) related is fun to read up on and play with. Papers and references (page maintained by central academic in the world of CRDTs): https://crdt.tech https://crdt.tech Group doing research into how they can be used to build interesting collaborative (and async) applications: https://www.inkandswitch.com https://www.inkandswitch.com A few of the major open source implementations - mostly for rich text editing or JSON like data structures: - Yjs: https://github.com/yjs/yjs https://github.com/yjs/yjs - Automerge: https://github.com/automerge/automerge https://github.com/automerge/automerge - Peritext: https://www.inkandswitch.com/peritext/ https://www.inkandswitch.com/peritext/ - Dimond types: https://github.com/josephg/diamond-types https://github.com/josephg/diamond-types People building eventually consistent database syncing with them: - https://electric-sql.com https://electric-sql.com (Postgres <-> SQLite) - https://vlcn.io https://vlcn.io (SQLite <-> SQLite) Open source colaborative servers (coordination, persistance, presence): - https://github.com/ueberdosis/hocuspocus https://github.com/ueberdosis/hocuspocus - https://github.com/partykit/partykit https://github.com/partykit/partykit - https://github.com/firesync-org/firesync https://github.com/firesync-org/firesync

josephg 3y ago
Diamond types author here. I’m working on another blog post - I had a big breakthrough getting collaborative text editing many times faster again using some new ideas. I’m in the process of writing up our new work now. And there’s another hard problem I’m stuck on: so, CRDTs like mine and Yjs use (random agent id, sequence number) as unique IDs for operations. But a troublesome user might reuse an operation ID, sending different operations to different peers and giving them the same (agent, seq) pair. This results in really awful, weird bugs. Martin Kleppman wrote a paper about BFT in CRDTs. His suggestion is we do what git does and use SHA hashes for IDs instead. But there’s two problems: 1. We don’t want to store a hash for every keystroke a user makes. That would get big, fast. We want a DAG of hashes like git, except a hash is generated with each keystroke. How do we build an efficient system that can query by hash, without storing all of the hashes? 2. I want users to be able to permanently delete inserted text. If I accidentally paste an AWS key into a document, I don’t want that key in the document history forever. How do I enable that while still getting all the benefits of the hashing system above? (Note if your hash includes the typed character, even if you delete the character itself from disk, you can trivially brute force the hash to recover any typed characters). Each of these problems in isolation has a solution. But the real prize is how do you solve both at the same time? I think this problem has a solution but I don’t think anyone has solved it yet. Want to name an algorithm and get my eternal respect? Here’s your chance.
- texuf 3y ago
  Troublesome user? As in a malicious user? Are you trying to lock down your attack surface against script kiddies or is there another instance where this situation comes up?
  - lcnPylGDnU4H9OF 3y ago
    It could mean that, as in "someone who causes trouble" or it could be a result of a bug which only affects a handful of users who suddenly "have some troubles".
  - KineticLensman 3y ago
    > or is there another instance where this situation comes up? Yes, if you are a Byzantine general trying to coordinate an attack, and you aren't sure of your peers' true allegiance.
  - josephg 3y ago
    Yes, a malicious user. I’ve also seen buggy software try to reuse IDs - which causes similar mayhem. It would be better if we could remove this entire class of problems.
- jsunderland323 3y ago
  Hi Joseph, This is a hard problem and something that I think has to be intrinsic to the serialization method of your CRDT. Unique IDs of any kind are really risky in CRDTs because they basically break the mathematical links between potential partitioned duplicates. Lists make this problem even harder because you have to contend with if you should incorporate the ordinal of each element into the hash value. I’m working on a version control system for visual programs. You wrote a response to someone on structured edits a few months back about how the UNIX fs not being schema/structure aware is the core problem with collaborative edits and destroys open interoperability. I think you hit the nail on the head. I’ve been working on something for nearly a year now to try to address that problem. Let me know if you want to compare notes.
  - 3y ago
beck5 3y ago
Thanks for mentioning FireSync, we haven't even offically launched yet! After 10+ years of building real time collabrative apps based on Operational Transformation (ShareLaTeX -> Overleaf.com) we have become quietly very excited about CRDT's and Yjs. Now we are focused on building a scalable Yjs compliant backend ontop of PG with FireSync. If anyone has thoughts about this space, feature requests, would like a preview of what we are building, or anything else, please do reach out direcly to me at henry@firesync.live, I'm talking to as many people as possible at the moment.
cromka 3y ago
Is this what Apple uses in Notes app for its recently added collaborative features? I read it here that the technology behind it is, in fact, quite robust, in order to provide the best possible conflict prevention and resolution.
chaxor 3y ago
I am interested in a concept close to a CRDT - but I think meaningfully different. Is there a 'data structure' or 'scheme/setup' which fits the below description? Have a repo (with a specific git commit hash), which is specifically constructed to reproducibly construct some data (database, dataset, set of examples files, etc) (which can then be checked by a checksum), such that when a different person pulls and executes that code, a decision could be made to either run the code again, or to pull it from the decentralized group of people that have that repo database. This is effectively "code as data" which is checked by a key value pairing: [git commit hash <==> data checksum hash]. So if you have a process that runs for 24 days on a good machine and produces a 30 MB file for people to use, they can check for reproducibilityif they want with the code, or just grab the file from everyone who pulled the repo to save time. Obviously having defaults for download or rerun could be determined by certain logic like execution time etc, but the base idea is something I've looked into for a while. Is there a name for this type of setup?
- killthebuddha 3y ago
  I'm very unsure that I understand your requirements, but if I squint really really hard it looks like you're asking for a blockchain.
  - chaxor 3y ago
    Hmmm... Perhaps that could be one component, but I don't know if proof of work in the typical way would be required? As in 'guessing' a hash (I don't know much about that area so I could be wrong here)., I don't think would be needed - but perhaps the proof of work could simply be 'calculate the output that you want to make anyway' - such as the weights of a neural network, a read only database to do complex queries on, an operating system compilation with specific configuration, a dataset of estimates of some physical science data using a particular algorithm, etc. So instead of using CPU cycles to do finance/currency things (or whatever is done in that arena), this would calculate whatever data you actually want directly. In some cases it could be a ton of calculation (estimating electron density functional, or training NN weights) to receive a small file (DFT functionals are quite small). Or it could be some calculation for a large amount of data (ETL for big we scraped data). One important aspect which is similar to the currency/Blockchain realm is that the commits would specify the data state, so the data would likely be mostly read-only for people, but if they change it, it would simply branch off to a different hash pair.

josephg 3y ago

Diamond types author here. I’m working on another blog post - I had a big breakthrough getting collaborative text editing many times faster again using some new ideas. I’m in the process of writing up our new work now. And there’s another hard problem I’m stuck on: so, CRDTs like mine and Yjs use (random agent id, sequence number) as unique IDs for operations. But a troublesome user might reuse an operation ID, sending different operations to different peers and giving them the same (agent, seq) pair. This results in really awful, weird bugs. Martin Kleppman wrote a paper about BFT in CRDTs. His suggestion is we do what git does and use SHA hashes for IDs instead. But there’s two problems: 1. We don’t want to store a hash for every keystroke a user makes. That would get big, fast. We want a DAG of hashes like git, except a hash is generated with each keystroke. How do we build an efficient system that can query by hash, without storing all of the hashes? 2. I want users to be able to permanently delete inserted text. If I accidentally paste an AWS key into a document, I don’t want that key in the document history forever. How do I enable that while still getting all the benefits of the hashing system above? (Note if your hash includes the typed character, even if you delete the character itself from disk, you can trivially brute force the hash to recover any typed characters). Each of these problems in isolation has a solution. But the real prize is how do you solve both at the same time? I think this problem has a solution but I don’t think anyone has solved it yet. Want to name an algorithm and get my eternal respect? Here’s your chance.

texuf 3y ago
Troublesome user? As in a malicious user? Are you trying to lock down your attack surface against script kiddies or is there another instance where this situation comes up?
- lcnPylGDnU4H9OF 3y ago
  It could mean that, as in "someone who causes trouble" or it could be a result of a bug which only affects a handful of users who suddenly "have some troubles".
- KineticLensman 3y ago
  > or is there another instance where this situation comes up? Yes, if you are a Byzantine general trying to coordinate an attack, and you aren't sure of your peers' true allegiance.
- josephg 3y ago
  Yes, a malicious user. I’ve also seen buggy software try to reuse IDs - which causes similar mayhem. It would be better if we could remove this entire class of problems.
jsunderland323 3y ago
Hi Joseph, This is a hard problem and something that I think has to be intrinsic to the serialization method of your CRDT. Unique IDs of any kind are really risky in CRDTs because they basically break the mathematical links between potential partitioned duplicates. Lists make this problem even harder because you have to contend with if you should incorporate the ordinal of each element into the hash value. I’m working on a version control system for visual programs. You wrote a response to someone on structured edits a few months back about how the UNIX fs not being schema/structure aware is the core problem with collaborative edits and destroys open interoperability. I think you hit the nail on the head. I’ve been working on something for nearly a year now to try to address that problem. Let me know if you want to compare notes.
- 3y ago

beck5 3y ago

Thanks for mentioning FireSync, we haven't even offically launched yet! After 10+ years of building real time collabrative apps based on Operational Transformation (ShareLaTeX -> Overleaf.com) we have become quietly very excited about CRDT's and Yjs. Now we are focused on building a scalable Yjs compliant backend ontop of PG with FireSync. If anyone has thoughts about this space, feature requests, would like a preview of what we are building, or anything else, please do reach out direcly to me at henry@firesync.live, I'm talking to as many people as possible at the moment.

cromka 3y ago

Is this what Apple uses in Notes app for its recently added collaborative features? I read it here that the technology behind it is, in fact, quite robust, in order to provide the best possible conflict prevention and resolution.

chaxor 3y ago

I am interested in a concept close to a CRDT - but I think meaningfully different. Is there a 'data structure' or 'scheme/setup' which fits the below description? Have a repo (with a specific git commit hash), which is specifically constructed to reproducibly construct some data (database, dataset, set of examples files, etc) (which can then be checked by a checksum), such that when a different person pulls and executes that code, a decision could be made to either run the code again, or to pull it from the decentralized group of people that have that repo database. This is effectively "code as data" which is checked by a key value pairing: [git commit hash <==> data checksum hash]. So if you have a process that runs for 24 days on a good machine and produces a 30 MB file for people to use, they can check for reproducibilityif they want with the code, or just grab the file from everyone who pulled the repo to save time. Obviously having defaults for download or rerun could be determined by certain logic like execution time etc, but the base idea is something I've looked into for a while. Is there a name for this type of setup?

killthebuddha 3y ago
I'm very unsure that I understand your requirements, but if I squint really really hard it looks like you're asking for a blockchain.
- chaxor 3y ago
  Hmmm... Perhaps that could be one component, but I don't know if proof of work in the typical way would be required? As in 'guessing' a hash (I don't know much about that area so I could be wrong here)., I don't think would be needed - but perhaps the proof of work could simply be 'calculate the output that you want to make anyway' - such as the weights of a neural network, a read only database to do complex queries on, an operating system compilation with specific configuration, a dataset of estimates of some physical science data using a particular algorithm, etc. So instead of using CPU cycles to do finance/currency things (or whatever is done in that arena), this would calculate whatever data you actually want directly. In some cases it could be a ton of calculation (estimating electron density functional, or training NN weights) to receive a small file (DFT functionals are quite small). Or it could be some calculation for a large amount of data (ETL for big we scraped data). One important aspect which is similar to the currency/Blockchain realm is that the commits would specify the data state, so the data would likely be mostly read-only for people, but if they change it, it would simply branch off to a different hash pair.