counter crdt in riak

Russell Brown russell.brown at me.com
Wed Oct 21 02:56:02 EDT 2015


On 21 Oct 2015, at 04:56, David Byron <dbyron at dbyron.com> wrote:

> Apologies if this is basic question, or one that's already been answered.  I've done a fair amount of digging (e.g. http://thread.gmane.org/gmane.comp.db.riak.user/12808/focus=12816), but I'm still confused about the documentation regarding conflict resolution for riak's crdt counter.  Specifically this: https://github.com/basho/basho_docs/blame/riak/2.1.1/source/languages/en/riak/theory/concepts/crdts.md#L238 (using the blame view to get a line number reference in markdown), which says:
> 
> "Counters | Each actor keeps an independent count for increments and decrements; upon merge, the pairwise maximum of the counts for each actor will win (e.g. if one count for an actor holds 172 and the other holds 173, 173 will win upon merge)"
> 
> This makes it sound to me like an increment from one of the actors gets dropped.  Fingers crossed this isn't actually what happens.

How so? I guess the implicit information missing from the statement is that each actor is unique, and acts serially. “An independent count for increments and decrements” means two integers, one for increments, one for decrements.

> 
> I think this is saying the same thing that the cdrt paper (section 3.1.2 State-based increment-only Counter (G-Counter) of https://hal.inria.fr/file/index/docid/555588/filename/techreport.pdf) says -- that increments that happen during a partition eventually resolve correctly.  I could use a more step-by-step illustration though -- pairwise maximum of the counts for each actor is a little dense.

Imagine the counter as a vector of triples, {ActorName, Increment Count, Decrement Count}
Imagine 2 nodes A, C as replicas. A increments it’s counter by 1 so the data looks like [{A, 1, 0}]
C decrements it’s counter, so it’s data is [{C, 0, 1}]
A sends it’s counter to C so C performs a Merge. It looks at each entry in the vector, and for each entry takes the maximum Increment and maximum Decrement and keeps them. If an Actor is not present in some vector, it’s counters are considered zero. That is the “pairwise maximum.” For any pair of vectors, take the maximum integers for any pair of entries (i.e. {A, 1, 0} compared to {A, 0, 0} = {A, max(1, 0), max(0, 0})
So now C has [{A, 1, 0}, {C, 0, 1}]
Now C does an increment [{A, 1, 0}, {C, 1, 1}] and sends it’s counter to A
A increments it’s counter by 1 [{A, 2, 0}] then decrements it by 1 [{A, 2, 1}]
C sends it’s counter to A and the merge results in [{A, 2, 1}, {C, 1, 1}]

Any actor will _always_ have the maximum values for their own entries.

> 
> Apologies for ugly formatting, but an example like this would make more sense to me.
> 
> - actor a increments counter
>  a {a: 1}                   b {}
> 
> - actor b increments counter
>  a {a: 1}                   b {b: 1}
> 
> - a merges b's info
>  a {a: 1, b: 1}             b {b: 1}
> 
> - b merges a's info
>  a:{a: 1, b: 1}             b {a: 1, b: 1}
> 
> so eventually this all resolves such that a and b both increment the counter by 2, right?  Is this how riak's crdt counter works?  If so I'll breathe a sigh of relief and make a pull request against the docs if you like.

Yes that’s how they work, but there are two integers per actor, one for increments and one for decrements. Please do make your pull request.

Cheers

Russell

> 
> Thanks much for your help.
> 
> -DB
> 
> _______________________________________________
> riak-users mailing list
> riak-users at lists.basho.com
> http://lists.basho.com/mailman/listinfo/riak-users_lists.basho.com





More information about the riak-users mailing list