Log in

No account? Create an account
'Twas brillig, and the slithy toves did gyre and gimble in the wabe [entries|archive|friends|userinfo]

[ website | Beware the Jabberwock... ]
[ deviantArt | the-boggyb ]
[ FanFiction | Torkell ]
[ Tumblr | torkellr ]

[Random links| BBC news | Vulture Central | Slashdot | Dangerous Prototypes | LWN | Raspberry Pi]
[Fellow blogs| a Half Empty Glass | the Broken Cube | The Music Jungle | Please remove your feet | A letter from home]
[Other haunts| Un4seen Developments | Jazz 2 Online | EmuTalk.net | Feng's shui]

Aren't "eventually consistent" databases fun? [Tuesday 16th August 2016 at 11:11 pm]

[Tags|, , ]
[Feeling |curiouscurious]
[Playing |Siobhan Donaghy - Coming Up For Air [Ghosts]]

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 AClient B

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

Client AClient B
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...

Link | Previous Entry | Share | Next Entry[ Penny for your thoughts? ]