Database Transactions & Concurrency Control: ACID, Locks, Deadlocks & Recovery

1. Introduction to Database Transactions

A transaction is a sequence of operations performed as a single logical unit of work. In databases, transactions ensure that data remains consistent and reliable even when multiple users access or modify it simultaneously.

Key Characteristics of a Transaction

Transactions must satisfy the ACID properties to be reliable:

Transaction States

A transaction progresses through these states:

stateDiagram-v2
    [*] --> Active
    Active --> Partially Committed
    Partially Committed --> Committed
    Active --> Failed
    Failed --> Aborted
    Aborted --> [*]
    Committed --> [*]

• Active: Transaction is executing.
• Partially Committed: All operations done, waiting for commit.
• Committed: Successfully completed (changes permanent).
• Failed: Error detected (e.g., insufficient funds).
• Aborted: Rolled back to original state.

2. Concurrency Control: Why It Matters

When multiple users access a database simultaneously, race conditions can corrupt data. For example:

• Bank Transfer Race Condition:
  • User A checks balance: ₹5,000.
  • User B checks balance: ₹5,000 (same as A).
  • Both deduct ₹2,000 → final balance: ₹1,000 (should be ₹3,000).

Concurrency Control prevents such issues by:

• Ensuring isolation (transactions don’t interfere).
• Maintaining consistency (no invalid states).
• Using locks or optimistic concurrency to manage access.

3. Locking Mechanisms

Locks restrict access to data items to prevent conflicts. Two types:

Locking Protocols

1. Two-Phase Locking (2PL):
   • Growing Phase: Acquire locks before releasing any.
   • Shrinking Phase: Release locks but no new acquisitions.
   • Example:

sequenceDiagram
    participant T1
    participant T2
    participant DB
    T1->>DB: Lock AccountA (X-lock)
    T2->>DB: Request Lock AccountA (X-lock) → Waits (T1 holds lock)
    T1->>DB: Release Lock AccountA
    T2->>DB: Lock AccountA (X-lock) → Proceeds
    note right of T1: Growing Phase
    note right of T2: Shrinking Phase

2. Deadlock Detection:
   • A deadlock occurs when two transactions wait indefinitely for each other’s locks.
   • Detection Methods:
     • Wait-For Graph: Nodes = transactions; edges = "waits for".
     • Example:

       graph TD
           T1-->|"Locks A"| T2
           T2-->|"Locks B"| T1
           T1-->|"Waits for B"| T2
           T2-->|"Waits for A"| T1

     • Solution: Abort one transaction (e.g., roll back T1).

4. Shadow Paging for Recovery

When a system crashes, uncommitted transactions may corrupt data. Shadow Paging is a recovery technique where:

1. A shadow copy of the database is created before changes.
2. On crash, the shadow copy is restored, and only committed transactions’ changes are reapplied.

How It Works:

Example:

• Scenario: A Daraz order system crashes mid-transaction.
• Recovery:
  1. Roll back all uncommitted orders (e.g., a failed payment).
  2. Reapply only confirmed orders (e.g., a successful ₹500 purchase).

5. Real-World Applications

In the Real World

1. eSewa/Khalti (Payment Gateways)

   • Idea: Atomicity ensures funds are deducted from your account and credited to the merchant or neither.
   • Example: Transferring ₹100 to a shop: if the shop’s account fails to update, your money is refunded.

2. NEPSE (Stock Exchange)

   • Idea: Isolation prevents two traders from buying the same share simultaneously.
   • Example: If Trader A and Trader B both request the last share of ABC Ltd., only one gets it (the other waits or fails).

3. Pathao (Ride-Hailing)

   • Idea: Locks ensure a bike is not double-booked.
   • Example: If Bike X is booked by User 1, User 2 cannot book it until User 1 cancels or completes the ride.

6. Worked Example: Bank Transfer with Locks

Scenario: Two users transfer money simultaneously.

sequenceDiagram
    participant User1
    participant User2
    participant BankDB
    User1->>BankDB: Lock AccountA (X-lock)
    User2->>BankDB: Lock AccountB (X-lock)
    BankDB-->>User1: Grant Lock
    BankDB-->>User2: Grant Lock
    User1->>BankDB: Debit AccountA (₹1,000)
    User2->>BankDB: Credit AccountB (₹1,000)
    BankDB->>BankDB: Commit Transaction
    BankDB->>BankDB: Release Locks
    note over User1,User2: Deadlock avoided due to separate locks

Without Locks:

• User1 deducts ₹1,000 from AccountA.
• User2 checks AccountA’s balance (now ₹4,999 instead of ₹5,000).
• User2 deducts ₹1,000 → AccountA has ₹3,999 (should be ₹4,000).

7. Comparison Table: Concurrency Control Methods

Exam Tip

• Focus on ACID: Always explain atomicity with a "all-or-nothing" example (e.g., flight booking).
• Lock Types: Differentiate S-lock (read) vs. X-lock (write) with a real scenario (e.g., two users editing a Daraz order).
• Deadlocks: Draw a wait-for graph and describe how to break it (abort one transaction).
• Shadow Paging: Relate to database recovery—mention restoring a "clean" copy after a crash.
• Transactions States: Memorize the state diagram and link each state to a real action (e.g., "Partially Committed" = waiting for COMMIT).

Common Pitfalls:

• Forgetting to mention isolation in concurrency control.
• Confusing optimistic vs. pessimistic concurrency (optimistic assumes no conflicts).
• Not including a worked example (e.g., bank transfer with locks).