3 ms·

I'll take one point here. Antirez's point that clients have to timeout on locks, otherwise the resource will be deadlocked is not correct. We implemented an al

I'll take one point here. Antirez's point that clients have to timeout on locks, otherwise the resource will be deadlocked is not correct. We implemented an alternative model based on distributed shared memory. Clients take a lock on the root of a subtree (of potentially millions of inodes in our version of HDFS) and persist the lock to shared memory and look for existing locks on the subtree in shared memory. If the client dies while processing the subtree, its lock is still persisted in shared memory alongs with the clientID. If another client tries to take the lock and it notices the client holding the lock has died, it takes the lock. We used heartbeats to shared memroy to implement the failure detector for clients (based again on shared memory http://www.jimdowling.info/sites/default/files/leader_election_using_newsql_db.pdf http://www.jimdowling.info/sites/default/files/leader_electi... ). Importantly, timeouts for heartbeats expand when the system is congested.

antirez 11y ago
There may be systems where you can reliably detect if a client has a lock at all, and if it's still alive or is failing. In most systems this is not possible, so your locks need to have an auto release feature. Distributed locks with auto release are like a huge needed evil: you avoid using it at all costs if you can, but there are problems when they are needed.
- jamesblonde 11y ago
  In this case, we transformed the problem from detecting if the client has the lock or not, to one of detecting if the client is dead or not - for which there are many more protocols (with different levels of accuracy). The point stands that auto-releasing distributed locks is not the only possible solution.
  - antirez 11y ago
    It is impossible to write a reliable distributed failure detector in this use case, in a practical system model.
    - jamesblonde 11y ago
      You mean in the asynchronous systems model, in the presence of failures, it is impossible to write a reliable failure detector: http://the-paper-trail.org/blog/a-brief-tour-of-flp-impossibility/ http://the-paper-trail.org/blog/a-brief-tour-of-flp-impossib... However, you can write a failure detector for a practical system with the help of omega (weakest failure detector): http://www.cs.utexas.edu/~lorenzo/corsi/cs380d/papers/p685-chandra.pdf http://www.cs.utexas.edu/~lorenzo/corsi/cs380d/papers/p685-c... In practice, failure detectors mean timeouts. What I am arguing is that you can have systems that adapt their timeouts for failure (such as our one), based on the current level of network congestion or load or whatever. The setting/changing of the timeout is averaged over a period of time, to ensure it is high enough to not give false positives. You could do the same approach at the per message level, but for all possible messages, it may be prohibitive. If you have a small number of messages, it may work. The problem with messages, compared to failure detection, however, is the following: how do you figure out you have had a false positive? For failure detection it's easy: the timeout expired, butre i'm still alive and my heartbeat arrives late, so we increase the timeout for that node. Vector clocks (fencing tokens) make it easier to reliably find out if messages arrive very late (identify false positives).

antirez 11y ago

There may be systems where you can reliably detect if a client has a lock at all, and if it's still alive or is failing. In most systems this is not possible, so your locks need to have an auto release feature. Distributed locks with auto release are like a huge needed evil: you avoid using it at all costs if you can, but there are problems when they are needed.

jamesblonde 11y ago
In this case, we transformed the problem from detecting if the client has the lock or not, to one of detecting if the client is dead or not - for which there are many more protocols (with different levels of accuracy). The point stands that auto-releasing distributed locks is not the only possible solution.
- antirez 11y ago
  It is impossible to write a reliable distributed failure detector in this use case, in a practical system model.
  - jamesblonde 11y ago
    You mean in the asynchronous systems model, in the presence of failures, it is impossible to write a reliable failure detector: http://the-paper-trail.org/blog/a-brief-tour-of-flp-impossibility/ http://the-paper-trail.org/blog/a-brief-tour-of-flp-impossib... However, you can write a failure detector for a practical system with the help of omega (weakest failure detector): http://www.cs.utexas.edu/~lorenzo/corsi/cs380d/papers/p685-chandra.pdf http://www.cs.utexas.edu/~lorenzo/corsi/cs380d/papers/p685-c... In practice, failure detectors mean timeouts. What I am arguing is that you can have systems that adapt their timeouts for failure (such as our one), based on the current level of network congestion or load or whatever. The setting/changing of the timeout is averaged over a period of time, to ensure it is high enough to not give false positives. You could do the same approach at the per message level, but for all possible messages, it may be prohibitive. If you have a small number of messages, it may work. The problem with messages, compared to failure detection, however, is the following: how do you figure out you have had a false positive? For failure detection it's easy: the timeout expired, butre i'm still alive and my heartbeat arrives late, so we increase the timeout for that node. Vector clocks (fencing tokens) make it easier to reliably find out if messages arrive very late (identify false positives).