Build a deadlock and let the database find it

import java.util.*;

/**
 * Warm-up: write the part of a database that notices two transactions are
 * stuck on each other.
 *
 * No database and no threads. Two transactions interleaved in an order you
 * write by hand, because a deadlock that depends on timing is not something
 * you can study.
 */
public class Starter {

    /** row -> the transaction holding its exclusive lock. */
    static final Map<String, String> heldBy = new LinkedHashMap<>();
    /** transaction -> the row it is currently blocked on. */
    static final Map<String, String> waitingFor = new LinkedHashMap<>();

    public static void main(String[] args) {

        // TODO 1: write lock(txn, row). Three outcomes:
        //   - the row is free, or already yours   -> take it, return OK
        //   - someone else holds it               -> record the wait, return BLOCKED
        //   - the wait would close a cycle        -> return DEADLOCK
        //
        // Do not attempt the cycle check yet. Get the first two working and
        // script this interleaving:
        //
        //   T1 locks acct:A
        //   T2 locks acct:B
        //   T1 locks acct:B      (blocked)
        //   T2 locks acct:A      (blocked)
        //
        // Both are now blocked forever and nothing has noticed. That is the
        // state a real database has to detect.

        // TODO 2: now the detection. From the transaction that is about to
        // wait, follow the chain: it waits for a row, that row is held by
        // someone, who may be waiting for another row, and so on. If you
        // arrive back at where you started, that is the cycle.
        //
        // Print the cycle when you find it, as T2 -> T1 -> T2.

        // TODO 3: pick a victim and roll it back — release every lock it
        // holds and clear its wait. Confirm the survivor can now proceed.
        //
        // Real engines choose the cheapest transaction to redo. Say why the
        // application cannot rely on which one it will be.

        // TODO 4: now prevent it. Run the same two transfers, but have both
        // transactions sort the two account ids and lock the lower one first.
        // Watch which line changes: one transaction now waits BEFORE it holds
        // anything. Explain in one sentence why that makes a cycle impossible.

        // TODO 5: retry the victim. After the survivor commits, run the
        // victim's statements again from the start and confirm it succeeds.
        // Say why this is safe here and impossible for a deadlocked Java
        // thread — the answer is one word about the rollback.

        // TODO 6: the surprising one. Model a table of five rows and a
        // statement with no usable index, which must lock every row it
        // EXAMINES rather than only the ones it matches. Then script:
        //
        //   T1 updates row 5 by primary key
        //   T2 updates by an unindexed column that matches only row 1
        //   T1 updates row 1 by primary key
        //
        // The rows they change do not overlap. Show that they deadlock anyway,
        // and say what you would check first in a real deadlock report.

        // TODO 7: finally, a lock wait timeout is NOT a deadlock — there is no
        // cycle, just a holder that is too slow. Script one. Say why the two
        // look identical to the application and want opposite responses.
    }
}