6 ms·

This response is incorrect at a very fundamental level. First, Antirez claims that requiring the "materialization" store to be able to tie break with a monoton

This response is incorrect at a very fundamental level. First, Antirez claims that requiring the "materialization" store to be able to tie break with a monotonically increasing token requires linearization? This is completely false. The monotonically increasing token allows for eventual consistency. That's the entire point of it. It's monotonically increasing. For anyone who claims that once you have coordination (locking) in your system you already lost is completely ignoring the research coming out of BOOM (Berkeley Orders of Magnitude). You can design your system to push the coordination out to the edge and way from your "choke points" and use these monotonically increasing tokens to keep your bottlenecks coordination free. Secondly, Antirez's argument that you can use a compare & swap in a transactional storage layer is also wrong. This is not possible to write safely. I'm not even going to touch his argument that using system clocks in a distributed locking algorithm is safe...

saganus 11y ago
Do you have any references for this? This discussion is very interesting and I would like to read up a bit more on your argument and why is this so. I know that distributed systems are hard, but this is a problem that I find interesting to learn more about.
- carllerche 11y ago
  References to what specifically? Martin provided a number in his original blog post, I also elaborated a bit more on my various points in other comments.
  - saganus 11y ago
    Upon reading a bit more on the subject I realized that I would need a more background before asking for references that will be a very specific in terms of subject depth. I read a bit on BOOM and it's not a field I'm keeping up with so I figured it would be no point in more references if I didn't understand the more shallower levels of the discussion first. Sorry about that, I tried to jump a bit too soon, and thanks for answering :)
jhugg 11y ago
> Secondly, Antirez's argument that you can use a compare & swap in a transactional storage layer is also wrong. This is not possible to write safely. Could you elaborate on this? I'm not sure I'm as pessimistic as you on this one point.
- carllerche 11y ago
  In short, either the storage layer provides enough guarantees to ensure safety without redlock OR it is not possible to ensure safety. I believe that antirez's proposal is the former, but if he has a safe algorithm that does not require a linearizable CAS operation in the storage layer and is safe w/ redlock, I would love to hear it. I also provided an example of how to use Cassandra which is eventually consistent safely with a locking service that provides monotonic tokens.
- jamesblonde 11y ago
  Compare and swap has a consensus number of 2. A consensus number is the maximum number of processes for which the object can solve a simple consensus problem. It is impossible to construct a wait-free implementation of an object with consensus number n from an object with a lower consensus number. In other words, test-and-set is weaker than transactions or Paxos for >2 concurrent clients. http://cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf http://cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf
  - jhallenworld 11y ago
    Wait, compare and swap has a consensus number of infinite (from Herlihy's paper).
    - jamesblonde 11y ago
      Oops, you're right. I was thinking of test-and-set.
dvirsky 11y ago
> I'm not even going to touch his argument that using system clocks in a distributed locking algorithm is safe... Please do
- carllerche 11y ago
  I don't need to, Martin did an excellent job touching on this in his original post, including real world references.
  - dvirsky 11y ago
    Antirez responded to that and disagreed to this point in his new post. What do you make of his response?
- Guvante 11y ago
  Clock drift is a real thing in distributed systems. If I have a 5 second lock that expires at 12:01:00 and my clock is off by 1 second I could write at 12:01:01 potentially after someone else has a lock, or worse, after someone else has written.
  - dvirsky 11y ago
    but the expiration time is relative to the redis server's time, and the time measurement on the client side is done relative to the client's time. Other clients don't care about your clock and you don't care about redis' clock AFAIK. From TFM: > The client computes how much time elapsed in order to acquire the lock, by subtracting from the current time the timestamp obtained in step 1. If and only if the client was able to acquire the lock in the majority of the instances (at least 3), and the total time elapsed to acquire the lock is less than lock validity time, the lock is considered to be acquired.
    - dsp1234 11y ago
      What is the effect on the client of a VM live migration "pause"? or daylight savings change? or ntp updates which change the time? Since the system clock can change relative to itself at any time, what effect does that have on the algorithm?
antirez 11y ago
From Martin post: "However, the storage server remembers that it has already processed a write with a higher token number (34), and so it rejects the request with token 33." This is not eventual consistency, this is refusing any new write with ID < past_ID, which requires linearizability. Second, about eventual consistency, the Token ID even when increasing may not be casually related with the work performed while the lock is hold. if you need just a random order when there are concurrent accesses, you can lexically order the random token IDs, for what is worth. Compare & Swap: could you argument that? If you want to avoid races in a read-modify-write scenario, you can set the token, do your work, and only write if the token is still the same, so that if your write succeed is because the state of the shared resource is still the same to when you started operating on it.
- querulous 11y ago
  you don't need a token service if you are going to set the token on the locked resource, perform work and then unset the token. your lock is completely superfluous in that scenario
  - antirez 11y ago
    That's my point in the blog post I wrote. Please read it, I would love your feedback. Or better, you could do even with a best-effort lock, given that race conditions from time to time are harmless.
    - querulous 11y ago
      2. If your data store can always accept the write only if your token is greater than all the past tokens, than it’s a linearizable store. If you have a linearizable store, you can just generate an incremental ID for each Redlock acquired, so this would make Redlock equivalent to another distributed lock system that provides an incremental token ID with every new lock. However in the next point I’ll show how this is not needed. you confuse which system is the linearizable one in this point. your storage system is just a dumb storage system that simply returns the object version with the highest clock. what makes it linearizable to an outside observer is that the system generating the lock ids is itself linearizable. if every insert is accompanied by an authentic lock id the system is linearizable. if you generate this lock id via the storage system itself then the storage system must also be linearizable 3. However “2” is not a sensible choice anyway: most of the times the result of working to a shared resource is not writing to a linearizable store, so what to do? Each Redlock is associated with a large random token (which is generated in a way that collisions can be ignored. The Redlock specification assumes textually “20 bytes from /dev/urandom”). What do you do with a unique token? For example you can implement Check and Set. When starting to work with a shared resource, we set its state to “`<token>`”, then we operate the read-modify-write only if the token is still the same when we write. would you say this sequence of events is correct: * process A acquires lock * process B acquires a lock on the same resource after a time out and sets it's lock id on the resource * process A sets it's lock id on the resource * process A writes a new version of the resource * process B attempts and fails to write a new version of the resource if it's not correct, would you say redlock prevents it? how? now consider what happens if the resource is only one of a group of resources that need to be transactionally updated the bottom line is that distributed transactional locking requires linearization and redlock is plainly not linearizable. please reconsider it's continued development and steer users towards something safer like zookeeper
Domenic_S 11y ago
> I'm not even going to touch his argument that using system clocks in a distributed locking algorithm is safe... He's using it relatively, ie. if (stop time - start time <= $got_lock_fast_enough) { continue... } Is this not legit?
- pygy_ 11y ago
  In a virtualized environment, system time and wall clock time can vary widely. Imagine a VM that's paused and restored.
  - derefr 11y ago
    I would assume that introducing a VM that has "time-travelled" (especially the restore-from-previous-state case someone mentioned above) into a distributed system would inherently break that distributed system, no matter what it's doing. It's a really crazy thing to do, much crazier than a regular network partition. Personally, though, I don't see why it's so hard to just say "this distributed lock system requires that soft real-time guarantees can be made of the host platform. If the platform misses the algorithm's scheduling deadline, the system breaks. If the platform has no way of providing for a soft real-time deadline (because e.g. it's running in a VM that can be paused), the software will detect this and fail to start."
    - jsprogrammer 11y ago
      Because you don't want the system to break.
      - derefr 11y ago
        But it wouldn't, because the surrounding infrastructure would be guaranteeing that. My point is that distributed systems engineers are assuming too few things about the hardware and OS. A much wider space of distributed algorithms become useful if you have full control over your stack. Do you think NASA quibbles about how to make a perfect consensus bit-coding algorithm between the fault-tolerant processors of a mars probe? No; they just use hardware+firmware that provides a hard real-time platform, allowing the algorithm itself to be simple.
pg_is_a_butt 11y ago
uh... compare & swap is most certainly possible to write safely for the sole purpose of either obtaining a lock or failing (and perhaps retrying). or, are you one of those people that think it is not possible to walk down the sidewalk safely? the CIA radio signals are putting the CPU into backdoor mode, right?

saganus 11y ago

Do you have any references for this? This discussion is very interesting and I would like to read up a bit more on your argument and why is this so. I know that distributed systems are hard, but this is a problem that I find interesting to learn more about.

carllerche 11y ago
References to what specifically? Martin provided a number in his original blog post, I also elaborated a bit more on my various points in other comments.
- saganus 11y ago
  Upon reading a bit more on the subject I realized that I would need a more background before asking for references that will be a very specific in terms of subject depth. I read a bit on BOOM and it's not a field I'm keeping up with so I figured it would be no point in more references if I didn't understand the more shallower levels of the discussion first. Sorry about that, I tried to jump a bit too soon, and thanks for answering :)

jhugg 11y ago

> Secondly, Antirez's argument that you can use a compare & swap in a transactional storage layer is also wrong. This is not possible to write safely. Could you elaborate on this? I'm not sure I'm as pessimistic as you on this one point.

carllerche 11y ago
In short, either the storage layer provides enough guarantees to ensure safety without redlock OR it is not possible to ensure safety. I believe that antirez's proposal is the former, but if he has a safe algorithm that does not require a linearizable CAS operation in the storage layer and is safe w/ redlock, I would love to hear it. I also provided an example of how to use Cassandra which is eventually consistent safely with a locking service that provides monotonic tokens.
jamesblonde 11y ago
Compare and swap has a consensus number of 2. A consensus number is the maximum number of processes for which the object can solve a simple consensus problem. It is impossible to construct a wait-free implementation of an object with consensus number n from an object with a lower consensus number. In other words, test-and-set is weaker than transactions or Paxos for >2 concurrent clients. http://cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf http://cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf
- jhallenworld 11y ago
  Wait, compare and swap has a consensus number of infinite (from Herlihy's paper).
  - jamesblonde 11y ago
    Oops, you're right. I was thinking of test-and-set.

dvirsky 11y ago

> I'm not even going to touch his argument that using system clocks in a distributed locking algorithm is safe... Please do

carllerche 11y ago
I don't need to, Martin did an excellent job touching on this in his original post, including real world references.
- dvirsky 11y ago
  Antirez responded to that and disagreed to this point in his new post. What do you make of his response?
Guvante 11y ago
Clock drift is a real thing in distributed systems. If I have a 5 second lock that expires at 12:01:00 and my clock is off by 1 second I could write at 12:01:01 potentially after someone else has a lock, or worse, after someone else has written.
- dvirsky 11y ago
  but the expiration time is relative to the redis server's time, and the time measurement on the client side is done relative to the client's time. Other clients don't care about your clock and you don't care about redis' clock AFAIK. From TFM: > The client computes how much time elapsed in order to acquire the lock, by subtracting from the current time the timestamp obtained in step 1. If and only if the client was able to acquire the lock in the majority of the instances (at least 3), and the total time elapsed to acquire the lock is less than lock validity time, the lock is considered to be acquired.
  - dsp1234 11y ago
    What is the effect on the client of a VM live migration "pause"? or daylight savings change? or ntp updates which change the time? Since the system clock can change relative to itself at any time, what effect does that have on the algorithm?

antirez 11y ago

From Martin post: "However, the storage server remembers that it has already processed a write with a higher token number (34), and so it rejects the request with token 33." This is not eventual consistency, this is refusing any new write with ID < past_ID, which requires linearizability. Second, about eventual consistency, the Token ID even when increasing may not be casually related with the work performed while the lock is hold. if you need just a random order when there are concurrent accesses, you can lexically order the random token IDs, for what is worth. Compare & Swap: could you argument that? If you want to avoid races in a read-modify-write scenario, you can set the token, do your work, and only write if the token is still the same, so that if your write succeed is because the state of the shared resource is still the same to when you started operating on it.

querulous 11y ago
you don't need a token service if you are going to set the token on the locked resource, perform work and then unset the token. your lock is completely superfluous in that scenario
- antirez 11y ago
  That's my point in the blog post I wrote. Please read it, I would love your feedback. Or better, you could do even with a best-effort lock, given that race conditions from time to time are harmless.
  - querulous 11y ago
    2. If your data store can always accept the write only if your token is greater than all the past tokens, than it’s a linearizable store. If you have a linearizable store, you can just generate an incremental ID for each Redlock acquired, so this would make Redlock equivalent to another distributed lock system that provides an incremental token ID with every new lock. However in the next point I’ll show how this is not needed. you confuse which system is the linearizable one in this point. your storage system is just a dumb storage system that simply returns the object version with the highest clock. what makes it linearizable to an outside observer is that the system generating the lock ids is itself linearizable. if every insert is accompanied by an authentic lock id the system is linearizable. if you generate this lock id via the storage system itself then the storage system must also be linearizable 3. However “2” is not a sensible choice anyway: most of the times the result of working to a shared resource is not writing to a linearizable store, so what to do? Each Redlock is associated with a large random token (which is generated in a way that collisions can be ignored. The Redlock specification assumes textually “20 bytes from /dev/urandom”). What do you do with a unique token? For example you can implement Check and Set. When starting to work with a shared resource, we set its state to “`<token>`”, then we operate the read-modify-write only if the token is still the same when we write. would you say this sequence of events is correct: * process A acquires lock * process B acquires a lock on the same resource after a time out and sets it's lock id on the resource * process A sets it's lock id on the resource * process A writes a new version of the resource * process B attempts and fails to write a new version of the resource if it's not correct, would you say redlock prevents it? how? now consider what happens if the resource is only one of a group of resources that need to be transactionally updated the bottom line is that distributed transactional locking requires linearization and redlock is plainly not linearizable. please reconsider it's continued development and steer users towards something safer like zookeeper

Domenic_S 11y ago

> I'm not even going to touch his argument that using system clocks in a distributed locking algorithm is safe... He's using it relatively, ie. if (stop time - start time <= $got_lock_fast_enough) { continue... } Is this not legit?

pygy_ 11y ago
In a virtualized environment, system time and wall clock time can vary widely. Imagine a VM that's paused and restored.
- derefr 11y ago
  I would assume that introducing a VM that has "time-travelled" (especially the restore-from-previous-state case someone mentioned above) into a distributed system would inherently break that distributed system, no matter what it's doing. It's a really crazy thing to do, much crazier than a regular network partition. Personally, though, I don't see why it's so hard to just say "this distributed lock system requires that soft real-time guarantees can be made of the host platform. If the platform misses the algorithm's scheduling deadline, the system breaks. If the platform has no way of providing for a soft real-time deadline (because e.g. it's running in a VM that can be paused), the software will detect this and fail to start."
  - jsprogrammer 11y ago
    Because you don't want the system to break.
    - derefr 11y ago
      But it wouldn't, because the surrounding infrastructure would be guaranteeing that. My point is that distributed systems engineers are assuming too few things about the hardware and OS. A much wider space of distributed algorithms become useful if you have full control over your stack. Do you think NASA quibbles about how to make a perfect consensus bit-coding algorithm between the fault-tolerant processors of a mars probe? No; they just use hardware+firmware that provides a hard real-time platform, allowing the algorithm itself to be simple.

pg_is_a_butt 11y ago

uh... compare & swap is most certainly possible to write safely for the sole purpose of either obtaining a lock or failing (and perhaps retrying). or, are you one of those people that think it is not possible to walk down the sidewalk safely? the CIA radio signals are putting the CPU into backdoor mode, right?