Reduce fair-locking deadlock detector amplification with key nodes

Background

With fair locking, waiters remain in TiKV when lock ownership changes.

Assume T1 owns a hot key and T2 ... Tn are waiting for it. The current deadlock detector represents the dependencies as transaction-to-transaction edges:

T2 -> T1
T3 -> T1
T4 -> T1

The key and its hash are stored as metadata of each edge, but the key itself is not a node in the graph.

When ownership changes from T1 to T2, TiKV updates the deadlock relationship for every remaining waiter. With many waiters and frequent ownership changes, the resulting Cleanup + Detect requests can be amplified significantly and eventually cause OOM, as described in #19846.

#20002 is a short-term mitigation. It avoids repeatedly updating these edges after an owner change, with the trade-off that some deadlocks may only be resolved after lock timeout and retry.

Proposed model

Represent each locked key as an explicit key node in the deadlock graph:

T2 ─┐
T3 ─┼──> key1 ──> T1
T4 ─┘

There are two kinds of edges:

• Transaction -> Key: the transaction is waiting for the key.
• Key -> Transaction: the key is owned by the transaction.

When ownership changes from T1 to T2:

• Remove the wait edge T2 -> key1, because T2 has acquired the lock.
• Change the owner edge from key1 -> T1 to key1 -> T2.
• Keep the wait edges of T3, T4, and the other waiters unchanged.

The graph then becomes:

T3 ─┐
T4 ─┼──> key1 ──> T2
... ┘

The detector could provide operations similar to:

• RegisterWait(transaction, key, owners)
• UnregisterWait(transaction, key)
• UpdateOwners(key, old_owners, new_owners)
• CleanupTransaction(transaction)

RegisterWait creates or refreshes the key-owner relationship, checks whether adding Transaction -> Key forms a cycle, and then registers the wait edge.

During a fair-locking handoff, the promoted transaction's wait edge is removed and the key-owner relationship is updated. A deadlock check is performed for the handoff, but the wait edges of all remaining waiters do not need to be rewritten.

Shared locks can naturally be represented by multiple Key -> Transaction edges. A deadlock victim must always be a transaction rather than a key node.

This changes a normal fair-locking handoff from O(number of waiters) detector edge updates and detect requests to O(1) graph updates and a deadlock check.

The current graph stores key information on transaction-to-transaction edges, so the same hot key may be duplicated for many waiters. With a key node, the key only needs to be stored once and can be shared by all wait edges, reducing detector memory usage.

Relation to #17451

This is related to #17451, but uses a different internal graph representation.

#17451 batches owner-change RPCs by key while still rewriting every affected transaction-to-owner edge inside the detector. With key nodes, the remaining transactions continue to point to the same key node, so their wait edges do not change when the owner changes.

Compatibility

The new graph should use a V2 deadlock-detection protocol so that V1 and V2 graph semantics are not mixed during a rolling upgrade.

One possible rollout is:

1. Ship V2 support while continuing to use V1.
2. Upgrade all TiKV nodes.
3. Enable V2 cluster-wide, reset the detector graph, and replay existing waiters.
4. Keep V1 as a fallback for some time.