Database Management SystemsDeadlock Handling

Deadlock Handling in Database Systems

LevelIntermediate

Duration75 mins

TopicDeadlock Handling

5 / 5

Deadlock Recovery

Breaking the Cycle

A deadlock has been detected. Multiple transactions are locked in a circular embrace, each waiting for resources held by another. The system knows the problem exists—now it must solve it. But how?

Deadlock recovery is the final phase of deadlock management—the moment when detection's diagnosis becomes action. The system must make critical decisions: Which transaction should be sacrificed? How much work should be undone? How do we minimize the cascade of effects?

These decisions have real consequences. Choosing the wrong victim can waste hours of completed work. Improper rollback can leave data inconsistent. Poor recovery strategies can cause the same deadlock to recur immediately. Mastering deadlock recovery is essential for maintaining database health under concurrent load.

What You Will Learn

By the end of this page, you will master the complete deadlock recovery lifecycle—victim selection algorithms, rollback strategies, cascading abort prevention, retry mechanisms, and best practices for minimizing recovery overhead in production systems.

The Recovery Challenge

When a deadlock is detected, the database faces a fundamental problem: the circular wait must be broken, but doing so requires revoking guaranteed transaction properties. Let's understand the full scope of this challenge:

The Irrevocable Decision:

To break a deadlock cycle, at least one transaction must be aborted. This transaction becomes the victim. Aborting means:

All changes rolled back — Every modification made by the victim is undone
All locks released — Other transactions in the cycle can now proceed
Transaction must restart — The victim's work starts over from the beginning
Application notified — Error returned to the application layer

The challenge is that ANY transaction in the cycle could be chosen as the victim. Different choices have vastly different consequences.

Recovery Goals

•Minimize work lost — Prefer aborting transactions that have done less work
•Maximize throughput — Get the system back to productive work quickly
•Ensure fairness — Don't always victimize the same transaction (starvation)
•Prevent cascade — Avoid triggering additional aborts
•Enable retry — Make it easy for victims to successfully retry

Recovery Constraints

•Must abort at least one — The cycle cannot be broken otherwise
•May need multiple — In complex cycles, single victim may not suffice
•Cannot predict future — We don't know if victims will deadlock again
•Time pressure — Other transactions are blocked waiting
•Consistency required — Rollback must maintain data integrity

The Cost is Real

A deadlock victim loses ALL its work. If a transaction has been running for 10 minutes, processed 100,000 rows, and is 99% complete—being selected as a victim means starting over. Good victim selection can save hours of wasted computation.

Victim Selection Algorithms

Choosing which transaction to abort is perhaps the most critical decision in deadlock recovery. Various algorithms exist, each optimizing for different goals:

Algorithm 1: Minimum Work Done (Cost-Based)

Select the transaction that has performed the least amount of work. This minimizes wasted effort.

def select_victim_minimum_work(deadlock_cycle):
    """
    Select victim based on minimum work already performed.
    Work can be measured by rows modified, log bytes generated, CPU time, etc.
    """
    min_work = float('inf')
    victim = None
    
    for transaction in deadlock_cycle:
        work = calculate_work_done(transaction)
        if work < min_work:
            min_work = work
            victim = transaction
    
    return victim

def calculate_work_done(transaction):
    """Calculate approximate work done by transaction."""
    return (
        transaction.rows_modified * 1.0 +
        transaction.rows_read * 0.1 +
        transaction.log_bytes_written * 0.01 +
        transaction.cpu_time_ms * 0.001
    )

Pros: Minimizes wasted work Cons: May repeatedly victimize young transactions, causing starvation

Algorithm 2: Youngest Transaction (Timestamp-Based)

Always abort the transaction that started most recently. Simple and predictable.

def select_victim_youngest(deadlock_cycle):
    """Select the most recently started transaction."""
    return max(deadlock_cycle, key=lambda t: t.start_timestamp)

Algorithm 3: Minimum Locks Held

Select the transaction holding the fewest locks, minimizing disruption to other waiters.

def select_victim_minimum_locks(deadlock_cycle):
    """Select transaction holding fewest locks."""
    return min(deadlock_cycle, key=lambda t: len(t.held_locks))

Algorithm 4: Priority-Based

Assign explicit priorities to transactions; always abort lowest priority.

def select_victim_priority(deadlock_cycle):
    """Select lowest priority transaction."""
    return min(deadlock_cycle, key=lambda t: t.priority)

Victim Selection Algorithm Comparison
Algorithm	Optimization Goal	Starvation Risk	Implementation Complexity	Best For
Minimum Work	Minimize wasted effort	High (small txns always chosen)	Medium	Varied transaction sizes
Youngest	Simple, predictable	Medium (new txns disadvantaged)	Low	General purpose
Minimum Locks	Minimize blocking	Low	Low	High-contention workloads
Priority-Based	Business requirements	None (explicit control)	Medium	Mixed criticality workloads
Composite Score	Balanced optimization	Low	High	Production systems

Composite Victim Scoring

Production databases typically use a composite cost function that weighs multiple factors to select victims fairly and efficiently:

The Composite Approach:

Instead of optimizing for a single factor, assign a cost score to each transaction considering multiple dimensions:

victim_selection.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class VictimSelector:
    """
    Production-grade victim selection using composite scoring.
    """
    
    # Weight configuration (tunable per workload)
    WEIGHT_LOG_SIZE = 1.0       # Log records generated
    WEIGHT_LOCKS_HELD = 0.5    # Number of locks held
    WEIGHT_CPU_TIME = 0.3      # CPU cycles consumed
    WEIGHT_AGE = 0.2           # Transaction age (prevent starvation)
    WEIGHT_ROLLBACK_COUNT = 2.0 # Previous rollbacks (prevent repeat)
    WEIGHT_PRIORITY = 5.0      # Explicit priority (business logic)
    
    def calculate_victim_cost(self, transaction):
        """
        Higher cost = less desirable to abort.
        We select the transaction with LOWEST cost.
        """
        cost = 0.0
        
        # Factor 1: Work done (log records are best proxy)
        cost += transaction.log_records_count * self.WEIGHT_LOG_SIZE
        
        # Factor 2: Locks held (aborting releases these)
        cost += len(transaction.held_locks) * self.WEIGHT_LOCKS_HELD
        
        # Factor 3: CPU time invested
        cost += transaction.cpu_time_ms * self.WEIGHT_CPU_TIME
        
        # Factor 4: Age (older transactions should complete)
        age_seconds = time.time() - transaction.start_timestamp
        cost += age_seconds * self.WEIGHT_AGE
        
        # Factor 5: Starvation prevention (penalize repeat victims)
        cost += transaction.rollback_count * self.WEIGHT_ROLLBACK_COUNT
        
        # Factor 6: Business priority
        # Higher priority = higher cost = less likely to abort
        cost += transaction.priority * self.WEIGHT_PRIORITY
        
        return cost
    
    def select_victim(self, deadlock_cycle):
        """
        Select transaction with minimum cost to abort.
        """
        if not deadlock_cycle:
            return None
        
        victim = min(deadlock_cycle, key=self.calculate_victim_cost)
        
        # Log selection rationale for debugging
        self.log_selection_rationale(deadlock_cycle, victim)
        
        return victim
    
    def log_selection_rationale(self, cycle, victim):
        """Log why this victim was selected for debugging."""
        scores = [(t.id, self.calculate_victim_cost(t)) for t in cycle]
        logging.info(
            f"Deadlock victim selection: {victim.id} "
            f"(cost: {self.calculate_victim_cost(victim):.2f}). "
            f"All scores: {scores}"
        )

Tuning Is Critical

The weights in composite scoring should be tuned based on your workload. A data warehouse with long-running analytical queries should weight CPU_TIME highly. An OLTP system with many small transactions might weight ROLLBACK_COUNT to prevent repeat failures.

Rollback Strategies

Once a victim is selected, the transaction must be rolled back. The rollback strategy determines how much work is undone:

Strategy 1: Total Rollback

Rollback the entire transaction to its beginning. Simple and safe, but maximizes work lost.

Transaction Timeline:
[START] → Op1 → Op2 → Op3 → [DEADLOCK] → [ROLLBACK TO START]
                                          ↑ All work lost

Implementation:

Apply undo log records in reverse order
Release all locks held
Return error to application
Application typically retries from beginning

Strategy 2: Partial Rollback (Savepoint-Based)

Rollback only to the most recent savepoint that releases the blocking lock. Preserves work done before the deadlock.

Transaction with Savepoints:
[START] → Op1 → [SAVEPOINT A] → Op2 → [SAVEPOINT B] → Op3 → [DEADLOCK]

Partial Rollback Options:
1. Rollback to B: Undo Op3, keep Op1, Op2 → Only Op3 lock needed?
2. Rollback to A: Undo Op2, Op3, keep Op1 → A releases blocking lock?

Benefits:

Less work lost if savepoint releases needed lock
Transaction can continue from checkpoint
Useful for complex, long-running transactions

Limitations:

Savepoints must be strategically placed
May not release the needed lock
Adds complexity to transaction logic

Rollback Strategy Comparison
Strategy	Work Preserved	Complexity	Lock Release	Application Impact
Total Rollback	None	Low	All locks released	Full restart required
Partial (to savepoint)	Work before savepoint	Medium	Only affected locks	Resume from savepoint
Partial (minimum)	Maximum possible	High	Only blocking lock	Complex state management

Total Rollback Is Most Common

Most databases default to total rollback because partial rollback requires application cooperation (savepoints) and doesn't always release the needed lock. The simplicity and reliability of total rollback makes it the practical choice.

Cascading Aborts and Prevention

A dangerous phenomenon in deadlock recovery is the cascading abort—where aborting one transaction forces the abort of others that read its uncommitted data:

Cascade Scenario:

T₁: Write X = 100
T₂: Read X (sees 100, uncommitted from T₁)
T₂: Based on X, modifies Y and Z
T₃: Read Y (sees uncommitted value from T₂)

[DEADLOCK DETECTED: T₁ selected as victim]

T₁ aborted → X value 100 never committed
T₂ read dirty data → T₂ must abort (cascade)
T₃ read T₂'s dirty data → T₃ must abort (cascade)

A single abort has cascaded into three aborts!

Cascade Prevention Strategies

•Strict 2PL Protocol — Hold all locks until commit. No other transaction can read uncommitted data, so cascades are impossible. Most common approach.
•No Dirty Reads — Use isolation level that prevents reading uncommitted data (READ COMMITTED or higher). This is the default in most databases.
•MVCC with Snapshot Isolation — Transactions read from consistent snapshots, never uncommitted data. Automatically prevents cascades.
•Cascadeless Victim Selection — When selecting victims, prefer transactions that no other transaction has read from. Limits cascade scope.
•Deferred Write Propagation — Don't make writes visible until commit. Aborts don't affect other transactions.

Why Modern Databases Avoid Cascades:

Most production databases use Strict 2PL or MVCC, which inherently prevent cascading aborts:

With Strict 2PL:
T₁: Write X = 100 (holds X-lock until commit)
T₂: Read X → BLOCKED (T₁ holds lock)

[DEADLOCK DETECTED: T₁ selected as victim]

T₁ aborted → X never read by anyone
T₂ unblocked → Reads original X value

No cascade! T₂ never saw T₁'s uncommitted write.

This is why isolation level configuration matters for deadlock recovery—higher isolation levels prevent cascades but may increase deadlock frequency (more blocking = more cycles possible).

READ UNCOMMITTED Risk

If using READ UNCOMMITTED isolation, cascading aborts ARE possible. This isolation level is rarely appropriate for transactional workloads precisely because of this risk. Use READ COMMITTED or higher for production OLTP.

Automatic Retry Mechanisms

After a transaction is aborted due to deadlock, it should typically be retried. Proper retry mechanisms are essential for transparent deadlock handling:

Retry Design Principles:

deadlock_retry.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
class DeadlockRetryHandler:
    """
    Robust retry handler for deadlock victims.
    """
    
    def __init__(
        self,
        max_retries: int = 5,
        base_delay_ms: int = 100,
        max_delay_ms: int = 5000,
        jitter_factor: float = 0.3
    ):
        self.max_retries = max_retries
        self.base_delay_ms = base_delay_ms
        self.max_delay_ms = max_delay_ms
        self.jitter_factor = jitter_factor
    
    def execute_with_retry(self, transaction_func, *args, **kwargs):
        """
        Execute transaction with automatic deadlock retry.
        """
        last_exception = None
        
        for attempt in range(self.max_retries):
            try:
                return transaction_func(*args, **kwargs)
                
            except DeadlockException as e:
                last_exception = e
                
                if attempt == self.max_retries - 1:
                    # Final attempt failed
                    logging.error(
                        f"Transaction failed after {self.max_retries} "
                        f"deadlock retries: {e}"
                    )
                    raise
                
                # Calculate backoff delay with jitter
                delay = self._calculate_delay(attempt)
                logging.warning(
                    f"Deadlock on attempt {attempt + 1}, "
                    f"retrying in {delay}ms"
                )
                
                time.sleep(delay / 1000.0)
        
        raise last_exception
    
    def _calculate_delay(self, attempt: int) -> int:
        """
        Calculate delay with exponential backoff and jitter.
        Jitter prevents synchronized retry storms.
        """
        # Exponential backoff
        delay = self.base_delay_ms * (2 ** attempt)
        delay = min(delay, self.max_delay_ms)
        
        # Add random jitter (±jitter_factor%)
        jitter_range = delay * self.jitter_factor
        jitter = random.uniform(-jitter_range, jitter_range)
        delay = int(delay + jitter)
        
        return max(delay, 1)  # Minimum 1ms
 
 
# Usage example
retry_handler = DeadlockRetryHandler(max_retries=5)
 
def transfer_funds(from_acc, to_acc, amount):
    with database.transaction():
        # Lock accounts (could deadlock)
        from_balance = db.get_balance(from_acc)
        to_balance = db.get_balance(to_acc)
        
        db.set_balance(from_acc, from_balance - amount)
        db.set_balance(to_acc, to_balance + amount)
 
# Execute with automatic retry
retry_handler.execute_with_retry(
    transfer_funds, 
    from_acc=1000, 
    to_acc=2000, 
    amount=100.00
)

Retry Best Practices

•Exponential Backoff — Each retry waits longer than the last (100ms → 200ms → 400ms). Reduces contention during high-load periods.
•Random Jitter — Add randomness to delays to prevent synchronized retries. Without jitter, multiple victims retry simultaneously and re-deadlock.
•Maximum Retry Limit — Cap retries to prevent infinite loops. 3-5 retries is typical; persistent failure indicates a systemic issue.
•Idempotent Operations — Ensure transactions can be safely re-executed. Non-idempotent operations (like incrementing) need careful handling.
•Preserving Context — Application state should be reconstructed correctly on retry. Pass all necessary data, don't rely on session state.

Recovery in Major Databases

Understanding how specific databases handle deadlock recovery helps you configure and troubleshoot production systems:

MySQL InnoDB:

InnoDB automatically detects and resolves deadlocks. The victim is rolled back and receives error 1213.

-- MySQL deadlock handling example
-- Application should catch and retry on error 1213

-- Check deadlock information
SHOW ENGINE INNODB STATUS\G
-- Look for 'LATEST DETECTED DEADLOCK' section

-- Victim selection is based on:
-- 1. Approximate row count modified (less = more likely victim)
-- 2. Insert buffer size
-- InnoDB typically picks the transaction that modified fewer rows

-- Configure automatic rollback behavior
SET innodb_rollback_on_timeout = ON;  -- Rollback entire transaction on timeout

PostgreSQL:

PostgreSQL aborts the transaction that completed the cycle (the one whose lock request created the deadlock). Error code is 40P01.

-- PostgreSQL returns SQLSTATE 40P01 for deadlocks

-- Logging configuration for deadlocks
SET log_lock_waits = on;              -- Log when waiting for locks
SET deadlock_timeout = '1s';          -- Detection delay

-- View locks and pending requests
SELECT * FROM pg_locks WHERE NOT granted;

-- Detailed deadlock info in server logs:
-- ERROR: deadlock detected
-- DETAIL: Process 12345 waits for ShareLock on transaction 67890;
--         blocked by process 23456.
--         Process 23456 waits for ShareLock on transaction 12345;
--         blocked by process 12345.
-- HINT: See server log for query details.

SQL Server:

SQL Server uses sophisticated cost-based victim selection with the DEADLOCK_PRIORITY setting allowing explicit control.

-- SQL Server deadlock priority (LOW, NORMAL, HIGH)
SET DEADLOCK_PRIORITY LOW;   -- This session more likely to be victim
SET DEADLOCK_PRIORITY HIGH;  -- This session protected from victimization

-- Numeric priority (-10 to 10)
SET DEADLOCK_PRIORITY 5;     -- Higher = less likely victim

-- Capture deadlock graphs with Extended Events
CREATE EVENT SESSION [DeadlockCapture] ON SERVER 
ADD EVENT sqlserver.xml_deadlock_report 
ADD TARGET package0.event_file(SET filename=N'Deadlocks');

-- Error number for deadlock is 1205
-- Applications should catch and retry on this error

Database Recovery Comparison
Database	Error Code	Victim Selection	Retry Responsibility	Priority Control
MySQL	1213	Fewest rows modified	Application layer	Limited (no explicit setting)
PostgreSQL	40P01	Cycle-completing transaction	Application layer	None
SQL Server	1205	Cost-based composite	Application layer	DEADLOCK_PRIORITY
Oracle	ORA-00060	Cycle-completing, oldest	Application layer	Limited

Summary: Mastering Deadlock Recovery

Deadlock recovery is the critical final phase of deadlock management—where detection becomes action. Here are the essential takeaways:

Key Takeaways

•Recovery requires sacrificing a transaction — at least one victim must be aborted to break the deadlock cycle. The choice of victim significantly impacts system efficiency.
•Victim selection algorithms vary — from simple (youngest transaction) to sophisticated (composite cost scoring). Production systems typically use multi-factor cost functions.
•Composite scoring balances multiple factors — including work done, locks held, transaction age, rollback history, and business priority. Weights should be tuned for your workload.
•Rollback strategies trade completeness for efficiency — total rollback is simple and safe; partial rollback preserves work but adds complexity. Most databases use total rollback.
•Cascading aborts are prevented by proper isolation levels (READ COMMITTED or higher) and locking protocols (Strict 2PL). Cascades multiply the cost of deadlocks.
•Retry mechanisms are essential — exponential backoff with jitter prevents retry storms. Applications must be prepared to catch deadlock errors and retry.
•Each database has specific recovery behaviors — understand your database's error codes, victim selection logic, and configuration options for production troubleshooting.

Module Complete:

Congratulations! You have now mastered the complete lifecycle of deadlock handling:

Definition — Understanding what deadlocks are and the four Coffman conditions
Detection — Algorithms and timing strategies for identifying deadlocks
Wait-For Graphs — The core data structure enabling detection
Prevention — Techniques that make deadlocks impossible
Recovery — Victim selection, rollback, and retry mechanisms

This knowledge equips you to design, configure, and troubleshoot concurrent database systems at the highest level.

Module Complete: Deadlock Handling Mastery

You now possess comprehensive expertise in deadlock handling—from theoretical foundations through practical implementation. This knowledge is essential for any database professional working with concurrent transaction systems and is directly applicable to production database administration and application development.

5 / 5

Loading learning content...

Database Management SystemsDeadlock Handling

Deadlock Handling in Database Systems

LevelIntermediate

Duration75 mins

TopicDeadlock Handling

5 / 5

Deadlock Recovery

Breaking the Cycle

A deadlock has been detected. Multiple transactions are locked in a circular embrace, each waiting for resources held by another. The system knows the problem exists—now it must solve it. But how?

What You Will Learn

The Recovery Challenge

The Irrevocable Decision:

To break a deadlock cycle, at least one transaction must be aborted. This transaction becomes the victim. Aborting means:

All changes rolled back — Every modification made by the victim is undone
All locks released — Other transactions in the cycle can now proceed
Transaction must restart — The victim's work starts over from the beginning
Application notified — Error returned to the application layer

The challenge is that ANY transaction in the cycle could be chosen as the victim. Different choices have vastly different consequences.

Recovery Goals

•Minimize work lost — Prefer aborting transactions that have done less work
•Maximize throughput — Get the system back to productive work quickly
•Ensure fairness — Don't always victimize the same transaction (starvation)
•Prevent cascade — Avoid triggering additional aborts
•Enable retry — Make it easy for victims to successfully retry

Recovery Constraints

•Must abort at least one — The cycle cannot be broken otherwise
•May need multiple — In complex cycles, single victim may not suffice
•Cannot predict future — We don't know if victims will deadlock again
•Time pressure — Other transactions are blocked waiting
•Consistency required — Rollback must maintain data integrity

The Cost is Real

Victim Selection Algorithms

Choosing which transaction to abort is perhaps the most critical decision in deadlock recovery. Various algorithms exist, each optimizing for different goals:

Algorithm 1: Minimum Work Done (Cost-Based)

Select the transaction that has performed the least amount of work. This minimizes wasted effort.

def select_victim_minimum_work(deadlock_cycle):
    """
    Select victim based on minimum work already performed.
    Work can be measured by rows modified, log bytes generated, CPU time, etc.
    """
    min_work = float('inf')
    victim = None
    
    for transaction in deadlock_cycle:
        work = calculate_work_done(transaction)
        if work < min_work:
            min_work = work
            victim = transaction
    
    return victim

def calculate_work_done(transaction):
    """Calculate approximate work done by transaction."""
    return (
        transaction.rows_modified * 1.0 +
        transaction.rows_read * 0.1 +
        transaction.log_bytes_written * 0.01 +
        transaction.cpu_time_ms * 0.001
    )

Pros: Minimizes wasted work Cons: May repeatedly victimize young transactions, causing starvation

Algorithm 2: Youngest Transaction (Timestamp-Based)

Always abort the transaction that started most recently. Simple and predictable.

def select_victim_youngest(deadlock_cycle):
    """Select the most recently started transaction."""
    return max(deadlock_cycle, key=lambda t: t.start_timestamp)

Algorithm 3: Minimum Locks Held

Select the transaction holding the fewest locks, minimizing disruption to other waiters.

def select_victim_minimum_locks(deadlock_cycle):
    """Select transaction holding fewest locks."""
    return min(deadlock_cycle, key=lambda t: len(t.held_locks))

Algorithm 4: Priority-Based

Assign explicit priorities to transactions; always abort lowest priority.

def select_victim_priority(deadlock_cycle):
    """Select lowest priority transaction."""
    return min(deadlock_cycle, key=lambda t: t.priority)

Victim Selection Algorithm Comparison
Algorithm	Optimization Goal	Starvation Risk	Implementation Complexity	Best For
Minimum Work	Minimize wasted effort	High (small txns always chosen)	Medium	Varied transaction sizes
Youngest	Simple, predictable	Medium (new txns disadvantaged)	Low	General purpose
Minimum Locks	Minimize blocking	Low	Low	High-contention workloads
Priority-Based	Business requirements	None (explicit control)	Medium	Mixed criticality workloads
Composite Score	Balanced optimization	Low	High	Production systems

Composite Victim Scoring

Production databases typically use a composite cost function that weighs multiple factors to select victims fairly and efficiently:

The Composite Approach:

Instead of optimizing for a single factor, assign a cost score to each transaction considering multiple dimensions:

victim_selection.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class VictimSelector:
    """
    Production-grade victim selection using composite scoring.
    """
    
    # Weight configuration (tunable per workload)
    WEIGHT_LOG_SIZE = 1.0       # Log records generated
    WEIGHT_LOCKS_HELD = 0.5    # Number of locks held
    WEIGHT_CPU_TIME = 0.3      # CPU cycles consumed
    WEIGHT_AGE = 0.2           # Transaction age (prevent starvation)
    WEIGHT_ROLLBACK_COUNT = 2.0 # Previous rollbacks (prevent repeat)
    WEIGHT_PRIORITY = 5.0      # Explicit priority (business logic)
    
    def calculate_victim_cost(self, transaction):
        """
        Higher cost = less desirable to abort.
        We select the transaction with LOWEST cost.
        """
        cost = 0.0
        
        # Factor 1: Work done (log records are best proxy)
        cost += transaction.log_records_count * self.WEIGHT_LOG_SIZE
        
        # Factor 2: Locks held (aborting releases these)
        cost += len(transaction.held_locks) * self.WEIGHT_LOCKS_HELD
        
        # Factor 3: CPU time invested
        cost += transaction.cpu_time_ms * self.WEIGHT_CPU_TIME
        
        # Factor 4: Age (older transactions should complete)
        age_seconds = time.time() - transaction.start_timestamp
        cost += age_seconds * self.WEIGHT_AGE
        
        # Factor 5: Starvation prevention (penalize repeat victims)
        cost += transaction.rollback_count * self.WEIGHT_ROLLBACK_COUNT
        
        # Factor 6: Business priority
        # Higher priority = higher cost = less likely to abort
        cost += transaction.priority * self.WEIGHT_PRIORITY
        
        return cost
    
    def select_victim(self, deadlock_cycle):
        """
        Select transaction with minimum cost to abort.
        """
        if not deadlock_cycle:
            return None
        
        victim = min(deadlock_cycle, key=self.calculate_victim_cost)
        
        # Log selection rationale for debugging
        self.log_selection_rationale(deadlock_cycle, victim)
        
        return victim
    
    def log_selection_rationale(self, cycle, victim):
        """Log why this victim was selected for debugging."""
        scores = [(t.id, self.calculate_victim_cost(t)) for t in cycle]
        logging.info(
            f"Deadlock victim selection: {victim.id} "
            f"(cost: {self.calculate_victim_cost(victim):.2f}). "
            f"All scores: {scores}"
        )

Tuning Is Critical

Rollback Strategies

Once a victim is selected, the transaction must be rolled back. The rollback strategy determines how much work is undone:

Strategy 1: Total Rollback

Rollback the entire transaction to its beginning. Simple and safe, but maximizes work lost.

Transaction Timeline:
[START] → Op1 → Op2 → Op3 → [DEADLOCK] → [ROLLBACK TO START]
                                          ↑ All work lost

Implementation:

Apply undo log records in reverse order
Release all locks held
Return error to application
Application typically retries from beginning

Strategy 2: Partial Rollback (Savepoint-Based)

Rollback only to the most recent savepoint that releases the blocking lock. Preserves work done before the deadlock.

Transaction with Savepoints:
[START] → Op1 → [SAVEPOINT A] → Op2 → [SAVEPOINT B] → Op3 → [DEADLOCK]

Partial Rollback Options:
1. Rollback to B: Undo Op3, keep Op1, Op2 → Only Op3 lock needed?
2. Rollback to A: Undo Op2, Op3, keep Op1 → A releases blocking lock?

Benefits:

Less work lost if savepoint releases needed lock
Transaction can continue from checkpoint
Useful for complex, long-running transactions

Limitations:

Savepoints must be strategically placed
May not release the needed lock
Adds complexity to transaction logic

Rollback Strategy Comparison
Strategy	Work Preserved	Complexity	Lock Release	Application Impact
Total Rollback	None	Low	All locks released	Full restart required
Partial (to savepoint)	Work before savepoint	Medium	Only affected locks	Resume from savepoint
Partial (minimum)	Maximum possible	High	Only blocking lock	Complex state management

Total Rollback Is Most Common

Cascading Aborts and Prevention

A dangerous phenomenon in deadlock recovery is the cascading abort—where aborting one transaction forces the abort of others that read its uncommitted data:

Cascade Scenario:

T₁: Write X = 100
T₂: Read X (sees 100, uncommitted from T₁)
T₂: Based on X, modifies Y and Z
T₃: Read Y (sees uncommitted value from T₂)

[DEADLOCK DETECTED: T₁ selected as victim]

T₁ aborted → X value 100 never committed
T₂ read dirty data → T₂ must abort (cascade)
T₃ read T₂'s dirty data → T₃ must abort (cascade)

A single abort has cascaded into three aborts!

Cascade Prevention Strategies

•Strict 2PL Protocol — Hold all locks until commit. No other transaction can read uncommitted data, so cascades are impossible. Most common approach.
•No Dirty Reads — Use isolation level that prevents reading uncommitted data (READ COMMITTED or higher). This is the default in most databases.
•MVCC with Snapshot Isolation — Transactions read from consistent snapshots, never uncommitted data. Automatically prevents cascades.
•Cascadeless Victim Selection — When selecting victims, prefer transactions that no other transaction has read from. Limits cascade scope.
•Deferred Write Propagation — Don't make writes visible until commit. Aborts don't affect other transactions.

Why Modern Databases Avoid Cascades:

Most production databases use Strict 2PL or MVCC, which inherently prevent cascading aborts:

With Strict 2PL:
T₁: Write X = 100 (holds X-lock until commit)
T₂: Read X → BLOCKED (T₁ holds lock)

[DEADLOCK DETECTED: T₁ selected as victim]

T₁ aborted → X never read by anyone
T₂ unblocked → Reads original X value

No cascade! T₂ never saw T₁'s uncommitted write.

This is why isolation level configuration matters for deadlock recovery—higher isolation levels prevent cascades but may increase deadlock frequency (more blocking = more cycles possible).

READ UNCOMMITTED Risk

Automatic Retry Mechanisms

After a transaction is aborted due to deadlock, it should typically be retried. Proper retry mechanisms are essential for transparent deadlock handling:

Retry Design Principles:

deadlock_retry.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
class DeadlockRetryHandler:
    """
    Robust retry handler for deadlock victims.
    """
    
    def __init__(
        self,
        max_retries: int = 5,
        base_delay_ms: int = 100,
        max_delay_ms: int = 5000,
        jitter_factor: float = 0.3
    ):
        self.max_retries = max_retries
        self.base_delay_ms = base_delay_ms
        self.max_delay_ms = max_delay_ms
        self.jitter_factor = jitter_factor
    
    def execute_with_retry(self, transaction_func, *args, **kwargs):
        """
        Execute transaction with automatic deadlock retry.
        """
        last_exception = None
        
        for attempt in range(self.max_retries):
            try:
                return transaction_func(*args, **kwargs)
                
            except DeadlockException as e:
                last_exception = e
                
                if attempt == self.max_retries - 1:
                    # Final attempt failed
                    logging.error(
                        f"Transaction failed after {self.max_retries} "
                        f"deadlock retries: {e}"
                    )
                    raise
                
                # Calculate backoff delay with jitter
                delay = self._calculate_delay(attempt)
                logging.warning(
                    f"Deadlock on attempt {attempt + 1}, "
                    f"retrying in {delay}ms"
                )
                
                time.sleep(delay / 1000.0)
        
        raise last_exception
    
    def _calculate_delay(self, attempt: int) -> int:
        """
        Calculate delay with exponential backoff and jitter.
        Jitter prevents synchronized retry storms.
        """
        # Exponential backoff
        delay = self.base_delay_ms * (2 ** attempt)
        delay = min(delay, self.max_delay_ms)
        
        # Add random jitter (±jitter_factor%)
        jitter_range = delay * self.jitter_factor
        jitter = random.uniform(-jitter_range, jitter_range)
        delay = int(delay + jitter)
        
        return max(delay, 1)  # Minimum 1ms
 
 
# Usage example
retry_handler = DeadlockRetryHandler(max_retries=5)
 
def transfer_funds(from_acc, to_acc, amount):
    with database.transaction():
        # Lock accounts (could deadlock)
        from_balance = db.get_balance(from_acc)
        to_balance = db.get_balance(to_acc)
        
        db.set_balance(from_acc, from_balance - amount)
        db.set_balance(to_acc, to_balance + amount)
 
# Execute with automatic retry
retry_handler.execute_with_retry(
    transfer_funds, 
    from_acc=1000, 
    to_acc=2000, 
    amount=100.00
)

Retry Best Practices

•Exponential Backoff — Each retry waits longer than the last (100ms → 200ms → 400ms). Reduces contention during high-load periods.
•Random Jitter — Add randomness to delays to prevent synchronized retries. Without jitter, multiple victims retry simultaneously and re-deadlock.
•Maximum Retry Limit — Cap retries to prevent infinite loops. 3-5 retries is typical; persistent failure indicates a systemic issue.
•Idempotent Operations — Ensure transactions can be safely re-executed. Non-idempotent operations (like incrementing) need careful handling.
•Preserving Context — Application state should be reconstructed correctly on retry. Pass all necessary data, don't rely on session state.

Recovery in Major Databases

Understanding how specific databases handle deadlock recovery helps you configure and troubleshoot production systems:

MySQL InnoDB:

InnoDB automatically detects and resolves deadlocks. The victim is rolled back and receives error 1213.

-- MySQL deadlock handling example
-- Application should catch and retry on error 1213

-- Check deadlock information
SHOW ENGINE INNODB STATUS\G
-- Look for 'LATEST DETECTED DEADLOCK' section

-- Victim selection is based on:
-- 1. Approximate row count modified (less = more likely victim)
-- 2. Insert buffer size
-- InnoDB typically picks the transaction that modified fewer rows

-- Configure automatic rollback behavior
SET innodb_rollback_on_timeout = ON;  -- Rollback entire transaction on timeout

PostgreSQL:

PostgreSQL aborts the transaction that completed the cycle (the one whose lock request created the deadlock). Error code is 40P01.

-- PostgreSQL returns SQLSTATE 40P01 for deadlocks

-- Logging configuration for deadlocks
SET log_lock_waits = on;              -- Log when waiting for locks
SET deadlock_timeout = '1s';          -- Detection delay

-- View locks and pending requests
SELECT * FROM pg_locks WHERE NOT granted;

-- Detailed deadlock info in server logs:
-- ERROR: deadlock detected
-- DETAIL: Process 12345 waits for ShareLock on transaction 67890;
--         blocked by process 23456.
--         Process 23456 waits for ShareLock on transaction 12345;
--         blocked by process 12345.
-- HINT: See server log for query details.

SQL Server:

SQL Server uses sophisticated cost-based victim selection with the DEADLOCK_PRIORITY setting allowing explicit control.

-- SQL Server deadlock priority (LOW, NORMAL, HIGH)
SET DEADLOCK_PRIORITY LOW;   -- This session more likely to be victim
SET DEADLOCK_PRIORITY HIGH;  -- This session protected from victimization

-- Numeric priority (-10 to 10)
SET DEADLOCK_PRIORITY 5;     -- Higher = less likely victim

-- Capture deadlock graphs with Extended Events
CREATE EVENT SESSION [DeadlockCapture] ON SERVER 
ADD EVENT sqlserver.xml_deadlock_report 
ADD TARGET package0.event_file(SET filename=N'Deadlocks');

-- Error number for deadlock is 1205
-- Applications should catch and retry on this error

Database Recovery Comparison
Database	Error Code	Victim Selection	Retry Responsibility	Priority Control
MySQL	1213	Fewest rows modified	Application layer	Limited (no explicit setting)
PostgreSQL	40P01	Cycle-completing transaction	Application layer	None
SQL Server	1205	Cost-based composite	Application layer	DEADLOCK_PRIORITY
Oracle	ORA-00060	Cycle-completing, oldest	Application layer	Limited

Summary: Mastering Deadlock Recovery

Deadlock recovery is the critical final phase of deadlock management—where detection becomes action. Here are the essential takeaways:

Key Takeaways

•Recovery requires sacrificing a transaction — at least one victim must be aborted to break the deadlock cycle. The choice of victim significantly impacts system efficiency.
•Victim selection algorithms vary — from simple (youngest transaction) to sophisticated (composite cost scoring). Production systems typically use multi-factor cost functions.
•Composite scoring balances multiple factors — including work done, locks held, transaction age, rollback history, and business priority. Weights should be tuned for your workload.
•Rollback strategies trade completeness for efficiency — total rollback is simple and safe; partial rollback preserves work but adds complexity. Most databases use total rollback.
•Cascading aborts are prevented by proper isolation levels (READ COMMITTED or higher) and locking protocols (Strict 2PL). Cascades multiply the cost of deadlocks.
•Retry mechanisms are essential — exponential backoff with jitter prevents retry storms. Applications must be prepared to catch deadlock errors and retry.
•Each database has specific recovery behaviors — understand your database's error codes, victim selection logic, and configuration options for production troubleshooting.

Module Complete:

Congratulations! You have now mastered the complete lifecycle of deadlock handling:

Definition — Understanding what deadlocks are and the four Coffman conditions
Detection — Algorithms and timing strategies for identifying deadlocks
Wait-For Graphs — The core data structure enabling detection
Prevention — Techniques that make deadlocks impossible
Recovery — Victim selection, rollback, and retry mechanisms

This knowledge equips you to design, configure, and troubleshoot concurrent database systems at the highest level.

Module Complete: Deadlock Handling Mastery

5 / 5