6 ms·

Am I missing why a distributed lock is an impossibility? The problem stated is that a partitioned node can't know it has lost the lock, but this is only an issu

Am I missing why a distributed lock is an impossibility? The problem stated is that a partitioned node can't know it has lost the lock, but this is only an issue if there is a way to lose the lock short of returning it. Which I guess is to say: what difference is there between a lease with an infinite timeout unless manually returned, and a "lock"? Certainly the system deadlocks under partition but I'm not sure why that makes this "impossible".

qlm 4y ago
I think it's possible to build such a lock, but if your lock will inevitably deadlock due to random failures it's probably not that useful.
convolvatron 4y ago
replace "impossible" with "not really useful"
rubiquity 4y ago
The short answer is because if the lock holder fails your other nodes have no way of knowing if the lock holder failed (consequence of FLP Impossibility result). If you set a timeout, then that’s a lease. The long answer is to peel this onion for yourself and see where it leads. It’s a lot of fun.
- derefr 4y ago
  Why does it matter (in fully-general theory, which is what we're discussing here) if the lock holder fails? The lock is either released, at which point someone else can acquire it; or never released, at which point the system doesn't try to do whatever that lock is about any more. Assuming that every distributed system has to successfully make progress in all cases is just that—an assumption. A design could require that operations "fail stalled." Like a physical padlock that is "tamper proof" in the sense that it permanently seizes up when you put in the wrong key.
  - di4na 4y ago
    Because you cannot differentiate a slow node from a dead node. People expect different responses to these.
    - derefr 4y ago
      Big assumption that a distributed system has to serve “people” and have “responses.” A distributed system might be, for example, the ACH system: all batch, all store-and-forward, no replies flowing down the line, only processed message response batches dropped off “eventually” in outboxes. Or, for another example: any workload manager, whether on an HPC cluster or your local Kubernetes node. No synchronous workload execution; just async batch scheduler enqueue with later best-effort status querying.
      - di4na 4y ago
        Note that ACH expect a reponse under 3 days, so a blocked forever do not work. Because guess what. People expect an answer. Saying to people "a system somewhere is blocked for possibly forever, so too bad we cannot do your thing" is our reality. Our system exist for their impact on people. Otherwise they are art... which also exist for its impact on people.
        derefr 4y ago
        It's not necessarily that "we cannot do your thing." Just that "we cannot do your thing using your lock. To get around this, simply make a new resource, to get a new lock." Think of how in e.g. an IaaS control plane, when you delete a VM, it may take an arbitrarily-long time before you can create another VM with the same ID. (Maybe forever!) But you can always create a VM with a different ID, that otherwise fulfills all the same purposes (e.g. has the old instance's IP, FQDN, etc.) The old ID essentially has a distributed lock on its use, with an unbounded release time — and that's perfectly fine for the use-case. For an example of fail-stalled being not only practical but preferred, consider tag-out locking systems (exclusive-access locks used to prevent machines from being turned on while maintenance is being performed on them.) If there was a digital lock of that type, you wouldn't want to ever automatically time it out. A human put that lock there, to keep them alive. They'll take it off when they're done. If you really suspect someone forgot to unlock the tag-out lock, you can always go and check with the lock's acquirer. But if you can't get in contact with them, you can't know that they don't still have their hands up in the gears of the machine. And in this case, failing to auto-restart the assembly line (until the "partition" is over and you can just ask the maintenance worker why they're still holding the lock) is worth much less than said maintenance worker's life.
evil-olive 4y ago
> a lease with an infinite timeout unless manually returned I would argue that "infinite timeout" is another negative shibboleth. every operation in a distributed system has some duration after which you can be 99.9% confident (or 99.9999%, or whatever threshold you want to pick) that it was lost to the void and will never return a result. in a robust distributed system, you want to pick a reasonable timeout value, and then take appropriate action in response to the timeout. typically this is retrying the operation, bubbling up a failure message to a higher level, or some combination of the two (retry a few times, fail if all the retries fail). an infinite timeout represents a deliberate design choice of "I don't want to handle the case of this message or API call being lost in-transit and never returning either success or failure". in my experience, infinite timeouts are often the cause of "hmm, this thing is up and running but seems 'stuck' and not making any progress, let me try manually restarting this service...OK, that seems to have recovered it" bugs and production alerts.
- mjevans 4y ago
  I agree; it's also one of the few issues I have with Linux (and possibly Unix generally). Zombie processes (dependent on some lock that will never clear) shouldn't be possible. At the very least abort (kill -9) should always be possible. Failure should always be an option; it should be the default assumption. All other order must be wrested from that chaos.
  - yencabulator 4y ago
    Zombie processes are already dead and aborted, there's nothing more a kill -9 would do to them. The kernel retains minimal state about them because the system has made a promise to report that the process exited to its parent process, and the parent process hasn't gotten around to asking for that yet. (Don't confuse zombies with uninterruptible I/O sleep, or buggy kernel workers.)
    - mjevans 4y ago
      I might have done that last line, but I do mean generally. Even if it isn't kill -9 (which it should be, somehow, since that's the human's intent when they use it); there should be some mechanism for reaching the 'failed' state and the process itself leaving the accounting tables. Stuck mounts have a half solution (lazy unmounts) but even _that_ interface really also needs a timeout value after which operations on the target should be assumed to fail rather than return correctly. Offhand, I wonder if there's currently or previously been a DoS attack based on defunct uninterruptible sleep. Theoretically a system could be exhausted of PIDs which could lead to nasty issues.
kgeist 4y ago
At our job someone decided to use a ready-to-use Go library which used Redis for distributed locking. But I found that it was broken by design and completely unreliable, and we had random transient errors stemming from it. It worked OK 99.9% the time, but once in a while we were getting inconsistent state in our application. The description initially made sense and the usage looked simple. It worked by a node creating a value with a TTL, which was used to make the lock auto-expire if a node crashed. If a node found that a value under the same name was already found in Redis, it would block. Since access to Redis is serialized, all such actions were basically atomic. The problem was due to the auto-expire feature. The TTL can expire while your code under the lock is scheduled out due to GC or waiting for I/O. So the lock that you held could be released basically at any point of execution while you were supposedly under the lock. Extending the lock's TTL after every line of code isn't practical and probably prone to race conditions anyway (and the library IIRC didn't provide a way to do it). I read there's a technique called token fencing but it requires additional changes to the way your shared resources are accessed which isn't always possible. I still don't know how to do distributed locks right and there seem to be many broken implementations in the wild.
- tonyg 4y ago
  So Redis isn't really a distributed locking system. The locks are all managed by a central, non-distributed server: Redis. But this kind of lock is useful too. One nice approach to handling crashes in a system like this is to use the idea of fate sharing [1]: you upper-bound the lifetime of a held lock by the lifetime of the TCP connection it was taken on. When the connection goes, the lock is auto-released. To support this, Redis would have to have some kind of EXPIRE_ON_DISCONNECT command - I don't know if it does or not. The idea of fate sharing is very general and useful: you can, for example, introduce reconnectable sessions, and attach shared state to those, which gets you transport-independence and the ability to recover from transport failure. [1] Clark, David D. “The Design Philosophy of the DARPA Internet Protocols.” ACM SIGCOMM Computer Communication Review 18, no. 4 (August 1988): 106–14. https://doi.org/10.1145/52325.52336 https://doi.org/10.1145/52325.52336.
  - junon 4y ago

qlm 4y ago

I think it's possible to build such a lock, but if your lock will inevitably deadlock due to random failures it's probably not that useful.

convolvatron 4y ago

replace "impossible" with "not really useful"

rubiquity 4y ago

The short answer is because if the lock holder fails your other nodes have no way of knowing if the lock holder failed (consequence of FLP Impossibility result). If you set a timeout, then that’s a lease. The long answer is to peel this onion for yourself and see where it leads. It’s a lot of fun.

derefr 4y ago
Why does it matter (in fully-general theory, which is what we're discussing here) if the lock holder fails? The lock is either released, at which point someone else can acquire it; or never released, at which point the system doesn't try to do whatever that lock is about any more. Assuming that every distributed system has to successfully make progress in all cases is just that—an assumption. A design could require that operations "fail stalled." Like a physical padlock that is "tamper proof" in the sense that it permanently seizes up when you put in the wrong key.
- di4na 4y ago
  Because you cannot differentiate a slow node from a dead node. People expect different responses to these.
  - derefr 4y ago
    Big assumption that a distributed system has to serve “people” and have “responses.” A distributed system might be, for example, the ACH system: all batch, all store-and-forward, no replies flowing down the line, only processed message response batches dropped off “eventually” in outboxes. Or, for another example: any workload manager, whether on an HPC cluster or your local Kubernetes node. No synchronous workload execution; just async batch scheduler enqueue with later best-effort status querying.
    - di4na 4y ago
      Note that ACH expect a reponse under 3 days, so a blocked forever do not work. Because guess what. People expect an answer. Saying to people "a system somewhere is blocked for possibly forever, so too bad we cannot do your thing" is our reality. Our system exist for their impact on people. Otherwise they are art... which also exist for its impact on people.
      - derefr 4y ago
        It's not necessarily that "we cannot do your thing." Just that "we cannot do your thing using your lock. To get around this, simply make a new resource, to get a new lock." Think of how in e.g. an IaaS control plane, when you delete a VM, it may take an arbitrarily-long time before you can create another VM with the same ID. (Maybe forever!) But you can always create a VM with a different ID, that otherwise fulfills all the same purposes (e.g. has the old instance's IP, FQDN, etc.) The old ID essentially has a distributed lock on its use, with an unbounded release time — and that's perfectly fine for the use-case. For an example of fail-stalled being not only practical but preferred, consider tag-out locking systems (exclusive-access locks used to prevent machines from being turned on while maintenance is being performed on them.) If there was a digital lock of that type, you wouldn't want to ever automatically time it out. A human put that lock there, to keep them alive. They'll take it off when they're done. If you really suspect someone forgot to unlock the tag-out lock, you can always go and check with the lock's acquirer. But if you can't get in contact with them, you can't know that they don't still have their hands up in the gears of the machine. And in this case, failing to auto-restart the assembly line (until the "partition" is over and you can just ask the maintenance worker why they're still holding the lock) is worth much less than said maintenance worker's life.

evil-olive 4y ago

> a lease with an infinite timeout unless manually returned I would argue that "infinite timeout" is another negative shibboleth. every operation in a distributed system has some duration after which you can be 99.9% confident (or 99.9999%, or whatever threshold you want to pick) that it was lost to the void and will never return a result. in a robust distributed system, you want to pick a reasonable timeout value, and then take appropriate action in response to the timeout. typically this is retrying the operation, bubbling up a failure message to a higher level, or some combination of the two (retry a few times, fail if all the retries fail). an infinite timeout represents a deliberate design choice of "I don't want to handle the case of this message or API call being lost in-transit and never returning either success or failure". in my experience, infinite timeouts are often the cause of "hmm, this thing is up and running but seems 'stuck' and not making any progress, let me try manually restarting this service...OK, that seems to have recovered it" bugs and production alerts.

mjevans 4y ago
I agree; it's also one of the few issues I have with Linux (and possibly Unix generally). Zombie processes (dependent on some lock that will never clear) shouldn't be possible. At the very least abort (kill -9) should always be possible. Failure should always be an option; it should be the default assumption. All other order must be wrested from that chaos.
- yencabulator 4y ago
  Zombie processes are already dead and aborted, there's nothing more a kill -9 would do to them. The kernel retains minimal state about them because the system has made a promise to report that the process exited to its parent process, and the parent process hasn't gotten around to asking for that yet. (Don't confuse zombies with uninterruptible I/O sleep, or buggy kernel workers.)
  - mjevans 4y ago
    I might have done that last line, but I do mean generally. Even if it isn't kill -9 (which it should be, somehow, since that's the human's intent when they use it); there should be some mechanism for reaching the 'failed' state and the process itself leaving the accounting tables. Stuck mounts have a half solution (lazy unmounts) but even _that_ interface really also needs a timeout value after which operations on the target should be assumed to fail rather than return correctly. Offhand, I wonder if there's currently or previously been a DoS attack based on defunct uninterruptible sleep. Theoretically a system could be exhausted of PIDs which could lead to nasty issues.

kgeist 4y ago

At our job someone decided to use a ready-to-use Go library which used Redis for distributed locking. But I found that it was broken by design and completely unreliable, and we had random transient errors stemming from it. It worked OK 99.9% the time, but once in a while we were getting inconsistent state in our application. The description initially made sense and the usage looked simple. It worked by a node creating a value with a TTL, which was used to make the lock auto-expire if a node crashed. If a node found that a value under the same name was already found in Redis, it would block. Since access to Redis is serialized, all such actions were basically atomic. The problem was due to the auto-expire feature. The TTL can expire while your code under the lock is scheduled out due to GC or waiting for I/O. So the lock that you held could be released basically at any point of execution while you were supposedly under the lock. Extending the lock's TTL after every line of code isn't practical and probably prone to race conditions anyway (and the library IIRC didn't provide a way to do it). I read there's a technique called token fencing but it requires additional changes to the way your shared resources are accessed which isn't always possible. I still don't know how to do distributed locks right and there seem to be many broken implementations in the wild.

tonyg 4y ago
So Redis isn't really a distributed locking system. The locks are all managed by a central, non-distributed server: Redis. But this kind of lock is useful too. One nice approach to handling crashes in a system like this is to use the idea of fate sharing [1]: you upper-bound the lifetime of a held lock by the lifetime of the TCP connection it was taken on. When the connection goes, the lock is auto-released. To support this, Redis would have to have some kind of EXPIRE_ON_DISCONNECT command - I don't know if it does or not. The idea of fate sharing is very general and useful: you can, for example, introduce reconnectable sessions, and attach shared state to those, which gets you transport-independence and the ability to recover from transport failure. [1] Clark, David D. “The Design Philosophy of the DARPA Internet Protocols.” ACM SIGCOMM Computer Communication Review 18, no. 4 (August 1988): 106–14. https://doi.org/10.1145/52325.52336 https://doi.org/10.1145/52325.52336.
- junon 4y ago