deadlock-prevention

デッドロックの防止

概要

2つのプロセスが互いを待ち続ける状態が、デッドロックです。

デッドロックは、永久に処理が停止する状態です。クラッシュもエラーもなく、ただ沈黙します。プロセスがリソースを保持したまま、ほかのプロセスが保持するリソースを待つことで、循環待ちが発生します。

使用する場面

• 複数のロックやリソースを取得するとき
• テーブルやサービスをまたいだネストされたトランザクション
• サービス間の呼び出しがある分散システム
• 「負荷がかかるとシステムがフリーズする」
• エラーはないのに処理が完了しない

絶対のルール

NEVER acquire locks in inconsistent order across the codebase.

例外はありません：

• 「この経路はまれだから」という理由
• 「タイムアウトを追加するから」という理由
• 「サービスが異なるので競合しない」という理由
• 「高負荷時にしか起きない」という理由

ロック取得順序が一貫していないと、いずれデッドロックが発生します。

デッドロックの4つの条件

デッドロックには4つすべての条件が必要です。どれか1つを崩せば、防止できます：

┌────────────────────────────────────────────────────────────┐
│ 1. MUTUAL EXCLUSION    │ Resource can only be held by one │
│ 2. HOLD AND WAIT       │ Hold one, wait for another       │
│ 3. NO PREEMPTION       │ Can't force release of resource  │
│ 4. CIRCULAR WAIT       │ A waits for B, B waits for A     │
└────────────────────────────────────────────────────────────┘

最も実用的な方法：一貫した順序付けで循環待ちを崩します。

検出：循環待ちのパターン

// ❌ VIOLATION: Inconsistent lock order = guaranteed deadlock

// Service A: Transfer from X to Y
async function transferAtoB(fromId: string, toId: string, amount: number) {
  await lockAccount(fromId);  // Lock A first
  await lockAccount(toId);    // Then lock B
  // transfer...
  await unlockAccount(toId);
  await unlockAccount(fromId);
}

// Service B: Transfer from Y to X  
async function transferBtoA(fromId: string, toId: string, amount: number) {
  await lockAccount(fromId);  // Lock B first (OPPOSITE ORDER!)
  await lockAccount(toId);    // Then lock A
  // transfer...
}

// Deadlock scenario:
// T1: Locks account A, waits for B
// T2: Locks account B, waits for A
// Result: Both wait forever

防止策

1. 一貫したロック取得順序（主な対策）

// ✅ CORRECT: Always acquire locks in the same order
async function transfer(
  accountId1: string, 
  accountId2: string, 
  amount: number
): Promise<void> {
  // ALWAYS lock lower ID first - creates total ordering
  const [first, second] = accountId1 < accountId2 
    ? [accountId1, accountId2] 
    : [accountId2, accountId1];
  
  const lock1 = await acquireLock(`account:${first}`);
  const lock2 = await acquireLock(`account:${second}`);
  
  try {
    await doTransfer(accountId1, accountId2, amount);
  } finally {
    await releaseLock(lock2);
    await releaseLock(lock1);  // Release in reverse order
  }
}

2. ロックのタイムアウト（非プリエンプションを崩す）

// ✅ CORRECT: Timeout prevents permanent deadlock
async function acquireWithTimeout(
  resource: string, 
  timeoutMs: number
): Promise<Lock | null> {
  const deadline = Date.now() + timeoutMs;
  
  while (Date.now() < deadline) {
    const lock = await tryAcquireLock(resource);
    if (lock) return lock;
    
    // Backoff with jitter
    await sleep(50 + Math.random() * 50);
  }
  
  return null;  // Timeout - caller must handle
}

async function transfer(from: string, to: string, amount: number) {
  const lock1 = await acquireWithTimeout(`account:${from}`, 5000);
  if (!lock1) throw new LockTimeoutError(from);
  
  try {
    const lock2 = await acquireWithTimeout(`account:${to}`, 5000);
    if (!lock2) {
      throw new LockTimeoutError(to);  // Release lock1 in finally
    }
    
    try {
      await doTransfer(from, to, amount);
    } finally {
      await releaseLock(lock2);
    }
  } finally {
    await releaseLock(lock1);
  }
}

3. try-lockとバックオフ（保持と待機を崩す）

// ✅ CORRECT: Don't hold while waiting - release and retry
async function acquireMultipleLocks(
  resources: string[], 
  maxRetries = 10
): Promise<Lock[]> {
  for (let attempt = 0; attempt < maxRetries; attempt++) {
    const locks: Lock[] = [];
    let success = true;
    
    // Sort for consistent ordering
    const sorted = [...resources].sort();
    
    for (const resource of sorted) {
      const lock = await tryAcquireLock(resource);
      if (lock) {
        locks.push(lock);
      } else {
        // Can't get this lock - release all and retry
        success = false;
        break;
      }
    }
    
    if (success) {
      return locks;
    }
    
    // Release all acquired locks
    await Promise.all(locks.map(releaseLock));
    
    // Exponential backoff with jitter
    await sleep(Math.pow(2, attempt) * 10 + Math.random() * 50);
  }
  
  throw new DeadlockPreventionError('Could not acquire all locks');
}

4. 関連リソースに単一のロックを使う

// ✅ CORRECT: One lock covers all related resources
async function transfer(from: string, to: string, amount: number) {
  // Use a higher-level lock instead of per-account locks
  const transferLock = await acquireLock('transfer-system');
  
  try {
    // No deadlock possible - only one lock
    await doTransfer(from, to, amount);
  } finally {
    await releaseLock(transferLock);
  }
}

// Trade-off: Less parallelism, but no deadlock risk
// Use when: Operations are fast, correctness > throughput

5. ロック階層

// ✅ CORRECT: Hierarchical locking - always acquire parent before child
enum LockLevel {
  SYSTEM = 0,
  REGION = 1,
  ACCOUNT = 2,
  TRANSACTION = 3,
}

class HierarchicalLock {
  private heldLocks: Map<LockLevel, Set<string>> = new Map();
  
  async acquire(level: LockLevel, resource: string): Promise<void> {
    // Validate hierarchy - can only acquire lower levels
    for (const [heldLevel] of this.heldLocks) {
      if (level <= heldLevel) {
        throw new LockHierarchyViolation(
          `Cannot acquire ${level} while holding ${heldLevel}`
        );
      }
    }
    
    await this.doAcquire(level, resource);
    
    if (!this.heldLocks.has(level)) {
      this.heldLocks.set(level, new Set());
    }
    this.heldLocks.get(level)!.add(resource);
  }
}

データベース固有のパターン

SQL：ロック取得順序

-- ❌ VIOLATION: No consistent order
-- Transaction 1
SELECT * FROM accounts WHERE id = 'A' FOR UPDATE;
SELECT * FROM accounts WHERE id = 'B' FOR UPDATE;

-- Transaction 2 (opposite order)
SELECT * FROM accounts WHERE id = 'B' FOR UPDATE;
SELECT * FROM accounts WHERE id = 'A' FOR UPDATE;

-- ✅ CORRECT: Always order by ID
SELECT * FROM accounts 
WHERE id IN ('A', 'B') 
ORDER BY id 
FOR UPDATE;

PostgreSQL：ロックのタイムアウト

-- Set lock timeout to prevent permanent deadlock
SET lock_timeout = '5s';

BEGIN;
SELECT * FROM accounts WHERE id = 'A' FOR UPDATE;
-- If can't acquire within 5s, transaction fails with error
-- Better than hanging forever
COMMIT;

分散システムのパターン

// ✅ CORRECT: Distributed lock with lease
class DistributedLock {
  async acquire(resource: string, leaseDuration: number): Promise<Lease> {
    const lease: Lease = {
      id: uuid(),
      resource,
      expiresAt: Date.now() + leaseDuration,
    };
    
    // Atomic set-if-not-exists with TTL
    const acquired = await redis.set(
      `lock:${resource}`,
      JSON.stringify(lease),
      'NX',  // Only if not exists
      'PX', leaseDuration  // Expire after duration
    );
    
    if (!acquired) {
      throw new LockNotAvailableError(resource);
    }
    
    return lease;
  }
  
  async release(lease: Lease): Promise<void> {
    // Only release if we still own it (compare lease ID)
    const script = `
      if redis.call("get", KEYS[1]) == ARGV[1] then
        return redis.call("del", KEYS[1])
      else
        return 0
      end
    `;
    await redis.eval(script, 1, `lock:${lease.resource}`, JSON.stringify(lease));
  }
}

プレッシャーへの対応プロトコル

1. 「タイムアウトを長くすればいい」

プレッシャー：「タイムアウトを延ばして失敗を避けよう」

**回答：**タイムアウトを延ばすと、失敗するまでのデッドロック時間が長くなります。デッドロック自体は残ります。

**対応：**ロック取得順序を修正してください。タイムアウトは安全策であり、解決策ではありません。

2. 「高負荷時にしか起きない」

プレッシャー：「まれなエッジケースだから、修正する価値はない」

**回答：**本番環境は高負荷になります。規模が大きくなると、「まれ」は「常態」になります。デッドロックは恒久的な障害です。

**対応：**今すぐ修正してください。デッドロックはトラフィックの増加に伴って増えます。

3. 「異なるサービスなら競合しない」

プレッシャー：「サービスは互いに独立している」

**回答：**リソース（DBの行、Redisのキー、ファイルなど）を共有していれば、競合します。

**対応：**サービス間でロック取得順序を調整してください。

4. 「再起動すればいい」

プレッシャー：「再起動すればデッドロックは解消する」

**回答：**再起動すると、実行中のトランザクションが強制終了します。データ破損のリスクがあり、ユーザーにも影響します。根本原因は残ります。

**対応：**デッドロックを防止してください。症状への対処で済ませないでください。

危険信号 — 作業を止めて再検討してください

次のいずれかに気づいたら、デッドロックのリスクが高い状態です：

• コード経路によってロックの取得順序が異なる
• 明確な階層がないまま、ロックをネストして取得している
• 「このエンドポイントはときどきハングする」
• ロックのタイムアウトがない
• 非同期処理をまたいでロックを保持している
• 調整せずにサービス間でロックを取得している
• ループ内でロックを取得している

これらに該当する場合は、ロック戦略を再設計してください。

デッドロックの検出

// Runtime deadlock detection
class DeadlockDetector {
  private waitGraph: Map<string, Set<string>> = new Map();  // who waits for whom
  
  recordWaiting(waiter: string, holder: string): void {
    if (!this.waitGraph.has(waiter)) {
      this.waitGraph.set(waiter, new Set());
    }
    this.waitGraph.get(waiter)!.add(holder);
    
    // Check for cycle
    if (this.hasCycle(waiter)) {
      throw new DeadlockDetectedError(
        `Deadlock: ${this.describeCycle(waiter)}`
      );
    }
  }
  
  private hasCycle(start: string, visited = new Set<string>()): boolean {
    if (visited.has(start)) return true;
    visited.add(start);
    
    for (const next of this.waitGraph.get(start) || []) {
      if (this.hasCycle(next, visited)) return true;
    }
    
    visited.delete(start);
    return false;
  }
}

よくある正当化（すべて誤りです）

言い訳	実態
「タイムアウトで対処できる」	タイムアウトは症状を和らげるだけです。デッドロックは発生します。
「通常の負荷ではまれだ」	重要なのは本番環境の負荷です。
「サービスは分離されている」	DBを共有していれば、リソースも共有しており、デッドロックが発生する可能性があります。
「停止したら再起動すればいい」	トランザクションを強制終了し、状態を破損させます。
「ロックの順序付けは制約が多すぎる」	順序付けされたロックは並列処理を可能にします。デッドロックはそれを妨げます。
「テストでは問題なかった」	テストでは本番環境のような同時実行は発生しません。

クイックリファレンス

戦略	使用する場面
一貫した順序付け	デフォルトの選択肢 — 常にロックの順序を統一する
ロックのタイムアウト	あらゆるロック処理の安全策
try-lockとバックオフ	競合が激しく、再試行できる場合
単一の粗粒度ロック	スループットが低くてもよく、シンプルさが必要な場合
ロック階層	リソースのネストがある複雑なシステム
リース付き分散ロック	サービス間の調整

デッドロック防止チェックリスト

要件	確認
すべてのロック取得で一貫した順序に従っている	☐
ロックのタイムアウトが設定されている	☐
finally ブロックでロックが解放されている	☐
可能な場合、await 境界をまたいでロックを保持していない	☐
デッドロックの検出・監視が導入されている	☐
チームをまたぐコードでロック順序が文書化されている	☐

要点

ロックの順序を決めましょう。必ず。すべての経路で。すべてのサービスで。

デッドロックは、一貫性のないロック順序が原因で発生します。順序（アルファベット順、ID 順、階層順）を決め、すべての場所で徹底してください。安全策としてタイムアウトを追加しましょう。ロック競合を監視してください。「とりあえずタイムアウトを追加して」と言われたら、代わりに順序を修正しましょう。