Kaushik's Notes

Two-phase Locking

6 min read

Overview

  • Protocol: Ensures serializability in concurrent transactions
  • Guarantee: Prevents lost updates and maintains consistency
  • Structure: Divides transaction into two distinct phases
  • Foundation: Core concurrency control mechanism in databases

The Two Phases

Phase 1: Growing Phase (Acquire)

  • Lock Acquisition: Transaction can only acquire locks
  • No Releases: Cannot release any locks during this phase
  • Progressive: Locks acquired as resources are accessed
  • Duration: Until transaction reaches maximum lock holdings

Phase 2: Shrinking Phase (Release)

  • Lock Release: Transaction can only release locks
  • No Acquisitions: Cannot acquire any new locks during this phase
  • Progressive: Locks released as transaction completes operations
  • Duration: Until all locks are released

Key Rules

Strict 2PL Rules

  1. No Mixed Operations: Cannot acquire and release locks in same phase
  2. One-Way Transition: Once shrinking phase starts, cannot return to growing
  3. Hold Write Locks: Exclusive (write) locks must be held until commit/abort (holding all locks to the end is Rigorous 2PL)
  4. Lock Point: Moment when last lock acquired (transition point)

Lock Point Concept

  • Definition: Instant when transaction acquires its last lock
  • Significance: Determines transaction’s position in serialization order
  • Ordering: Transactions can be ordered by their lock points
  • Serializability: Guarantees serializable execution

Variants of 2PL

Basic 2PL

  • Release Timing: Can release locks before commit
  • Problem: Cascading aborts possible
  • Usage: Rarely used due to abort risks

Strict 2PL (S2PL)

  • Release Timing: Hold all exclusive (write) locks until commit/abort; shared (read) locks may be released earlier in the shrinking phase
  • Advantage: Prevents cascading aborts (no one can read uncommitted writes)
  • Trade-off: Lower concurrency, higher safety
  • Most Common: Used by most database systems

Rigorous 2PL (R2PL)

  • Release Timing: Hold all locks (shared and exclusive) until commit/abort
  • Strictest: Most restrictive variant
  • Difference from Strict: Strict 2PL holds only write locks to the end; Rigorous holds read locks too, so the commit order equals the serialization order
  • Advantage: Strongest isolation guarantees
  • Usage: High-consistency requirements

Problem: Double Booking Example

Scenario

  • System: Hotel reservation system
  • Resource: Single room for specific date
  • Conflict: Two customers trying to book same room simultaneously

Without 2PL

-- Transaction A (Customer 1)
SELECT available_rooms FROM rooms WHERE date = '2024-01-15' AND room_id = 101;
-- Returns: 1 room available
 
-- Transaction B (Customer 2) - runs concurrently
SELECT available_rooms FROM rooms WHERE date = '2024-01-15' AND room_id = 101;
-- Returns: 1 room available (same data)
 
-- Both see room as available
-- Transaction A
INSERT INTO bookings (room_id, date, customer_id) VALUES (101, '2024-01-15', 'A');
UPDATE rooms SET available_rooms = 0 WHERE room_id = 101 AND date = '2024-01-15';
 
-- Transaction B
INSERT INTO bookings (room_id, date, customer_id) VALUES (101, '2024-01-15', 'B');
UPDATE rooms SET available_rooms = -1 WHERE room_id = 101 AND date = '2024-01-15';
 
-- Result: Double booking!

With 2PL Solution

-- Transaction A
BEGIN TRANSACTION;
SELECT available_rooms FROM rooms WHERE date = '2024-01-15' AND room_id = 101 FOR UPDATE;
-- Acquires exclusive lock on room record
 
-- Transaction B (must wait)
BEGIN TRANSACTION;
SELECT available_rooms FROM rooms WHERE date = '2024-01-15' AND room_id = 101 FOR UPDATE;
-- Blocked: waiting for Transaction A's lock
 
-- Transaction A continues
IF available_rooms > 0 THEN
    INSERT INTO bookings (room_id, date, customer_id) VALUES (101, '2024-01-15', 'A');
    UPDATE rooms SET available_rooms = available_rooms - 1 WHERE room_id = 101;
END IF;
COMMIT; -- Releases all locks
 
-- Now Transaction B can proceed
-- Will see updated available_rooms = 0
-- Booking fails gracefully

Implementation Details

Lock Acquisition Strategy

  • On-Demand: Acquire locks when accessing data
  • Predeclaration: Declare all needed locks upfront
  • Mixed Approach: Combine both strategies

Lock Types in 2PL

  • Shared Locks: For read operations
  • Exclusive Locks: For write operations
  • Update Locks: Intention to upgrade to exclusive
  • Intent Locks: Hierarchical locking support

Lock Granularity

  • Row-Level: High concurrency, more overhead
  • Page-Level: Balanced approach
  • Table-Level: Lower concurrency, less overhead
  • Database-Level: Minimal concurrency

Advantages of 2PL

Serializability Guarantee

  • Consistency: Always produces serializable schedules
  • Predictability: Deterministic transaction outcomes
  • Correctness: Maintains database integrity

Deadlock Detection

  • Automatic: Database handles deadlock detection
  • Resolution: Abort one transaction to break cycle
  • Recovery: Applications can retry aborted transactions

Flexibility

  • Lock Types: Supports various lock modes
  • Granularity: Works with different lock levels
  • Adaptability: Can be tuned for specific workloads

Disadvantages of 2PL

Reduced Concurrency

  • Lock Duration: Locks held longer than necessary
  • Blocking: Transactions wait for lock releases
  • Throughput: Lower overall system throughput

Deadlock Potential

  • Circular Waits: Multiple transactions can deadlock
  • Overhead: Deadlock detection and resolution costs
  • Aborts: Some transactions must be restarted

Performance Impact

  • Lock Management: Overhead of acquiring/releasing locks
  • Memory Usage: Lock table storage requirements
  • Contention: Hot spots create bottlenecks

Optimizations

Lock Escalation

  • Dynamic Granularity: Start with row locks, escalate to table
  • Memory Management: Reduce lock table size
  • Performance: Trade granularity for overhead

Lock Timeout

  • Deadlock Prevention: Abort long-waiting transactions
  • Assumption: Long waits likely indicate deadlocks
  • Trade-off: May abort legitimate waits

Lock Upgrading

  • Shared to Exclusive: Upgrade when needed for writes
  • Efficiency: Avoid exclusive locks for reads
  • Complexity: Handle upgrade conflicts

Real-World Applications

Banking Systems

  • Account Transfers: Prevent double spending
  • Balance Updates: Maintain account consistency
  • Audit Trails: Ensure transaction integrity

E-commerce Platforms

  • Inventory Management: Prevent overselling
  • Order Processing: Maintain stock levels
  • Price Updates: Consistent pricing across orders

Airline Reservations

  • Seat Assignment: Prevent double bookings
  • Flight Capacity: Maintain accurate availability
  • Loyalty Programs: Consistent point calculations

Monitoring and Tuning

Key Metrics

  • Lock Wait Time: Average time waiting for locks
  • Deadlock Frequency: Rate of deadlock occurrences
  • Lock Escalation: Frequency of granularity changes
  • Transaction Throughput: Successful transactions per second

Tuning Parameters

  • Lock Timeout: Balance between deadlock prevention and legitimate waits
  • Escalation Threshold: When to escalate lock granularity
  • Deadlock Detection: Frequency of deadlock checking

Performance Analysis

  • Lock Contention: Identify hot spots and bottlenecks
  • Transaction Patterns: Analyze access patterns for optimization
  • Resource Usage: Monitor lock table memory consumption

Best Practices

Application Design

  • Short Transactions: Minimize lock hold time
  • Consistent Ordering: Access resources in same order
  • Error Handling: Implement retry logic for deadlocks
  • Appropriate Isolation: Use minimum required isolation level

Database Configuration

  • Lock Granularity: Choose appropriate default level
  • Timeout Settings: Configure reasonable timeout values
  • Memory Allocation: Adequate lock table space

Development Guidelines

  • Explicit Locking: Use SELECT FOR UPDATE when needed
  • Transaction Scope: Keep transactions focused and brief
  • Index Strategy: Proper indexing reduces lock duration

Common Pitfalls

Long-Running Transactions

  • Problem: Hold locks too long, reduce concurrency
  • Solution: Break into smaller transactions where possible

Inconsistent Resource Access

  • Problem: Different access orders cause deadlocks
  • Solution: Establish consistent resource ordering

Over-Locking

  • Problem: Acquire unnecessary locks
  • Solution: Lock only what’s needed, when needed

Summary

  • Purpose: Ensures serializability through controlled lock acquisition/release
  • Phases: Growing (acquire only) and Shrinking (release only)
  • Variants: Basic, Strict, and Rigorous 2PL
  • Key Benefit: Prevents anomalies like double booking
  • Trade-off: Consistency vs concurrency
  • Best Practice: Use Strict 2PL with short transactions and consistent resource ordering

Graph View

Backlinks