Transactions, Concurrency & Recovery: Logs, Schedules & ACID

TAKEAWAYS:

• Transactions guarantee ACID (Atomicity, Consistency, Isolation, Durability) to maintain data integrity.
• Concurrency control (locking, timestamping, MVCC) prevents lost updates and dirty reads in multi-user systems.
• Recovery uses logs (before-image/after-image) and checkpoints to restore databases after crashes.
• Serializability ensures schedules behave like serial transactions; conflict serializability and view serializability are key tests.
• Deadlocks occur in circular-wait scenarios; detection and resolution (timeout, rollback) are critical.
• Real-world impact: Banks (loan processing), eSewa (payment transactions), and Daraz (order fulfillment) rely on these mechanisms.

1. Transactions: The Building Blocks of Reliable Data Operations

A transaction is a sequence of operations that must execute atomically (all or nothing) to maintain database consistency. Think of it as a single logical unit of work—like transferring money from one bank account to another.

ACID Properties: The Pillars of Trust

Transactions must satisfy ACID to be reliable:

• Atomicity: Either all operations complete or none do (e.g., a bank transfer fails if the debit succeeds but credit fails).
• Consistency: The database moves from one valid state to another (e.g., total money in accounts remains unchanged).
• Isolation: Concurrent transactions do not interfere (e.g., two users checking the same bank balance see the same value).
• Durability: Once committed, changes survive system failures (e.g., a committed order on Daraz remains even after a server crash).

stateDiagram-v2
    [*] --> Active: Transaction starts
    Active --> Partially_committed: All operations executed
    Partially_committed --> Committed: Commit succeeds
    Partially_committed --> Aborted: Rollback triggered
    Committed --> [*]
    Aborted --> [*]

2. Concurrency Control: Managing Multiple Transactions

When multiple transactions run simultaneously, concurrency conflicts arise:

• Lost Update: Two transactions read the same data, then overwrite it, losing one update.
• Dirty Read: A transaction reads data written by an uncommitted transaction (e.g., seeing a "pending" Daraz order as "shipped" before confirmation).
• Inconsistent Analysis: A transaction reads data twice, but another transaction modifies it in between (e.g., checking stock availability twice in an online store).

Concurrency Control Techniques

Example: Bank Transfer Conflict

Scenario: Two users (A and B) transfer money from the same account to different accounts.

sequenceDiagram
    participant A as User A
    participant B as User B
    participant DB as Database
    A->>DB: Read(Account_X = 1000)
    B->>DB: Read(Account_X = 1000)
    A->>DB: Write(Account_X = 800) [Transfer 200 to Y]
    B->>DB: Write(Account_X = 600) [Transfer 400 to Z]
    Note right of B: Lost Update! Final balance: 600 (should be 400)

Solution: Use exclusive locks to prevent overlapping writes.

3. Serializability: Ensuring Correct Schedules

A schedule is an interleaving of transactions. For correctness, it must be serializable—equivalent to executing transactions one after another.

Types of Serializability

Detecting Serializability

Use a precedence graph:

1. Draw a node for each transaction.
2. Add an edge Tᵢ → Tⱼ if Tᵢ writes to data that Tⱼ reads/writes later.
3. If the graph has a cycle, the schedule is not conflict-serializable.

Example:

graph TD
    T1["T1"] --> T2["T2"]
    T2 --> T3["T3"]
    T3 --> T1

4. Deadlocks: The Circular Wait Problem

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

Four Necessary Conditions for Deadlock:

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.

Two transactions deadlocking over Account_X and Account_Y. (Image: Kkaaii, CC BY-SA 4.0, via Wikimedia Commons)

Deadlock Handling Strategies

Real-World Example: In eSewa, if two users try to transfer money simultaneously and deadlock occurs, the system may timeout and roll back one transaction to resolve the conflict.

5. Recovery Systems: Bringing the Database Back to Life

Databases use logs and checkpoints to recover from crashes.

Log-Based Recovery

A log records changes before (before-image) and after (after-image) they are applied.

Log Record Format:

<Transaction ID, Operation, Data Item, Before-Image, After-Image, Timestamp>

Example:

T1, Write, Balance, 1000, 800, 12:00:00
T2, Read, Balance, -, -, 12:00:01

Recovery Steps:

1. Redo: Reapply committed transactions from the log.
2. Undo: Roll back uncommitted transactions.

sequenceDiagram
    participant DB as Database
    participant Log as Log File
    DB->>Log: Write log record (T1, Write, Balance, 1000, 800)
    DB-->>Log: Crash occurs
    Log->>DB: Redo committed transactions
    Log->>DB: Undo uncommitted transactions

Checkpointing

• Checkpoint: A snapshot of the database where all logs up to that point are flushed to disk.
• Benefits: Reduces recovery time by minimizing the need to redo/undo from the start.

Example:

Checkpoint at time T:
- All logs up to T are written to disk.
- Active transactions: T1 (committed), T2 (aborted).
- Recovery starts from T instead of the beginning.

6. Real-World Applications

1. Banking (Nabil Bank, Global IME)

• Transactions: Loan approvals, fund transfers.
• Concurrency: Multiple users checking/updating accounts simultaneously.
• Recovery: Logs ensure that if a server crashes during a transfer, the system can undo or redo the transaction.

2. eSewa & Khalti (Digital Payments)

• Transactions: Money transfers between users.
• Conflict: Two users transferring money from the same account at the same time.
• Solution: Locking the account balance during the transfer to prevent lost updates.

3. Daraz (E-Commerce Orders)

• Transactions: Order placement, stock updates.
• Concurrency: Multiple users buying the same product.
• Solution: MVCC allows readers to see the stock before it’s updated, while writers lock the stock.

4. NTC & Ncell (Billing Systems)

• Transactions: Updating customer bills, processing payments.
• Recovery: Logs ensure that if a power outage occurs, bills are not lost or duplicated.

Exam Tip

What Examiners Look For

1. Definitions: Clearly define ACID, serializability, deadlock, and recovery.
2. Examples: Always support answers with schedules, precedence graphs, or log records.
   • For serializability, draw a graph and explain cycles.
   • For recovery, show a log example and steps for redo/undo.
3. Real-World Links: Connect concepts to banks, eSewa, or Daraz (e.g., "Like in eSewa, transactions must be atomic to avoid partial money transfers").
4. Diagrams: Use state diagrams for transaction life cycles, sequence diagrams for concurrency conflicts, and graphs for deadlocks.
5. Common Pitfalls:
   • Lost Update ≠ Dirty Read: Know the difference!
   • Conflict Serializable ≠ View Serializable: Examiners test this distinction.
   • Deadlock Prevention vs. Detection: Don’t confuse the two.

High-Score Answer Structure

For questions like:

"Explain log-based recovery with an example."

Do This:

1. Define log-based recovery (redo/undo).
2. Show a log record (with before/after images).
3. Trace recovery steps (e.g., "After crash, redo T1 and undo T2").
4. Link to real-world: "Like in Nabil Bank, logs ensure transactions are not lost during power cuts."

Avoid:

• Vague explanations ("Logs help recover data").
• Missing steps (e.g., forgetting to mention checkpoints).
• No diagrams (always draw a log record table or recovery flow).

Practice Questions (Self-Check)

1. Draw a precedence graph for the following schedule and check for serializability:

   T1: Read(A), Write(B)
   T2: Read(B), Write(A)
   

2. Explain how MVCC prevents dirty reads in a high-concurrency system like Daraz.
3. Write a log record for a transaction that reads Salary = 50000 and then writes Salary = 55000.
4. Describe how a bank would detect and resolve a deadlock between two loan-processing transactions.

Final Note: Master ACID, serializability, and log recovery—these are the core of reliable database systems. Use diagrams to visualize conflicts, deadlocks, and recovery steps. Real-world examples (banks, eSewa) will help you remember concepts during exams!