Lecture - Department of Computing
Download
Report
Transcript Lecture - Department of Computing
Term 2, 2004, Lecture 6, Transactions
Marian Ursu, Department of Computing, Goldsmiths College
3
Transactions
1
Term 2, 2004, Lecture 6, Transactions
Marian Ursu, Department of Computing, Goldsmiths College
Outline
transactions - generalities
concurrency control
concurrency problems
locking
2
Term 2, 2004, Lecture 6, Transactions
Marian Ursu, Department of Computing, Goldsmiths College
1
3
Term 2, 2004, Lecture 6, Transactions
Marian Ursu, Department of Computing, Goldsmiths College
Transactions – example
Parts (P_id, P_name, Colour, Weight, Total_qty)
Contracted (S_id, P_id, Qty)
add a new contract for ‘S4’ for 200 pieces of ‘P1’
P_id
P1
P2
…
P_name
gear
pin
…
Colour Weight
white
black
…
S_id
S1
S1
S2
S3
S3
P_id
P1
P3
P1
P1
P2
1.233
0.1
…
Total_qty
1150
10000
…
Qty
500
200
150
500
1000
4
Term 2, 2004, Lecture 6, Transactions
Marian Ursu, Department of Computing, Goldsmiths College
Transaction
logical unit of work
sequence of database operations
transforms a consistent state of a db into another
consistent state
between operations the db can be inconsistent
5
Term 2, 2004, Lecture 6, Transactions
Marian Ursu, Department of Computing, Goldsmiths College
Transaction Processing
do not allow for
one operation to be performed and the other ones not
principle of transaction processing support
if some operations are executed and then a failure occurs
(before the planned termination) then those operations will
be undone
6
Term 2, 2004, Lecture 6, Transactions
Marian Ursu, Department of Computing, Goldsmiths College
Transaction Manager
COMMIT TRANSACTION
• a logical unit of work was successfully completed
• all the updates can be made permanent
ROLLBACK TRANSACTION
• unsuccessful end of transaction
• all the attempted updates must be rolled back
they are issued from applications
7
Term 2, 2004, Lecture 6, Transactions
Marian Ursu, Department of Computing, Goldsmiths College
Example
execute(BEGIN TRANSACTION);
execute(INSERT (‘S4’, ‘P1’, 200) INTO Contracted);
if(/*any error occurred*/) then go to undo;
execute( UPDATE Parts WHERE P_id =‘P1’
SET Total_qty = Total_qty + 200);
if(/*any error occurred*/) then go to undo;
execute(COMMIT TRANSACTION);
go to finish;
undo : execute(ROLLBACK TRANSACTION);
finish : return;
8
Term 2, 2004, Lecture 6, Transactions
Marian Ursu, Department of Computing, Goldsmiths College
SQL Support
COMMIT and ROLLBACK
No BEGIN TRANSACTION (in SQL2 and Oracle)
all data definition and data manipulation statements are
transaction initiating
PostgreSQL provides
BEGIN [TRANSACTION]
9
Term 2, 2004, Lecture 6, Transactions
Marian Ursu, Department of Computing, Goldsmiths College
At the COMMIT point
all updates, since the previous commit, are made
permanent (will not be undone)
all database positioning and all tuple locks are lost
10
Term 2, 2004, Lecture 6, Transactions
Marian Ursu, Department of Computing, Goldsmiths College
ACID Properties of Transactions
Atomicity
• all or nothing
Consistency
• preserve database consistency
Isolation
• transactions are isolated from one another
Durability
• committed transaction updates are performed
11
Term 2, 2004, Lecture 6, Transactions
Marian Ursu, Department of Computing, Goldsmiths College
2
12
Term 2, 2004, Lecture 6, Transactions
Marian Ursu, Department of Computing, Goldsmiths College
Concurrency
more than one transaction have access to data
simultaneously
13
Term 2, 2004, Lecture 6, Transactions
Marian Ursu, Department of Computing, Goldsmiths College
Three concurrency problems
the lost update
the uncommitted dependency
the inconsistent analysis
14
Term 2, 2004, Lecture 6, Transactions
Marian Ursu, Department of Computing, Goldsmiths College
The lost update problem
Transaction A
time
RETRIEVE (t)
t1
t2
UPDATE (t) TO (t1)
Transaction B
RETRIEVE (t)
t3
t4
UPDATE (t) TO (t2)
15
Term 2, 2004, Lecture 6, Transactions
Marian Ursu, Department of Computing, Goldsmiths College
The uncommitted dependency problem
Transaction A
RETRIEVE (t)
time
Transaction B
t1
UPDATE (t)
t2
t3
ROLLBACK
16
Term 2, 2004, Lecture 6, Transactions
Marian Ursu, Department of Computing, Goldsmiths College
The uncommitted dependency problem
Transaction A
UPDATE p
time
Transaction B
t1
UPDATE p
t2
t3
ROLLBACK
17
Term 2, 2004, Lecture 6, Transactions
Marian Ursu, Department of Computing, Goldsmiths College
The inconsistent analysis problem
Transaction A
BEGIN TRANSACTION
RETRIEVE (SugarA)
[sum = 500]
RETRIEVE (SugarB)
[sum = 700]
RETRIEVE (SugarC)
[sum = 800]
end result: sum = 800
time
t0
t1
t2
t3
t4
t5
Transaction B
BEGIN TRANSACTION
RETRIEVE (SugarA)
UPDATE SugarA TO 0
COMMIT
t6
18
Term 2, 2004, Lecture 6, Transactions
Marian Ursu, Department of Computing, Goldsmiths College
Issue
all these problems may lead to an inconsistent
(incorrect) database
is there a criterion based on which to decide weather
a certain set of transaction, if executed concurrently,
leads to an incorrect database or not?
19
Term 2, 2004, Lecture 6, Transactions
Marian Ursu, Department of Computing, Goldsmiths College
Serialisability
criterion for correctness for concurrent execution of
transactions:
the interleaved execution of a set of transactions is
guaranteed to be correct if it is serialisable
correct the DB is not in an inconsistent state
serialisability: an interleaved execution has the same result
as some serial execution
20
Term 2, 2004, Lecture 6, Transactions
Marian Ursu, Department of Computing, Goldsmiths College
Serialisable schedule
Interleaved schedule for transaction 1, 2 and 3
time
Transaction 1
Transaction 2
Transaction 3
t1
op11
t2
t3
t4
op12
op21
t5
t6
op22
op23
t7
op13
op31
t8
t9
op14
op32
Equivalent serial schedule (Transaction 1 then Transaction 3 then Transaction 2)
time
Transaction 1
Transaction 2
Transaction 3
t1
op11
t2
op12
t3
op13
t4
op14
t5
op31
t6
t7
t8
t9
op21
op22
op23
op32
21
Term 2, 2004, Lecture 6, Transactions
Marian Ursu, Department of Computing, Goldsmiths College
Notes
the schedules described in the concurrency problems
examples were not serialisable
neither A-then-B nor B-then-A
two different interleaved transactions might produce
different results, yet both can be considered correct
22
Term 2, 2004, Lecture 6, Transactions
Marian Ursu, Department of Computing, Goldsmiths College
3
23
Term 2, 2004, Lecture 6, Transactions
Marian Ursu, Department of Computing, Goldsmiths College
Two-phase locking theorem
if all transactions obey the
two phase locking protocol
then all possible interleaved schedules are
serialisable
• i.e., they can be executed concurrently, because they will leave
the database in a consistent state
24
Term 2, 2004, Lecture 6, Transactions
Marian Ursu, Department of Computing, Goldsmiths College
Two-phase locking protocol
1.before operating on an object a transaction must acquire a lock
on that object
2.after releasing a lock a transaction must not go on to acquire any
more locks
• phase1 (growing): acquire locks (not simultaneously)
• phase2 (shrinking): release locks (no further acquisitions
allowed)
• usually locks are released by the COMMIT or ROLLBACK
operation
in practice
• trade-off between “release lock early and acquire more locks”
and the “two phase locking protocol”
25
Term 2, 2004, Lecture 6, Transactions
Marian Ursu, Department of Computing, Goldsmiths College
Locking
usually, applicable to tuples
types
• X, exclusive - write
• S, shared - read
rules
• compatibility matrix
26
Term 2, 2004, Lecture 6, Transactions
Marian Ursu, Department of Computing, Goldsmiths College
Compatibility matrix
existing lock on t
X
S
none
X
refused
refused
granted
S
refused
granted
granted
-
-
-
request for lock on t
no request
27
Term 2, 2004, Lecture 6, Transactions
Marian Ursu, Department of Computing, Goldsmiths College
Data access protocol
retrieve tuple acquire S lock (on that tuple)
update tuple acquire X lock (on that tuple), or
promote the S lock it holds (if it holds one)
• implicit request
if request for lock is denied transaction goes in
wait state until the lock is released
• livelock - first come first served
X locks are held until end of transaction (COMMIT or
ROLLBACK) (two phase locking protocol)
28
Term 2, 2004, Lecture 6, Transactions
Marian Ursu, Department of Computing, Goldsmiths College
The uncommitted dependency problem: OK
Transaction A
RETRIEVE (t)
(request X lock on t)
wait
wait
resume RETRIEVE (t)
(acquire S lock on t)
time
Transaction B
t1
UPDATE (t)
(X lock on t)
t2
t3
COMMIT / ROLL..
(release X lock on t)
t4
29
Term 2, 2004, Lecture 6, Transactions
Marian Ursu, Department of Computing, Goldsmiths College
The lost update problem : dead-lock
Transaction A
RETRIEVE p
(acquire S lock on p)
time
t1
t2
UPDATE p
(request X lock on p
denied)
wait
wait
wait
Transaction B
RETRIEVE p
(acquire S lock on p)
t3
t4
UPDATE p
(request X lock on p
denied)
wait
30
Term 2, 2004, Lecture 6, Transactions
Marian Ursu, Department of Computing, Goldsmiths College
Locking
solves the three basic problems of concurrency
theorem
• if all the transactions of a set S of transactions comply with the
two phase locking protocol, then all their possible interleaved
executions (schedules) are serialisable
• however, not all schedules produce the same result
– think of examples
introduces another problem: deadlock
31
Term 2, 2004, Lecture 6, Transactions
Marian Ursu, Department of Computing, Goldsmiths College
Deadlock
two or more transaction are waiting for the other to
release a lock
• in practice: usually two transactions
detect a deadlock
• cycle in the wait-for graph, or
• timing mechanism
break a deadlock
• rollback a victim transaction
• what happens to the victim?
32
Term 2, 2004, Lecture 6, Transactions
Marian Ursu, Department of Computing, Goldsmiths College
Further topics
• two phase locking protocol - not feasible in practice (not
efficient)
levels of isolation
• degree of interference
intent locking
• locking granularity
SQL support
• no explicit locking facilities
• it supports different isolation levels (with “locking behind the
scenes”)
33
Term 2, 2004, Lecture 6, Transactions
Marian Ursu, Department of Computing, Goldsmiths College
–
34
Term 2, 2004, Lecture 6, Transactions
Marian Ursu, Department of Computing, Goldsmiths College
Conclusions
transactions
concurrency
concurrency problems
locking
35