serialized vector clock as global counter?

[Toby DiPasquale <to...@cbcg.net>]

Hi all,

I'm trying to write an application using Cassandra which requires the
use of a global, monotonically-increasing counter. I've seen the
previous threads on this subject which basically say that this can't
be done in Cassandra as is, but I think I've come up with a method
that might work. I wanted to get the list's feedback on whether or not
this method is workable:

* Each client maintains its own monotonically-increasing counter as a
row in Cassandra
* When a client wants to increment the counter, it will:
  * increment its own counter key using a quorum write
  * read all keys in the CF using a quorum read
  * the sum of the values is then the value of the counter

This method is robust against nodes coming and going (new nodes just
get a new counter and dead nodes never increase their counter again).
It also doesn't matter for my application if some possible values for
the counter are skipped over, as long as every value is greater than
the last. I believe this scheme to be commensurate to a vector clock,
no?

My question would be: assuming we're using both quorum reads and
writes, is it possible that clients A and B could race in the
following manner:

* A updates its counter
* B updates its counter
* A reads the keys to get sum X
* B reads the keys to get the same sum X

...thus violating the ever-increasing constraint?

Google App Engine suggests a similar method for doing global counters
on Datastore: http://code.google.com/appengine/articles/sharding_counters.html.
I'm troubled by their implementation, though, because the reads on the
list of counters are not transactional and are potentially subject to
the same race that I've described above.

Any thoughts/ideas?

-- 
Toby DiPasquale

Re: serialized vector clock as global counter?

[Benjamin Black <b...@b3k.us>]

Whether or not it can be made to work, it seems a poor fit for
Cassandra.  Why not use Zookeeper?

On Sun, Mar 14, 2010 at 9:46 AM, Toby DiPasquale <to...@cbcg.net> wrote:
> Hi all,
>
> I'm trying to write an application using Cassandra which requires the
> use of a global, monotonically-increasing counter. I've seen the
> previous threads on this subject which basically say that this can't
> be done in Cassandra as is, but I think I've come up with a method
> that might work. I wanted to get the list's feedback on whether or not
> this method is workable:
>
> * Each client maintains its own monotonically-increasing counter as a
> row in Cassandra
> * When a client wants to increment the counter, it will:
>  * increment its own counter key using a quorum write
>  * read all keys in the CF using a quorum read
>  * the sum of the values is then the value of the counter
>
> This method is robust against nodes coming and going (new nodes just
> get a new counter and dead nodes never increase their counter again).
> It also doesn't matter for my application if some possible values for
> the counter are skipped over, as long as every value is greater than
> the last. I believe this scheme to be commensurate to a vector clock,
> no?
>
> My question would be: assuming we're using both quorum reads and
> writes, is it possible that clients A and B could race in the
> following manner:
>
> * A updates its counter
> * B updates its counter
> * A reads the keys to get sum X
> * B reads the keys to get the same sum X
>
> ...thus violating the ever-increasing constraint?
>
> Google App Engine suggests a similar method for doing global counters
> on Datastore: http://code.google.com/appengine/articles/sharding_counters.html.
> I'm troubled by their implementation, though, because the reads on the
> list of counters are not transactional and are potentially subject to
> the same race that I've described above.
>
> Any thoughts/ideas?
>
> --
> Toby DiPasquale
>

Re: serialized vector clock as global counter?

[Toby DiPasquale <to...@cbcg.net>]

On Sun, Mar 14, 2010 at 6:37 PM, Dwight Merriman <dw...@10gen.com> wrote:
> yes - take a look at this app engine blog post:
>
> http://googleappengine.blogspot.com/2009/09/migration-to-better-datastore.html
>
> if i read this correctly, app engine data store is pretty much in the
> "strongly consistent" camp while cassandra is more eventually consistent --
> so really quite different.  you would get higher availability on an EC
> system but atomic updates become quite hard (at least when fully
> generalized)

I get that GAE Datastore is more in the strongly consistent camp, but
my proposal specified quorum reads and writes, also bringing it into
the strongly consistent camp, no?

-- 
Toby DiPasquale

Re: serialized vector clock as global counter?

[Dwight Merriman <dw...@10gen.com>]

yes - take a look at this app engine blog post:

http://googleappengine.blogspot.com/2009/09/migration-to-better-datastore.html

if i read this correctly, app engine data store is pretty much in the
"strongly consistent" camp while cassandra is more eventually consistent --
so really quite different.  you would get higher availability on an EC
system but atomic updates become quite hard (at least when fully
generalized)

On Sun, Mar 14, 2010 at 6:29 PM, Fred Wulff <fr...@stanford.edu> wrote:

> Hey Toby,
>
> I'm not an expert on Cassandra's infrastructure, but I believe the
> thing the AppEngine datastore has that Cassandra doesn't is a
> transaction between the read and write of a sharded counter. That
> means that while the read of the various counters may be inconsistent,
> the actual update of the shard is always consistent and the read of
> that shard is always consistent with the previous write.
>
> -Fred
>
> On Sun, Mar 14, 2010 at 9:46 AM, Toby DiPasquale <to...@cbcg.net> wrote:
> > Hi all,
> >
> > I'm trying to write an application using Cassandra which requires the
> > use of a global, monotonically-increasing counter. I've seen the
> > previous threads on this subject which basically say that this can't
> > be done in Cassandra as is, but I think I've come up with a method
> > that might work. I wanted to get the list's feedback on whether or not
> > this method is workable:
> >
> > * Each client maintains its own monotonically-increasing counter as a
> > row in Cassandra
> > * When a client wants to increment the counter, it will:
> >  * increment its own counter key using a quorum write
> >  * read all keys in the CF using a quorum read
> >  * the sum of the values is then the value of the counter
> >
> > This method is robust against nodes coming and going (new nodes just
> > get a new counter and dead nodes never increase their counter again).
> > It also doesn't matter for my application if some possible values for
> > the counter are skipped over, as long as every value is greater than
> > the last. I believe this scheme to be commensurate to a vector clock,
> > no?
> >
> > My question would be: assuming we're using both quorum reads and
> > writes, is it possible that clients A and B could race in the
> > following manner:
> >
> > * A updates its counter
> > * B updates its counter
> > * A reads the keys to get sum X
> > * B reads the keys to get the same sum X
> >
> > ...thus violating the ever-increasing constraint?
> >
> > Google App Engine suggests a similar method for doing global counters
> > on Datastore:
> http://code.google.com/appengine/articles/sharding_counters.html.
> > I'm troubled by their implementation, though, because the reads on the
> > list of counters are not transactional and are potentially subject to
> > the same race that I've described above.
> >
> > Any thoughts/ideas?
> >
> > --
> > Toby DiPasquale
> >
>

Re: serialized vector clock as global counter?

[Fred Wulff <fr...@stanford.edu>]

Hey Toby,

I'm not an expert on Cassandra's infrastructure, but I believe the
thing the AppEngine datastore has that Cassandra doesn't is a
transaction between the read and write of a sharded counter. That
means that while the read of the various counters may be inconsistent,
the actual update of the shard is always consistent and the read of
that shard is always consistent with the previous write.

-Fred

On Sun, Mar 14, 2010 at 9:46 AM, Toby DiPasquale <to...@cbcg.net> wrote:
> Hi all,
>
> I'm trying to write an application using Cassandra which requires the
> use of a global, monotonically-increasing counter. I've seen the
> previous threads on this subject which basically say that this can't
> be done in Cassandra as is, but I think I've come up with a method
> that might work. I wanted to get the list's feedback on whether or not
> this method is workable:
>
> * Each client maintains its own monotonically-increasing counter as a
> row in Cassandra
> * When a client wants to increment the counter, it will:
>  * increment its own counter key using a quorum write
>  * read all keys in the CF using a quorum read
>  * the sum of the values is then the value of the counter
>
> This method is robust against nodes coming and going (new nodes just
> get a new counter and dead nodes never increase their counter again).
> It also doesn't matter for my application if some possible values for
> the counter are skipped over, as long as every value is greater than
> the last. I believe this scheme to be commensurate to a vector clock,
> no?
>
> My question would be: assuming we're using both quorum reads and
> writes, is it possible that clients A and B could race in the
> following manner:
>
> * A updates its counter
> * B updates its counter
> * A reads the keys to get sum X
> * B reads the keys to get the same sum X
>
> ...thus violating the ever-increasing constraint?
>
> Google App Engine suggests a similar method for doing global counters
> on Datastore: http://code.google.com/appengine/articles/sharding_counters.html.
> I'm troubled by their implementation, though, because the reads on the
> list of counters are not transactional and are potentially subject to
> the same race that I've described above.
>
> Any thoughts/ideas?
>
> --
> Toby DiPasquale
>

Re: serialized vector clock as global counter?

[David Strauss <da...@fourkitchens.com>]

On 2010-03-15 00:57, Toby DiPasquale wrote:
> I'm actually just trying to build a little URL shortener to use as a
> demo for an upcoming presentation I'm doing on Cassandra. The counter
> is to be used as the short key for a new URL submitted to the system:
> increment the counter and then use the Base-62 encoding of that
> counter value as the key for that new URL. That's why I'm able to skip
> some values, but can't have any two clients reading the same value.

OK, so then counters shouldn't be managed in Cassandra at all. Each
server should have a prefix and its own counter, maintained entirely
locally. The "prefix" could be a character or as few bits as you need to
uniquely identify machines in your cluster.

When a server gets a URL to shorten and increments its counter, it
inserts the <prefix + counter, URL> item into Cassandra. I'm guessing
this would be with a row with the key <prefix + counter> and a single
column in the row storing the URL.

Any server translating a short URL to the full one queries Cassandra
with the combined <prefix + counter> key. It's irrelevant whether the
server that generated the original mapping is online or even existent
anymore.

My suggested approach avoids a slow read in Cassandra when storing each
URL and doesn't introduce any new SPOF. You lose a tiny bit of data
density, but I don't think it's significant.

If this were for a production system, I would use memcached as a
write-through cache to avoid reading from Cassandra. You could even use
memcached to maintain the counters. You'd have to be careful to avoid
re-using values on memcached restart or clearing, but there are many
ways to do that.

-- 
David Strauss
   | david@fourkitchens.com
Four Kitchens
   | http://fourkitchens.com
   | +1 512 454 6659 [office]
   | +1 512 870 8453 [direct]

Re: serialized vector clock as global counter?

[Toby DiPasquale <to...@cbcg.net>]

On Sun, Mar 14, 2010 at 7:47 PM, David Strauss <da...@fourkitchens.com> wrote:
> On 2010-03-14 16:46, Toby DiPasquale wrote:
>> My question would be: assuming we're using both quorum reads and
>> writes, is it possible that clients A and B could race in the
>> following manner:
>>
>> * A updates its counter
>> * B updates its counter
>> * A reads the keys to get sum X
>> * B reads the keys to get the same sum X
>>
>> ...thus violating the ever-increasing constraint?
>
> Yes. You'd need a cluster-wide lock to solve that problem, but then you
> may as well use that same cluster-wide locking mechanism to maintain the
> count.
>
> You'll get more interesting responses from this list if you share the
> original problem you're trying to solve instead of asking us how to
> implement a component of your chosen solution.

I'm actually just trying to build a little URL shortener to use as a
demo for an upcoming presentation I'm doing on Cassandra. The counter
is to be used as the short key for a new URL submitted to the system:
increment the counter and then use the Base-62 encoding of that
counter value as the key for that new URL. That's why I'm able to skip
some values, but can't have any two clients reading the same value.

-- 
Toby DiPasquale

Re: serialized vector clock as global counter?

[David Strauss <da...@fourkitchens.com>]

On 2010-03-14 16:46, Toby DiPasquale wrote:
> My question would be: assuming we're using both quorum reads and
> writes, is it possible that clients A and B could race in the
> following manner:
> 
> * A updates its counter
> * B updates its counter
> * A reads the keys to get sum X
> * B reads the keys to get the same sum X
> 
> ...thus violating the ever-increasing constraint?

Yes. You'd need a cluster-wide lock to solve that problem, but then you
may as well use that same cluster-wide locking mechanism to maintain the
count.

You'll get more interesting responses from this list if you share the
original problem you're trying to solve instead of asking us how to
implement a component of your chosen solution.

-- 
David Strauss
   | david@fourkitchens.com
Four Kitchens
   | http://fourkitchens.com
   | +1 512 454 6659 [office]
   | +1 512 870 8453 [direct]