cassandra-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Jim Newsham <jnews...@referentia.com>
Subject Re: Concurrency: Does C* support a Happened-Before relation between processes' writes?
Date Fri, 24 Jun 2011 20:09:20 GMT
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 
> <mailto: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.
>
>


Mime
View raw message