1 of 25

CSE 414: �Transactions with Locks

February 18, 2021

Section 7

2 of 25

Announcements

  • Hw5 released
    • Due 11/23 @ 11 PM
  • Quiz 2 next week
  • Use Ed for quiz questions

3 of 25

Txn & Locking overview

Remember - locking is for database internal implementation

  • A way to provide the ACID guarantees
  • Pessimistic concurrency control
  • Users of a database need only specify �BEGIN TRANSACTION … COMMIT / ROLLBACK
    • ...and the isolation level...

4 of 25

Conflicts Review

READ-WRITE

WRITE-READ

WRITE-WRITE

​

“Intra-transactional” - don’t mess with the order of operations within a transaction

}

Inter-transactional

  • represent with a conflict graph
  • conflict across separate transactions

5 of 25

Serializability Review

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

It is conflict serializable if it can be transformed into a serial schedule via a series of non-conflicting swaps.

​

​

Serializable

Conflict

Serializable

Easy to check

Not easy to check

6 of 25

True or False: If all transactions are read-only, then every schedule is serializable.

7 of 25

2PL: 2 Phase Locking

  • Locking phase
  • Unlocking phase

Guarantees conflict serializability

8 of 25

Limitations of 2PL

  • Deadlocks
  • Recoverability

See lecture for examples of both

9 of 25

Strict 2PL

Similar to 2PL BUT with an additional constraint:

  • All unlocks happen at the same time, during commit/rollback

10 of 25

2PL v.s. Strict 2PL at a glance

2PL:

  • In every transaction, all lock requests must precede all unlock requests
  • Ensures conflict serializability
  • Might not be able to recover (Dirty Read: Read on some write that gets rolled back)
  • Deadlock possible

Strict 2PL:

  • Every lock for each transaction is held until commit or abort
  • Ensures conflict serializability
  • Recoverable b/c each transaction does not affect others until commit/abort
  • Deadlock possible

11 of 25

2PL v.s. Strict 2PL

Invalid reads

Trickled unlock and transaction end

12 of 25

Practice: Is this schedule possible under a Strict 2PL Protocol?

R2(B), W2(B), R3(C), W3(C), R3(A), W3(A), Co3, R2(C), W2(C), Co2, R1(A), R1(B), W1(A), W1(B), Co1

13 of 25

Practice: Is this schedule possible under a Strict 2PL Protocol?

R2(B), W2(B), R3(C), W3(C), R3(A), W3(A), Co3, R2(C), W2(C), Co2

R1(A), R1(B), W1(A), W1(B), Co1

​

Answer: Yes

​

​

​

14 of 25

Practice: Is this schedule possible under a Strict 2PL Protocol?

R2(B), W2(B), R3(C), W3(C), R1(A), R1(B), W1(A), W1(B), Co1, R2(C), W2(C), Co2, R3(A), W3(A), Co3

​

​

15 of 25

Practice: Is this schedule possible under a Strict 2PL Protocol?

R2(B), W2(B), R3(C), W3(C), R1(A), R1(B), W1(A), W1(B), Co1,

R2(C), W2(C), Co2,

R3(A), W3(A), Co3

Answer: Nope

​

​

16 of 25

Binary Locks

  • L(A) - Exclusive lock on A
    • No other transaction can read or write to A
  • U(A) - No lock on A (or think of it as Unlock)
    • This transaction does not hold a lock on A

17 of 25

3-Tiered Locking (Shared/Exclusive locks)

  • X(A) - Exclusive lock on A
    • No other transaction can read or write to A
  • S(A) - Shared lock on A
    • Other transactions can acquire a shared lock to A, only allows for reads
    • If only one transaction holds a shared lock for A, �then it can upgrade to an exclusive lock
  • U(A) - No lock on A (or think of it as Unlock)
    • This transaction does not hold a lock on A
    • If it had a shared lock, some other transactions might still have a lock for A

18 of 25

Basically, you can have:

  1. Multiple shared (read) locks on any database/part of data (your chosen granularity)

OR

  • Only one exclusive lock on that part of data (so no shared locks)

19 of 25

All the locks!

Concurrency Control Method

Benefit

2PL

Ensures conflict serializability

Strict 2PL

Ensures recovery

Conservative 2PL (not studied in 414)

Ensures deadlock-free

Lock Type

Benefit

Binary Locks

Simplest lock implementation

Shared/Exclusive Locks

Greater throughput on reads

20 of 25

Database Lock

Table Lock

Predicate Lock

Tuple Lock

Lock Granularity

SQLite!

Less Concurrency

More Concurrency

21 of 25

What Lock is this? (#1)

T1

T2

S(A)

​

R(A)

​

​

S(A)

​

R(A)

U(A), Commit

​

​

X(B)

​

U(A)

​

W(B)

​

U(B), Commit

  • What type of lock is used? (Binary or 3-Tiered)

​

  • Can this schedule run under the 2PL protocol?

​

  • Can this schedule run under the Strict 2PL protocol?

22 of 25

What Lock is this? (#1)

T1

T2

S(A)

​

R(A)

​

​

S(A)

​

R(A)

U(A), Commit

​

​

X(B)

​

U(A)

​

W(B)

​

U(B), Commit

  • What type of lock is used? (Binary or 3-Tiered)

Shared/Exclusive Locks

  • Can this schedule run under the 2PL protocol?

Yes

  • Can this schedule run under the Strict 2PL protocol?

No

23 of 25

What Lock is this? (#2)

T1

T2

L(A)

​

​

L(B)

R(A)

​

​

R(B)

U(A), Commit

​

​

L(A)

​

W(A)

​

R(A)

​

U(A), U(B), Commit

  • What type of lock is used? (Binary or 3-Tiered)

​

  • Can this schedule run under the 2PL protocol?

​

  • Can this schedule run under the Strict 2PL protocol?

24 of 25

What Lock is this? (#2)

T1

T2

L(A)

​

​

L(B)

R(A)

​

​

R(B)

U(A), Commit

​

​

L(A)

​

W(A)

​

R(A)

​

U(A), U(B), Commit

  • What type of lock is used? (Binary or 3-Tiered)

Binary Locks

  • Can this schedule run under the 2PL protocol?

Yes

  • Can this schedule run under the Strict 2PL protocol?

Yes

25 of 25

Takeaways...

  • What are 2PL, strict 2PL, why do we need them �(what problems does each solve?)
  • How to recognize schedules as 2PL vs Strict 2PL
  • Different types of locks and granularity levels
  • You now have everything you need to finish Hw5!