14 ms·

I’m a “true believer” in CRDTs, which I have some experience in. You can implement a useful CRDT for simple applications in under 100 lines if all you care abou

I’m a “true believer” in CRDTs, which I have some experience in. You can implement a useful CRDT for simple applications in under 100 lines if all you care about are standard database objects - like maps, sets and values. List CRDTs are where they get complicated, but most applications aren’t collaborative text editors. The promise of CRDTs is that unlike most conflict resolution systems, you can layer over a crdt library and basically ignore all the implantation details. Applications should (can) mostly ignore how a CRDT works when building up the stack. The biggest roadblock to their use is that they’re poorly understood. Well, that and implementation maturity. Automerge-rs merged a PR the other day which brought a 5 minute benchmark run down to 2 seconds. But by bit we’re getting there.

a_conservative 5y ago
Can you point to a good introduction to Conflict-free replicated data types (CRDT)? It's crossed my (short attention span) radar a couple times and seems interesting. I really love the idea about being able to use it, but also "forget" about it while developing. Does "leaky abstraction" apply here? If you constrain things enough, can a dev really use it and forget about the details?
jitl 5y ago
I work on a collaborative text editing system (https://www.notion.so https://www.notion.so) and read a lot about CRDTs, thank you for your work in this area, particularly https://josephg.com/blog/crdts-go-brrr/ https://josephg.com/blog/crdts-go-brrr/ I agree with your assessments here - CRDT is the way forward for most applications; no user wants to fiddle with a merge UI or picking versions like with iCloud. I think RxDB’s position here is from their CouchDB lineage. > The biggest roadblock to their use is that they’re poorly understood. Well, that and implementation maturity. I certainly have more understanding to do. My biggest open question is how to design my centralized server side storage system for CRDT data. To service writes from old clients I need to retain a total history of a document, but I don’t want to force new clients to download the entire history nor do I want these big histories in my cache, so I end up wanting a hot/cold system; and building that kind of thing and dealing with the edge cases seems like more than 100 lines of code. It seems like the Yjs authors also recognize that CRDT storage on the server is an area to address, there was some work on a custom database in 2018, although my thinking is more about how to retrofit text CRDTs into my existing very conservative production cloud software stack than about writing to block storage.
- deleted 5y ago
  [deleted]
- derefr 5y ago
  > no user wants to fiddle with a merge UI or picking versions like with iCloud. For prose text, what do you think about combining a document-scale CRDT, with fine-grained locking — e.g. splitting the document into a "list of lines/sentences", where lines have identity, and then only allowing one person to be modifying a given line at a time? I've always felt like this was under-explored, given that in prose text it's almost always semantically incoherent for multiple people to be trying to change a single sentence in different ways at the same time anyway (i.e. they would each have a series of edits they want to do to line A to turn it into either A' or A"; but any result that's not either purely A' or A" will very likely be nonsensical. One could say that the A → A' transformation a user does to a sentence is intentionally transactional.) I almost thought Notion would be a good example of this, but apparently not (https://www.notion.so/Real-time-collaboration-20a1873baf334d528bca621fa9717ccb https://www.notion.so/Real-time-collaboration-20a1873baf334d...) — they actually do allow multiple users to be editing the same leaf-node content block at the same time, and so have taken on the full scope of the CRDT problem. > but I don’t want to force new clients to download the entire history nor do I want these big histories in my cache, so I end up wanting a hot/cold system; and building that kind of thing and dealing with the edge cases seems like more than 100 lines of code. Yes, but these needs are able to be cleanly abstracted away on the backend — there are internally-complex infrastructure components (like CouchDB, or Kafka) that expose a pure CQRS model to clients, but internally are doing fancier stuff involving reducing changes onto snapshots and then exposing new CQRS streams that begin history with atomic "introduce all this stuff from a snapshot"-typed 'changes'. There's also some convergent evolution happening here with non-replay sync strategies in blockchains (which can be more interesting to look at if you care about the serverless p2p Operational Transformation type use-case of CRDTs.)
  - tylerhou 5y ago
    There is no notion of “same time” in a distributed system — what if a client locks a line and disconnects? Also, it leads to a poor user experience.
mikevm 5y ago
So how do the various popular CRDT libraries compare nowadays? There's Yjs (with a Rust port that is in progress), Automerge-rs, and your own diamond-types project :). Is Yjs still the current go-to for most projects' needs?
- hunterb123 5y ago
  There's also GUN (https://gun.eco/ https://gun.eco/) if you want a CRDT graph p2p syncing database. I have no relation to the project, but the community is awesome.
  - sagichmal 5y ago
    Gun is snake oil.
    - detaro 5y ago
      why?
    - i001962 5y ago
      That is a bold claim and no supporting evidence. This forum can be so valuable and yet so maddening. Please do share your experiences that support your opinion. Gun.js can seem ‘magical’ but then again the 100 lines of code (iirc it’s less) are there for all to see. I’ve found the time invested to learn about gun (the sync protocol) and RAD (storage abstraction layer) quite worth it. The addition of SEA (security encryption authorization) wrapping around gun enables a lot of implementation options which some find frustrating as they’d rather not have to think about topology before building ‘an app’. Could that be a reason for your comment? Would love to hear why you think it’s snake oil.
      - sagichmal 5y ago
        Because when the author writes or speaks about the project, they consistently demonstrate a fundamental lack of understanding of the domain. There is a reason that GunDB is never mentioned in literature or papers.
jasode 5y ago
>I’m a “true believer” in CRDTs, which I have some experience in. What is the largest-scale or highest-profile real-world usage of CRDT today? (I glanced at this CRDT vs OT topic before but I'm not up-to-date on where things stand in the real-world performance: https://news.ycombinator.com/item?id=23988999 https://news.ycombinator.com/item?id=23988999)
- jitl 5y ago
  Grandparent wrote a good article on CRDT performance https://josephg.com/blog/crdts-go-brrr/ https://josephg.com/blog/crdts-go-brrr/
- dugmartin 5y ago
  I'm not sure about the largest-scale single usage but the Phoenix Framework uses CRDTs for handing user presence. It isn't enabled by default but it is very easy to use and the CRDT backend is basically hidden away. More info: - https://hexdocs.pm/phoenix/presence.html https://hexdocs.pm/phoenix/presence.html - https://dockyard.com/blog/2016/03/25/what-makes-phoenix-presence-special-sneak-peek https://dockyard.com/blog/2016/03/25/what-makes-phoenix-pres...
- dunham 5y ago
  It's not really high scale / high performance, but Apple's notes.app uses state based CRDTs internally for conflict resolution. It is perhaps high profile, since a lot of people are using it.
- LAC-Tech 5y ago
  TomTom uses CRDTs for their SatNav software.
mamcx 5y ago
I'm interesting to se how can this apply for "regular" database apps (like invoicing). I need to add sync/offline to my main app and want something solid to build upon (have done things homemade before) and has wonder if CRDT could be applied, but how?
- a_conservative 5y ago
  I'm a CRDT newbie, but I'll take a stab, hopefully someone can correct me if I'm getting it wrong. After a quick reading the "CRDTs go brr" and the wikipedia page, I think CRDT gives us a mathematical strategy for resolving conflicts. It doesn't mean that the end result will make sense. The Wikipedia article gives an example of merging an event flag represented by a boolean variable. So the var in this case means that "someone observed this event happening". So the rule for merging this var from different sources is simple, if any source of data reports the var as true, the merged result should be true as well. The implication is it matters what the data represents, not just whether it is a boolean or a string, etc. I'm guessing that a colloborative notes field, or a "did someone call this customer" boolean might benefit from a CRDT more so than keeping track of bank account values.
- fauigerzigerk 5y ago
  I would like to know the answer to that as well. My current understanding is that CRDTs merely guarantee derministic merging of updates to some basic data structures, where deterministic means that the outcome is well defined and always the same regardless of the order in which updates are merged. That doesn't mean the outcome makes any sense at all in terms of the sort of application level requirements and constraints you would typically find in a transactional database application. Conflicts may still arise on that level. So I think what we need to really fulfill the promise of CRDTs is a way to express those application level constraints on top of them.
- azteceagle 5y ago
  We are in the same need right now. Something that we have researched and think it has a lot of potential, at least for us is James Long sync implementation. You can check out his talks and demos at: * https://www.youtube.com/watch?v=2dh_gtndayY&feature=emb_imp_woyt https://www.youtube.com/watch?v=2dh_gtndayY&feature=emb_imp_... * https://www.youtube.com/watch?v=DEcwa68f-jY https://www.youtube.com/watch?v=DEcwa68f-jY And his demo implementation (and annotated fork): * https://github.com/jlongster/crdt-example-app https://github.com/jlongster/crdt-example-app * htps://github.com/clintharris/crdt-example-app_annotated/blob/master/NOTES.md I wonder why there isn't some open source engine based on this at least for CRUD apps since it has a lot of potential and it is really "simple" to implement and even understand.
JamesSwift 5y ago
Just read your "crdts-go-brrr" post from the other commenter and just wanted to say thanks for writing all that up! Great insight and great information.
amelius 5y ago
> I’m a “true believer” in CRDTs Don't make the same mistake as the Google Wave team. Collaborative editing is a great intellectual challenge to work on, but in reality users don't care much about documents that auto-update in real time. In fact, it can be annoying.
- readams 5y ago
  That's like the main feature of Google Docs and people use it all the time.
  - Thaxll 5y ago
    Most of the time they don't use it for the realtime aspect of it, they use it to easily share documents.
    - twicetwice 5y ago
      I think you're typical-minding here. The realtime aspect is used all the time by many many people.
- jitl 5y ago
  You're replying to someone who worked on Wave.
- cjblomqvist 5y ago
  Parent was actually a part of the team doing the core engine for Wave, so in that case it's more like he never dropped his belief in it.
fendrak 5y ago
I would very much love to see the "simple CRDT" implementation described above, seems like it would be a great learning tool and/or foundation on which to build something more complicated!
- azteceagle 5y ago
  This presentation by James Long helped me a lot: https://www.youtube.com/watch?v=DEcwa68f-jY https://www.youtube.com/watch?v=DEcwa68f-jY
- josephg 5y ago
  The CRDT I was referencing was Shelf by Greg Little. He's given a few talks about it at the braid meetups. When he first showed it off, Kevin Jahns (the Yjs author) was also there and was as impressed as I was: https://braid.org/meeting-8 https://braid.org/meeting-8 (the shelf part with Greg starts at about 43 minutes in to the recording.) The code is all here. Its tiny: https://github.com/dglittle/shelf https://github.com/dglittle/shelf
  - fendrak 5y ago
    Thank you!
BiteCode_dev 5y ago
Man, I will remember Google Wave for the rest of my life. It was really ahead of its time. Kuddos for being that visionary.
BiteCode_dev 5y ago
We all think of CRDT for collaborative text editors, but can you give example of how it's used in the wild that are unexpected, yet very useful?
the_duke 5y ago
I might be missing something, but I have trouble seeing how CRDTs can work for regular CRUD style applications. Just the first example that pops into my head: edit A sets an invoice status to paid, edit b changes the invoice amount from 100 to 120. The merge is a paid invoice with an incorrect amount. A workaround would be to record a separate PaidInvoice that wont be changed by the application logic. But that's just a really trivial example that only involves scalar fields inside a single object, and also relies on the application logic considering all ways that the CRDT might behave. There are countless ways to end up with data that violates the constraints of the domain. Is there any theoretical groundwork happening on how CRDTs can preserve domain semantics?
- olah_1 5y ago
  I think CRDTs necessitate a robust permission system to be more than a toy. If you want a decentralized CRDT, you'd probably end up re-inventing smart contracts (which is what I found myself doing once).
  - sagichmal 5y ago
    CRDTs and smart contracts are almost totally unrelated to each other.
- ollysb 5y ago
  Your general point withstanding, in this case wouldn't the merge be a partially paid invoice?
  - jeremyjh 5y ago
    No, its over-payment that no one knows was over-paid.
- josephg 5y ago
  Thats a great example. In this specific case, you'd want to associate the invoice status (paid) with the point in time when that change was made so concurrent changes to the invoice result in merge conflicts. I don't know anyone who's building a CRDT like that; but its definitely possible. Basho's RIAK databases had a CRDT implementation that would provide a grounding to handle cases like that. When concurrent changes happen, the database simply stored each conflicting value. It was up to the application to decide how the conflicting values merged together. On top of something like that, you can imagine a bunch of different merging strategies which would be appropriate in different situations: Optimistic (recursively merge all children), Arbitrary-writer-wins, or Conflict-and-bother-the-user. In this case, generating a conflict state is appropriate. Conflicts also make sense when merging branches in git; and I'd love to see a CRDT which managed to reproduce that functionality. But no, I don't know of any work happening in that space. Maybe the inventor could be you!
thamer 5y ago
I was also a "true believer" in CRDTs for a long time, implementing my first ones in Erlang about 9 years ago[1], but my opinion of where they fit has changed significantly. The one issue with CRDT that I find is rarely mentioned and often ignored is the case where you've deployed these data structures that include merge logic to a set of participating nodes that you can't necessarily update at will. Think phones that people don't update, or IOT/sensor devices like electric meters or other devices "in the wild". When you include merge logic – really any code or rules that dictate what happens when the the data of 2 or more CRDTs are merged – and you have bugs in this code running on devices you can never update, this can be a huge mess. Sure you can implement simple counters easily (like the ones I linked to), and you can even use model checking to validate them. But what about complex tree logic like for edits made to a document? Conflict resolution logic? Distributed file system operations? These are already very complex and hard to get right without multiple versions involved and unfixable bugs causing mayhem. Having to deal with these bugs in the context of a fleet of participants on a wide range of versions of the code, the combinatorial explosion of the number of possible interactions and effects of these differing versions and bugs taken together can really become impossible to manage. I'd be interested to hear from folks who have experience with these kinds of issues and how they have dealt with them, especially if they are still convinced that CRDTs were the right choice. [1] https://github.com/nicolasff/distributed-counters https://github.com/nicolasff/distributed-counters
- bmurphy1976 5y ago
  How are CRDTs unique in this respect? Ossification is a challenge for all APIs, domain models, network layers, protocol specs, etc.
  - lazide 5y ago
    Because those other options abstract the decision making away from the ‘can never be updated’ part usually into some part of the system where the consequences of a problem/interest in the right solution are also collocated with someone who can do something about it (a API server with ossified clients, or network switch with buggy NIC’s wired into it, etc.) If truly peer to peer, that is a lot less clear - do you end up in a collaborative p2p document model forking the documents between ‘new rev’ clients and ‘old rev’ clients? Who ‘wins’? What is the consequence of losing? At least an API server can clearly reject the client and give an error message - if it’s a CRDT, how does that work?
hinkley 5y ago
I started trying to build a non-PHP Wiki for a hobby, and the notion that I was going to have to implement my own version control on top of it stymied me, so CRDTs looked good to me when I first started to get familiar with the idea. Trac (project management) does some stuff behind the scenes stored in svn, which it uses for edit history. I always liked that idea. Why have two? I have wished for some time that someone did a Trac for git. I just don't want to be the one to write it. I've also wished for some time that someone would make a new git, not designed by barbarian cannibals, potentially based on CRDTs. Somehow these notions melted together and now making progress hinges on whether there's a CRDT out there that's up to the task of managing source code - and written in a language I can handle. So far those two haven't appeared, and based on the number of corner cases I've heard described when I watch lectures on CRDTs, I'm pretty sure if I tried to write one myself I'd never see daylight again, but might see the inside of a padded room. Do you think it's safe to say we're still in the distillation phase of invention where CRDT's are concerned? Is this accidental complexity we are seeing or is most of it intrinsic? I'm instead spending a lot of my free time on the hobby instead of on writing collaborative tools and/or accidentally writing a Trac replacement.
omginternets 5y ago
Is there some kind of crdt bloom filter, where items in the set are densely encoded?

a_conservative 5y ago

Can you point to a good introduction to Conflict-free replicated data types (CRDT)? It's crossed my (short attention span) radar a couple times and seems interesting. I really love the idea about being able to use it, but also "forget" about it while developing. Does "leaky abstraction" apply here? If you constrain things enough, can a dev really use it and forget about the details?

jitl 5y ago

I work on a collaborative text editing system (https://www.notion.so https://www.notion.so) and read a lot about CRDTs, thank you for your work in this area, particularly https://josephg.com/blog/crdts-go-brrr/ https://josephg.com/blog/crdts-go-brrr/ I agree with your assessments here - CRDT is the way forward for most applications; no user wants to fiddle with a merge UI or picking versions like with iCloud. I think RxDB’s position here is from their CouchDB lineage. > The biggest roadblock to their use is that they’re poorly understood. Well, that and implementation maturity. I certainly have more understanding to do. My biggest open question is how to design my centralized server side storage system for CRDT data. To service writes from old clients I need to retain a total history of a document, but I don’t want to force new clients to download the entire history nor do I want these big histories in my cache, so I end up wanting a hot/cold system; and building that kind of thing and dealing with the edge cases seems like more than 100 lines of code. It seems like the Yjs authors also recognize that CRDT storage on the server is an area to address, there was some work on a custom database in 2018, although my thinking is more about how to retrofit text CRDTs into my existing very conservative production cloud software stack than about writing to block storage.

deleted 5y ago
[deleted]
derefr 5y ago
> no user wants to fiddle with a merge UI or picking versions like with iCloud. For prose text, what do you think about combining a document-scale CRDT, with fine-grained locking — e.g. splitting the document into a "list of lines/sentences", where lines have identity, and then only allowing one person to be modifying a given line at a time? I've always felt like this was under-explored, given that in prose text it's almost always semantically incoherent for multiple people to be trying to change a single sentence in different ways at the same time anyway (i.e. they would each have a series of edits they want to do to line A to turn it into either A' or A"; but any result that's not either purely A' or A" will very likely be nonsensical. One could say that the A → A' transformation a user does to a sentence is intentionally transactional.) I almost thought Notion would be a good example of this, but apparently not (https://www.notion.so/Real-time-collaboration-20a1873baf334d528bca621fa9717ccb https://www.notion.so/Real-time-collaboration-20a1873baf334d...) — they actually do allow multiple users to be editing the same leaf-node content block at the same time, and so have taken on the full scope of the CRDT problem. > but I don’t want to force new clients to download the entire history nor do I want these big histories in my cache, so I end up wanting a hot/cold system; and building that kind of thing and dealing with the edge cases seems like more than 100 lines of code. Yes, but these needs are able to be cleanly abstracted away on the backend — there are internally-complex infrastructure components (like CouchDB, or Kafka) that expose a pure CQRS model to clients, but internally are doing fancier stuff involving reducing changes onto snapshots and then exposing new CQRS streams that begin history with atomic "introduce all this stuff from a snapshot"-typed 'changes'. There's also some convergent evolution happening here with non-replay sync strategies in blockchains (which can be more interesting to look at if you care about the serverless p2p Operational Transformation type use-case of CRDTs.)
- tylerhou 5y ago
  There is no notion of “same time” in a distributed system — what if a client locks a line and disconnects? Also, it leads to a poor user experience.

mikevm 5y ago

So how do the various popular CRDT libraries compare nowadays? There's Yjs (with a Rust port that is in progress), Automerge-rs, and your own diamond-types project :). Is Yjs still the current go-to for most projects' needs?

hunterb123 5y ago
There's also GUN (https://gun.eco/ https://gun.eco/) if you want a CRDT graph p2p syncing database. I have no relation to the project, but the community is awesome.
- sagichmal 5y ago
  Gun is snake oil.
  - detaro 5y ago
    why?
  - i001962 5y ago
    That is a bold claim and no supporting evidence. This forum can be so valuable and yet so maddening. Please do share your experiences that support your opinion. Gun.js can seem ‘magical’ but then again the 100 lines of code (iirc it’s less) are there for all to see. I’ve found the time invested to learn about gun (the sync protocol) and RAD (storage abstraction layer) quite worth it. The addition of SEA (security encryption authorization) wrapping around gun enables a lot of implementation options which some find frustrating as they’d rather not have to think about topology before building ‘an app’. Could that be a reason for your comment? Would love to hear why you think it’s snake oil.
    - sagichmal 5y ago
      Because when the author writes or speaks about the project, they consistently demonstrate a fundamental lack of understanding of the domain. There is a reason that GunDB is never mentioned in literature or papers.

jasode 5y ago

>I’m a “true believer” in CRDTs, which I have some experience in. What is the largest-scale or highest-profile real-world usage of CRDT today? (I glanced at this CRDT vs OT topic before but I'm not up-to-date on where things stand in the real-world performance: https://news.ycombinator.com/item?id=23988999 https://news.ycombinator.com/item?id=23988999)

jitl 5y ago
Grandparent wrote a good article on CRDT performance https://josephg.com/blog/crdts-go-brrr/ https://josephg.com/blog/crdts-go-brrr/
dugmartin 5y ago
I'm not sure about the largest-scale single usage but the Phoenix Framework uses CRDTs for handing user presence. It isn't enabled by default but it is very easy to use and the CRDT backend is basically hidden away. More info: - https://hexdocs.pm/phoenix/presence.html https://hexdocs.pm/phoenix/presence.html - https://dockyard.com/blog/2016/03/25/what-makes-phoenix-presence-special-sneak-peek https://dockyard.com/blog/2016/03/25/what-makes-phoenix-pres...
dunham 5y ago
It's not really high scale / high performance, but Apple's notes.app uses state based CRDTs internally for conflict resolution. It is perhaps high profile, since a lot of people are using it.
LAC-Tech 5y ago
TomTom uses CRDTs for their SatNav software.

mamcx 5y ago

I'm interesting to se how can this apply for "regular" database apps (like invoicing). I need to add sync/offline to my main app and want something solid to build upon (have done things homemade before) and has wonder if CRDT could be applied, but how?

a_conservative 5y ago
I'm a CRDT newbie, but I'll take a stab, hopefully someone can correct me if I'm getting it wrong. After a quick reading the "CRDTs go brr" and the wikipedia page, I think CRDT gives us a mathematical strategy for resolving conflicts. It doesn't mean that the end result will make sense. The Wikipedia article gives an example of merging an event flag represented by a boolean variable. So the var in this case means that "someone observed this event happening". So the rule for merging this var from different sources is simple, if any source of data reports the var as true, the merged result should be true as well. The implication is it matters what the data represents, not just whether it is a boolean or a string, etc. I'm guessing that a colloborative notes field, or a "did someone call this customer" boolean might benefit from a CRDT more so than keeping track of bank account values.
fauigerzigerk 5y ago
I would like to know the answer to that as well. My current understanding is that CRDTs merely guarantee derministic merging of updates to some basic data structures, where deterministic means that the outcome is well defined and always the same regardless of the order in which updates are merged. That doesn't mean the outcome makes any sense at all in terms of the sort of application level requirements and constraints you would typically find in a transactional database application. Conflicts may still arise on that level. So I think what we need to really fulfill the promise of CRDTs is a way to express those application level constraints on top of them.
azteceagle 5y ago
We are in the same need right now. Something that we have researched and think it has a lot of potential, at least for us is James Long sync implementation. You can check out his talks and demos at: * https://www.youtube.com/watch?v=2dh_gtndayY&feature=emb_imp_woyt https://www.youtube.com/watch?v=2dh_gtndayY&feature=emb_imp_... * https://www.youtube.com/watch?v=DEcwa68f-jY https://www.youtube.com/watch?v=DEcwa68f-jY And his demo implementation (and annotated fork): * https://github.com/jlongster/crdt-example-app https://github.com/jlongster/crdt-example-app * htps://github.com/clintharris/crdt-example-app_annotated/blob/master/NOTES.md I wonder why there isn't some open source engine based on this at least for CRUD apps since it has a lot of potential and it is really "simple" to implement and even understand.

JamesSwift 5y ago

Just read your "crdts-go-brrr" post from the other commenter and just wanted to say thanks for writing all that up! Great insight and great information.

amelius 5y ago

> I’m a “true believer” in CRDTs Don't make the same mistake as the Google Wave team. Collaborative editing is a great intellectual challenge to work on, but in reality users don't care much about documents that auto-update in real time. In fact, it can be annoying.

readams 5y ago
That's like the main feature of Google Docs and people use it all the time.
- Thaxll 5y ago
  Most of the time they don't use it for the realtime aspect of it, they use it to easily share documents.
  - twicetwice 5y ago
    I think you're typical-minding here. The realtime aspect is used all the time by many many people.
jitl 5y ago
You're replying to someone who worked on Wave.
cjblomqvist 5y ago
Parent was actually a part of the team doing the core engine for Wave, so in that case it's more like he never dropped his belief in it.

fendrak 5y ago

I would very much love to see the "simple CRDT" implementation described above, seems like it would be a great learning tool and/or foundation on which to build something more complicated!

azteceagle 5y ago
This presentation by James Long helped me a lot: https://www.youtube.com/watch?v=DEcwa68f-jY https://www.youtube.com/watch?v=DEcwa68f-jY
josephg 5y ago
The CRDT I was referencing was Shelf by Greg Little. He's given a few talks about it at the braid meetups. When he first showed it off, Kevin Jahns (the Yjs author) was also there and was as impressed as I was: https://braid.org/meeting-8 https://braid.org/meeting-8 (the shelf part with Greg starts at about 43 minutes in to the recording.) The code is all here. Its tiny: https://github.com/dglittle/shelf https://github.com/dglittle/shelf
- fendrak 5y ago
  Thank you!

BiteCode_dev 5y ago

Man, I will remember Google Wave for the rest of my life. It was really ahead of its time. Kuddos for being that visionary.

BiteCode_dev 5y ago

We all think of CRDT for collaborative text editors, but can you give example of how it's used in the wild that are unexpected, yet very useful?

the_duke 5y ago

I might be missing something, but I have trouble seeing how CRDTs can work for regular CRUD style applications. Just the first example that pops into my head: edit A sets an invoice status to paid, edit b changes the invoice amount from 100 to 120. The merge is a paid invoice with an incorrect amount. A workaround would be to record a separate PaidInvoice that wont be changed by the application logic. But that's just a really trivial example that only involves scalar fields inside a single object, and also relies on the application logic considering all ways that the CRDT might behave. There are countless ways to end up with data that violates the constraints of the domain. Is there any theoretical groundwork happening on how CRDTs can preserve domain semantics?

olah_1 5y ago
I think CRDTs necessitate a robust permission system to be more than a toy. If you want a decentralized CRDT, you'd probably end up re-inventing smart contracts (which is what I found myself doing once).
- sagichmal 5y ago
  CRDTs and smart contracts are almost totally unrelated to each other.
ollysb 5y ago
Your general point withstanding, in this case wouldn't the merge be a partially paid invoice?
- jeremyjh 5y ago
  No, its over-payment that no one knows was over-paid.
josephg 5y ago
Thats a great example. In this specific case, you'd want to associate the invoice status (paid) with the point in time when that change was made so concurrent changes to the invoice result in merge conflicts. I don't know anyone who's building a CRDT like that; but its definitely possible. Basho's RIAK databases had a CRDT implementation that would provide a grounding to handle cases like that. When concurrent changes happen, the database simply stored each conflicting value. It was up to the application to decide how the conflicting values merged together. On top of something like that, you can imagine a bunch of different merging strategies which would be appropriate in different situations: Optimistic (recursively merge all children), Arbitrary-writer-wins, or Conflict-and-bother-the-user. In this case, generating a conflict state is appropriate. Conflicts also make sense when merging branches in git; and I'd love to see a CRDT which managed to reproduce that functionality. But no, I don't know of any work happening in that space. Maybe the inventor could be you!

thamer 5y ago

I was also a "true believer" in CRDTs for a long time, implementing my first ones in Erlang about 9 years ago[1], but my opinion of where they fit has changed significantly. The one issue with CRDT that I find is rarely mentioned and often ignored is the case where you've deployed these data structures that include merge logic to a set of participating nodes that you can't necessarily update at will. Think phones that people don't update, or IOT/sensor devices like electric meters or other devices "in the wild". When you include merge logic – really any code or rules that dictate what happens when the the data of 2 or more CRDTs are merged – and you have bugs in this code running on devices you can never update, this can be a huge mess. Sure you can implement simple counters easily (like the ones I linked to), and you can even use model checking to validate them. But what about complex tree logic like for edits made to a document? Conflict resolution logic? Distributed file system operations? These are already very complex and hard to get right without multiple versions involved and unfixable bugs causing mayhem. Having to deal with these bugs in the context of a fleet of participants on a wide range of versions of the code, the combinatorial explosion of the number of possible interactions and effects of these differing versions and bugs taken together can really become impossible to manage. I'd be interested to hear from folks who have experience with these kinds of issues and how they have dealt with them, especially if they are still convinced that CRDTs were the right choice. [1] https://github.com/nicolasff/distributed-counters https://github.com/nicolasff/distributed-counters

bmurphy1976 5y ago
How are CRDTs unique in this respect? Ossification is a challenge for all APIs, domain models, network layers, protocol specs, etc.
- lazide 5y ago
  Because those other options abstract the decision making away from the ‘can never be updated’ part usually into some part of the system where the consequences of a problem/interest in the right solution are also collocated with someone who can do something about it (a API server with ossified clients, or network switch with buggy NIC’s wired into it, etc.) If truly peer to peer, that is a lot less clear - do you end up in a collaborative p2p document model forking the documents between ‘new rev’ clients and ‘old rev’ clients? Who ‘wins’? What is the consequence of losing? At least an API server can clearly reject the client and give an error message - if it’s a CRDT, how does that work?

hinkley 5y ago

I started trying to build a non-PHP Wiki for a hobby, and the notion that I was going to have to implement my own version control on top of it stymied me, so CRDTs looked good to me when I first started to get familiar with the idea. Trac (project management) does some stuff behind the scenes stored in svn, which it uses for edit history. I always liked that idea. Why have two? I have wished for some time that someone did a Trac for git. I just don't want to be the one to write it. I've also wished for some time that someone would make a new git, not designed by barbarian cannibals, potentially based on CRDTs. Somehow these notions melted together and now making progress hinges on whether there's a CRDT out there that's up to the task of managing source code - and written in a language I can handle. So far those two haven't appeared, and based on the number of corner cases I've heard described when I watch lectures on CRDTs, I'm pretty sure if I tried to write one myself I'd never see daylight again, but might see the inside of a padded room. Do you think it's safe to say we're still in the distillation phase of invention where CRDT's are concerned? Is this accidental complexity we are seeing or is most of it intrinsic? I'm instead spending a lot of my free time on the hobby instead of on writing collaborative tools and/or accidentally writing a Trac replacement.

omginternets 5y ago

Is there some kind of crdt bloom filter, where items in the set are densely encoded?