我在一家小型软件公司工作，我的任务是研究一个分布式锁管理器供我们使用。它必须与 Java 和 C++ 接口(interface)。

我已经使用 ZooKeeper 几个星期了，并且 have implemented shared locks (read and write locks) according to the documentation.我现在需要实现死锁检测。如果每个客户端都可以维护一个锁图，那将是快速和容易的。然而，you cannot reliably see every change that happens to a node in ZooKeeper ，因此不可能保持准确的图表。这意味着每次检查死锁时，我都需要下载很多锁，这似乎不切实际。

另一种解决方案是在 ZooKeeper 服务器内实现死锁检测，我现在正在研究这个问题。每个客户端将在“/waiting”中创建一个以其 session ID 命名的节点，其数据将是其等待的锁。由于每个锁都有一个临时所有者，我将有足够的信息来检测死锁。

我遇到的问题是 ZooKeeper 服务器没有 ZooKeeper 客户端所具有的同步保证。另外，ZooKeeper 服务器不像客户端那样有很好的文档记录，因为您通常不应该接触它。

所以我的问题是:应该如何使用 Apache ZooKeeper 实现死锁检测？我在这里看到很多人推荐 ZooKeeper 作为分布式锁管理器，但如果它不能支持死锁检测，那么就没有人应该将它用于此目的。

编辑:

我有一个可行的解决方案。我不能保证它的正确性，但它已经通过了我所有的测试。

我正在分享我的 checkForDeadlock 方法，它是死锁检测算法的核心。以下是您需要了解的其他信息:

• 一次只能有一个客户端运行死锁检测。
• 首先，客户端尝试获取对资源的锁定。如果资源已经被锁定并且客户端想要等到资源可用，那么客户端接下来会检查是否存在死锁。如果等待资源不会导致死锁，那么它接下来会在一个特殊目录中创建一个 znode，该目录标识该客户端正在等待该资源。该行如下所示:waitNode = zooKeeper.create(waitingPath + "/"+ sessionID, resource.getBytes(), ZooDefs.Ids.OPEN_ACL_UNSAFE, CreateMode.EPHEMERAL);
• 在此客户端创建等待节点之前，其他客户端不应开始检查死锁。
• 如果两个客户端几乎同时尝试获取锁，但都授予它们会导致死锁，那么有可能不是第一个客户端获得锁而第二个客户端被拒绝，而是第一个客户端可以被拒绝，第二个客户可以获得锁。这应该不是问题。
如果
• checkForDeadlock 发现死锁，它会抛出一个 DeadlockException。否则，它正常返回。
• 严格按顺序授予锁。如果一个资源有一个已授予的读锁和一个正在等待的写锁，而另一个客户端想要获取一个读锁，它必须等到写锁被授予后再释放。
• bySequenceNumber 是一个比较器，它按照 ZooKeeper 附加到顺序 znode 末尾的顺序对 znode 进行排序。

代码:

private void checkForDeadlock(String pathToResource) throws DeadlockException {
    // Algorithm:
    //   For each client who holds a lock on this resource:
    //     If this client is me, announce deadlock.
    //     Otherwise, if this client is waiting for a reserved resource, recursively check for deadlock on that resource.
    try {
        List<String> lockQueue = zooKeeper.getChildren(pathToResource, false); // Last I checked, children is implemented as an ArrayList.
        // lockQueue is the list of locks on this resource.
        // FIXME There is a slight chance that lockQueue could be empty.
        Collections.sort(lockQueue, bySequenceNumber);
        ListIterator<String> lockQueueIterator = lockQueue.listIterator();
        String grantedLock = lockQueueIterator.next(); // grantedLock is one lock on this resource.
        do {
            // lockQueue must contain a write lock, because there is a lock waiting.
            String lockOwner = null;
            try {
                lockOwner = Long.toString(zooKeeper.exists(pathToResource + "/" + grantedLock, false).getEphemeralOwner());
                // lockOwner is one client who holds a lock on this resource.
            }
            catch (NullPointerException e) {
                // Locks may be released while I'm running deadlock detection. I got a NullPointerException because
                // the lock I was currently looking at was deleted. Since the lock was deleted, its owner was obviously
                // not part of a deadlock. Therefore I can ignore this lock and move on to the next one.
                // (Note that a lock can be deleted if and only if its owner is not part of a deadlock.) 
                continue;
            }
            if (lockOwner.equals(sessionID)) { // If this client is me.
                throw new DeadlockException("Waiting for this resource would result in a deadlock.");
            }
            try {
                // XXX: Is is possible that reservedResource could be null?
                String reservedResource = new String(zooKeeper.getData(waitingPath + "/" + lockOwner, false, new Stat()));
                // reservedResource is the resource that this client is waiting for. If this client is not waiting for a resource, see exception.
                // I only recursively check the next reservedResource if I havn't checked it before.
                // I need to do this because, while I'm running my deadlock detection, another client may attempt to acquire
                // a lock that would cause a deadlock. Without this check, I would loop in that deadlock cycle indefinitely.
                if (checkedResources.add(reservedResource)) {
                    checkForDeadlock(reservedResource); // Depth-first-search
                }
            }
            catch (KeeperException.NoNodeException e) {
                // lockOwner is not waiting for a resource.
            }
            catch (KeeperException e) {
                e.printStackTrace(syncOut);
            }
            // This loop needs to run for each lock that is currently being held on the resource. There are two possibilities:
            // A. There is exactly one write lock on this resource. (Any other locks would be waiting locks.)
            //      In this case, the do-while loop ensures that the write lock has been checked.
            //      The condition that requires that the current lock is a read lock ensures that no locks after the write lock will be checked.
            // B. There are one or more read locks on this resource.
            //      In this case, I just check that the next lock is a read lock before moving on.
        } while (grantedLock.startsWith(readPrefix) && (grantedLock = lockQueueIterator.next()).startsWith(readPrefix));
    }
    catch (NoSuchElementException e) {
        // The condition for the do-while loop assumes that there is a lock waiting on the resource.
        // This assumption was made because a client just reported that it was waiting on the resource.
        // However, there is a small chance that the client has since gotten the lock, or even released it before
        // we check the locks on the resource.
        // FIXME (This may be a problem.)
        // In such a case, the childrenIterator.next() call could throw a NoSuchElementException.
        // We can safely assume that we are finished searching this branch, and therefore return.
    }
    catch (KeeperException e) {
        e.printStackTrace(syncOut);
    }
    catch (InterruptedException e) {
        e.printStackTrace(syncOut);
    }

}

最佳答案

您需要两件事来进行死锁检测，一个锁拥有者列表和一个锁等待者列表，这是标准的 zk lock recipe给你，只要你将某种节点 ID 写入你创建的 znode。

您不需要查看 zookeeper 中的每个更改来检测死锁。死锁不是会出现并迅速消失的东西。根据定义，死锁将一直存在，直到您对其采取措施为止。因此，如果您编写代码让您的客户端监视他们感兴趣的每个锁节点，客户端最终将看到每个锁的所有者和等待者，并且客户端将看到死锁。

但是你必须要小心。客户端可能无法按顺序看到更新，因为更新可能在客户端重新注册 watch 时发生。因此，如果客户端确实检测到死锁，则客户端应通过重新读取所有者/观察者以查找死锁中涉及的锁来仔细检查死锁是否真实，并确保死锁是真实的。

关于java - 使用 Apache ZooKeeper 实现死锁检测，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10304948/