Deadlock

Definition

• Circular Wait: Two or more transactions wait for each other indefinitely
• Resource Dependency: Transaction A waits for resource held by Transaction B, which waits for resource held by Transaction A
• System State: No transaction can proceed without external intervention
• Database Problem: Common issue in concurrent database systems

Deadlock Conditions (Must All Be Present)

1. Mutual Exclusion

• Resource Access: Only one transaction can hold a resource at a time
• Lock Types: Exclusive locks prevent sharing
• Example: Row-level exclusive locks for updates

2. Hold and Wait

• Partial Allocation: Transaction holds some resources while requesting others
• Progressive Locking: Acquiring locks throughout transaction lifecycle
• Example: Hold lock on Table A while requesting lock on Table B

3. No Preemption

• Voluntary Release: Resources can only be released by holding transaction
• No Forced Release: System cannot forcibly take resources away
• Database Context: Locks held until transaction commits/aborts

4. Circular Wait

• Chain Formation: Closed loop of transactions waiting for each other
• Dependency Cycle: Transaction A → B → C → A
• Breaking Point: Must break cycle to resolve deadlock

Simple Deadlock Example

Scenario: Concurrent Inserts

Transaction 1	Transaction 2
BEGIN TRANSACTION;	BEGIN TRANSACTION;
INSERT INTO TEST VALUES (21);	INSERT INTO TEST VALUES (20);
INSERT INTO TEST VALUES (20); ← Waits	INSERT INTO TEST VALUES (21); ← Waits
Blocked: Waiting for row 20	Blocked: Waiting for row 21
Result: Deadlock detected by database	Resolution: One transaction rolled back

Why This Deadlocks

• Transaction 1: Holds lock on row 21, wants lock on row 20
• Transaction 2: Holds lock on row 20, wants lock on row 21
• Circular Dependency: Neither can proceed
• Database Action: Automatically detects and resolves

Common Deadlock Scenarios

1. Resource Ordering Conflict

-- Transaction A
UPDATE accounts SET balance = balance - 100 WHERE id = 1;
UPDATE accounts SET balance = balance + 100 WHERE id = 2;
 
-- Transaction B (same time)
UPDATE accounts SET balance = balance - 50 WHERE id = 2;
UPDATE accounts SET balance = balance + 50 WHERE id = 1;

2. Index Lock Conflicts

-- Transaction A
UPDATE users SET name = 'Alice' WHERE email = 'alice@example.com';
 
-- Transaction B
UPDATE users SET email = 'bob@new.com' WHERE name = 'Bob';

3. Foreign Key Deadlocks

-- Transaction A
INSERT INTO orders (customer_id, amount) VALUES (1, 100);
UPDATE customers SET total_orders = total_orders + 1 WHERE id = 1;
 
-- Transaction B
DELETE FROM customers WHERE id = 1;

Deadlock Detection

Wait-For Graph

• Nodes: Represent transactions
• Edges: Represent wait relationships
• Cycle Detection: Algorithm finds circular dependencies
• Frequency: Database checks periodically (e.g., every second)

Detection Process

1. Build Graph: Map transaction dependencies
2. Cycle Search: Look for circular waits
3. Victim Selection: Choose transaction to abort
4. Rollback: Abort chosen transaction and release locks

Detection Timing

• Immediate: Check after each lock request (expensive)
• Periodic: Check at regular intervals (most common)
• Timeout: Assume deadlock after wait timeout

Deadlock Resolution

Victim Selection Criteria

• Transaction Size: Prefer aborting smaller transactions
• Work Done: Minimize lost work
• Transaction Age: Sometimes prefer newer transactions
• Lock Count: Consider number of locks held

Resolution Steps

1. Detect Deadlock: Identify circular wait condition
2. Choose Victim: Select transaction to abort
3. Rollback Transaction: Undo all changes made by victim
4. Release Locks: Free all resources held by victim
5. Notify Application: Return deadlock error to client

Error Handling

-- Application should retry after deadlock
BEGIN TRANSACTION;
-- ... operations ...
COMMIT;
-- If deadlock detected, transaction automatically rolled back
-- Application receives deadlock error and should retry

Deadlock Prevention Strategies

1. Resource Ordering

• Consistent Order: Always acquire resources in same order
• Example: Always update accounts in ascending ID order
• Implementation: Sort resource IDs before acquiring locks

-- Good: Consistent ordering (transfer 100 from :from_id to :to_id)
-- Lock both rows in ascending id order first, then apply the debit/credit
SELECT id FROM accounts WHERE id IN (:from_id, :to_id) ORDER BY id FOR UPDATE;
UPDATE accounts SET balance = balance - 100 WHERE id = :from_id;
UPDATE accounts SET balance = balance + 100 WHERE id = :to_id;

• Why not LEAST/GREATEST in the UPDATEs: that always debits the lower id, so a transfer from 2 to 1 would move money the wrong way. Order the locking, not the business logic.

2. Timeout-Based Prevention

• Lock Timeout: Set maximum wait time for locks
• Abort on Timeout: Assume deadlock if timeout exceeded
• Trade-off: May abort legitimate waits

3. Wait-Die Protocol

• Age-Based: Older transactions wait, younger die
• Preemption: Younger transactions abort when conflict
• Restart: Aborted transactions restart with same timestamp

4. Wound-Wait Protocol

• Age-Based: Older transactions preempt younger
• Wound: Older forces younger to abort
• Wait: Younger waits for older

Deadlock Avoidance

1. Two-Phase Locking with Ordering

• Acquire Phase: Get all locks before any operation (this is conservative 2PL; plain 2PL only requires no new lock after the first release, and can still deadlock)
• Release Phase: Release all locks after commit
• Ordering: Acquire locks in predetermined order

2. Reduce Transaction Scope

• Shorter Transactions: Minimize lock hold time
• Specific Operations: Avoid unnecessary locks
• Quick Commits: Reduce probability of conflicts

3. Application Design Patterns

• Retry Logic: Implement exponential backoff
• Lock Granularity: Use appropriate lock levels
• Access Patterns: Design to minimize conflicts

Performance Impact

Detection Overhead

• CPU Cost: Cycle detection algorithms
• Memory Usage: Wait-for graph storage
• Frequency Trade-off: More frequent = higher overhead, faster detection

Resolution Cost

• Rollback Work: Undoing aborted transaction
• Retry Overhead: Re-executing failed operations
• Lock Thrashing: Repeated deadlocks in same area

Monitoring and Troubleshooting

Key Metrics

• Deadlock Frequency: Number of deadlocks per time period
• Victim Selection: Which transactions get aborted
• Wait Times: Average lock wait duration
• Hot Spots: Tables/rows with frequent deadlocks

Database-Specific Commands

-- PostgreSQL: View current locks
SELECT * FROM pg_locks;
 
-- MySQL: Show current deadlock info
SHOW ENGINE INNODB STATUS;
 
-- SQL Server: Deadlock graph in extended events
SELECT * FROM sys.dm_exec_requests WHERE blocking_session_id > 0;

Troubleshooting Steps

1. Identify Patterns: Which operations cause deadlocks
2. Analyze Queries: Look for resource ordering issues
3. Review Indexes: Check for index-related conflicts
4. Optimize Transactions: Reduce scope and duration

Best Practices

Application Development

• Consistent Ordering: Always access resources in same order
• Short Transactions: Minimize lock duration
• Retry Logic: Handle deadlock exceptions gracefully
• Appropriate Isolation: Use minimum required isolation level

Database Design

• Index Strategy: Minimize index lock conflicts
• Table Partitioning: Reduce contention through partitioning
• Foreign Keys: Design to minimize FK deadlocks
• Normalization: Balance between consistency and performance

Operational

• Monitor Metrics: Track deadlock frequency and patterns
• Query Optimization: Improve query performance to reduce lock time
• Connection Pooling: Manage concurrent connections effectively
• Regular Analysis: Review deadlock logs periodically

Prevention vs Detection Trade-offs

Prevention Approaches

• Advantages: No deadlocks occur, predictable performance
• Disadvantages: Reduced concurrency, may be overly conservative
• When to Use: High-conflict scenarios, critical systems

Detection Approaches

• Advantages: Maximum concurrency, handle deadlocks when they occur
• Disadvantages: Overhead of detection and recovery
• When to Use: Low-conflict scenarios, acceptable retry costs

Summary

• Definition: Circular wait condition where transactions block each other indefinitely
• Conditions: Mutual exclusion, hold & wait, no preemption, circular wait
• Detection: Wait-for graphs and cycle detection algorithms
• Resolution: Abort victim transaction and retry
• Prevention: Resource ordering, timeouts, protocol-based approaches
• Best Practice: Design applications to minimize deadlock probability through consistent resource ordering and short transactions