You want to modify locked resource X. You set X.currlock = token. Then you read, do whatever you want, and when you write, you "write-if-currlock == token". If another client did X.currlock = somethingelse, the transaction fails.
Edit: note that I noticed some confusion about this. Any other client is free to replace X.currlock even if set to a past value.
try
token=lock.aquire
val=raw(shared, key, token)
do_things
awar(shared, key, val, token)
except fail("Can't do!")
finally lock.release
Where a shared object has:
1) a key to store a value being changed in the critical section; 2) a currlock to store a random fence token associated with a lock.
The raw reads the shared key's value after the currlock was written to the shared object.
The awar does an atomic write of the value to the key, only if the currlock has an expected token (i.e. is unchanged).When things go wrong, the do_things may be executed more than once, in parallel, but the key is safe and guaranteed to have no lost updates to its value.
Doesn't it mean that this can happen?
A: X.currlock = Token_ID_A
A: resource read
A: is X.currlock still Token_ID_A? yes
B: X.currlock = Token_ID_B
B: resource read
B: is X.currlock still Token_ID_B? yes
B: resource write
A: resource write
Is there anything that makes the "write-if-currlock == token" operation atomic? https://en.wikipedia.org/wiki/Test-and-set
Or the more efficient test and test and set? https://en.wikipedia.org/wiki/Test_and_test-and-setThe monotonic sequence provides that detection means. So in the example you gave, the tardy (expired) tx commit would abort since its lock id would break the monotonic sequence of accepted lock-ops (which clearly can have gaps, 1, 2, 4, 6, 7, ... etc.[)]
1. Most of the times when you need a distributed lock system that can guarantee mutual exclusivity, when this property is violated you already lost. Distributed locks are very useful exactly when we have no other control in the shared resource.
In context, Sanfilippo seems to be arguing that providing monotonic logical timestamps or sequence numbers is futile, since a system that relies on locks that break is going to fail one way or another.
That is probably true, but wildly misses the point: when a sound system that relies on distributed locks fails, it doesn't silently corrupt data. But that's exactly what happens in the "unfenced" lock-breaking scenario Kleppmann describes.
There are worse things than crashing, is the point.
slightly later
The argument about storage servers taking fencing tokens being "linearizable" also seems flimsy: aren't they "linearizable" (in whatever sense Sanfillippo means) in the case Kleppmann because because the lock service arranges for them to be? That's functionality Kleppmann says is missing from Redlock.