Aren't "eventually consistent" databases fun?

[torkell]

So here's a bit of a thought experiment, inspired by a problem I tackled at work recently...

Say you've got some sort of data store where the only operations you can do are read a chunk of data or write a chunk of data. You can guarantee that all operations you do execute atomically and in-order, and that you see the results of any operations someone else does in the order that they do them... but you have no guarantees at all as to whether writes you do happen before or after writes that someone else does.

Given that, if a pair of clients simultaneously create the same entry can they tell who was first to create it? You are allowed to add other data in the same write such as a transaction ID.

Just doing read-create doesn't help as both clients may see an empty entry and proceed to create it...

Client A	Client B
Read
	Read
Create
	Create

I don't think extending it to a read-create-check helps as you might get this ordering...

Client A	Client B
Read
	Read
	Create (set id=B)
	Check (returns id=B)
Create (set id=A)
Check (returns id=A)

...and both clients will think that they won the race. Which results in much sadness as both clients then proceed to update other statistics and leave you wondering why you have 10 items but can only see 5 of them.

We solved it by cheating and using a data type that maintained insertion order (so we can tell who got there first), but it got me wondering if you can do it without that. I think you could manage it if you had a small delay between the create and the check so that if two clients created the row at the same time the second create would complete before either client did the check, but that adds latency which is annoying. Hmm...