Transaction Management & Concurrency Control: ACID, Locks, Protocols & Recovery

TAKEAWAYS:

• ACID properties (Atomicity, Consistency, Isolation, Durability) are the foundation of reliable transactions.
• Concurrency control prevents lost updates, dirty reads, and inconsistent states using locking protocols (2PL) or timestamp ordering.
• Deadlocks occur when transactions wait indefinitely; detection and resolution are critical for system stability.
• Recovery techniques (checkpointing, logging) restore databases to a consistent state after failures.
• Real-world systems (eSewa, Ncell, Daraz) use these concepts to manage concurrent user requests safely.
• SQL transactions use BEGIN, COMMIT, and ROLLBACK to enforce ACID guarantees.

Core Concepts: Transactions and ACID Properties

A transaction is a sequence of operations performed as a single logical unit of work. For example, transferring money from one bank account to another involves:

1. Deducting from Account A.
2. Adding to Account B. If either step fails, the entire transaction must be aborted to maintain consistency.

ACID Properties

ACID ensures transactions are processed reliably. Visualize it as a shield protecting data integrity:

stateDiagram-v2
    [*] --> ACID: Atomicity
    ACID --> Consistency: Maintains database rules
    ACID --> Isolation: Hides intermediate states
    ACID --> Durability: Survives failures
    ACID --> [*]

1. Atomicity: All operations in a transaction succeed or fail together.
   • Example: In eSewa, if your payment fails, the entire transaction is rolled back, and no money is deducted.
2. Consistency: The database moves from one valid state to another.
   • Example: A bank loan approval must follow rules (e.g., credit score ≥ 600).
3. Isolation: Transactions appear to execute sequentially, even if they run concurrently.
   • Example: Two users checking the same Daraz product stock simultaneously see the same value.
4. Durability: Once committed, changes persist even after system failures.
   • Example: After you confirm a Pathao ride, the booking remains even if the app crashes.

Concurrency Control: Why It Matters

Without concurrency control, race conditions occur:

• Lost Update: Two transactions read the same data and overwrite each other’s changes.
  • Example: Two users book the same Ncell data plan simultaneously. Only one should succeed.
• Dirty Read: A transaction reads uncommitted data from another transaction.
  • Example: You see a "low stock" alert for a Daraz product, but it’s later canceled by the seller.
• Inconsistent Analysis: A transaction reads data affected by another uncommitted transaction.
  • Example: A bank calculates your loan eligibility based on a temporary deposit that gets rolled back.

Concurrency control techniques resolve these issues:

1. Locking Protocols (e.g., 2PL)
2. Optimistic Concurrency Control (assumes conflicts are rare)
3. Timestamp Ordering (orders transactions by time)

Two-Phase Locking (2PL) Protocol

2PL divides a transaction into two phases:

1. Growing Phase: Acquire locks (shared or exclusive).
2. Shrinking Phase: Release locks; no new locks can be acquired.

How 2PL Works

sequenceDiagram
    participant T1
    participant T2
    participant Database
    T1->>Database: Lock(X) [Exclusive]
    T2->>Database: Lock(X) [Shared]
    Database-->>T2: Granted (Shared)
    Database-->>T1: Granted (Exclusive)
    T1->>Database: Read(X)
    T2->>Database: Read(X)
    T1->>Database: Unlock(X) [Release]
    T2->>Database: Lock(X) [Exclusive] → Blocked (T1 holds exclusive lock)

Example: Two users updating the same NEPSE stock price.

• If both try to lock the record exclusively, one waits (avoiding lost updates).
• If one holds a shared lock (read-only), others can read but not write.

Types of Locks

Advantages of 2PL:

• Prevents deadlocks if locks are acquired in a fixed order (e.g., always lock Account before Transaction).
• Simple to implement.

Disadvantages:

• Low concurrency: Transactions may wait unnecessarily.
• Deadlocks: Can still occur if locks are not managed carefully.

Deadlocks: Detection and Resolution

A deadlock occurs when two or more transactions wait indefinitely for locks held by each other.

Example: Deadlock in a Bank Transfer

graph LR
    T1["Transaction 1: Lock(Account_A)"] -->|"Waits for"| T2["Transaction 2: Lock(Account_B)"]
    T2 -->|"Waits for"| T1

• T1 locks Account_A and waits for Account_B (held by T2).
• T2 locks Account_B and waits for Account_A (held by T1).
• Result: Both transactions are stuck.

Deadlock Prevention Strategies

1. Lock Ordering: Always acquire locks in a predefined order (e.g., alphabetical).
2. Timeouts: Abort transactions that wait too long.
3. Deadlock Detection: Use a wait-for graph to detect cycles.
   • Example: Ncell’s billing system detects deadlocks when two users try to update the same SIM card balance simultaneously.

Timestamp Ordering

Instead of locks, transactions are ordered by timestamps (logical clocks). Each transaction gets a unique timestamp when it starts.

How It Works

1. Read/Write Rules:
   • A transaction Tᵢ can read X only if Tᵢ’s timestamp ≥ X’s last write timestamp.
   • A transaction Tᵢ can write X only if Tᵢ’s timestamp > X’s last write timestamp.
2. Abort Late Transactions: If a transaction violates these rules, it is aborted and restarted.

Example: WhatsApp message delivery.

• If two users send messages to the same group simultaneously, timestamp ordering ensures one is processed first, avoiding conflicts.

Advantages:

• No deadlocks (since no locks are used).
• Higher concurrency than 2PL.

Disadvantages:

• Restarts: Transactions may be aborted and retried, increasing overhead.
• Starvation: Late transactions may repeatedly abort.

Recovery Mechanisms

Databases use logging and checkpointing to recover from failures.

1. Logging

A log file records all changes before they are applied to the database. Example:

<Start Transaction T1>
<Write Account_A: 1000 → 900>
<Commit T1>

• If the system crashes after writing to Account_A but before committing, the log helps undo the change.

2. Checkpointing

Periodically, the database writes all modified pages to disk and logs a checkpoint record. This reduces recovery time.

Example: NTC’s billing system.

• Every hour, NTC saves all pending bill updates to disk. If a power failure occurs, recovery starts from the last checkpoint, not from scratch.

## In the Real World

1. eSewa (Nepal):

   • Concept Used: 2PL (Two-Phase Locking) and ACID Transactions.
   • How: When you pay a bill, eSewa locks your account and the utility provider’s records until the transaction completes. If your internet cuts off mid-transaction, the system rolls back to avoid partial payments.

2. Ncell (Telecom):

   • Concept Used: Timestamp Ordering and Deadlock Detection.
   • How: When two users recharge the same number simultaneously, Ncell’s backend assigns timestamps to ensure one transaction completes before the other. If a deadlock is detected (e.g., two users updating the same SIM’s data plan), the system aborts the later transaction.

3. Daraz (E-commerce):

   • Concept Used: Isolation (ACID) and Locking.
   • How: When you add an item to your cart, Daraz locks the inventory count for that product. If another user tries to buy the last unit, they either see "out of stock" or wait until your transaction completes. This prevents overselling.

4. NEPSE (Stock Exchange):

   • Concept Used: Atomicity and Durability.
   • How: When you place a stock trade, NEPSE ensures either:
     • Your order is fully executed and the stock price updates, or
     • Nothing happens (rolls back) if the trade fails due to market rules.

## Worked Example: Bank Loan Processing

Scenario: A bank processes two loan applications concurrently:

• Transaction T1: Approves a loan for Customer A (credit score = 700).
• Transaction T2: Updates Customer A’s credit score to 650 (due to a new inquiry).

Problem: If T2 updates the score before T1 checks it, T1 might incorrectly approve the loan.

Solution Using 2PL

1. T1 acquires an exclusive lock on Customer_A.Credit_Score.
2. T2 tries to acquire a lock but is blocked (since T1 holds an exclusive lock).
3. T1 reads the score (700) and approves the loan.
4. T1 releases the lock.
5. T2 now acquires the lock and updates the score to 650.

Result: No dirty read; T1 sees the correct score.

Solution Using Timestamp Ordering

• Assume T1 starts at t=100 and T2 at t=105.
• T1 reads the score (700) and approves the loan.
• T2 tries to write but is aborted because 105 < 100 (violates write rule).
• T2 restarts later and succeeds.

## Comparison Table: Concurrency Control Techniques

## Exam Tip

1. ACID Properties: Always define them in order (Atomicity, Consistency, Isolation, Durability). Use real-world examples (e.g., "Like a bank transfer where either both accounts update or none do").
2. 2PL Protocol:
   • Explain the two phases (growing/shrinking).
   • Draw a sequence diagram showing lock acquisition/release.
   • Mention deadlock prevention (e.g., lock ordering).
3. Deadlocks:
   • Define with a wait-for graph.
   • Explain four conditions (Mutual exclusion, Hold and wait, No preemption, Circular wait).
4. Recovery:
   • Differentiate undo (ROLLBACK) and redo (REDO) operations.
   • Mention checkpoints as "snapshots" of the database.
5. SQL Transactions:
   • Write a sample transaction with BEGIN, COMMIT, and ROLLBACK.
   • Example:

     BEGIN TRANSACTION;
     UPDATE Accounts SET Balance = Balance - 1000 WHERE AccountID = 1;
     UPDATE Accounts SET Balance = Balance + 1000 WHERE AccountID = 2;
     COMMIT; -- or ROLLBACK;
     

6. Past Exam Patterns:
   • Short Questions: Define concurrency control, 2PL, or deadlocks in 3-4 sentences.
   • Long Questions: Compare 2PL vs. Timestamp Ordering (use the table above).
   • SQL: Write a transaction for a given scenario (e.g., "Update student grades with ACID").

Avoid:

• Vague answers like "locks prevent problems."
• Forgetting to link concepts to real systems (e.g., "Like Ncell’s billing system...").
• Skipping diagrams (always draw a sequence diagram for 2PL or a wait-for graph for deadlocks).