Concurrency Control: Locking

Data Science 310

Boston University

Recoverability

• While serializability is important, it isn’t enough for full isolation.
• Consider the serializable schedule at right.
  • includes “c” actions that indicate when the transactions commit

• Imagine that the system crashes:
  • after T1’s commit
  • before T2’s commit

• During recovery from the crash, the system:
  • keeps all of T1’s changes, because it committed before the crash
  • undoes all of T2’s changes, because it didn’t commit before the crash

Recoverability (cont.)

• This is problematic!
  • T1 reads T2’s write of B
  • it then performs actions that may be based on the new value of B
  • during recovery from the crash, T2 is rolled back
    → B’s old value is restored
  • it’s possible T1 would have behaved differently if it had read B’s old value
  • it’s too late to roll back T1, because it has already committed!

• We say that this schedule is unrecoverable.
  • if a crash occurs between the two commits, the process of recovering from the crash could lead to problematic results

Dirty Reads and Cascading Rollbacks

• Dirty data is data written by an uncommitted txn.

• it remains dirty until the txn is either:
  • committed: in which case the data is no longer dirty and it is safe for other txns to read it

• rolled back: in which case the write of the dirty data is undone

• A dirty read is a read of dirty data.

• Dirty reads can lead to cascading rollbacks.
  • if the writer of the dirty data is rolled back, the reader must be, too

Dirty Reads and Cascading Rollbacks (cont.)

• We made our earlier schedule recoverable by switching the order of the commits:

• Could the revised schedule lead to a cascading rollback?

• yes!
• T1 performs a dirty read of T2’s write of B.

• if T2 is later rolled back, T1 must be, too.

• To get a cascadeless schedule, don’t allow dirty reads.

Practice

• What scenarios involving the schedule at right could produce cascading rollbacks?

A. T1 is rolled back sometime after T3 reads A.   yes

B. T2 is rolled back sometime after T1 reads B.   yes

C. T3 is rolled back sometime after T2 reads C.   yes

D. two of the above

E. all three of the above (A, B and C)

Concurrency Control Goals

• Goals: ensure that schedules of concurrent txns are:
  • serializable: equivalent to some serial schedule
  • recoverable: ordered so that the system can safely recover from a crash or undo an aborted transaction
  • cascadeless: ensure that an abort of one transaction does not produce a series of cascading rollbacks

• To achieve these goals, we use some type of concurrency control mechanism.
  • controls the actions of concurrent transactions
  • prevents problematic interleavings

Locking

• Locking is one way to provide concurrency control.
• Involves associating one or more locks with each database element.
  • each page
  • each record
  • possibly even each collection

Locking Basics

• A transaction must request and acquire a lock for a data element before it can access it.

• In our initial scheme, every lock can be held by only one txn at a time.

• As necessary, the DBMS:
  • denies lock requests for elements that are currently locked
  • makes the requesting transaction wait

• A transaction unlocks an element when it’s done with it.

• After the unlock, the DBMS can grant the lock to a waiting txn.
  • we’ll show a second lock request when the lock is granted

Locking and Serializability

• Just having locks isn’t enough to guarantee serializability.
• Example: our problematic schedule can still be carried out.

Two-Phase Locking (2PL)

• One way to ensure serializability is two-phase locking (2PL).
• 2PL requires that all of a txn’s lock actions come before all its unlock actions.

• Two phases:
  • lock-acquisition phase: a txn acquires locks, but it doesn’t release any

• lock-release phase: once a txn releases a lock, it can’t acquire any new ones

• Reads and writes can occur in both phases.
  • provided that a txn holds the necessary locks

• 2PL is per-transaction.
  • one txn could be in its lock-release phase while another txn is still in its lock-acquisition phase

Two-Phase Locking (2PL) (cont.)

• In our earlier example, T1 does not follow the 2PL rule.
  • 2PL would prevent this interleaving.

• More generally, 2PL produces conflict serializable schedules.

An Informal Argument for 2PL’s Correctness

• Consider schedules involving only two transactions.
  To get one that is not conflict serializable, we need:
  • 1) at least one conflict that requires T1 → T2

• T1 operates first on the data item in this conflict

• T1 must unlock it before T2 can lock it:  u₁(A) .. l₂(A)

• 2) at least one conflict that requires T2 → T1

• T2 operates first on the data item in this conflict

• T2 must unlock it before T1 can lock it:  u₂(B) .. l₁(B)

• Consider all of the ways these pairs of actions could be ordered:

Extra Practice

• Is the schedule at right:
  • conflict serializable?

• yes. conflicts are:
• r₁(B) … w₂(B):  T1 → T2

• w₁(A) … r₂(A):  T1 → T2

• → equivalent to T1;T2

• serializable?

• yes. conflict serializable → serializable

• recoverable?

• yes. only dirty read is r₂(A). reader (T2) commits after writer (T1), so it’s okay

• cascadeless?

• no, because of dirty read. if T1 is rolled back after T2 reads A, T2 must be, too!

Extra Practice (cont.)

The Need for Different Types of Locks

• With only one type of lock, overlapping transactions can’t read the same data item, even though two reads don’t conflict.
  • Two transactions could be forced to be serialized unnecessarily
  • This can have a negative impact on database performance
• To get around this, use more than one mode of lock.

Exclusive vs. Shared Locks

• An exclusive lock allows a transaction to write or read an item.
  • gives the txn exclusive access to that item
  • only one txn can hold it at a given time

• xl_i(A) = transaction T_i requests an exclusive lock for A

• if another txn holds any lock for A, T_i must wait until that lock is released

• A shared lock only allows a transaction to read an item.
  • multiple txns can hold a shared lock for the same data item at the same time

• sl_i(A) = transaction T_i requests a shared lock for A

• if another txn holds an exclusive lock for A, T_i must wait until that lock is released

Lock Compatibility Matrix

• Used to specify when a lock request for a currently locked item should be granted.

Examples of Using Shared and Exclusive Locks

• sl_i(A) = transaction T_i requests a shared lock for A
• xl_i(A) = transaction T_i requests an exclusive lock for A
• Examples:

Which requests are granted?

Shared vs. Exclusive Locks (cont.)

Which requests are granted?

What About Recoverability / Cascadelessness?

• 2PL alone does not guarantee either of them.

Takeaways

• To build high-performance databases we are concerned with ACID properties:
  • Atomicity: transactions should be all-or-nothing
    • We must be able to “roll back” a transaction
  • Consistency: transactions should leave the database consistent
    • Eg, must be able to transfer a bank balance correctly
  • Isolation: transactions should not interfere
    • They must be serializable
  • Durability: transactions that are committed must survive a crash
    • And, for consistency, they must be recoverable

Techniques for achieving ACID

• We can check serializability using conflicting operations
  • But to ensure serializability in general, we may use locking
• To avoid inconsistencies, we must follow a discipline when using locking: acquire all locks before releasing any
  • Called 2 Phase Locking
• And to avoid inconsistencies, commit order must be recoverable
• Observations:
  • Using locking modes (shared, exclusive) allows for overlapping reads
  • Dirty reads can be problematic
    • They can lead to cascading rollbacks
    • And a txn performing a dirty read must commit after the writer for recoverability