Transaction States, Concurrency & Deadlocks: ACID, Protocols, and Recovery

TAKEAWAYS:

• A transaction is a sequence of operations that must appear atomic, consistent, isolated, and durable (ACID) to maintain database integrity.
• Transactions cycle through active → partial → failed/aborted or prepared → committed states, with rollback or commit as the final step.
• Concurrency control prevents anomalies like lost updates or dirty reads using protocols like two-phase locking (2PL) or timestamp ordering.
• Deadlocks occur when transactions wait indefinitely for locks; detection (wait-for graph) and resolution (preemption) are critical in high-traffic systems.
• Shadow paging and undo/redo logs enable fast recovery from failures without full database rebuilds.
• Real-world systems (e.g., eSewa transactions, Daraz order processing) rely on these mechanisms to handle thousands of concurrent operations per second.

1. What is a Transaction?

A transaction is a logical unit of work that reads and/or updates database records. It must behave as a single, indivisible operation to preserve data integrity. Examples:

• Transferring ₹10,000 from Account A to Account B (both debits/credits must succeed or fail together).
• Booking a flight seat (reserving a seat and updating inventory atomically).

ACID Properties ensure transactions are reliable:

mindmap:
  root((ACID Properties))
    Atomicity["Must execute fully or not at all (all-or-nothing)"]
    Consistency["Transitions database from one valid state to another"]
    Isolation["Concurrent transactions appear sequential (no interference)"]
    Durability["Once committed, survives system crashes (persistent)"]

Worked Example: Bank Transfer Consider two transactions:

1. T1: Withdraw ₹500 from Account X (balance: ₹2,000 → ₹1,500).
2. T2: Deposit ₹500 into Account Y (balance: ₹1,000 → ₹1,500).

If T1 updates X but crashes before updating Y, the system would have ₹1,500 (X) + ₹1,000 (Y) = ₹2,500 instead of ₹2,000. Atomicity prevents this by ensuring both updates succeed or fail together.

2. Transaction States and State Diagram

A transaction progresses through 6 states (with transitions shown below):

stateDiagram-v2
    [*] --> Active
    Active --> Partial: Operation executed
    Partial --> Failed: Error detected
    Partial --> Prepared: Commit decision made
    Prepared --> Committed: Logged to disk
    Prepared --> Aborted: Rollback triggered
    Failed --> [*]
    Aborted --> [*]
    Committed --> [*]

Key Transitions:

• Active → Partial: Transaction begins executing (e.g., locking rows, updating tables).
• Partial → Failed: Violation of constraints (e.g., negative balance) or system error.
• Partial → Prepared: Transaction prepares to commit (writes to redo log).
• Committed/Aborted: Final state after commit or rollback.

Real-World Tie: eSewa Payment When you pay ₹100 via eSewa:

1. The transaction starts (Active).
2. eSewa locks your account balance and deducts ₹100 (Partial).
3. If successful, it commits (Committed) and updates both your and the merchant’s balances.
4. If the merchant’s bank rejects the payment, eSewa aborts and refunds you.

3. Concurrency Control: Why and How

Problem: Without control, concurrent transactions can cause:

• Lost Update: Two transactions read/write the same data; the second overwrites the first’s changes.
• Dirty Read: A transaction reads uncommitted data (e.g., sees a pending transfer that later fails).
• Inconsistent Analysis: Intermediate results are exposed (e.g., stock price mid-trade).

Solutions:

Two-Phase Locking (2PL) Protocol

1. Growing Phase: Transaction acquires locks (read/write).
2. Shrinking Phase: Transaction releases locks (only after commit/abort).

sequenceDiagram
  participant T1
  participant T2
  participant DB
  T1->>DB: Lock Row X (read)
  T2->>DB: Lock Row X (write)
  DB-->>T2: Wait (T1 holds lock)
  alt Deadlock Risk
    T1->>DB: Unlock Row X (commit)
    DB-->>T2: Grant lock
  else No Deadlock
    T2->>DB: Unlock Row X (commit)
  end

Worked Example: Daraz Order Processing When two users buy the same item:

• T1 locks the item’s inventory (count = 5).
• T2 requests the lock but waits (2PL).
• If T1 commits first, T2 proceeds; if T1 aborts, T2 retries.

4. Deadlocks: Detection and Resolution

A deadlock occurs when two+ transactions wait for locks held by each other, creating a circular wait.

Example:

sequenceDiagram
    participant T1
    participant T2
    participant DB
    T1->>DB: Lock Account A (write)
    T2->>DB: Lock Account B (write)
    T1->>DB: Request Lock Account B  --> Waits (T2 holds it)
    T2->>DB: Request Lock Account A  --> Waits (T1 holds it)
    DB-->>T1,T2: Deadlock detected!

Detection:

• Wait-For Graph: Nodes = transactions; edges = "waits for." If a cycle exists (e.g., T1→T2→T1), a deadlock occurs.

Resolution Strategies:

1. Preemption: Forcefully abort one transaction (e.g., T1) and retry later.
2. Priority-Based: Abort the younger transaction.
3. Timeout: If a lock isn’t released within X seconds, abort.

Real-World Tie: Kathmandu Traffic Imagine two buses (T1: Bus A, T2: Bus B) waiting at a junction:

• T1 holds the "left turn" lock; T2 holds the "right turn" lock.
• Both request the other’s lock → deadlock. The traffic controller (DBMS) must abort one bus (transaction) to resolve it.

5. Database Recovery: Shadow Paging

Problem: If a system crashes during a transaction, uncommitted changes are lost. Recovery must restore consistency.

Shadow Paging Technique:

1. Before Transaction: A "shadow copy" of the database is created (e.g., at midnight).
2. During Transaction: Changes are written to a redo log and a shadow page (temporary copy).
3. Crash Recovery:
   • Roll back uncommitted changes using the shadow copy.
   • Replay committed changes from the redo log.

[Original Database] ←[Shadow Copy]→ [Shadow Pages]
                     ↑
[Crash] → Rollback uncommitted changes → Restore from shadow copy

Worked Example: Ncell Call Logs

• At 2 AM, Ncell creates a shadow copy of call logs.
• During the day, a transaction updates a user’s call history (written to redo log + shadow page).
• If a crash occurs, Ncell restores the shadow copy and reapplies only the committed changes.

6. NoSQL vs. ACID: Trade-offs

While relational databases enforce ACID strictly, NoSQL databases (e.g., MongoDB, Cassandra) often sacrifice ACID for scalability or flexibility. Compare:

Example: WhatsApp Messages

• WhatsApp uses NoSQL (Firebase) for chat history because:
  • Availability > strict consistency: Messages may appear out of order but eventually sync.
  • Scalability: Handles billions of users globally.

In the Real World

1. eSewa Transactions

   • Idea: Two-Phase Locking ensures that when you pay ₹500, neither your balance nor the merchant’s is updated partially. If the merchant’s bank rejects the payment, eSewa aborts the transaction and refunds you immediately.
   • State Diagram: Your payment follows the Active → Partial → Aborted path if the merchant declines.

2. Daraz Order Queue

   • Idea: Shadow Paging ensures that if Daraz’s servers crash during checkout, your order status is restored from the last committed shadow copy. Unpaid orders are rolled back, and you’re notified to retry.
   • Concurrency: When two users buy the last "Nike Air Max" shoe, Daraz uses timestamp ordering to prioritize the first request, preventing lost updates.

3. Pathao Ride Booking

   • Idea: Deadlock Detection prevents two drivers from claiming the same ride simultaneously. If Driver A locks a bike and Driver B requests the same bike, Pathao’s system detects the circular wait and aborts Driver B’s request (or assigns it to the next available driver).

Exam Tip

1. ACID Properties: Always explain each property with a real-world example (e.g., "Atomicity in bank transfers").
2. State Diagram: Draw the 6-state diagram and label transitions clearly. Examiners love this!
3. Concurrency Control: Compare 2PL vs. timestamp ordering in a table (as above). Mention deadlocks and how to detect/resolve them.
4. Shadow Paging: Describe the before/after crash workflow step-by-step. Include a simple diagram of shadow pages vs. redo logs.
5. NoSQL Trade-offs: Know when to use SQL vs. NoSQL (e.g., "Use NoSQL for high write throughput like Instagram posts").
6. Worked Examples: Practice tracing transactions through states (e.g., "What happens if T1 commits after T2 aborts in a deadlock?").

Common Pitfalls:

• Forgetting to mention rollback in transaction states.
• Confusing logical vs. physical data independence (this is Unit 10!).
• Describing shadow paging without linking it to redo logs.