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.

  • Locking involves associating one or more locks with each database element.

  • We can associate a lock with

    • a page
    • a record
    • possibly even a collection (eg, relation)

Each database element has its own lock. Element A is locked by transaction T1, which can read and write A. Transaction T2 also wants A and must wait for the lock. Element B is unlocked.

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

database element X T1 T2 holds the lock can access X locked by T1 requests the lock request denied must wait unlocks X unlocked still waiting lock granted can access X locked by T2

Locking and Serializability

  • We will attempt to use locks to enforce serializability.
  • However, just having locks isn’t enough to guarantee serializability.
    • It matters how the locks are used.
  • Example: our problematic schedule can still be carried out.

  • The problem is that T1 released its lock on balance1 “too soon”.

  • Notice that T1 acquired a lock on balance2 later; this suggests that the transaction was not “done” when it released the lock on balance1.

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.

Schedule in which T1 unlocks balance1 and later locks balance2

  • 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:  u1(A) .. l2(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:  u2(B) .. l1(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:
  • r1(B) … w2(B):  T1 → T2
  • w1(A) … r2(A):  T1 → T2
  • → equivalent to T1;T2
  • serializable?
  • yes. conflict serializable → serializable
  • recoverable?
  • yes. only dirty read is r2(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

  • Recall that our goal is to allow overlapping transactions to read the same data item, even though two reads don’t conflict.
  • With only one type of lock, overlapping transactions can’t read the same data item, even though they 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
  • xli(A) = transaction Ti requests an exclusive lock for A
  • if another txn holds any lock for A, Ti 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
  • sli(A) = transaction Ti requests a shared lock for A
  • if another txn holds an exclusive lock for A, Ti must wait until that lock is released
database element A T1 holds the lock read and write exclusive · only T1 one transaction has exclusive access to A T1 xl1(A) exclusive lock exclusive · only T1 T1 requests an exclusive lock only one txn can hold it T1 xl1(A) holds a lock locked by T1 T2 request denied must wait T1 already holds a lock on A so T2 waits T1 shared lock can read A T2 shared lock can read A shared · T1 and T2 several transactions at once a shared lock allows reading only T1 sl1(A) can read A T2 sl2(A) can read A shared · T1 and T2 sl1(A) and sl2(A) both hold a shared lock on A T1 xl1(A) exclusive lock exclusive · T1 T2 sl2(A) must wait T1 holds an exclusive lock so T2's shared request waits

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

  • sli(A) = transaction Ti requests a shared lock for A
  • xli(A) = transaction Ti requests an exclusive lock for A
element A A element B B element C C exclusive · T2 unlocked unlocked T2 holds an exclusive lock on A and writes A exclusive · T2 shared · T1 unlocked T1 takes a shared lock on B and reads B exclusive · T2 shared · T1 and T2 unlocked T2 also takes a shared lock on B and reads B exclusive · T2 shared · both are reading B unlocked both read B at the same time without shared locks, T2 would wait for T1 to unlock B exclusive · T2 exclusive · T1 shared · T1 and T2 T1 locks C exclusively before reading it Why not a shared lock? exclusive · T2 exclusive · will write C shared · T1 and T2 T1 already knows it will write C so it takes the exclusive lock before the read unlocked shared · T1 only exclusive · T1 T2 unlocks A and B. T1 still holds B and C unlocked unlocked unlocked T1 writes C, then unlocks B and C every lock in the example has been released

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