6 ms·

Conflict-Free Replicated Data Types (CRDT)

204 points by leonidasv 5y ago

mountainriver 5y ago
CRDTs are pretty rad, I’m really excited to see what the future might hold for them particularly around development
- ibash 5y ago
  They’ve been rad for years, and a lot of work has been done around them. Usually people find that there are simpler/better ways to get the job done. I think they’re better left as an implementation detail at this point.
  - josephg 5y ago
    > Usually people find that there are simpler/better ways to get the job done. CRDTs can do one magic trick no other technology solutions can do: They can let users collaboratively edit without needing a centralized server. And this works between users, between devices or between processes. Its just, most of the time that doesn't matter. Servers are cheap, and big companies frankly seem to love it when we're dependent on their infrastructure. I want CRDTs for more "personal computing". I want my data to be shared between my devices seamlessly. And I want that to keep working even when I can't contact google's computers. I also really like something about Git - which is the fact that my computers are first class citizens in a repository. Unlike Google Docs, if github ever goes down, I don't lose any data and I can still get my work done, and collaborate with my teammates. All software should work like that. I'm fighting to make CRDTs work well so we can bring that future within reach.
    - refulgentis 5y ago
      To OP's point, which I secretly wished I had the courage to post when CRDTs came up a couple times last week: I've been seeing these posts, and your comment, for what feels like my entire 13 years on HN. (That can't be true. But I distinctly recall someone saying "if they can do text this fast hey'll be able to do arbitrary JSON soon!" at least 5 years ago) At the beginning of that period I made and sold a startup on having a dead simple sync strategy, by myself, while I watched 3 funded competitors try to build sync, fail and go under. I had no funding and no CS education, I was a waiter.
      - josephg 5y ago
        Arbitrary JSON has been done plenty of times, and it works great. Automerge, Yjs and ShareDB all manage it.
        refulgentis 5y ago
        I don't quite understand what's going on then because I swear I just read in one of those threads last week that even the best text automerger still needs manual intervention to avoid creating nonsense...which, to be honest, sounded off because I thought this whole thing was popularized by Google Docs? Wave? and it didn't have that issue
        josephg 5y ago
        Can you link the other comment? Its hard to know what you're talking about without that context. In any case, you can't use a text "automerger" to collaboratively edit JSON text. (Whats an "automerger"?) To understand why, suppose we had an empty (JSON) list: []. Two users concurrently inserted two items, "a" and "b". If those inserts get translated into string inserts, you end up with a JSON string containing ["a""b"] - which is a syntax error! The trick to making this work correctly is that the CRDT / OT system needs to understand that you're editing a list. Don't collaboratively edit the JSON string. Collaboratively edit a list then JSON.stringify the result.
        lewisjoe 5y ago
        There's a possibility he's talking about what I wrote about CRDTs for syntax trees - https://writer.zohopublic.com/writer/published/grcwy5c699d67b9c444219b60cdb90ccbabc7 https://writer.zohopublic.com/writer/published/grcwy5c699d67... Related HN thread: https://news.ycombinator.com/item?id=29433896 https://news.ycombinator.com/item?id=29433896
        mlajtos 5y ago
        > the best text automerger still needs manual intervention to avoid creating nonsense AFAIK the best production-ready CRDT solution for text is Yjs [0], and in some specific cases, the result of the merge might be something unexpected (one example [1]). However, there is research-quality CRDT called Peritext [2] which is specifically designed to handle styled text in an intuitive way, so the merge is more predictable. [0]: https://github.com/yjs/yjs https://github.com/yjs/yjs [1]: https://github.com/yjs/yjs/issues/382 https://github.com/yjs/yjs/issues/382 [2]: https://www.inkandswitch.com/peritext/ https://www.inkandswitch.com/peritext/
    - jamil7 5y ago
      > Servers are cheap, and big companies frankly seem to love it when we're dependent on their infrastructure. I've worked on a few different sync engines for mobile apps over the years, it's also a matter of user expectations in consumer apps. Users expect to seamlessly pick up where they left off on another device and the absence of an intermediary server makes that difficult.
      - josephg 5y ago
        You can always have an intermediary server with CRDTs is you want. They're just another peer on the network.
        jamil7 5y ago
        Yeah I'm aware - I got the impression from your comment you were advocating for a more pure P2P approach (not necessarily CRDT related).
        josephg 5y ago
        I am. I guess thats something I really like about git + github - you get the best of both worlds. Github is fantastic, and you can use github all day long. But you don't depend on it. If github had an outage like atlassian is having at the moment, there's no downtime. There's no risk of data loss. You can keep working and if you need to you can always move to gitlab or self host. The downside is you sort of have the worst of both worlds in terms of complexity. You need a working, performant CRDT and a working centralized server. But I think its a great model that we (as an industry) should explore more.
        jamil7 5y ago
        Yeah I agree it's great from that perspective but the business goals very rarely make it a priority given the added complexity. Even supporting offline-first style workflows is step up as you can tolerate more downtime on the backend as your app doesn't become completely useless.
  - LAC-Tech 5y ago
    Usually people find that there are simpler/better ways to get the job done. Here's all the ways I know for dealing with write conflicts in a distributed systems: - Last write wins, AKA I'm going to pretend I've solved the problem and just randomly lose data - Record all versions of the data, pick an arbitrary winner, store a revision, and surface it to the user if there's a conflict (the CouchDB strategy, I don't know anything else using this) - Model your data so it's append only (events, maybe) then merge just becomes a set union of all the different nodes[0] So including CRDTs, that's my general taxonomy of solutions to this problem. Are there more? [0] Working on a prototype for this right now, if anyone has done similar work I'd love to pick your brain, email in profile.
    - maffydub 5y ago
      Slightly pedantic, but I think you'll actually find that all of these are CRDTs. If you read "Conflict-free Replicated Data Types: An Overview" (https://arxiv.org/pdf/1806.10254.pdf https://arxiv.org/pdf/1806.10254.pdf), it refers to both last write wins and "record all versions of the data" as CRDTs in 2.1.1. My understanding is that "CRDT" really just means that you've defined how you're going to resolve conflicts consistently (see criteria in s2.2 of the paper above).
      - LAC-Tech 5y ago
        Yeah it had occurred to me that what I'm doing was just a GSet writ large. In my mind a CRDT was always a single record, not a collection of them - still not convinced that doesn't change it. But if CRDTs really are a kind of a meta-language for resolving conflicts in a sane way - whether the CRDT is a single record or a whole data store - that's a nice thought. The CouchDB CRDT could be defined.
    - kd5bjo 5y ago
      CRDTs don’t quite fit in this list, as these are all valid merge strategies that a CRDT can use. The fundamental idea of a CRDT is that all of these schemes have something in common: They’re based on iteratively merging a bunch of versions together with a merge operator that fulfills a few basic properties (where + means merge: - Associativity: (A + B) + C == A + (B + C) - Commutativity: A + B == B + A - Idempotency: A + A = A - Closure: Every merge result is a valid merge argument - (perhaps a few others; it’s been a while since I read the original papers) As long as your merge operator has all of these properties, you get the strong eventual consistency result that makes CRDTs a useful abstraction: Any two users that have received versions including the same updates will reconstruct the document in the same way, even if the actual set of versions seen differs.
- hinkley 5y ago
  The pessimist in my brain keeps waiting for someone to prove mathematically that they’re impossible. NP complete might be fine for many uses, since the branching factor for code for example is pretty low. But for some people NP complete is a magical force field that shuts off all rational thought.
  - veselin 5y ago
    Yes. There is a paper that shows that if a data type has non-commutative operations, then avoiding expensive synchronization is impossible https://hagit.net.technion.ac.il/files/2015/09/popl168gf-attiya.pdf https://hagit.net.technion.ac.il/files/2015/09/popl168gf-att...
    - hinkley 5y ago
      That agrees with my intuition for the most part, although it might carve out some space for hope, in the sense that a paper about proof of A that doesn't mention !A means someone spent time in there and didn't find a bigger problem. The more times someone carves out a small amount of negative space in a problem domain, the higher the odds are that there's an asymptote that is nonzero. What I'm more worried about is that we will prove that 'interesting text merges' are not all commutative. Though one trick we keep doing in spaces where things are proven impossible is that we cheat by creating tools that disallow or discourage the intractable scenarios. That could, for instance, lead to a generation of programming languages with a strange file structure that makes most workflows commutative. That may sound strange or terrible to some people, but it's been my opinion for a number of years now that most of our coding conventions boil down to issues of avoiding merge conflicts, so a language that enforced a stronger form of conflict avoidance would be an 'opinionated' language but within the realm of the sorts of things we already put up with. Maybe no stranger than pure functional or Actor based languages, for instance.
legerdemain 5y ago
The story I have in my head for CRDTs is basically all math and theory. I'd love a quick perspective on how CRDTs integrate into real app infrastructure in the real world. Do they interact with disk storage? Are there dedicated DB solutions that don't ruin their mathematical guarantees?
- josephg 5y ago
  > I'd love a quick perspective on how CRDTs integrate into real app infrastructure in the real world. There just aren't a lot of good integrations with databases yet. There's nothing technical stopping that from happening - but I don't think we even know CRDTs could be fast enough to be practically useful until last year. So its going to take a few years before this stuff bleeds into databases. A list CRDT like diamond types or Automerge is just a set of changes. Changes are like git commits - they have an ID, parents, and details of the change. Its like if you wanted to store a git commit per edit / per keystroke a user makes. The algorithms / mathematical guarantees don't care how you store and send that data set. Aside from some clever algorithms, an (operation based) CRDT is essentially an append-only set of operations, that needs to be replicated between peers. There's nothing magic about them, and any infrastructure which can do that can support CRDTs. So you could just store each change as an entry in a database table - and actually, that'd work fine in practice[1]. The problem is that you'd end up using up a lot of space for a document, because there are so many changes. Type a 10 page paper? That'll be 260k database entries! There are plenty of tricks to storing this information compactly. Simple RLE encoding decreases size by an order of magnitude. (Thanks to Martin Kleppmann for this work). But lots of compact binary representation tricks don't play that nice with modern databases. And you don't want to have to load & re-save the data each time you change something. One long term answer would be to bake CRDT compaction techniques into databases themselves, but obviously this will be idiosyncratic. And there's lots of shorter term solutions, like using multiple tables + run-length encoding values. But I think the CRDT libraries themselves (Yjs, Automerge, Diamond Types, etc) need to mature some more. I don't see much point hacking up postgres when the set of fields & semantics are still (somewhat) in flux. (Well, yjs might be more ready for this work - but its probably still a good idea to wait until yjs's rust port (yrs) is done). [1] It'd work fine the way my own CRDT (diamond types) is designed, since DT just needs to store the "origin positions" of each change. In Yjs and Automerge, changes store references to the ID of the item to the immediate left. In order to generate those changes, both automerge and yjs need to look up those persistent IDs - which in practice means they need to load the document state into memory first.
alephnan 5y ago
For context, one of the main motivations for CRDT was multiple users simultaneously editing some document. E.G. Google Docs. I was researching these approaches when I was implementing my own collaborative text editor. CRDT was too mathematically steep for me. Another approach is differential syncing. I think Google Docs was originally implemented with differential syncing and then switched to CRDT. https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/35605.pdf https://static.googleusercontent.com/media/research.google.c... I think the tradeoff and why I leaned towards differential syncing was that the implementation was easier. There are some gaps / unclear implementation details in this white paper's algorithm that you kind of have to rediscover yourself, because if you followed the algorithm listed here it will not work. I forgot the details. I'm still not sure if that was intentional. I hope now the literature on CRDT has gotten more mainstream and digestible for non-mathematicians because that seems like the future.
- thesz 5y ago
  From what I know, Google Docs never used CRDT. They adopted Google Wave's algorithm which was taken from Jupiter UI system [1]: operational transformations [2] with conflict resolution on the server side. [1] https://svn.apache.org/repos/asf/incubator/wave/whitepapers/operational-transform/operational-transform.html https://svn.apache.org/repos/asf/incubator/wave/whitepapers/... [2] https://en.wikipedia.org/wiki/Operational_transformation https://en.wikipedia.org/wiki/Operational_transformation When the server does ordering operation, operational transformations became a piece of cake to implement and reason about. If you add hierarchical addressing like "book/chapter/section/subsection/paragraph/char", they are also quite conflict free. But you need a central authority. In case of Google, it is easy and fits the profit model. Bonus: https://code.google.com/archive/p/google-mobwrite/ https://code.google.com/archive/p/google-mobwrite/ A library to collaboratively edit HTML forms.
LAC-Tech 5y ago
I've read a couple of CRDT papers but never used them in anger. (Zero interest in collaborative text editing, but a lot of interests in multi-master systems involving local databases that lose internet connectivity). Anyone have any good war stories? The general impression I get is that anything more than a state delta two-phase set is an open research problem to implement efficiently - the papers make it sound pretty straight forward but there's a whole garbage collection problem to deal with, there was another research paper dealing with just that IIRC.
- andy_ppp 5y ago
  Chris McCord had fun implementing a CRDT in Phoenix.Presence: https://www.youtube.com/watch?v=XJ9ckqCMiKk https://www.youtube.com/watch?v=XJ9ckqCMiKk (from about 17 mins by the looks of things).
- vmaurin 5y ago
  Maybe somebody from soundcloud ? https://developers.soundcloud.com/blog/roshi-a-crdt-system-for-timestamped-events https://developers.soundcloud.com/blog/roshi-a-crdt-system-f...
- celeritascelery 5y ago
  Raph Levien had a good post about using CRDTs for text editing. He feels they didn’t live up to his expectations. https://raphlinus.github.io/xi/2020/06/27/xi-retrospective.html https://raphlinus.github.io/xi/2020/06/27/xi-retrospective.h...
- kevinjahns 5y ago
  It's interesting to me that people still doubt that CRDTs can be used in practice. The fact is that they are already being used in practice by many companies with millions of users for applications like rich-text editing and state management in 3d applications. See https://github.com/yjs/yjs#who-is-using-yjs https://github.com/yjs/yjs#who-is-using-yjs In fact, Yjs - a CRDT implementation- is the most downloaded solution for collaborative applications. Even more than ShareDB (the most popular OT-based solution). Yjs ~90k/week - https://www.npmjs.com/package/yjs https://www.npmjs.com/package/yjs ShareDB ~13k/week - https://www.npmjs.com/package/yjs https://www.npmjs.com/package/yjs
samatman 5y ago
Is anyone working on a CRDT system using pijul patches and merge strategy? The "Replicated Data Type" part of CRDTs seems to be a solved problem, making "Conflict-Free" give results that are as close to what the user would expect as is theoretically possible would appear to be the hard part.
- euroderf 5y ago
  I'm hoping that one of these days, pijul will compile on Mac. Or that they will distribute a Mac binary.
  - andai 5y ago
    You can get it in 3 lines (apparently, don't have a Mac handy right now). brew install llvm libsodium openssl xxhash zstd curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh cargo install pijul --version "~1.0.0-alpha" But yeah, I can see how that might hurt adoption.
    - euroderf 5y ago
      I reinstalled rust per your line 2 but the build still failed. Oh well.
      - pmeunier 5y ago
        There are so many ways to ask for help about that: - https://pijul.zulipchat.com https://pijul.zulipchat.com - https://discourse.pijul.org https://discourse.pijul.org - https://nest.pijul.com/pijul/pijul/discussions/new https://nest.pijul.com/pijul/pijul/discussions/new if the failure is in Pijul itself and not in one of its dependencies. And even on Twitter (@pijul_org)!
        euroderf 5y ago
        It also barfed on my wife's Mac (which has not been loaded with a mish-mash of development stuff), so I give up. If nobody else is reporting the same problems as I'm having then I guess it's just that I'm having a bad hair year.
yonz 5y ago
Lots of the comments here seem to be about why do you need CRDT when so many solutions can solve collaborative text editing. The biggest bang is for de-centralization or edge based storage similar idea to @josephg (personal computing). Imagine taking multiple hours provisioning your personal compute with all your data and stream the diff across your devices and having an internet that runs off your devices. This would finally allow for a multi device local-first experience (https://www.inkandswitch.com/local-first/ https://www.inkandswitch.com/local-first/) where your phone streams the changes to your data while you were on your flight to your desktop and at a bigger scale entire facebook/google data store is a streaming system with auto-merge instead of a focus on ACID DB structures and coherence. Hands down Martin Kleppmann (Author of data intensive applications) is the biggest fan of CRDTs and this page has a lot of great info https://martin.kleppmann.com/2020/07/06/crdt-hard-parts-hydra.html https://martin.kleppmann.com/2020/07/06/crdt-hard-parts-hydr...
jFriedensreich 5y ago
the crux of crdts is for solutions that don't want to use central always online sync backends, have a need to merge deep history not just pick a winner of a global latest state but are ok with losing some conflicting detailed information stored inside your data. - if you can just pick a global winner for the object/document after diverging histories/ conflicts its much simpler to just pick a latest win strategy especially for simple data - if you cannot lose conflicting detail information, crdts will not solve your problems and you most probably need to implement application specific conflict resolution. an example is someone renaming a todo from "create invoice summary 2019" to "create latest invoice summary 2023" and at the same time someone else setting the "create invoice summary 2019" as done. a crdt can consistently merge the changes but you might end up with a todo that is set to done and is called "create latest invoice summary 2023" which is a wrong result
lgessler 5y ago
How do CRDTs work with denormalized data, or more generally, data where some fields have invariants that must be maintained between them? Let's say we have an object with an array of strings and a count of that array: { "words": ["a", "b", "c"], "count": 3 } Now suppose users A and B edit the document so that one word is deleted, and two words are added, respectively: { "words": ["a", "b"], "count": 2 } { "words": ["a", "b", "c", "d", "e"], "count": 5 } What probably should happen now is that we reach the state where `words` is `["a", "b", "d", "e"]` and `count` is `4`, but is that really what would happen? That would require the CRDT to understand changes to `count` as increment/decrement operations, but aren't there also situations where you'd simply want one of the two values to win?
- enkrs 5y ago
  Yes, it would work if you implement the schema correctly: among the standard value types there are also counter types. See for example https://automerge.org/docs/types/counters/ https://automerge.org/docs/types/counters/
- greiskul 5y ago
  I think with CRDT's you wouldn't just have an integer type. You would have to choose your int type acording to the operations you would want done for it. So it could be declared as a "register" crdt, in which case the semantics would be of set and override, or it could be declared as a counter, with semantics of increment/decrement.

204 points by leonidasv 5y ago

mountainriver 5y ago

CRDTs are pretty rad, I’m really excited to see what the future might hold for them particularly around development

ibash 5y ago
They’ve been rad for years, and a lot of work has been done around them. Usually people find that there are simpler/better ways to get the job done. I think they’re better left as an implementation detail at this point.
- josephg 5y ago
  > Usually people find that there are simpler/better ways to get the job done. CRDTs can do one magic trick no other technology solutions can do: They can let users collaboratively edit without needing a centralized server. And this works between users, between devices or between processes. Its just, most of the time that doesn't matter. Servers are cheap, and big companies frankly seem to love it when we're dependent on their infrastructure. I want CRDTs for more "personal computing". I want my data to be shared between my devices seamlessly. And I want that to keep working even when I can't contact google's computers. I also really like something about Git - which is the fact that my computers are first class citizens in a repository. Unlike Google Docs, if github ever goes down, I don't lose any data and I can still get my work done, and collaborate with my teammates. All software should work like that. I'm fighting to make CRDTs work well so we can bring that future within reach.
  - refulgentis 5y ago
    To OP's point, which I secretly wished I had the courage to post when CRDTs came up a couple times last week: I've been seeing these posts, and your comment, for what feels like my entire 13 years on HN. (That can't be true. But I distinctly recall someone saying "if they can do text this fast hey'll be able to do arbitrary JSON soon!" at least 5 years ago) At the beginning of that period I made and sold a startup on having a dead simple sync strategy, by myself, while I watched 3 funded competitors try to build sync, fail and go under. I had no funding and no CS education, I was a waiter.
    - josephg 5y ago
      Arbitrary JSON has been done plenty of times, and it works great. Automerge, Yjs and ShareDB all manage it.
      - refulgentis 5y ago
        I don't quite understand what's going on then because I swear I just read in one of those threads last week that even the best text automerger still needs manual intervention to avoid creating nonsense...which, to be honest, sounded off because I thought this whole thing was popularized by Google Docs? Wave? and it didn't have that issue
        josephg 5y ago
        Can you link the other comment? Its hard to know what you're talking about without that context. In any case, you can't use a text "automerger" to collaboratively edit JSON text. (Whats an "automerger"?) To understand why, suppose we had an empty (JSON) list: []. Two users concurrently inserted two items, "a" and "b". If those inserts get translated into string inserts, you end up with a JSON string containing ["a""b"] - which is a syntax error! The trick to making this work correctly is that the CRDT / OT system needs to understand that you're editing a list. Don't collaboratively edit the JSON string. Collaboratively edit a list then JSON.stringify the result.
        lewisjoe 5y ago
        There's a possibility he's talking about what I wrote about CRDTs for syntax trees - https://writer.zohopublic.com/writer/published/grcwy5c699d67b9c444219b60cdb90ccbabc7 https://writer.zohopublic.com/writer/published/grcwy5c699d67... Related HN thread: https://news.ycombinator.com/item?id=29433896 https://news.ycombinator.com/item?id=29433896
        mlajtos 5y ago
        > the best text automerger still needs manual intervention to avoid creating nonsense AFAIK the best production-ready CRDT solution for text is Yjs [0], and in some specific cases, the result of the merge might be something unexpected (one example [1]). However, there is research-quality CRDT called Peritext [2] which is specifically designed to handle styled text in an intuitive way, so the merge is more predictable. [0]: https://github.com/yjs/yjs https://github.com/yjs/yjs [1]: https://github.com/yjs/yjs/issues/382 https://github.com/yjs/yjs/issues/382 [2]: https://www.inkandswitch.com/peritext/ https://www.inkandswitch.com/peritext/
  - jamil7 5y ago
    > Servers are cheap, and big companies frankly seem to love it when we're dependent on their infrastructure. I've worked on a few different sync engines for mobile apps over the years, it's also a matter of user expectations in consumer apps. Users expect to seamlessly pick up where they left off on another device and the absence of an intermediary server makes that difficult.
    - josephg 5y ago
      You can always have an intermediary server with CRDTs is you want. They're just another peer on the network.
      - jamil7 5y ago
        Yeah I'm aware - I got the impression from your comment you were advocating for a more pure P2P approach (not necessarily CRDT related).
        josephg 5y ago
        I am. I guess thats something I really like about git + github - you get the best of both worlds. Github is fantastic, and you can use github all day long. But you don't depend on it. If github had an outage like atlassian is having at the moment, there's no downtime. There's no risk of data loss. You can keep working and if you need to you can always move to gitlab or self host. The downside is you sort of have the worst of both worlds in terms of complexity. You need a working, performant CRDT and a working centralized server. But I think its a great model that we (as an industry) should explore more.
        jamil7 5y ago
        Yeah I agree it's great from that perspective but the business goals very rarely make it a priority given the added complexity. Even supporting offline-first style workflows is step up as you can tolerate more downtime on the backend as your app doesn't become completely useless.
- LAC-Tech 5y ago
  Usually people find that there are simpler/better ways to get the job done. Here's all the ways I know for dealing with write conflicts in a distributed systems: - Last write wins, AKA I'm going to pretend I've solved the problem and just randomly lose data - Record all versions of the data, pick an arbitrary winner, store a revision, and surface it to the user if there's a conflict (the CouchDB strategy, I don't know anything else using this) - Model your data so it's append only (events, maybe) then merge just becomes a set union of all the different nodes[0] So including CRDTs, that's my general taxonomy of solutions to this problem. Are there more? [0] Working on a prototype for this right now, if anyone has done similar work I'd love to pick your brain, email in profile.
  - maffydub 5y ago
    Slightly pedantic, but I think you'll actually find that all of these are CRDTs. If you read "Conflict-free Replicated Data Types: An Overview" (https://arxiv.org/pdf/1806.10254.pdf https://arxiv.org/pdf/1806.10254.pdf), it refers to both last write wins and "record all versions of the data" as CRDTs in 2.1.1. My understanding is that "CRDT" really just means that you've defined how you're going to resolve conflicts consistently (see criteria in s2.2 of the paper above).
    - LAC-Tech 5y ago
      Yeah it had occurred to me that what I'm doing was just a GSet writ large. In my mind a CRDT was always a single record, not a collection of them - still not convinced that doesn't change it. But if CRDTs really are a kind of a meta-language for resolving conflicts in a sane way - whether the CRDT is a single record or a whole data store - that's a nice thought. The CouchDB CRDT could be defined.
  - kd5bjo 5y ago
    CRDTs don’t quite fit in this list, as these are all valid merge strategies that a CRDT can use. The fundamental idea of a CRDT is that all of these schemes have something in common: They’re based on iteratively merging a bunch of versions together with a merge operator that fulfills a few basic properties (where + means merge: - Associativity: (A + B) + C == A + (B + C) - Commutativity: A + B == B + A - Idempotency: A + A = A - Closure: Every merge result is a valid merge argument - (perhaps a few others; it’s been a while since I read the original papers) As long as your merge operator has all of these properties, you get the strong eventual consistency result that makes CRDTs a useful abstraction: Any two users that have received versions including the same updates will reconstruct the document in the same way, even if the actual set of versions seen differs.
hinkley 5y ago
The pessimist in my brain keeps waiting for someone to prove mathematically that they’re impossible. NP complete might be fine for many uses, since the branching factor for code for example is pretty low. But for some people NP complete is a magical force field that shuts off all rational thought.
- veselin 5y ago
  Yes. There is a paper that shows that if a data type has non-commutative operations, then avoiding expensive synchronization is impossible https://hagit.net.technion.ac.il/files/2015/09/popl168gf-attiya.pdf https://hagit.net.technion.ac.il/files/2015/09/popl168gf-att...
  - hinkley 5y ago
    That agrees with my intuition for the most part, although it might carve out some space for hope, in the sense that a paper about proof of A that doesn't mention !A means someone spent time in there and didn't find a bigger problem. The more times someone carves out a small amount of negative space in a problem domain, the higher the odds are that there's an asymptote that is nonzero. What I'm more worried about is that we will prove that 'interesting text merges' are not all commutative. Though one trick we keep doing in spaces where things are proven impossible is that we cheat by creating tools that disallow or discourage the intractable scenarios. That could, for instance, lead to a generation of programming languages with a strange file structure that makes most workflows commutative. That may sound strange or terrible to some people, but it's been my opinion for a number of years now that most of our coding conventions boil down to issues of avoiding merge conflicts, so a language that enforced a stronger form of conflict avoidance would be an 'opinionated' language but within the realm of the sorts of things we already put up with. Maybe no stranger than pure functional or Actor based languages, for instance.

legerdemain 5y ago

The story I have in my head for CRDTs is basically all math and theory. I'd love a quick perspective on how CRDTs integrate into real app infrastructure in the real world. Do they interact with disk storage? Are there dedicated DB solutions that don't ruin their mathematical guarantees?

josephg 5y ago
> I'd love a quick perspective on how CRDTs integrate into real app infrastructure in the real world. There just aren't a lot of good integrations with databases yet. There's nothing technical stopping that from happening - but I don't think we even know CRDTs could be fast enough to be practically useful until last year. So its going to take a few years before this stuff bleeds into databases. A list CRDT like diamond types or Automerge is just a set of changes. Changes are like git commits - they have an ID, parents, and details of the change. Its like if you wanted to store a git commit per edit / per keystroke a user makes. The algorithms / mathematical guarantees don't care how you store and send that data set. Aside from some clever algorithms, an (operation based) CRDT is essentially an append-only set of operations, that needs to be replicated between peers. There's nothing magic about them, and any infrastructure which can do that can support CRDTs. So you could just store each change as an entry in a database table - and actually, that'd work fine in practice[1]. The problem is that you'd end up using up a lot of space for a document, because there are so many changes. Type a 10 page paper? That'll be 260k database entries! There are plenty of tricks to storing this information compactly. Simple RLE encoding decreases size by an order of magnitude. (Thanks to Martin Kleppmann for this work). But lots of compact binary representation tricks don't play that nice with modern databases. And you don't want to have to load & re-save the data each time you change something. One long term answer would be to bake CRDT compaction techniques into databases themselves, but obviously this will be idiosyncratic. And there's lots of shorter term solutions, like using multiple tables + run-length encoding values. But I think the CRDT libraries themselves (Yjs, Automerge, Diamond Types, etc) need to mature some more. I don't see much point hacking up postgres when the set of fields & semantics are still (somewhat) in flux. (Well, yjs might be more ready for this work - but its probably still a good idea to wait until yjs's rust port (yrs) is done). [1] It'd work fine the way my own CRDT (diamond types) is designed, since DT just needs to store the "origin positions" of each change. In Yjs and Automerge, changes store references to the ID of the item to the immediate left. In order to generate those changes, both automerge and yjs need to look up those persistent IDs - which in practice means they need to load the document state into memory first.

alephnan 5y ago

For context, one of the main motivations for CRDT was multiple users simultaneously editing some document. E.G. Google Docs. I was researching these approaches when I was implementing my own collaborative text editor. CRDT was too mathematically steep for me. Another approach is differential syncing. I think Google Docs was originally implemented with differential syncing and then switched to CRDT. https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/35605.pdf https://static.googleusercontent.com/media/research.google.c... I think the tradeoff and why I leaned towards differential syncing was that the implementation was easier. There are some gaps / unclear implementation details in this white paper's algorithm that you kind of have to rediscover yourself, because if you followed the algorithm listed here it will not work. I forgot the details. I'm still not sure if that was intentional. I hope now the literature on CRDT has gotten more mainstream and digestible for non-mathematicians because that seems like the future.

thesz 5y ago
From what I know, Google Docs never used CRDT. They adopted Google Wave's algorithm which was taken from Jupiter UI system [1]: operational transformations [2] with conflict resolution on the server side. [1] https://svn.apache.org/repos/asf/incubator/wave/whitepapers/operational-transform/operational-transform.html https://svn.apache.org/repos/asf/incubator/wave/whitepapers/... [2] https://en.wikipedia.org/wiki/Operational_transformation https://en.wikipedia.org/wiki/Operational_transformation When the server does ordering operation, operational transformations became a piece of cake to implement and reason about. If you add hierarchical addressing like "book/chapter/section/subsection/paragraph/char", they are also quite conflict free. But you need a central authority. In case of Google, it is easy and fits the profit model. Bonus: https://code.google.com/archive/p/google-mobwrite/ https://code.google.com/archive/p/google-mobwrite/ A library to collaboratively edit HTML forms.

LAC-Tech 5y ago

I've read a couple of CRDT papers but never used them in anger. (Zero interest in collaborative text editing, but a lot of interests in multi-master systems involving local databases that lose internet connectivity). Anyone have any good war stories? The general impression I get is that anything more than a state delta two-phase set is an open research problem to implement efficiently - the papers make it sound pretty straight forward but there's a whole garbage collection problem to deal with, there was another research paper dealing with just that IIRC.

andy_ppp 5y ago
Chris McCord had fun implementing a CRDT in Phoenix.Presence: https://www.youtube.com/watch?v=XJ9ckqCMiKk https://www.youtube.com/watch?v=XJ9ckqCMiKk (from about 17 mins by the looks of things).
vmaurin 5y ago
Maybe somebody from soundcloud ? https://developers.soundcloud.com/blog/roshi-a-crdt-system-for-timestamped-events https://developers.soundcloud.com/blog/roshi-a-crdt-system-f...
celeritascelery 5y ago
Raph Levien had a good post about using CRDTs for text editing. He feels they didn’t live up to his expectations. https://raphlinus.github.io/xi/2020/06/27/xi-retrospective.html https://raphlinus.github.io/xi/2020/06/27/xi-retrospective.h...
kevinjahns 5y ago
It's interesting to me that people still doubt that CRDTs can be used in practice. The fact is that they are already being used in practice by many companies with millions of users for applications like rich-text editing and state management in 3d applications. See https://github.com/yjs/yjs#who-is-using-yjs https://github.com/yjs/yjs#who-is-using-yjs In fact, Yjs - a CRDT implementation- is the most downloaded solution for collaborative applications. Even more than ShareDB (the most popular OT-based solution). Yjs ~90k/week - https://www.npmjs.com/package/yjs https://www.npmjs.com/package/yjs ShareDB ~13k/week - https://www.npmjs.com/package/yjs https://www.npmjs.com/package/yjs

samatman 5y ago

Is anyone working on a CRDT system using pijul patches and merge strategy? The "Replicated Data Type" part of CRDTs seems to be a solved problem, making "Conflict-Free" give results that are as close to what the user would expect as is theoretically possible would appear to be the hard part.

euroderf 5y ago
I'm hoping that one of these days, pijul will compile on Mac. Or that they will distribute a Mac binary.
- andai 5y ago
  You can get it in 3 lines (apparently, don't have a Mac handy right now). brew install llvm libsodium openssl xxhash zstd curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh cargo install pijul --version "~1.0.0-alpha" But yeah, I can see how that might hurt adoption.
  - euroderf 5y ago
    I reinstalled rust per your line 2 but the build still failed. Oh well.
    - pmeunier 5y ago
      There are so many ways to ask for help about that: - https://pijul.zulipchat.com https://pijul.zulipchat.com - https://discourse.pijul.org https://discourse.pijul.org - https://nest.pijul.com/pijul/pijul/discussions/new https://nest.pijul.com/pijul/pijul/discussions/new if the failure is in Pijul itself and not in one of its dependencies. And even on Twitter (@pijul_org)!
      - euroderf 5y ago
        It also barfed on my wife's Mac (which has not been loaded with a mish-mash of development stuff), so I give up. If nobody else is reporting the same problems as I'm having then I guess it's just that I'm having a bad hair year.

yonz 5y ago

Lots of the comments here seem to be about why do you need CRDT when so many solutions can solve collaborative text editing. The biggest bang is for de-centralization or edge based storage similar idea to @josephg (personal computing). Imagine taking multiple hours provisioning your personal compute with all your data and stream the diff across your devices and having an internet that runs off your devices. This would finally allow for a multi device local-first experience (https://www.inkandswitch.com/local-first/ https://www.inkandswitch.com/local-first/) where your phone streams the changes to your data while you were on your flight to your desktop and at a bigger scale entire facebook/google data store is a streaming system with auto-merge instead of a focus on ACID DB structures and coherence. Hands down Martin Kleppmann (Author of data intensive applications) is the biggest fan of CRDTs and this page has a lot of great info https://martin.kleppmann.com/2020/07/06/crdt-hard-parts-hydra.html https://martin.kleppmann.com/2020/07/06/crdt-hard-parts-hydr...

jFriedensreich 5y ago

the crux of crdts is for solutions that don't want to use central always online sync backends, have a need to merge deep history not just pick a winner of a global latest state but are ok with losing some conflicting detailed information stored inside your data. - if you can just pick a global winner for the object/document after diverging histories/ conflicts its much simpler to just pick a latest win strategy especially for simple data - if you cannot lose conflicting detail information, crdts will not solve your problems and you most probably need to implement application specific conflict resolution. an example is someone renaming a todo from "create invoice summary 2019" to "create latest invoice summary 2023" and at the same time someone else setting the "create invoice summary 2019" as done. a crdt can consistently merge the changes but you might end up with a todo that is set to done and is called "create latest invoice summary 2023" which is a wrong result

lgessler 5y ago

How do CRDTs work with denormalized data, or more generally, data where some fields have invariants that must be maintained between them? Let's say we have an object with an array of strings and a count of that array: { "words": ["a", "b", "c"], "count": 3 } Now suppose users A and B edit the document so that one word is deleted, and two words are added, respectively: { "words": ["a", "b"], "count": 2 } { "words": ["a", "b", "c", "d", "e"], "count": 5 } What probably should happen now is that we reach the state where `words` is `["a", "b", "d", "e"]` and `count` is `4`, but is that really what would happen? That would require the CRDT to understand changes to `count` as increment/decrement operations, but aren't there also situations where you'd simply want one of the two values to win?

enkrs 5y ago
Yes, it would work if you implement the schema correctly: among the standard value types there are also counter types. See for example https://automerge.org/docs/types/counters/ https://automerge.org/docs/types/counters/
greiskul 5y ago
I think with CRDT's you wouldn't just have an integer type. You would have to choose your int type acording to the operations you would want done for it. So it could be declared as a "register" crdt, in which case the semantics would be of set and override, or it could be declared as a counter, with semantics of increment/decrement.