Sign in Get started

Coding problem · Hard · Design & Data Structures

Row Lock Manager with Deadlock Detection

Hard Practical tasks

Implement a tiny row lock manager, like the one inside Postgres or InnoDB.

  • acquire(tx, row):
    • If the row is free, or already held by tx, grant it and return "granted".
    • Otherwise, if waiting would create a cycle (the row's holder is — directly or through a chain of waits — waiting for tx), the request is the deadlock victim: abort tx (release all its locks, granting each released row to the next waiter) and return "deadlock".
    • Otherwise append tx to the row's FIFO wait queue and return "waiting". (A transaction waits for at most one row at a time.)
  • release(tx) — commit or rollback: remove tx from any wait queue, release every row it holds, and grant each released row to the first waiter in its queue. Return the grants as "tx:row" strings, processing released rows in ascending row order.

Practice for How Deadlocks Happen.

Example 1

Input: ["LockManager","acquire","acquire","acquire","acquire","release","acquire"]
[[],["T1","A"],["T2","B"],["T1","B"],["T2","A"],["T1"],["T2","A"]]
Output: [null,"granted","granted","waiting","deadlock",[],"granted"]
Explanation: T2 asking for A would close the cycle T2→T1→T2, so T2 is aborted; B passes to the waiting T1.

Hints

Hint 1

Track: row → holder, row → FIFO queue, tx → row it waits for.

Hint 2

Cycle check: start at the holder of the requested row; follow 'waits for row' → 'holder of that row' until you reach tx (deadlock) or a transaction that isn't waiting.

Hint 3

Aborting is the same as releasing, except acquire returns "deadlock".

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time acquire O(chain length), release O(rows held · log rows held) · Space O(rows + transactions)

Keep three maps: the holder of each row, a FIFO queue per row, and which row each transaction waits for. Granting is O(1). Before enqueueing, walk the wait-for chain from the row's holder: holder → the row it waits for → that row's holder … If the walk reaches the requester, enqueueing would close a cycle, so the requester becomes the victim and is aborted like a release. Real databases detect cycles the same way (Postgres after deadlock_timeout, InnoDB immediately) and pick a victim, which surfaces in your app as SQLSTATE 40P01 / MySQL error 1213.

Reference solution

class LockManager {
  constructor() {
    this.holder = new Map();      // row -> tx
    this.queue = new Map();       // row -> [tx]
    this.waitingFor = new Map();  // tx -> row
  }

  acquire(tx, row) {
    const owner = this.holder.get(row);
    if (owner === undefined || owner === tx) {
      this.holder.set(row, tx);
      return "granted";
    }
    // Would waiting close a cycle? Follow holder -> row it waits for -> that row's holder ...
    const seen = new Set();
    let cur = owner;
    while (cur !== undefined && !seen.has(cur)) {
      if (cur === tx) {
        this.release(tx);
        return "deadlock";
      }
      seen.add(cur);
      const row2 = this.waitingFor.get(cur);
      cur = row2 === undefined ? undefined : this.holder.get(row2);
    }
    if (!this.queue.has(row)) this.queue.set(row, []);
    this.queue.get(row).push(tx);
    this.waitingFor.set(tx, row);
    return "waiting";
  }

  release(tx) {
    const waitRow = this.waitingFor.get(tx);
    if (waitRow !== undefined) {
      this.queue.set(waitRow, this.queue.get(waitRow).filter((t) => t !== tx));
      this.waitingFor.delete(tx);
    }
    const rows = [...this.holder].filter(([, t]) => t === tx).map(([r]) => r).sort();
    const grants = [];
    for (const row of rows) {
      this.holder.delete(row);
      const q = this.queue.get(row) ?? [];
      if (q.length) {
        const next = q.shift();
        this.holder.set(row, next);
        this.waitingFor.delete(next);
        grants.push(`${next}:${row}`);
      }
    }
    return grants;
  }
}

Common mistakes

  • Forgetting to remove an aborted or released transaction from wait queues.
  • Granting a released row to a waiter without clearing its 'waiting for' entry.
  • Treating a re-request of a row you already hold as a wait.

Follow-up questions

  • Shared (read) and exclusive (write) lock modes.
  • Lock timeouts: give up after N ms instead of waiting forever.
  • Choose the youngest transaction as the victim instead of the requester.