You are viewing a plain text version of this content. The canonical link for it is here.
Posted to user@couchdb.apache.org by Benoit Chesneau <bc...@gmail.com> on 2014/01/29 14:48:10 UTC
distributed counters
Hi all,
I wonder if someone already thought to implement distributed counters using
couchdb? Or more exactly counters that follow these requirements:
- works over data replicated between different machine
- beeing updated with the last value even if the machine became offline.
- if a counter is {in/de}cremented on a replication the counter value on
the network should be updated with this increment on the next replication
-
I saw different solutions but I am none of them are really convincing:
1. At the application, have a script taking a doc value and incrementing it
then saving the doc with the new value. It doesn't really work with many
machines. A lot of concurrent updates can happen and it is a good way to
introduce a race condition.
2. Update the counter on one place, only when the machine is online.
3. Take one document maintaining a counter state.
ie we could have a tree maintaining decrement/increments so we could find
the conflicts
Only this doc would be updated and replicated. But we have still a possible
race condition
4. Put all the increments as standalone docs. And associate them to a
counter id. All the documents would be retrieved using a views:
emit(counterid, val)
And reduce them. I am seeing one problem with that: the value of the
counter is different on each machines. I am actually not sure it's a
problem.
5. making a combination of 3 and 4. A instant T a concensus document is
created with will collect the counter value on X machines using this
concensus doc will create an update tree or an LWW-Set or smth like it if
we follow the CRDT. once this doc has been created on each machines choosen
it is replicated.
I am not exactly sure about the details needed for 5 right now...
Anyway any feedback is welcome, let me know.
- benoit
Re: distributed counters
Posted by Simon Metson <si...@cloudant.com>.
On Wednesday, 29 January 2014 at 15:34, Benoit Chesneau wrote:
> On Wed, Jan 29, 2014 at 3:31 PM, Simon Metson <simon@cloudant.com (mailto:simon@cloudant.com)> wrote:
>
> > I started futzing around with a crdt-like counter a while back. Will dust
> > it off when I get a chance.
>
>
> Thanks! Which design did you choose? Using 1 doc to keep all the state?
> Anything else ?
>
Multiple docs (recording increments and decrements) and a view to calculate the sum for a given counter, with some client side logic. I think it’s the only way to have an available counter in a multiple node system. Incrementing a count on a single doc is going to result in conflicts, and potentially lost counts.
Cheers
Simon
Re: distributed counters
Posted by Benoit Chesneau <bc...@gmail.com>.
On Wed, Jan 29, 2014 at 3:31 PM, Simon Metson <si...@cloudant.com> wrote:
> I started futzing around with a crdt-like counter a while back. Will dust
> it off when I get a chance.
>
>
Thanks! Which design did you choose? Using 1 doc to keep all the state?
Anything else ?
- benoit
Re: distributed counters
Posted by Simon Metson <si...@cloudant.com>.
I started futzing around with a crdt-like counter a while back. Will dust it off when I get a chance.
On Wednesday, 29 January 2014 at 13:48, Benoit Chesneau wrote:
> Hi all,
>
> I wonder if someone already thought to implement distributed counters using
> couchdb? Or more exactly counters that follow these requirements:
>
> - works over data replicated between different machine
> - beeing updated with the last value even if the machine became offline.
> - if a counter is {in/de}cremented on a replication the counter value on
> the network should be updated with this increment on the next replication
> -
>
> I saw different solutions but I am none of them are really convincing:
>
> 1. At the application, have a script taking a doc value and incrementing it
> then saving the doc with the new value. It doesn't really work with many
> machines. A lot of concurrent updates can happen and it is a good way to
> introduce a race condition.
>
> 2. Update the counter on one place, only when the machine is online.
>
> 3. Take one document maintaining a counter state.
>
> ie we could have a tree maintaining decrement/increments so we could find
> the conflicts
>
> Only this doc would be updated and replicated. But we have still a possible
> race condition
>
> 4. Put all the increments as standalone docs. And associate them to a
> counter id. All the documents would be retrieved using a views:
>
> emit(counterid, val)
>
> And reduce them. I am seeing one problem with that: the value of the
> counter is different on each machines. I am actually not sure it's a
> problem.
>
>
> 5. making a combination of 3 and 4. A instant T a concensus document is
> created with will collect the counter value on X machines using this
> concensus doc will create an update tree or an LWW-Set or smth like it if
> we follow the CRDT. once this doc has been created on each machines choosen
> it is replicated.
>
> I am not exactly sure about the details needed for 5 right now...
>
>
> Anyway any feedback is welcome, let me know.
>
> - benoit
Re: distributed counters
Posted by Jens Alfke <je...@couchbase.com>.
On Jan 29, 2014, at 1:26 PM, Simon Metson <si...@cloudant.com> wrote:
> Thats fragile/brittle in a distributed system. Imagine you had a large number of conflicts, with a very complicated revision history - the simple merge isn’t practical.
How so? I'm not claiming it's the most practical system, but I don't see how it could lose data as long as the participants play fair (always adding new keys).
—Jens
Re: distributed counters
Posted by Simon Metson <si...@cloudant.com>.
On Wednesday, 29 January 2014 at 21:19, Jens Alfke wrote:
>
> On Jan 29, 2014, at 5:48 AM, Benoit Chesneau <bchesneau@gmail.com (mailto:bchesneau@gmail.com)> wrote:
>
> > I wonder if someone already thought to implement distributed counters using
> > couchdb?
>
>
>
> Quick and dirty idea: Implement the counter as a document storing a map from UUIDs to deltas (1 or -1). To modify the count, add a new UUID key whose value is the amount to increment/decrement by. The value of the counter is the sum of all the increment values. When there's a conflict, just merge together the two documents keeping all key/value pairs that occur in either map.
>
> You can store more info if you want by using something descriptive in place of the UUID, for example a username+timestamp. Just as long as it's guaranteed to be unique.
>
Thats fragile/brittle in a distributed system. Imagine you had a large number of conflicts, with a very complicated revision history - the simple merge isn’t practical. You need the inc/dec’s to be standalone documents and do the summing in the database via a view.
A similar pattern can work for sets, I think, but requires a more complex view, and possibly a bit more logic outside of the DB.
Cheers
Simon
Re: distributed counters
Posted by Jens Alfke <je...@couchbase.com>.
On Jan 29, 2014, at 5:48 AM, Benoit Chesneau <bc...@gmail.com> wrote:
> I wonder if someone already thought to implement distributed counters using
> couchdb?
Quick and dirty idea: Implement the counter as a document storing a map from UUIDs to deltas (1 or -1). To modify the count, add a new UUID key whose value is the amount to increment/decrement by. The value of the counter is the sum of all the increment values. When there's a conflict, just merge together the two documents keeping all key/value pairs that occur in either map.
You can store more info if you want by using something descriptive in place of the UUID, for example a username+timestamp. Just as long as it's guaranteed to be unique.
—Jens