12-1-More on Distributed Transactions and Concurrency Control

Serializability of schedules

Two operations conflict if:

1. They belong to different transactions
2. They operate on the same data
3. One of them is a write

Two schedules are equivalent if

1. They involve the same transactions and operations
2. All conflicting operations are ordered the same way

A schedule is serializable only if it is equivalent to a serial schedule.

Testing for serializability

Intuition: swap non-conflicting operations until you reach a serial schedule.

Example 1

Suppose conflicting operations (blue):

By swapping non-conflicting operations, you can achieve a serial schedule:

Example 2

Suppose another conflicting operations:

After attempting to swap non-conflicting operations, the schedule is not serializable:

Another way to test serializability

Another way to test serializability:

1. Draw arrows between conflicting operations
2. Arrow points in the direction of time
3. If no cycles between transactions, the schedule is serializable

Example 1

Draw arrow between conflicting operations:

No cycle is found, thus serializable.

Example 2

Draw arrows between conflicting operations:

A cycle is found, thus not serializable

Implementing serializability: 2PL

2PL guarantees serializability by disallowing cycles between transactions.

There could be dependencies in the waits-for graph among transactions waiting for locks:

• Edge from T2 to T1 means T2 is waiting for the lock acquired by T1
• Edge from T1 to T2 means T1 is waiting for the lock acquired by T2
• Cycles mean deadlock, and in this case 2PL won’t proceed

Deadlock Example

Observe waits-for graph creating a cycle:

You can deal with deadlocks by aborting one of the two transactions by detecting with timeout.

Releasing locks too early

Suppose another example with plain 2PL:

Suppose initially:

A = 100

T1 changes it:

R(A) = 100
W(A) = 200

But T1 has not committed yet.
Under basic 2PL, T1 is allowed to release its lock on A before commit as long as it never acquires another lock afterward:

Lock-X(A)
R(A)
W(A)
Unlock-X(A)

The problem is when T2 reads R(B) = 200, it is an uncommitted value.
Imagine T1 later discovers an error and has to abort, causing it to rollback A = 100.
Therefore, everything T2 did based on A = 200 is invalid, so T2 has to abort as well.

This sequence of aborts is known as cascading abort.
This degrades performance.

Strict 2PL

Strict 2PL adds another rule to prevent uncommitted values to be read by other transaction:

• Do not release write locks until the transaction commits or aborts.
• Variant of 2PL implemented by most databases in practice

For example, the T1 released the lock after the abort:

T1: X(A) R(A) W(A) -------- ABORT → rollback → unlock(A)
                         |
                         | T2 waits
                         ↓
T2:                    WAIT ------------------> S(A) R(A)
                                                  ↑
                                         restored value

T2 can proceed with its operations regardless of T1 abortion.

If abort didn’t happen:

T1: X(A) R(A) W(A) -------- commit → unlock(A)
                         |
                         | T2 waits
                         ↓
T2:                    WAIT ------------------> S(A) R(A) = 200

The transactions succeed normally.

Two ways of implementing serializability: 2PL, OCC

2PL (pessimistic):

1. Assume conflicts are prevalent so ensures lock always
2. High overhead for non-conflicting transactions
3. Must check for deadlock

Optimistic concurrency control (OCC):

1. Assume conflicts are not prevalent
2. Low overhead for non-conflicting transactions, but high for conflicting transactions
3. Ensure correctness by aborting transactions if conflict occurs

Optimistic concurrency control

• Execute optimistically: Read committed values, write changes locally
• Validate: Check if data has changed since original read
• Commit (Write): Commit if no change, else abort

Atomic commit for OCC

Use two-phase commit (2PC) to achieve atomic commit (validate + commit writes)

Phase 1: send prepare to each shard: include buffered write + original read for that shard

• Shards validate reads and acquire locks (exclusive for write locations, shared for read locations)
• If this succeeds, respond with yes; else respond with no

Phase 2: collect votes, send result (abort or commit) to all shards

• If commit, shards apply buffereed writes
• All shards release locks