counter crdt in riak

David Byron dbyron at dbyron.com
Wed Oct 21 12:44:08 EDT 2015


Whoops...didn't mean to drop the mailing list off the recipient list.

Pull request here: https://github.com/basho/basho_docs/pull/1865.

-DB

On 10/21/15 7:52 AM, David Byron wrote:
>
>
> On 10/20/15 11:56 PM, Russell Brown wrote:
>>
>> 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.
>
> The notion of something winning (and therefore also something losing) is
> I think the thing that confuses me.  The way I think of it, everybody
> wins.  It's almost like there aren't any conflicts to resolve.
>
>>> 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.
>
> Thanks for the detailed explanation.
>
>>> 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.
>
> Will do.
>
> -DB




More information about the riak-users mailing list