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 <a...@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
