Transaction ACID, Concurrency & Deadlocks: Locks, Timestamps, Serializability

TAKEAWAYS:

• Transactions guarantee ACID reliability: Atomicity, Consistency, Isolation, Durability.
• Concurrency control prevents anomalies like dirty reads and lost updates via locking, timestamps, or validation.
• Deadlocks occur when transactions wait indefinitely; wait-for graphs detect them.
• Serializability ensures concurrent transactions behave like sequential ones.
• Two-phase locking (2PL) and timestamp ordering are key protocols for concurrency.
• Real-world use: Banks (loan processing), eSewa (payment transactions), Daraz (order fulfillment).

1. Transactions: The Building Blocks of Reliable Databases

A transaction is a sequence of operations executed as a single logical unit of work. It must either complete fully (commit) or undo entirely (rollback). Think of it like transferring money between two bank accounts: either both accounts update correctly, or neither does.

ACID Properties: The Golden Rules

Transactions follow ACID to ensure reliability:

• Atomicity: All operations succeed or none do (e.g., a bank transfer either completes or fails entirely).
• Consistency: The database moves from one valid state to another (e.g., total money remains unchanged).
• Isolation: Concurrent transactions do not interfere (e.g., two users checking the same account balance see the same data).
• Durability: Once committed, changes persist even after crashes (e.g., a confirmed order on Daraz stays in the system).

stateDiagram-v2
    [*] --> Active: Transaction starts
    Active --> PartiallyCommitted: All operations executed
    PartiallyCommitted --> Committed: Changes saved (durable)
    PartiallyCommitted --> Aborted: Rollback (atomicity)
    Committed --> [*]
    Aborted --> [*]

Worked Example: eSewa Payment When you pay a bill via eSewa:

1. Atomicity: Either money is deducted from your wallet and credited to the service provider, or neither happens.
2. Consistency: Your wallet balance + service provider’s balance remains unchanged.
3. Isolation: Another user checking their wallet during the transaction sees their own balance, not a partial update.
4. Durability: Even if eSewa’s server crashes mid-transaction, the payment is either fully processed or rolled back.

2. Concurrency Control: Managing Multiple Transactions

When multiple transactions run simultaneously, concurrency control ensures correctness. Without it, problems like dirty reads, lost updates, and inconsistent analysis occur.

Common Concurrency Problems

3. Concurrency Control Techniques

Three main methods ensure serializability (the illusion that transactions run one after another):

A. Locking-Based Protocols

Transactions acquire locks on data items to prevent conflicts.

• Shared (Read) Lock (S-lock): Allows multiple transactions to read but not write.
• Exclusive (Write) Lock (X-lock): Grants a single transaction write access.

Two-Phase Locking (2PL)

1. Growing Phase: Transaction acquires all locks.
2. Shrinking Phase: Transaction releases all locks.
   • Ensures serializability but can cause deadlocks.

sequenceDiagram
    participant T1
    participant T2
    participant Database
    T1->>Database: Acquire X-lock on Account A
    Database-->>T1: Grant lock
    T1->>Database: Read Account A
    T2->>Database: Acquire X-lock on Account A (waits)
    T1->>Database: Release X-lock on Account A
    Database-->>T2: Grant lock

Worked Example: Daraz Order Queue When you place an order on Daraz:

1. The system acquires an X-lock on your cart and inventory.
2. If another user tries to buy the same item, they wait until the lock is released.
3. After payment, the lock is released, and the next transaction proceeds.

B. Timestamp-Based Protocols

Transactions are ordered by timestamps (logical clocks) to ensure serializability.

• Timestamp Ordering (TO): Rejects transactions that violate the order.
• Thomas’ Write Rule: Ignores writes that would violate the order (optimistic approach).

How Timestamp Ordering Works

1. Assign a timestamp to each transaction (e.g., T1: 100, T2: 101).
2. If T1 (older) tries to write after T2 (newer) reads the same data, abort T1.
3. Ensures strict serializability.

Worked Example: Ncell Top-Up When you top up via Ncell:

1. Your transaction gets a timestamp T100.
2. If another user’s transaction T101 reads your balance before T100 commits, T100 is aborted and retried to avoid dirty reads.

C. Validation-Based Protocols

Transactions execute optimistically and are validated before commit.

• Checks for conflicts (read-write, write-read, write-write).
• Aborts if conflicts violate serializability.

Comparison Table: Concurrency Control Methods

4. Deadlocks: When Transactions Get Stuck

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

Four Conditions for Deadlock (Coffman Conditions)

1. Mutual Exclusion: Only one transaction can hold a lock.
2. Hold and Wait: A transaction holds a lock while waiting for another.
3. No Preemption: Locks cannot be forcibly taken.
4. Circular Wait: A cycle exists in the wait-for graph.

Detecting Deadlocks with Wait-For Graphs

1. Draw a graph where nodes = transactions, edges = "waits for."
2. If a cycle exists, a deadlock occurs.

graph TD
    T1["Transaction 1"] -->|"waits for"| T2["Transaction 2"]
    T2 -->|"waits for"| T3["Transaction 3"]
    T3 -->|"waits for"| T1

Example: In a bank, T1 locks Account A, T2 locks Account B, and both wait for the other’s lock → deadlock.

Solutions

• Deadlock Prevention: Break one of the four conditions (e.g., no hold-and-wait).
• Deadlock Detection: Use wait-for graphs to detect cycles.
• Deadlock Recovery: Abort one transaction or force unlocks.

Worked Example: Kathmandu Traffic (Analogy) Imagine two cars:

• Car A holds the ring road lock and waits for Car B to release the Thapathali lock.
• Car B holds the Thapathali lock and waits for Car A to release the ring road lock. → Deadlock! The solution? One car must yield (like aborting a transaction).

5. Serializability: The Goal of Concurrency Control

A schedule is serializable if it produces the same result as some serial (one-after-another) schedule.

Types of Serializability

Example: Two Transactions

sequenceDiagram
    participant T1
    participant T2
    participant DB
    T1->>DB: Read A (value=10)
    T2->>DB: Read A (value=10)
    T1->>DB: Write A (value=20)
    T2->>DB: Write A (value=30)

• Non-serializable: If T2 reads A=20 after T1 writes, the final value depends on commit order.
• Serializable: If T1 commits before T2, the result matches T1 → T2.

6. Real-World Applications

A. eSewa & Khalti: Payment Transactions

• ACID in Action: When you pay a bill, the system ensures:
  • Atomicity: Money is deducted and credited, or neither happens.
  • Isolation: Other users don’t see partial updates.
• Concurrency Control: Locks prevent two users from double-spending the same amount.

B. Daraz: Order Fulfillment

• Two-Phase Locking: When you buy an item:
  1. Daraz locks the inventory.
  2. If another user tries to buy the same item, they wait.
  3. After payment, the lock releases, and the item is reserved.

C. Ncell: Mobile Top-Ups

• Timestamp Ordering: Your top-up transaction gets a timestamp. If another user’s transaction reads your balance before yours commits, yours is aborted to avoid dirty reads.

D. Banks: Loan Processing

• Deadlock Prevention: If two loans require the same fund pool, the bank uses timeout mechanisms to avoid deadlocks.

Exam Tip

1. ACID Properties: Always explain with a real-world example (e.g., bank transfer, eSewa payment).
2. Concurrency Problems: Draw a table comparing dirty reads, lost updates, and inconsistent analysis.
3. Locking vs. Timestamp: Know when to use 2PL (locking) vs. timestamp ordering (e.g., 2PL for short transactions, timestamps for high concurrency).
4. Deadlocks: Practice drawing wait-for graphs and explaining Coffman’s conditions.
5. Serializability: Show conflict matrices or schedule examples to prove serializability.
6. Shortcuts for Full Marks:
   • For ACID, use the mnemonic "Atomic Consistency Isolation Durability."
   • For deadlocks, remember "Mutual Exclusion, Hold and Wait, No Preemption, Circular Wait."
   • For 2PL, say "Growing phase: acquire locks; Shrinking phase: release locks."

Final Note: Master one worked example per topic (e.g., eSewa for ACID, Daraz for 2PL, Ncell for timestamps). Examiners love real-world ties!