Hacker News Reader

Comment by boothead | Hacker News Reader

> The tl;dr on CRDTs is that by constraining your operations to only those which are associative, commutative, and idempotent.

Interesting. We have an event stream database implemented in Haskell, and this looks like an excellent way to index it. Especially associative, commutative and idempotent can (probably) all be encoded in the type system!

View on HN

Interesting, I have seen CRDTs mostly in the Erlang context (monitoring and following works Basho has been doing for Riak).

Basically a lot of this:

http://basho.com/tag/crdt

But using Haskell's type system is an interesting idea.

You can start with one level higher than just looking for associative, commutative and idempotent, because that actually comes the definition of a semilattice

http://en.wikipedia.org/wiki/Semilattice

The crucial part is that you have an appropriate meet or join operator (and that it satisfies the above requirements).

Informally think of a functions like max() over natural numbers or a union() over sets. Those are some examples.

I don't know Haskell but found this interesting gist of someone who has tried this, and frankly a lot of stuff there is above my head, but it might help you:

https://gist.github.com/pozorvlak/6540639

That is interesting (but also sadly over my head too).

I think some of the theory there is starting to get into operational transformation territory [1]. If that's the case then a really interesting application might be applying the same semantics indexing a stream of events to expressing events as a diff against state and propagating them to clients...

[1] http://en.wikipedia.org/wiki/Operational_transformation

You probably want to look at LVish, is you want to see what this looks like in haskell.

http://www.cs.indiana.edu/~lkuper/

Has tons of papers and

https://hackage.haskell.org/package/lvish

is the lib.

This is definitely aligned with OT. OT typically comes in two steps—merge and simplify. Merge takes two divergent histories and puts them together into a collective view. Simplify takes that collective view and reduces it to a single "consistent" view according to domain rules.

With CRDTs the merge operation is made such that the simplify operation is id.

It's also interesting to note that the merge operation is just a pullback in the appropriate category.

I've never used it, but there is a lattice package on hackage which provides typeclasses for semilattices:

http://hackage.haskell.org/package/lattices-1.2.1/docs/Algeb...

It's an idempotent commutative monoid, so you can encode that quite straightforwardly as a type class.

Twitter's Algebird[1] has a wide range of monoid implementations (in Scala). It's a surprisingly useful type class for something so simple.

I have a talk[2] and some code [3] that goes into more detail on CRDTs and the connection to monoids.

[1:] https://github.com/twitter/algebird

[2:] http://noelwelsh.com/programming/2013/12/20/crdts-for-fun-an...

[3:] https://github.com/noelwelsh/crdt

It's only a monoid if there's an identity.

Thanks Noel, I had seen algebird before - it looks great!

They can be tested with quickcheck as well: http://yellerapp.com/posts/2014-05-08-testing-riak.html

Relevant work I've done in the past:

http://christophermeiklejohn.com/coq/2013/06/11/distributed-...

Also, see related papers from PaPEC '14:

http://dl.acm.org/citation.cfm?id=2596631

Cool, what's your database?

Reply on news.ycombinator.com