私は小さなソフトウェア会社で働いており、使用する分散ロックマネージャーの研究を任されています。JavaとC++の両方とインターフェースする必要があります。
私はZooKeeperを数週間使用しており、ドキュメントに従って共有ロック（読み取りおよび書き込みロック）を実装しました。ここで、デッドロック検出を実装する必要があります。各クライアントがロックのグラフを維持できれば、それは迅速かつ簡単になります。ただし、ZooKeeperのノードに発生するすべての変更を確実に確認できるわけではないため、正確なグラフを維持することは不可能です。これは、デッドロックをチェックするたびに、多くのロックをダウンロードする必要があることを意味しますが、これは実用的ではないようです。
もう1つの解決策は、現在取り組んでいるZooKeeperサーバー内にデッドロック検出を実装することです。各クライアントは、セッションIDにちなんで名付けられた「/ waiting」内にノードを作成し、そのデータは待機中のロックになります。各ロックには一時的な所有者がいるため、デッドロックを検出するのに十分な情報があります。
私が抱えている問題は、ZooKeeperサーバーには、ZooKeeperクライアントが持っている同期保証がないことです。さらに、ZooKeeperサーバーは、クライアントのように適切に文書化されていません。これは、通常、ZooKeeperサーバーに触れることを想定していないためです。
だから私の質問はこれです：Apache ZooKeeperでデッドロック検出を実装するにはどうすればよいですか？ここでは、分散ロックマネージャーとしてZooKeeperを推奨している人がたくさんいますが、デッドロック検出をサポートできない場合は、この目的で使用しないでください。
編集：
私には実用的な解決策があります。その正確性を保証することはできませんが、すべてのテストに合格しています。
checkForDeadlockデッドロック検出アルゴリズムの心臓部である私の方法を共有しています。知っておく必要のある追加情報は次のとおりです。
- 一度に1つのクライアントのみがデッドロック検出を実行する必要があります。
- 最初に、クライアントはリソースのロックを取得しようとします。リソースがすでにロックされていて、クライアントがリソースが使用可能になるまで待機したい場合、クライアントは次にデッドロックをチェックします。リソースを待機してもデッドロックが発生しない場合は、次に、このクライアントがそのリソースを待機していることを識別する特別なディレクトリにznodeを作成します。その行は次のようになります。
waitNode = zooKeeper.create(waitingPath + "/" + sessionID, resource.getBytes(), ZooDefs.Ids.OPEN_ACL_UNSAFE, CreateMode.EPHEMERAL); - このクライアントが待機ノードを作成するまで、他のクライアントはデッドロックのチェックを開始しないでください。
- 2つのクライアントがほぼ同時にロックを取得しようとしたが、両方を許可するとデッドロックが発生する場合、最初のクライアントがロックを取得して2番目のクライアントが拒否される代わりに、最初のクライアントが拒否されて2番目のクライアントがロックを取得する可能性があります。これは問題にはならないはずです。
checkForDeadlockDeadlockExceptionデッドロックを検出すると、をスローします。それ以外の場合は、正常に戻ります。- ロックは厳密に順番に付与されます。リソースに許可された読み取りロックと待機中の書き込みロックがあり、別のクライアントが読み取りロックを取得したい場合、書き込みロックが許可されてから解放されるまで待機する必要があります。
bySequenceNumberZooKeeperがシーケンシャル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);
}
}