3 ms·

One of their supported storage primitives is CRDT-based, according to [1]. I, for one, am really interested to see how this works in practice. I've been quite e

One of their supported storage primitives is CRDT-based, according to [1]. I, for one, am really interested to see how this works in practice. I've been quite excited about CRDTs, but haven't seen enough examples of them in the wild to get a sense of their drawbacks — for instance, how difficult it is to use them to model various processes or data structures. [1] https://twitter.com/adrianco/status/476843040330743809 https://twitter.com/adrianco/status/476843040330743809

platz 12y ago
Do you know of a resource for learning the basics CRDTs that doesn't require a PHD?
- seiji 12y ago
  The name is intimidating, but the operations are simple. Basically, your storage has container types ("T"). A list, a set, a dictionary, etc. Container types can be split and added together in a distributed fashion ("R" and "D"). The "C" in CRDT stands for "Convergent and Commutative" to imply your distributed operations can obtain the same value when merged. Quick example: If you have a node with a key pointing to value (set) [a, b, c] and another node with the same key but different value [c, e, f], then when the nodes communicate, they can do a set union for the actual result of [a, b, c, e, f]. Keys can keep a running log of recent operations to clean up the global result too (like: [c, e, (recently deleted f)], so on merge, if the other list has f, it would be deleted instead of re-added). Before CRDTs were a thing, Bob made state box and it's very easy to understand. Give the README a read to understand more basics: https://github.com/mochi/statebox https://github.com/mochi/statebox
  - platz 12y ago
    That's helpful, thanks (I've downloaded some crdt videos to watch in the meantime). At the surface they sound like something vaguely resembling an abelian group (+/- inverses), but the conflict resolution stuff is the heart of it I'd guess.
    - spiralganglion 12y ago
      Yes, from my (limited but growing) understanding of it, they are indeed similar to abelian groups.
      - noelwelsh 12y ago
        CRDTs are, in the basic case, a idempotent commutative monoid, aka an idempotent abelian monoid. If this floats your boat, here's me on CRDTs: https://skillsmatter.com/skillscasts/5301-convergent-replicated-data-types https://skillsmatter.com/skillscasts/5301-convergent-replica...
        ryanobjc 12y ago
        I don't think you understand the word basic... CRDTs wont have mainstream success until people stop using the words 'monoid' and 'abelian' etc. Most programmers aren't required to learn this kind of math in a CS degree, AND furthermore, many programmers dont have a CS degree/forgot it. So the question is, are CRDTs a useful technique for all developers, or just a way for a minute few to demonstrate their ability to sling around math words?
        noelwelsh 12y ago
        Did you read the thread? The parents were using terms from abstract algebra, so I replied using the same language. In another context I would have avoided those terms and perhaps used an explanation like this: http://noelwelsh.com/programming/2013/12/20/crdts-for-fun-and-eventual-profit/ http://noelwelsh.com/programming/2013/12/20/crdts-for-fun-an...
- dahjelle 12y ago
  Aral Balkan gave a talk[1] describing WOOT, a CRDT for collaborative editing. Best intro to the idea of how a more complex CRDT works that I've seen. (Really only the last 8 minutes or so are about WOOT. The rest is why he chose it.) [1] https://www.youtube.com/watch?v=NSTZ4mIv_wk https://www.youtube.com/watch?v=NSTZ4mIv_wk
- msrivas 12y ago
  I found this to be really useful - http://research.microsoft.com/apps/video/default.aspx?id=153540&r=1 http://research.microsoft.com/apps/video/default.aspx?id=153...
trhway 12y ago
it seems that CRDT are just another face, or an implementation, of the CALM : http://www.bloom-lang.net/calm/ http://www.bloom-lang.net/calm/ "Informally, a block of code is logically monotonic if it satisfies a simple property: adding things to the input can only increase the output. " http://db.cs.berkeley.edu/papers/cidr11-bloom.pdf http://db.cs.berkeley.edu/papers/cidr11-bloom.pdf " A sufficient condition for eventual consistency is order independence ..."

platz 12y ago

Do you know of a resource for learning the basics CRDTs that doesn't require a PHD?

seiji 12y ago
The name is intimidating, but the operations are simple. Basically, your storage has container types ("T"). A list, a set, a dictionary, etc. Container types can be split and added together in a distributed fashion ("R" and "D"). The "C" in CRDT stands for "Convergent and Commutative" to imply your distributed operations can obtain the same value when merged. Quick example: If you have a node with a key pointing to value (set) [a, b, c] and another node with the same key but different value [c, e, f], then when the nodes communicate, they can do a set union for the actual result of [a, b, c, e, f]. Keys can keep a running log of recent operations to clean up the global result too (like: [c, e, (recently deleted f)], so on merge, if the other list has f, it would be deleted instead of re-added). Before CRDTs were a thing, Bob made state box and it's very easy to understand. Give the README a read to understand more basics: https://github.com/mochi/statebox https://github.com/mochi/statebox
- platz 12y ago
  That's helpful, thanks (I've downloaded some crdt videos to watch in the meantime). At the surface they sound like something vaguely resembling an abelian group (+/- inverses), but the conflict resolution stuff is the heart of it I'd guess.
  - spiralganglion 12y ago
    Yes, from my (limited but growing) understanding of it, they are indeed similar to abelian groups.
    - noelwelsh 12y ago
      CRDTs are, in the basic case, a idempotent commutative monoid, aka an idempotent abelian monoid. If this floats your boat, here's me on CRDTs: https://skillsmatter.com/skillscasts/5301-convergent-replicated-data-types https://skillsmatter.com/skillscasts/5301-convergent-replica...
      - ryanobjc 12y ago
        I don't think you understand the word basic... CRDTs wont have mainstream success until people stop using the words 'monoid' and 'abelian' etc. Most programmers aren't required to learn this kind of math in a CS degree, AND furthermore, many programmers dont have a CS degree/forgot it. So the question is, are CRDTs a useful technique for all developers, or just a way for a minute few to demonstrate their ability to sling around math words?
        noelwelsh 12y ago
        Did you read the thread? The parents were using terms from abstract algebra, so I replied using the same language. In another context I would have avoided those terms and perhaps used an explanation like this: http://noelwelsh.com/programming/2013/12/20/crdts-for-fun-and-eventual-profit/ http://noelwelsh.com/programming/2013/12/20/crdts-for-fun-an...
dahjelle 12y ago
Aral Balkan gave a talk[1] describing WOOT, a CRDT for collaborative editing. Best intro to the idea of how a more complex CRDT works that I've seen. (Really only the last 8 minutes or so are about WOOT. The rest is why he chose it.) [1] https://www.youtube.com/watch?v=NSTZ4mIv_wk https://www.youtube.com/watch?v=NSTZ4mIv_wk
msrivas 12y ago
I found this to be really useful - http://research.microsoft.com/apps/video/default.aspx?id=153540&r=1 http://research.microsoft.com/apps/video/default.aspx?id=153...

trhway 12y ago

it seems that CRDT are just another face, or an implementation, of the CALM : http://www.bloom-lang.net/calm/ http://www.bloom-lang.net/calm/ "Informally, a block of code is logically monotonic if it satisfies a simple property: adding things to the input can only increase the output. " http://db.cs.berkeley.edu/papers/cidr11-bloom.pdf http://db.cs.berkeley.edu/papers/cidr11-bloom.pdf " A sufficient condition for eventual consistency is order independence ..."