You are viewing a plain text version of this content. The canonical link for it is here.
Posted to user@cassandra.apache.org by AJ <aj...@dude.podzone.net> on 2011/06/24 20:33:11 UTC
Concurrency: Does C* support a Happened-Before relation between processes'
writes?
Sorry, I know this is long-winded but I just want to make sure before I
go through the trouble to implement this since it's not something that
can be reliably tested and requires in-depth knowledge about C*
internals. But, this ultimately deals with concurrency control so
anyone interested in that subject may want to try and answer this. Thanks!
I would like to know how to do a series of writes and reads such that I
can tell definitively what process out of many was the first to create a
unique flag column.
IOW, I would like to have multiple processes (clients) compete to see
who is first to write a token column. The tokens start with a known
prefix, such as "Token_" followed by the name of the process that
created it and a UUID so that all columns are guaranteed unique and
don't get overwritten. For example, Process A could create:
Token_ProcA_<UUID>
and process B would create:
Token_ProcB_<UUID>
These writes/reads are asynchronous between the two or more processes.
After the two processes write their respective tokens, each will read
back all columns named "Token_*" that exist (a slice). They each do
this in order to find out who "won". The process that wrote the column
with the lowest timestamp wins. The purpose is to implement a lock.
I think all that is required is for the processes to use QUORUM
read/writes to make sure the final read is consistent and will assure
each process that it can rely on what's returned from the final read and
that there isn't an earlier write floating around somewhere. This is
where the "happened-before" question comes in. Is it possible that
Process A which writes it's token with a lower timestamp (and should be
the winner), that this write may not be seen by Process B when it does
it's read (which is after it's token write and after Process A wrote
it's token), and thus conclude incorrectly that itself (Process B) is
the winner since it will not see Process A's token? I'm 99% sure using
QUORUM read/writes will allow this to work because that's the whole
purpose, but I just wanted to double-check in case there's another
detail I'm forgetting about C* that would defeat this.
Thanks!
P.S. I realize this will cost me in performance, but this is only meant
to be used on occasion.
Re: Concurrency: Does C* support a Happened-Before relation between
processes' writes?
Posted by AJ <aj...@dude.podzone.net>.
On 6/24/2011 2:27 PM, Jonathan Ellis wrote:
> Might be able to do it with
> http://en.wikipedia.org/wiki/Lamport%27s_bakery_algorithm. "It is
> remarkable that this algorithm is not built on top of some lower level
> "atomic" operation, e.g. compare-and-swap."
>
I've been meaning to get back to reading that. Thanks for the reminder
Jonathan!
Re: Concurrency: Does C* support a Happened-Before relation between
processes' writes?
Posted by AJ <aj...@dude.podzone.net>.
On 6/25/2011 8:24 AM, Edward Capriolo wrote:
> I played around with the bakery algorithm and had ok success the
> challenges are most implementations assume an n size array of fixed
> clients and when you get it working it turns out to be a good number
> of cassandra ops to acquire your bakery lock.
>
I was thinking rather than making certain that there is a column
reserved for each node and having to keep it updated, you can just over
allocate a large number that would always be enough, like 100. A slice
of 100 byte-sized values shouldn't be a significant perf hit vs 3 or 4.
If you only have 3 nodes in your cluster and the last 97 go unused, that
would be ok; it would be as if those non-existent "customers" never take
a number.
For optimizing for C*, I think you can get away with minimal getSlices
for the loops. If you're lucky, you can fall through all of them using
the results from only 1 getSlice. Only if a process is "entering" or
has a higher priority number will you need to wait and then do another
getSlice and only a slice for the remaining columns. I think my logic
is correct; do you agree?
Did you have other problems other than performance?
Re: Concurrency: Does C* support a Happened-Before relation between
processes' writes?
Posted by Edward Capriolo <ed...@gmail.com>.
I played around with the bakery algorithm and had ok success the
challenges are most implementations assume an n size array of fixed
clients and when you get it working it turns out to be a good number
of cassandra ops to acquire your bakery lock.
On Saturday, June 25, 2011, AJ <aj...@dude.podzone.net> wrote:
> On 6/24/2011 2:27 PM, Jonathan Ellis wrote:
>
> Might be able to do it with
> http://en.wikipedia.org/wiki/Lamport%27s_bakery_algorithm. "It is
> remarkable that this algorithm is not built on top of some lower level
> "atomic" operation, e.g. compare-and-swap."
>
>
> This looks like it may work. Jonathan, have you guru's discussed this algorithm before and come to a consensus on it by chance?
>
Re: Concurrency: Does C* support a Happened-Before relation between
processes' writes?
Posted by AJ <aj...@dude.podzone.net>.
On 6/24/2011 2:27 PM, Jonathan Ellis wrote:
> Might be able to do it with
> http://en.wikipedia.org/wiki/Lamport%27s_bakery_algorithm. "It is
> remarkable that this algorithm is not built on top of some lower level
> "atomic" operation, e.g. compare-and-swap."
This looks like it may work. Jonathan, have you guru's discussed this
algorithm before and come to a consensus on it by chance?
Re: Concurrency: Does C* support a Happened-Before relation between
processes' writes?
Posted by Jonathan Ellis <jb...@gmail.com>.
Might be able to do it with
http://en.wikipedia.org/wiki/Lamport%27s_bakery_algorithm. "It is
remarkable that this algorithm is not built on top of some lower level
"atomic" operation, e.g. compare-and-swap."
On Fri, Jun 24, 2011 at 1:33 PM, AJ <aj...@dude.podzone.net> wrote:
> Sorry, I know this is long-winded but I just want to make sure before I go
> through the trouble to implement this since it's not something that can be
> reliably tested and requires in-depth knowledge about C* internals. But,
> this ultimately deals with concurrency control so anyone interested in that
> subject may want to try and answer this. Thanks!
>
>
> I would like to know how to do a series of writes and reads such that I can
> tell definitively what process out of many was the first to create a unique
> flag column.
>
> IOW, I would like to have multiple processes (clients) compete to see who is
> first to write a token column. The tokens start with a known prefix, such
> as "Token_" followed by the name of the process that created it and a UUID
> so that all columns are guaranteed unique and don't get overwritten. For
> example, Process A could create:
>
> Token_ProcA_<UUID>
>
> and process B would create:
>
> Token_ProcB_<UUID>
>
> These writes/reads are asynchronous between the two or more processes.
> After the two processes write their respective tokens, each will read back
> all columns named "Token_*" that exist (a slice). They each do this in
> order to find out who "won". The process that wrote the column with the
> lowest timestamp wins. The purpose is to implement a lock.
>
> I think all that is required is for the processes to use QUORUM read/writes
> to make sure the final read is consistent and will assure each process that
> it can rely on what's returned from the final read and that there isn't an
> earlier write floating around somewhere. This is where the
> "happened-before" question comes in. Is it possible that Process A which
> writes it's token with a lower timestamp (and should be the winner), that
> this write may not be seen by Process B when it does it's read (which is
> after it's token write and after Process A wrote it's token), and thus
> conclude incorrectly that itself (Process B) is the winner since it will not
> see Process A's token? I'm 99% sure using QUORUM read/writes will allow
> this to work because that's the whole purpose, but I just wanted to
> double-check in case there's another detail I'm forgetting about C* that
> would defeat this.
>
> Thanks!
>
> P.S. I realize this will cost me in performance, but this is only meant to
> be used on occasion.
>
--
Jonathan Ellis
Project Chair, Apache Cassandra
co-founder of DataStax, the source for professional Cassandra support
http://www.datastax.com
Re: Concurrency: Does C* support a Happened-Before relation between
processes' writes?
Posted by AJ <aj...@dude.podzone.net>.
On 6/24/2011 2:09 PM, Jim Newsham wrote:
> On 6/24/2011 9:28 AM, Yang wrote:
>> without a clear description of your pseudo-code, it's difficult to
>> say whether it will work.
>>
>> but I think it can work fine as an election/agreement protocol, which
>> you can use as a lock to some degree, but this requires
>> all the potential lock contenders to all participate, you can't grab
>> a lock before everyone has voiced their vote yet
>
> I agree with this statement. I think the issue is that the timestamps
> are generated by the clients and their clocks may not be in sync, so
> write A from client A might arrive with timestamp T, and write B from
> client B may reach the node later in time, however it may have an
> earlier timestamp (T', where T' < T). Client A may perform a read
> immediately after its write and notice that it was the only client to
> request a lock -- so it will assume it has acquired the lock. After
> Client B's lock request, it will perform a read and observe that it
> has written the request with the earliest timestamp -- so it will also
> assume it has acquired the lock, which would result in a failure of
> the locking scheme. If each client is required to wait for all other
> clients to "vote", then this issue goes away.
>
Yes, you both understand the problem. Hopefully we can find a solution
without relying on a hack and based on C* design that will be supported
in the future.
I'll be thinking on this some more. Thanks.
Re: Concurrency: Does C* support a Happened-Before relation between
processes' writes?
Posted by Jim Newsham <jn...@referentia.com>.
On 6/24/2011 9:28 AM, Yang wrote:
> without a clear description of your pseudo-code, it's difficult to say
> whether it will work.
>
> but I think it can work fine as an election/agreement protocol, which
> you can use as a lock to some degree, but this requires
> all the potential lock contenders to all participate, you can't grab a
> lock before everyone has voiced their vote yet
I agree with this statement. I think the issue is that the timestamps
are generated by the clients and their clocks may not be in sync, so
write A from client A might arrive with timestamp T, and write B from
client B may reach the node later in time, however it may have an
earlier timestamp (T', where T' < T). Client A may perform a read
immediately after its write and notice that it was the only client to
request a lock -- so it will assume it has acquired the lock. After
Client B's lock request, it will perform a read and observe that it has
written the request with the earliest timestamp -- so it will also
assume it has acquired the lock, which would result in a failure of the
locking scheme. If each client is required to wait for all other
clients to "vote", then this issue goes away.
I'm interested in the objectives of this thread as well, as I was
contemplating something similar. Any other ideas? :)
Jim
> . let's say the code is like
>
> lock(UUID) {
> write_column( "token_"+my_hostname()+"_"+UUID, getTimeStamp() );
> for all possible node N :
> block until ( token = read_column("token_" + N + "_" + UUID,
> getTimeStamp()) ) != null
>
> return "LOCKED" if my timestamp is the lowest among all nodes
> }
>
>
> you have to wait for all nodes to voice their timestamp because the
> timestamp in cassandra is client-generated, a latter node can create a
> column with an earlier
> timestamp.
>
> On Fri, Jun 24, 2011 at 11:33 AM, AJ <aj@dude.podzone.net
> <ma...@dude.podzone.net>> wrote:
>
> Sorry, I know this is long-winded but I just want to make sure
> before I go through the trouble to implement this since it's not
> something that can be reliably tested and requires in-depth
> knowledge about C* internals. But, this ultimately deals with
> concurrency control so anyone interested in that subject may want
> to try and answer this. Thanks!
>
>
> I would like to know how to do a series of writes and reads such
> that I can tell definitively what process out of many was the
> first to create a unique flag column.
>
> IOW, I would like to have multiple processes (clients) compete to
> see who is first to write a token column. The tokens start with a
> known prefix, such as "Token_" followed by the name of the process
> that created it and a UUID so that all columns are guaranteed
> unique and don't get overwritten. For example, Process A could
> create:
>
> Token_ProcA_<UUID>
>
> and process B would create:
>
> Token_ProcB_<UUID>
>
> These writes/reads are asynchronous between the two or more
> processes. After the two processes write their respective tokens,
> each will read back all columns named "Token_*" that exist (a
> slice). They each do this in order to find out who "won". The
> process that wrote the column with the lowest timestamp wins. The
> purpose is to implement a lock.
>
> I think all that is required is for the processes to use QUORUM
> read/writes to make sure the final read is consistent and will
> assure each process that it can rely on what's returned from the
> final read and that there isn't an earlier write floating around
> somewhere. This is where the "happened-before" question comes in.
> Is it possible that Process A which writes it's token with a
> lower timestamp (and should be the winner), that this write may
> not be seen by Process B when it does it's read (which is after
> it's token write and after Process A wrote it's token), and thus
> conclude incorrectly that itself (Process B) is the winner since
> it will not see Process A's token? I'm 99% sure using QUORUM
> read/writes will allow this to work because that's the whole
> purpose, but I just wanted to double-check in case there's another
> detail I'm forgetting about C* that would defeat this.
>
> Thanks!
>
> P.S. I realize this will cost me in performance, but this is only
> meant to be used on occasion.
>
>
Re: Concurrency: Does C* support a Happened-Before relation between
processes' writes?
Posted by Yang <te...@gmail.com>.
by "possible node N", I mean possible clients that will ever try to do the
locking
On Fri, Jun 24, 2011 at 12:28 PM, Yang <te...@gmail.com> wrote:
> without a clear description of your pseudo-code, it's difficult to say
> whether it will work.
>
> but I think it can work fine as an election/agreement protocol, which you
> can use as a lock to some degree, but this requires
> all the potential lock contenders to all participate, you can't grab a lock
> before everyone has voiced their vote yet
> . let's say the code is like
>
> lock(UUID) {
>
> write_column( "token_"+my_hostname()+"_"+UUID, getTimeStamp() );
> for all possible node N :
> block until ( token = read_column("token_" + N + "_" + UUID,
> getTimeStamp()) ) != null
>
> return "LOCKED" if my timestamp is the lowest among all nodes
> }
>
>
> you have to wait for all nodes to voice their timestamp because the
> timestamp in cassandra is client-generated, a latter node can create a
> column with an earlier
> timestamp.
>
>
> On Fri, Jun 24, 2011 at 11:33 AM, AJ <aj...@dude.podzone.net> wrote:
>
>> Sorry, I know this is long-winded but I just want to make sure before I go
>> through the trouble to implement this since it's not something that can be
>> reliably tested and requires in-depth knowledge about C* internals. But,
>> this ultimately deals with concurrency control so anyone interested in that
>> subject may want to try and answer this. Thanks!
>>
>>
>> I would like to know how to do a series of writes and reads such that I
>> can tell definitively what process out of many was the first to create a
>> unique flag column.
>>
>> IOW, I would like to have multiple processes (clients) compete to see who
>> is first to write a token column. The tokens start with a known prefix,
>> such as "Token_" followed by the name of the process that created it and a
>> UUID so that all columns are guaranteed unique and don't get overwritten.
>> For example, Process A could create:
>>
>> Token_ProcA_<UUID>
>>
>> and process B would create:
>>
>> Token_ProcB_<UUID>
>>
>> These writes/reads are asynchronous between the two or more processes.
>> After the two processes write their respective tokens, each will read back
>> all columns named "Token_*" that exist (a slice). They each do this in
>> order to find out who "won". The process that wrote the column with the
>> lowest timestamp wins. The purpose is to implement a lock.
>>
>> I think all that is required is for the processes to use QUORUM
>> read/writes to make sure the final read is consistent and will assure each
>> process that it can rely on what's returned from the final read and that
>> there isn't an earlier write floating around somewhere. This is where the
>> "happened-before" question comes in. Is it possible that Process A which
>> writes it's token with a lower timestamp (and should be the winner), that
>> this write may not be seen by Process B when it does it's read (which is
>> after it's token write and after Process A wrote it's token), and thus
>> conclude incorrectly that itself (Process B) is the winner since it will not
>> see Process A's token? I'm 99% sure using QUORUM read/writes will allow
>> this to work because that's the whole purpose, but I just wanted to
>> double-check in case there's another detail I'm forgetting about C* that
>> would defeat this.
>>
>> Thanks!
>>
>> P.S. I realize this will cost me in performance, but this is only meant
>> to be used on occasion.
>>
>
>
Re: Concurrency: Does C* support a Happened-Before relation between
processes' writes?
Posted by Yang <te...@gmail.com>.
without a clear description of your pseudo-code, it's difficult to say
whether it will work.
but I think it can work fine as an election/agreement protocol, which you
can use as a lock to some degree, but this requires
all the potential lock contenders to all participate, you can't grab a lock
before everyone has voiced their vote yet
. let's say the code is like
lock(UUID) {
write_column( "token_"+my_hostname()+"_"+UUID, getTimeStamp() );
for all possible node N :
block until ( token = read_column("token_" + N + "_" + UUID,
getTimeStamp()) ) != null
return "LOCKED" if my timestamp is the lowest among all nodes
}
you have to wait for all nodes to voice their timestamp because the
timestamp in cassandra is client-generated, a latter node can create a
column with an earlier
timestamp.
On Fri, Jun 24, 2011 at 11:33 AM, AJ <aj...@dude.podzone.net> wrote:
> Sorry, I know this is long-winded but I just want to make sure before I go
> through the trouble to implement this since it's not something that can be
> reliably tested and requires in-depth knowledge about C* internals. But,
> this ultimately deals with concurrency control so anyone interested in that
> subject may want to try and answer this. Thanks!
>
>
> I would like to know how to do a series of writes and reads such that I can
> tell definitively what process out of many was the first to create a unique
> flag column.
>
> IOW, I would like to have multiple processes (clients) compete to see who
> is first to write a token column. The tokens start with a known prefix,
> such as "Token_" followed by the name of the process that created it and a
> UUID so that all columns are guaranteed unique and don't get overwritten.
> For example, Process A could create:
>
> Token_ProcA_<UUID>
>
> and process B would create:
>
> Token_ProcB_<UUID>
>
> These writes/reads are asynchronous between the two or more processes.
> After the two processes write their respective tokens, each will read back
> all columns named "Token_*" that exist (a slice). They each do this in
> order to find out who "won". The process that wrote the column with the
> lowest timestamp wins. The purpose is to implement a lock.
>
> I think all that is required is for the processes to use QUORUM read/writes
> to make sure the final read is consistent and will assure each process that
> it can rely on what's returned from the final read and that there isn't an
> earlier write floating around somewhere. This is where the
> "happened-before" question comes in. Is it possible that Process A which
> writes it's token with a lower timestamp (and should be the winner), that
> this write may not be seen by Process B when it does it's read (which is
> after it's token write and after Process A wrote it's token), and thus
> conclude incorrectly that itself (Process B) is the winner since it will not
> see Process A's token? I'm 99% sure using QUORUM read/writes will allow
> this to work because that's the whole purpose, but I just wanted to
> double-check in case there's another detail I'm forgetting about C* that
> would defeat this.
>
> Thanks!
>
> P.S. I realize this will cost me in performance, but this is only meant to
> be used on occasion.
>