4 ms·

IMO one of great things that came out of NoSQL are CRDTs[1]. This is something that would be interesting to see if it could work with a relational database. [1

by takeda 10y ago

IMO one of great things that came out of NoSQL are CRDTs[1]. This is something that would be interesting to see if it could work with a relational database. [1] https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type https://en.wikipedia.org/wiki/Conflict-free_replicated_data_...

naasking 10y ago
Concurrent Revisions [1] are even better IMO. Much simpler to reason about. In fact, if you know how to work with git and other distributed SCM tools, then you already understand the model: branch, do your work locally, then deterministic merge. [1] http://research.microsoft.com/en-us/projects/revisions/ http://research.microsoft.com/en-us/projects/revisions/
- Jweb_Guru 10y ago
  Yes, I just found out about these recently and am surprised no datastores have been built around them. They are basically a usable version of fork-join causal consistency. They also subsume CRDTs.
  - naasking 10y ago
    Do they? The papers on CRDTs I've skimmed often mention concurrent revisions, but they've never claimed CR subsume CRDTs.
    - Jweb_Guru 10y ago
      This paper does (in fact, it points out that any total function can be emulated by a query-update automaton, which can be used with concurrent revisions). At least, that's my recollection, it could be a generalization of CR.
      - naasking 10y ago
        What is the "this paper" you're referring to? The papers at the link I provided don't mention CRDTs much.
        Jweb_Guru 10y ago
        http://research.microsoft.com/pubs/155638/msr-tr-2011-117%282%29.pdf http://research.microsoft.com/pubs/155638/msr-tr-2011-117%28...: "Our definition is strictly more general than CRDTs [17] in the following sense: From any state-based CRDT we can obtain a FJ-QUA by using the same state and initial state, the same query and update functions, a fork function that creates a new replica and then merges the forker state, and a join function that uses the merge. Note that the definition of strong eventual consistency in [17], just like ours, requires that updates can be applied to any state."
        jacques_chester 10y ago
        > Note that the definition of strong eventual consistency in [17], just like ours, requires that updates can be applied to any state. My favourite gotcha. It solves distributed statefulness! ... so long as someone else solves statefulness!
        naasking 10y ago
        I don't think that's a fair summary. Stateful cells have non-local and non-commutative evolution, which is why they're hard to distribute. These frameworks eliminate the non-locality, which isn't negotiable if you want to scale, but at the expense of preserving the requirement that you manually ensure commutativity. Not a bad tradeoff, and I highly recommend the CR papers if you haven't read them. I'd say most programs have a natural expression in terms of revisions, and you're left with only a small set of circumstances where state simply must evolve consistently and atomically (airplane seat reservations, for instance). I would still like a framework for reasoning about these circumstances that integrates naturally with CR though.

by takeda 10y ago

naasking 10y ago

Concurrent Revisions [1] are even better IMO. Much simpler to reason about. In fact, if you know how to work with git and other distributed SCM tools, then you already understand the model: branch, do your work locally, then deterministic merge. [1] http://research.microsoft.com/en-us/projects/revisions/ http://research.microsoft.com/en-us/projects/revisions/

Jweb_Guru 10y ago
Yes, I just found out about these recently and am surprised no datastores have been built around them. They are basically a usable version of fork-join causal consistency. They also subsume CRDTs.
- naasking 10y ago
  Do they? The papers on CRDTs I've skimmed often mention concurrent revisions, but they've never claimed CR subsume CRDTs.
  - Jweb_Guru 10y ago
    This paper does (in fact, it points out that any total function can be emulated by a query-update automaton, which can be used with concurrent revisions). At least, that's my recollection, it could be a generalization of CR.
    - naasking 10y ago
      What is the "this paper" you're referring to? The papers at the link I provided don't mention CRDTs much.
      - Jweb_Guru 10y ago
        http://research.microsoft.com/pubs/155638/msr-tr-2011-117%282%29.pdf http://research.microsoft.com/pubs/155638/msr-tr-2011-117%28...: "Our definition is strictly more general than CRDTs [17] in the following sense: From any state-based CRDT we can obtain a FJ-QUA by using the same state and initial state, the same query and update functions, a fork function that creates a new replica and then merges the forker state, and a join function that uses the merge. Note that the definition of strong eventual consistency in [17], just like ours, requires that updates can be applied to any state."
        jacques_chester 10y ago
        > Note that the definition of strong eventual consistency in [17], just like ours, requires that updates can be applied to any state. My favourite gotcha. It solves distributed statefulness! ... so long as someone else solves statefulness!
        naasking 10y ago
        I don't think that's a fair summary. Stateful cells have non-local and non-commutative evolution, which is why they're hard to distribute. These frameworks eliminate the non-locality, which isn't negotiable if you want to scale, but at the expense of preserving the requirement that you manually ensure commutativity. Not a bad tradeoff, and I highly recommend the CR papers if you haven't read them. I'd say most programs have a natural expression in terms of revisions, and you're left with only a small set of circumstances where state simply must evolve consistently and atomically (airplane seat reservations, for instance). I would still like a framework for reasoning about these circumstances that integrates naturally with CR though.