search

basho / riak_dt

Convergent replicated datatypes in Erlang
Apache License 2.0
353 stars 70 forks source link

Explore an interface for mapping between CRDTs. #70

Closed cmeiklejohn closed 9 years ago

cmeiklejohn commented 10 years ago

What I'm looking at integrating is keys, that are derived from each other in Riak KV; for instance, I could have a counter key, and specified in the metadata, have any updates to it propogate to another key which is a boolean key based on a particular predicate.

This would allow for things like counters derived on the size of grow-only sets, booleans derived from counters, etc.

Purely a prototype; just wanted to start the conversation.

@russelldb @seancribbs

seancribbs commented 10 years ago

Like monotone functions, essentially?

russelldb commented 10 years ago

Sorry, I didn't close it, I just tapped my mouse for focus and github reloaded the content in the background and put the close button under my pointer. Re-opened.

russelldb commented 10 years ago

Anyway, I'm thinking if you want to Map one CRDT to another, they need to be co-located at a key. Compose them together in a riak_dt_map and add a local invariant or mapping between elements in the composition. That way you're getting a derived value that is always going to be "correct" in single replica sense without adding machinery to Riak.

cmeiklejohn commented 10 years ago

Interesting, I didn't think about it this way.

I guess in the case I was imagining, the derived value would be in a separate key to allow for getting that value, when getting all of the data for the other value was not needed. If you can pull the entire map down and run the function yourself, why even bother having the derived value as the derived value is usually an optimization?

russelldb commented 10 years ago

So once calculated this mapped value would never change? Your implementation requires both values to calculate a value. If the mapped value never changes it suggests that the inputs cant "go backwards" as it were. A lot like the bloom/l paper. In that case I think its useful to save a client repeatedly deriving a value that will never change. If riak did this automatically it would approximate an LVar threshold read.

seancribbs commented 10 years ago

Assigning to 2.1 so we can explore these ideas later.

cmeiklejohn commented 9 years ago

Closing.