Interleaving

When multiple transactions execute concurrently, their individual operations don't simply run in parallel and then merge results. Instead, they interleave—operations from different transactions are woven together in time, executed one after another in some specific ordering chosen by the database scheduler.

Think of it like a card shuffle: each transaction is a deck of cards (operations), and the scheduler interleaves them into a single deck. The final order determines whether the result is correct (equivalent to running transactions one at a time) or corrupt (exhibiting one of the concurrency problems we've discussed).

Interleaving is both the mechanism that enables concurrency benefits and the source of concurrency problems. Understanding how interleaving works, what makes certain interleavings safe, and how to reason about interleaved execution is fundamental to mastering database concurrency.

Interleaving refers to the mixing of operations from multiple transactions into a single sequence for execution. Rather than completing one transaction before starting another, operations from different transactions are executed in alternating fashion.

Formal Definition:

Given transactions T₁ and T₂ with operations:

• T₁: O₁₁, O₁₂, O₁₃ (in this order)
• T₂: O₂₁, O₂₂ (in this order)

An interleaved schedule is any sequence containing all operations that:

1. Includes every operation from every transaction exactly once
2. Preserves the internal ordering of operations within each transaction

Examples of valid interleavings:

• O₁₁, O₁₂, O₁₃, O₂₁, O₂₂ (serial: T₁ then T₂)
• O₂₁, O₂₂, O₁₁, O₁₂, O₁₃ (serial: T₂ then T₁)
• O₁₁, O₂₁, O₁₂, O₂₂, O₁₃ (interleaved)
• O₂₁, O₁₁, O₁₂, O₂₂, O₁₃ (interleaved differently)

Why Interleaving Happens:

Interleaving is not random—it's a consequence of practical system behavior:

1. I/O Waits: When T₁ waits for disk I/O, the scheduler lets T₂ proceed
2. Lock Waits: When T₁ waits for a lock, T₂ can execute other operations
3. Multi-core Execution: Different CPU cores may execute different transactions' operations truly in parallel
4. Network/Client Delays: While T₁ waits for client communication, T₂ can proceed

The scheduler interleaves operations to maximize resource utilization while (ideally) maintaining correctness.

The scheduler (also called the concurrency control manager or serialization manager) is the DBMS component responsible for determining how operations are interleaved. It makes real-time decisions about when each operation can execute.

Scheduler Responsibilities:

1. Receive operations from transactions as they're submitted
2. Decide execution order based on correctness requirements and performance goals
3. Delay or block operations that would cause problems if executed immediately
4. Abort transactions when necessary to prevent or resolve deadlocks
5. Maintain serializability (or the configured isolation level) guarantee

The Fundamental Challenge:

The scheduler must make decisions incrementally and without knowledge of the future. When operation O arrives:

• The scheduler doesn't know what operations will come next
• It doesn't know if the current transaction will commit or abort
• It doesn't know how long other transactions will take

Yet it must decide: execute now, delay, or abort the transaction?

Two Approaches to Scheduling:

1. Pessimistic (Locking-based): Assume conflicts will occur. Prevent problems by acquiring locks before accessing data. Operations wait until locks are available.

2. Optimistic (Validation-based): Assume conflicts are rare. Execute operations freely, but validate before commit that no conflicts occurred. Abort if validation fails.

Most production databases use some form of pessimistic concurrency control (locking or MVCC).

Not all interleavings are created equal. Some produce results identical to running transactions serially; others produce corrupted or inconsistent data. Understanding what makes an interleaving 'safe' is central to concurrency control.

The Serializability Standard:

An interleaved schedule is safe (or correct) if it's serializable—meaning it produces the same result as some serial execution of the same transactions. The transactions might have executed with interleaved operations, but the end result is as if they ran one at a time in some order.

Formal Definition:

Schedule S is serializable if there exists a serial schedule S' with the same transactions such that:

1. Both S and S' produce the same final database state, AND
2. Both S and S' return the same values to read operations in each transaction

The key to understanding which interleavings are safe lies in the concept of conflicting operations. Not all pairs of operations interact—only conflicting operations affect each other's results when reordered.

Definition of Conflicting Operations:

Two operations O₁ (from T₁) and O₂ (from T₂) conflict if:

1. They belong to different transactions (T₁ ≠ T₂)
2. They access the same data item
3. At least one is a write operation

Why Conflicts Matter:

Non-conflicting operations can be reordered without affecting the result. But conflicting operations' relative order matters—swapping them changes the outcome.

• Read-Read: No conflict. Both get same value regardless of order.
• Read-Write: Conflict! Order determines whether read sees old or new value.
• Write-Read: Conflict! Same reason as above.
• Write-Write: Conflict! Order determines which value persists.

Conflict Equivalence:

Two schedules are conflict equivalent if:

1. They contain the same transactions and operations
2. All pairs of conflicting operations are ordered the same way in both schedules

If a schedule is conflict equivalent to a serial schedule, it's called conflict serializable and is guaranteed to be safe.

The Precedence Graph Method:

To test conflict serializability:

1. Create a node for each transaction
2. For each pair of conflicting operations where Oᵢ (from Tᵢ) comes before Oⱼ (from Tⱼ), draw an edge Tᵢ → Tⱼ
3. If the graph has no cycles, the schedule is conflict serializable
4. If there's a cycle, the schedule is NOT conflict serializable

Interleaving directly impacts the ACID properties—particularly Isolation—and indirectly affects Consistency. Understanding this relationship clarifies why proper interleaving management is essential.

Impact on Isolation:

The Isolation property promises that concurrent transactions don't interfere with each other—each appears to execute alone. Unsafe interleaving violates this promise:

• Dirty reads occur when interleaving allows reading uncommitted writes
• Non-repeatable reads occur when interleaving allows committed changes between reads
• Lost updates occur when interleaving allows write-write conflicts to overwrite

A serializable interleaving preserves perfect isolation. Weaker isolation levels permit specific safe violations for better performance.

The Consistency Connection:

Database consistency means the database always satisfies its integrity constraints. A transaction takes the database from one consistent state to another. But during the transaction, the database may temporarily violate constraints (e.g., mid-transfer, money has left Account A but not arrived at Account B).

If another transaction sees this mid-transaction state through bad interleaving, it sees an inconsistent database—even though no individual transaction violated consistency.

Example:

Constraint: A + B + C = $1000 (total money in system)

T1 (transfer): subtract from A, add to B
Midway: A has $100 less, B hasn't been updated yet
T2 (sum): reads all accounts, computes A + B + C = $900 (WRONG!)

T2 saw a consistent-constraint violation because interleaving exposed T1's intermediate state.

Being able to visualize and analyze interleavings is a crucial skill for database developers and administrators. Several notation and visualization methods exist.

Timeline Notation:

The most intuitive representation shows time flowing downward (or left-to-right), with each transaction in its own column:

     T1         T2
     |          |
     r1(A)      |
     |          r2(A)
     w1(A)      |
     |          r2(B)
     r1(B)      |
     w1(B)      |
     |          r2(C)
     commit     |
     |          commit

This clearly shows the temporal ordering and which operations overlap.

Operation Sequence Notation:

A compact representation lists operations in order with subscripts indicating transactions:

r₁(A) r₂(A) w₁(A) r₂(B) r₁(B) w₁(B) r₂(C)

This makes it easy to identify conflicts and check ordering.

The Precedence Graph:

A directed graph showing transaction dependencies from conflicts:

T1 ──→ T2  (means T1 must come before T2 in equivalent serial schedule)

The graph is acyclic if and only if the schedule is conflict serializable.

The specific interleaving that occurs in any execution depends on many factors, some controllable and others not. Understanding these factors helps in predicting and debugging concurrency behavior.

System-Level Factors:

1. CPU Scheduling: Which transaction's thread gets CPU time affects which operations proceed
2. I/O Completion Order: Disk operations complete in unpredictable order due to seek optimization
3. Network Latency: Distributed transactions experience variable communication delays
4. Lock Queue Order: Which waiting transaction gets a released lock

Application-Level Factors:

1. Transaction Arrival Time: When transactions start relative to each other
2. Operation Mix: Read-heavy transactions interleave more freely than write-heavy ones
3. Data Access Patterns: Transactions accessing the same data conflict more
4. Transaction Length: Longer transactions provide more interleaving opportunities

The Heisenbug Problem:

Concurrency bugs are notoriously hard to debug because:

1. The bug only appears with specific interleavings that may occur rarely
2. Adding debugging code (print statements, breakpoints) changes timing, hiding the bug
3. The bug may disappear under observation (like Heisenberg's uncertainty principle)

This is why databases use proven concurrency control protocols rather than relying on testing to find all problematic interleavings. It's mathematically impossible to test all possible interleavings.

From a million operations: Even a modest workload generates astronomical numbers of possible interleavings. Testing can never cover them all. Correctness must come from protocol design, not exhaustive testing.