Внедрение обнаружения взаимоблокировок с помощью Apache ZooKeeper

Я работаю в небольшой компании-разработчике программного обеспечения, и мне поручили разработать распределенный менеджер блокировок, который мы могли бы использовать.Он должен взаимодействовать как с Java, так и с C++.

Я работаю с ZooKeeper пару недель и внедрил общие блокировки (блокировки чтения и записи )в соответствии с документацией. Теперь мне нужно реализовать обнаружение взаимоблокировок. Если бы каждый клиент мог вести граф блокировок, это было бы быстро и легко. Однако вы не можете надежно увидеть каждое изменение, которое происходит с узлом в ZooKeeper , поэтому поддержание точного графика будет невозможным. Это означает, что каждый раз, когда я проверяю взаимоблокировку, мне нужно будет загружать много блокировок, что кажется нецелесообразным.

Другим решением может стать обнаружение взаимоблокировок на сервере ZooKeeper, над чем я сейчас работаю. Каждый клиент создаст узел в «/waiting», названный в честь его идентификатора сеанса, и его данные будут блокировкой, которую он ожидает. Поскольку у каждой блокировки есть эфемерный владелец, у меня будет достаточно информации, чтобы обнаружить взаимоблокировку.

Моя проблема заключается в том, что сервер 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— это компаратор, который сортирует z-узлы по последовательности, которую ZooKeeper добавляет в конец последовательных z-узлов.

Код:

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

}