Galaxy internals

[pron]

I have finished writing a three-part blog post series detailing Galaxy's implementation. It can be found here.

[Sebastian Schmitt]

First of all, I have to thank you for sharing your (brilliant!) thoughts! I read through your blog posts with great interest and I am very happy to see that there are still people out there thinking about old problems in a new and different way!

I stumbled upon one possible conflicting situation that I can not resolve on my own. I will try to describe it here and hope that you can help me out with that:

Assuming you have three machines A,B,C and two cache lines 1,2.

A is owner of 2 and holds a (still valid) copy of 1

B is owner of 1

C doesn't know any of those cache lines until now.

Now, two transactions happen concurrently (i.e. they do not notice each other in any way):

T1 runs on A and modifies 2 on the basis of the current value of 1

T2 runs on B and modifies 1

After those transactions have finished, machine C requests copies of the two cache lines.

Now, machine C has the value of 2 that is based on the old value of 1 and it has the new value of 1.

Doesn't this break your consistency assumptions? Is there some logic to prevent this situation from happening that I just missed?

Thanks in advance and again: "Go, go, go!"

[pron]

The scenario you describe does not break consistency because you can find a serial, valid, ordering of the transactions; in this case, T1 just appears to have happened before T2. It doesn't matter if T1 happened an hour earlier than T2 or two milliseconds later - to everyone involved it appears to have happened sometime before T2. The fact that node B invalidates all copies of 1 before letting C see the new value ensures that the T1 would happen either completely before T2 or completely after - in this case completely after.

If, however, you want to tie the values of 1 and 2 together, so that they are always synchronized with one another, node A would have to become the owner of 1 as well before executing the transaction. In your description it doesn't do that, so it must be OK with others seeing an out-of-date value of 2.