Transcript CC 1 - CS-People by full name

Concurrency Control
General Overview
 Relational model - SQL
 Formal & commercial query languages
 Functional Dependencies
 Normalization
 Transaction Processing and CC
 Physical Design
 Indexing
 Query Processing and Optimization
Transaction Concept
 A transaction is a unit of program execution that
accesses and possibly updates various data items.
 A transaction must see a consistent database.
 During transaction execution the database may be
inconsistent.
 When the transaction is committed, the database must
be consistent.
State 1
State 2
ACID Properties
To preserve integrity of data, the database system must ensure:
 Atomicity. Either all operations of the transaction are
properly reflected in the database or none are.
 Consistency. Execution of a transaction in isolation
preserves the consistency of the database.
 Isolation. Each transaction must be unaware of other
concurrently executing transactions.
 Durability. After a transaction completes successfully, the
changes it has made to the database persist, even if there
are system failures.
AC[I]D
 Isolation
 Concurrent xctions unaware of each other
 How?
Serial execution of transactions
Poor Throughput and response time
Ensure concurrency
Prevent “bad” concurrency (pessimistic)
Recognize “bad” concurrency, fix (optimistic)
Qualify concurrency through analysis of “schedules”
Review - Schedules
 An interleaving of xction operations
T1
1
2
3
T2
A
B
C
D
T1
1
T2
A
B
A schedule for T1,T2
2
3
C
D
•Inter ops: may interleave
•Intra ops: remain in order
Review - Schedules
T1
•Serial Schedule
- All operations of each xction executed together,
xtions executed in succesion
•Serializable schedule
- Any schedule whose final effect matches
that of any serial schedule
T2
1
2
3
A
B
C
T1
T2
1
2
A
B
C
3
Example Schedules
Transactions:
T1: transfers $50 from A to B
T2: transfers 10% of A to B
T1
read(A)
A <- A -50
write(A)
read(B)
B<-B+50
write(B)
Example 1: a “serial” schedule
T2
Constraint: The sum of A+B
must be the same
Before: 100+50
=150, consistent
read(A)
tmp <- A*0.1
A <- A – tmp
write(A)
read(B)
B <- B+ tmp
write(B)
After: 45+105
Example Schedule
 Another “serial” schedule:
T1
read(A)
A <- A -50
write(A)
read(B)
B<-B+50
write(B)
T2
read(A)
tmp <- A*0.1
A <- A – tmp
write(A)
read(B)
B <- B+ tmp
write(B)
Before: 100+50
=150, consistent
After: 40+110
Consistent but not the
same as previous schedule..
Either is OK!
Example Schedule (Cont.)
Another “good” schedule:
T1
read(A)
A <- A -50
write(A)
T2
Effect:
read(A)
tmp <- A*0.1
A <- A – tmp
write(A)
read(B)
B<-B+50
write(B)
read(B)
B <- B+ tmp
write(B)
Before
A
100
B
50
After
45
105
Same as one of the serial schedules
Serializable
Example Schedules (Cont.)
A “bad” schedule
T1
read(A)
A <- A -50
T2
read(A)
tmp <- A*0.1
A <- A – tmp
write(A)
read(B)
write(A)
read(B)
B<-B+50
write(B)
Before: 100+50 = 150
After: 50+60 = 110 !!
Not consistent
Non Serializable
B <- B+ tmp
write(B)
Concurrency Control
 Concurrency Control
Ensures interleaving of operations amongst
concurrent xctions result in serializable schedules
 How?
Xction operations interleaved following a protocol
How to enforce serializable schedules?
Prevent P(S) cycles from occurring using a concurrency control
manager: ensures interleaving of operations amongst
concurrent xctions only result in serializable schedules.
T1 T2 …..
Tn
CC Scheduler
DB
Concurrency Via Locks
Xction , txn : short for transaction
 Idea:
 Data items modified by one xction at a time
 Locks
 Control access to a resource
 Can block a xction until lock granted
 Two modes:
 Shared (read only)
 eXclusive (read & write)
Granting Locks
 Requesting locks
 Must request before accessing a data item
 Granting Locks
 No lock on data item? Grant
 Existing lock on data item?
 Check compatibility:
– Compatible? Grant
– Not? Block xction
shared
exclusive
shared
Yes
No
exclusive
No
No
Lock instructions
 New instructions
- lock-S: shared lock request
- lock-X: exclusive lock request
- unlock: release previously held lock
T1
Example:
lock-X(B)
read(B)
B B-50
write(B)
unlock(B)
lock-X(A)
read(A)
A A + 50
write(A)
unlock(A)
T2
lock-S(A)
read(A)
unlock(A)
lock-S(B)
read(B)
unlock(B)
display(A+B)
Locks
 Shared locks
 SELECT statements (w/o any updates)
 Exception In Oracle: select statements do not obtain any
shared locks: They read from a committed version
(read-consistency protocol).
High throughput for analysis-tread-only queries
 Exclusive locks
 Update, delete, insert, and select-for-update
 Lock individual rows
 Lock Table …
Locking Issues
 Starvation
 T1 holds shared lock on Q
 T2 requests exclusive lock on Q: blocks
 T3, T4, ..., Tn request shared locks: granted
 T2 is starved!
 Solution?
Do not grant locks if other xction (with incompatible lock) is waiting
Locking Issues
 No xction proceeds:
T1
T2
Deadlock
- T1 waits for T2 to unlock A
lock-X(B)
- T2 waits for T1 to unlock B
read(B)
After timeout, one of them is rolled back.
B  B-50
write(B)
lock-S(A)
read(A)
Rollback transactions
Can be costly...
lock-S(B)
lock-X(A)
Locking Issues
 Locking itself does not ensure serializability by itself:
T1
lock-X(B)
read(B)
B B-50
write(B)
unlock(B)
T2
lock-S(A)
read(A)
unlock(A)
lock-S(B)
read(B)
unlock(B)
display(A+B)
lock-X(A)
read(A)
A A + 50
write(A)
unlock(A)
T2 displays 50 less!!
Not same as
<T1, T2> or <T2, T1>
The Two-Phase Locking Protocol
 This is a protocol which ensures conflict-serializable schedules.
 Phase 1: Growing Phase
 transaction may obtain locks
 transaction may not release locks
 Phase 2: Shrinking Phase
 transaction may release locks
 transaction may not obtain locks
 The protocol assures serializability. It can be proved that the
transactions can be serialized in the order of their lock points
(i.e. the point where a transaction acquired its final lock).
2PL
 Example: T1 in 2PL
Growing phase
Shrinking phase


T1
lock-X(B)
read(B)
B  B - 50
write(B)
lock-X(A)
read(A)
Lock point
(final lock in txn)
A  A - 50
write(A)
unlock(B)
unlock(A)
The order of the “lock points” of txns determines the serializability order.
2PL & Serializability
 Recall: Precedence Graph
T1
T2
T3
read(Q)
write(Q)
read(R)
write(R)
read(S)
T1
T2
T3
2PL & Serializability
 Recall: Precedence Graph
T1
T2
T3
read(Q)
write(Q)
read(R)
write(R)
read(S)
write(S)
T1
T2
T3
Cycle  Non-serializable
2PL & Serializability
Relation between Growing & Shrinking phase:
T1G < T1S
T1
T2G < T2S
T2
T3G < T3S
T1 must release locks for other to proceed
T3
T1S < T2G
T2S < T3G
T3S < T1G
T1G < T1S< T2G <T2S<T3G<T3S<T1G
Not Possible under 2PL!
It can be generalized for any set of transactions...
2PL Issues
 2PL does not prevent deadlock
T1
T2
lock-X(B)
read(B)
 > 2 xctions involved?
- Rollbacks expensive
B  B-50
write(B)
lock-S(A)
read(A)
lock-S(B)
lock-X(A)
2PL Issues: Cascading Rollbacks
T1
T2
T3
lock-X(A)
read(A)
lock-S(B)
read(B)
write(A)
unlock(A)
lock-X(A)
read(A)
write(A)
unlock(A)
lock-S(A)
read(A)
<xction fails>
T2, T3 need to be rolled back because T1 failed
The Two-Phase Locking Protocol (Cont.)
 Two-phase locking does not ensure freedom from
 deadlocks,
 cascading rollbacks
 Cascading roll-back is possible under two-phase locking. To avoid this,
follow a modified protocol called strict two-phase locking. Here a
transaction must hold all its exclusive locks till it commits/aborts.
 Rigorous two-phase locking is even stricter: here all locks are held
till commit/abort. In this protocol transactions can be serialized in the
order in which they commit.
2PL Variants
 Strict two phase locking
 Exclusive locks must be held until xction commits
 Ensures data written by xction can’t be read by others
 Prevents cascading rollbacks
Strict 2PL & No Cascading Rollbacks
T1
T2
T3
lock-X(A)
read(A)
lock-S(B)
read(B)
write(A)
unlock(A)
lock-X(A)
read(A)
write(A)
unlock(A)
Strict 2PL
Does not
Allow that
(need to
Unlock at
Commit time)
lock-S(A)
read(A)
<xction fails>
Strict 2PL
 Ensures any data written by uncommited xction not
read by another
 Strict 2PL would prevent T2 and T3 from reading A
T1 & T2 wouldn’t rollback if T1 does
2PL Variants
 Strict 2PL
 Only Exclusive locks are held till txn commits
 Rigorous two-phase locking
Exclusive and shared locks too must be held until
xction commits
Order the txns commit is serializability order
 Both variants often used in DB systems
 Strict 2PL
Lock Conversions
 Two-phase locking with lock conversions:
– First Phase:
 can acquire a lock-S on item
 can acquire a lock-X on item
 can convert a lock-S to a lock-X (upgrade)
– Second Phase:
 can release a lock-S
 can release a lock-X
 can convert a lock-X to a lock-S (downgrade)
 This protocol assures serializability. But still relies on the
programmer to insert the various locking instructions.
Automatic Acquisition of Locks
 A transaction Ti issues the standard read/write instruction,
without explicit locking calls.
 The operation read(D) is processed as:
if Ti has a lock on D
then
read(D)
else begin
if necessary wait until no other
transaction has a lock-X on D
grant Ti a lock-S on D;
read(D)
end
Automatic Acquisition of Locks (Cont.)
 write(D) is processed as:
if Ti has a lock-X on D
then
write(D)
else begin
if necessary wait until no other trans. has any lock on D,
if Ti has a lock-S on D
then
upgrade lock on D to lock-X
else
grant Ti a lock-X on D
write(D)
end;
 All locks are released after commit or abort
Implementation of Locking
 A lock manager can be implemented as a separate process to
which transactions send lock and unlock requests
 The lock manager replies to a lock request by sending a lock
grant messages (or a message asking the transaction to roll
back, in case of a deadlock)
 The requesting transaction waits until its request is answered
 The lock manager maintains a data-structure called a lock
table to record granted locks and pending requests
 The lock table is usually implemented as an in-memory hash
table indexed on the name of the data item being locked
Lock Table
 Black rectangles indicate granted
locks, white ones indicate waiting
requests
 Lock table also records the type of
lock granted or requested
 New request is added to the end of
the queue of requests for the data
item, and granted if it is compatible
with all earlier locks
 Unlock requests result in the
Granted
Waiting
request being deleted, and later
requests are checked to see if they
can now be granted
 If transaction aborts, all waiting or
granted requests of the transaction
are deleted
 lock manager may keep a list of
locks held by each transaction, to
implement this efficiently