使用Apache ZooKeeper实现死锁检测

Question

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

我已经使用ZooKeeper工作了几个星期,并根据文档实现了共享锁(读写锁).我现在需要实现死锁检测.如果每个客户端都可以维护锁的图形,那么它将是快速而简单的.但是,您无法可靠地查看ZooKeeper中节点发生的每个更改,因此无法保持准确的图形.这意味着每次检查死锁时,我都需要下载许多锁,这似乎不切实际.

另一种解决方案是在ZooKeeper服务器中实现死锁检测,我现在正在研究它.每个客户端都会在'/ waiting'中创建一个以其会话ID命名的节点,其数据将是其等待的锁.由于每个锁都有一个短暂的所有者,我将有足够的信息来检测死锁.

我遇到的问题是ZooKeeper服务器没有ZooKeeper客户端的同步保证.另外,ZooKeeper服务器没有像客户端那样很好地记录,因为你通常不应该触摸它.

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

---

编辑:

我有一个有效的解决方案.我无法保证其正确性,但它已通过我的所有测试.

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

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

码:

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);
    }

}

Answer 1

您需要两件事来进行死锁检测，一个锁所有者列表和一个锁等待者列表，标准zk 锁配方为您提供了这些列表，只要您将某种节点 id 写入您创建的 znode 即可。

您不需要查看 Zookeeper 中的每个更改来检测死锁。僵局不会出现然后很快消失。根据定义，僵局将一直存在，直到你采取行动。因此，如果您编写代码让客户端监视他们感兴趣的每个锁节点，则客户端最终将看到每个锁的所有者和等待者，并且客户端将看到死锁。

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