5 ms·

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 t

by 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/
  - anecd0te 5y ago
    I don't think this comment makes much sense, arbitrary unicode text is very different than JSON. What application domain are you talking about?
- 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.

by ibash 5y ago

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/
- anecd0te 5y ago
  I don't think this comment makes much sense, arbitrary unicode text is very different than JSON. What application domain are you talking about?
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.