Transactions in the databse management and computer science.ppt

database management system in computer science and engineering

1. CS 542: Topics in
Distributed Systems
Transactions and Concurrency Control

2. Banking transaction for a customer (e.g., at
ATM or browser)
Transfer $100 from saving to checking account;
Transfer $200 from money-market to checking account;
Withdraw $400 from checking account.
Transaction (invoked at client): /* Every step is an RPC */
1. savings.withdraw(100)/* includes verification */
2. checking.deposit(100)/* depends on success of 1 */
3. mnymkt.withdraw(200)/* includes verification */
4. checking. deposit(200)/* depends on success of 3 */
5. checking.withdraw(400)/* includes verification */
6. dispense(400)
7. commit
Transactions
Client Server
Transaction

3. Bank Server: CoordinatorInterface
All the following are RPCs from a client to the server
Transaction calls that can be made at a client, and return
values from the server:
openTransaction() -> trans;
starts a new transaction and delivers a unique transaction identifier
(TID) trans. This TID will be used in the other operations in the
transaction.
closeTransaction(trans) -> (commit, abort);
ends a transaction: a commitreturn value indicates that the
transaction has committed; an abortreturn value indicates that it has
aborted.
abortTransaction(trans);
aborts the transaction.
TID can be passed implicitly (for other operations between
open and close) with CORBA
Transactions can be implemented using RPCs/RMIs!

4. Bank Server: Account, Branchinterfaces
deposit(amount)
deposit amount in the account
withdraw(amount)
withdraw amount from the account
getBalance() -> amount
return the balance of the account
setBalance(amount)
set the balance of the account to amount
create(name) -> account
create a new account with a given name
lookup(name) -> account
return a reference to the account with the given
name
branchTotal() -> amount
return the total of all the balances at the branch
Operations of the Branch interface
Operations of the Account interface

5. Transaction
Sequence of operations that forms a single step,
transforming the server data from one consistent
state to another.
All or nothingprinciple: a transaction either completes
successfully, and the effects are recorded in the objects, or it has
no effect at all. (even with multiple clients, or crashes)
A transactions is indivisible(atomic) from the point
of view of other transactions
No access to intermediate results/states of other transactions
Free from interference by operations of other transactions
But…
Transactions could run concurrently, i.e., with
multiple clients
Transactions may be distributed, i.e., across
multiple servers

6. Transaction:
1. savings.deduct(100)
2. checking.add(100)
3. mnymkt.deduct(200)
4. checking.add(200)
5. checking.deduct(400)
6. dispense(400)
7. commit
Transaction Failure Modes
A failure at these
points means the
customer loses
money; we need
to restore old state
A failure at
these points
does not cause
lost money, but
old steps
cannot be
repeated
This is the point of
no return
A failure after the
commit point
(ATM crashes)
needs corrective
action; no undoing
possible.

7. Transactions in Traditional Databases (ACID)
Atomicity: All or nothing
Consistency: if the server starts in a consistent state, the
transaction ends the server in a consistent state.
Isolation: Each transaction must be performed without
interference from other transactions, i.e., the non-final effects
of a transaction must not be visible to other transactions.
Durability: After a transaction has completed successfully, all
its effects are saved in permanent storage.
Atomicity: store tentative object updates (for later
undo/redo) –many different ways of doing this
Durability: store entire results of transactions (all updated
objects) to recover from permanent server crashes.

8. Concurrent Transactions:LostUpdate Problem
One transaction causes loss of info. for another:
consider three account objects
Transaction T1Transaction T2
balance = b.getBalance()
balance = b.getBalance()
b.setBalance(balance*1.1)
b.setBalance(balance*1.1)
a.withdraw(balance* 0.1)
c.withdraw(balance*0.1)
T1/T2’s update on the shared object, “b”, is lost
100 200 300a: b: c:
280c:
80a:
220b:
220b:

9. Conc. Trans.: Inconsistent Retrieval Prob.
Partial, incomplete results of one transaction are
retrieved by another transaction.
Transaction T1Transaction T2
a.withdraw(100)
total = a.getBalance()
total = total + b.getBalance
b.deposit(100)
total = total + c.getBalance
T1’s partial result is used by T2, giving the wrong
result for T2
100 200
0.00
a: b:
00a:
500
200
300c:
total
300b:

10. An interleaving of the operations of 2 or more transactions is
said to be serially equivalent if the combined effect is the same
as if these transactions had been performed sequentially (in
some order).
Transaction T1 Transaction T2
balance = b.getBalance()
b.setBalance(balance*1.1)
balance = b.getBalance()
b.setBalance(balance*1.1)
a.withdraw(balance* 0.1)
c.withdraw(balance*0.1)
Concurrency Control: “Serial Equivalence”
100 200 300a: b: c:
278c:
a:
242b:
b:220
80
== T1 (complete) followed
by T2 (complete)

11. The effect of an operation refers to
The value of an object set by a write operation
The result returned by a read operation.
Two operationsare said to be conflicting operations, if their
combined effectdepends on the orderthey are executed,
e.g., read-write, write-read, write-write (all on same
variables). NOT read-read, NOT on different variables.
Two transactionsare serially equivalent if and only if all
pairs of conflicting operations (pair containing one operation
from each transaction) are executed in the same order
(transaction order) for all objects (data) they both access.
Why? Can start from original operation sequence and swap the order of
non-conflicting operations to obtain a series of operations where one
transaction finishes completely before the second transaction starts
Why is the above result important? Because: Serial equivalence
is the basis for concurrency control protocols for
transactions.
Checking Serial Equivalence –
Conflicting Operations

12. Readand WriteOperation Conflict Rules
Operations of different
transactions
Conflict Reason
read readNo Because the effect of a pair of readoperations
does not depend on the order in which they are
executed
read writeYes Because the effect of a readand a writeoperation
depends on the order of their execution
write writeYes Because the effect of a pair of writeoperations
depends on the order of their execution

13. An interleaving of the operations of 2 or more transactions is
said to be serially equivalent if the combined effect is the same
as if these transactions had been performed sequentially (in
some order).
Transaction T1 Transaction T2
balance = b.getBalance()
b.setBalance(balance*1.1)
balance = b.getBalance()
b.setBalance(balance*1.1)
a.withdraw(balance* 0.1)
c.withdraw(balance*0.1)
Concurrency Control: “Serial Equivalence”
100 200 300a: b: c:
278c:
a:
242b:
b:220
80
== T1 (complete) followed
by T2 (complete)
Pairs of Conflicting Operations

14. Conflicting Operators Example
Transaction T1 Transaction T2
x= a.read()
a.write(20)
y = b.read()
b.write(30)
b.write(x)
z = a.read()
x= a.read()
a.write(20)
z = a.read()
b.write(x)
y = b.read()
b.write(30)
Serially
equivalent
interleaving
of
operations
(why?)
Conflicting
Ops.
Non-
serially
equivalent
interleaving
of
operations

15. Inconsistent Retrieval Prob
Partial, incomplete results of one transaction are
retrieved by another transaction.
Transaction T1Transaction T2
a.withdraw(100)
total = a.getBalance()
total = total + b.getBalance
b.deposit(100)
total = total + c.getBalance
T1’s partial result is used by T2, giving the wrong
result for T2
100 200
0.00
a: b:
00a:
500
200
300c:
total
300b:

16. A Serially Equivalent Interleaving of T1 and T2
Transaction T1:
a.withdraw(100);
b.deposit(100)
Transaction T2:
aBranch.branchTotal()
a.withdraw(100);
$100
b.deposit(100)
$300
total = a.getBalance()
$100
total = total+b.getBalance()
$400
total = total+c.getBalance()...

17. How can we prevent isolation from being violated?
Concurrent operations must be consistent:
If trans.Thas executed a readoperation on object A, a
concurrent trans. U must not writeto A until T commits or
aborts.
If trans. T has executed a writeoperation on object A, a
concurrent U must not read or writeto A until T commits
or aborts.
How to implement this?
Implementing Concurrent Transactions

18. Concurrency control
•Lost update
–3 accounts (A, B, C)
»with balances 100, 200, 300
–T1 transfers from A to B, for 10% increase
–T2 transfers from C to B, for 10% increase
–Both T1, T2 read balance of B (200)
–T1 overwrites the update by T2
»Without seeing it
Transactions should not read a “stale” value & use it in
computing a new value

19. Concurrency control
•Inconsistent retrievals
–T1: transfers 10% of account A to account B
–T2: computes sum of account balances
–T2 computes sum beforeT1 updates B
Update transactions should not interfere with retrievals.
In general:
Transactions should not violate operation conflict rules.

20. Concurrency control
Serial equivalence
criterion for correct concurrent execution
T1 serially equivalentwith T2 iff:
All pairs of conflicting operations of the two transactions are executed in the
same order at all objects that both transactions access.
3 approaches to CC:
-Locking
-Optimistic CC
-Timestamp ordering
Tx’s wait for one another
OR:
Restart Tx’s after conflicts
have been detected

21. Recoverability from aborts
•Servers must prevent a aborting Tx from affecting other
concurrent Tx’s.
–Dirty reads:
»T2 sees result update by T1 on account A
»T2 performs its own update on A & then commits.
»T1 aborts -> T2 has seen a “transient” value
•T2 is not recoverable
»If T2 delays its commit until T1’s outcome is resolved:
•Abort(T1) -> Abort(T2)
•However, if T3 has seen results of T2:
–Abort(T2) -> Abort(T3) !
»Cascading aborts
Tx’s should only read values written by committed Tx’s

22. Recoverability from aborts
•Premature writes:
–Assume server implements abort by maintaining the
“before” image of all update operations
»T1 & T2 both updates account A
»T1 completes its work before T2
»If T1 commits & T2 aborts, the balance of A is correct
»If T1 aborts & T2 commits, the “before” image that is restored
corresponds to the balance of A beforeT2
»If both T1 & T2 abort, the “before” image that is restored
corresponds to the balance of A as set by T1
Tx’s should be delayed until earlier Tx’s that update the
Same objects have been either committed or aborted.

23. Recoverability from aborts
•Tx’s should delay both their reads & updates in order to
avoid interference
–Strict execution-> enforce isolation
•Servers should maintain tentative versions of objects in
volatile memory
Tx’s should be delayed until earlier Tx’s that update the
Same objects have been either committed or aborted.

24. Concurrency Control: Locks
•Transactions:
–Must be scheduled so that their effect on shared data is
serially equivalent
–Two types of approach
»Pessimistic If something can go wrong, it will
Operations are synchronized before they are carried
out
»Optimistic In general, nothing will go wrong
Operations are carried out, synchronization at the end
of the transaction
–Locks (pessimistic)
»can be used to ensuring serializability
»lock(x), unlock(x)

25. Locks: Basics
•Oldest and most widely used CC algorithm
•A process before read/write requests the
scheduler to grant a lock
•Upon finishing read/write the lock is released
•In order to ensure serialized transaction Two
Phase Locking (2PL) is used

26. Locking
•How Locks prevent consistency problems
–Lost update and inconsistent retrieval:
–Causes:
»are caused by the conflict between r
i(x) and
w
j(x)
»two transactions read a value and use it to
compute new value
–Prevention:
»delay the reads of later transactions until the
earlier ones have completed
•Disadvantage of Locking
–Deadlocks

27. 2PL
•Strict 2PL avoids Cascading Aborts
–A situation where a committed transaction has to be undone
because it saw a file it shouldn’t have seen.
•Problems of Locking
–Deadlocks
–Livelocks
»A transaction can’t proceed for an indefinite amount of time
while other transactions continue normally. It happens due
to unfair locking.
–Lock overhead
»If the system doesn’t allow shared access--wastage of
resources
–Avoidance of Cascading Aborts may be costly
»Strict 2PL in fact, reduces the effect of concurrency

28. Exclusive Locks
Transaction T1 Transaction T2
OpenTransaction()
balance = b.getBalance() OpenTransaction()
balance = b.getBalance()
b.setBalance(balance*1.1)
a.withdraw(balance* 0.1)
CloseTransaction()
b.setBalance(balance*1.1)
c.withdraw(balance*0.1)
CloseTransaction()
Example: Concurrent Transactions
Lock
B
Lock
A
UnLock
B
UnLock
A
Lock
C
UnLock
B
UnLock
C
…
WAIT
on B
Lock
B
…

29. Transaction managers (on server side) set locks
on objects they need. A concurrent trans. cannot
access locked objects.
Two phase locking:
In the first (growing) phase of the transaction,
new locks are only acquired, and in the second
(shrinking) phase, locks are only released.
A transaction is not allowed acquire anynew
locks, once it has released any one lock.
Basic Locking

30. Strict two phase locking:
Locking on an object is performed only before
the first request to read/write that object is
about to be applied.
Unlocking is performed by the commit/abort
operations of the transaction coordinator.
To prevent dirty reads and premature writes, a
transaction waits for another to commit/abort
However, use of separate readand writelocks leads to more
concurrency than a single exclusivelock –Next slide
Basic Locking

31. non-exclusivelock compatibility
Lock already Lock requested
set read write
none OK OK
read OK WAIT
write WAIT WAIT
A read lock is promotedto a write lock when the
transaction needs write access to the same object.
A read lock sharedwith other transactions’read
lock(s) cannot be promoted. Transaction waits for
other read locks to be released.
Cannot demote a write lock to read lock during
transaction –violates the 2P principle
2P Locking: Non-exclusive lock (per object)

32. Two Phase Locking (2PL) Protocols
•In 2PL—All lockoperations must precede the first
unlock operation
–Two phases
»expanding or growing phase: all locking are done in this
phase but no lock release allowed
»shrinking phase: all lock release but no lock acquire
Growing phase Shrinking phase
Time
No. of
Locks

33. When an operation accesses an object:
if you can, promote a lock (nothing -> read -> write)
Don’t promote the lock if it would result in a conflict with
another transaction’s already-existing lock
wait until all shared locks are released, then lock &
proceed
When a transaction commitsor aborts:
release all locks that were set by the transaction
Locking Procedure in Strict-2P Locking

34. Non-exclusive Locks
Transaction T1 Transaction T2
OpenTransaction()
balance = b.getBalance() OpenTransaction()
balance = b.getBalance()
b.setBalance(balance*1.1)
Commit
Example: Concurrent Transactions
R-Lock
B
…
R-
Lock
B
Cannot Promote lock on B, Wait
Promote lock on B

35. What happens in the example below?
Transaction T1 Transaction T2
OpenTransaction()
balance = b.getBalance() OpenTransaction()
balance = b.getBalance()
b.setBalance(balance*1.1)
b.setBalance=balance*1.1
Example: Concurrent Transactions
R-Lock
B
…
R-
Lock
B
Cannot Promote lock on B, Wait
Cannot Promote lock on B, Wait
…

36. Deadlock with write locks
Transaction T Transaction U
Operations Locks Operations Locks
a.deposit(100);
write lock A
b.deposit(200)
write lock B
b.withdraw(100)
waits for U’sa.withdraw(200);waits for T’s
lock on B lock on A
T locks A and waits for U to release the lock on B, U on the other
hand locks B and waits for T to release the lock on A
Circular hold and wait Deadlock

37. The corresponding wait-for graph
B
A
Waits for
Held by
Held by
T UU T
Waits for

38. Deadlocks
Necessary conditions for deadlocks
Non-shareable resources (exclusive lock modes)
No preemption on locks
Hold & Wait or Circular Wait
T U
Wait forHeld by
Held by
Wait for
A
B
T
U
Wait forHeld by
Held by
Wait for
A
B
V
W
...
...
Wait for
Wait for
Held by
Held by
Hold & Wait Circular Wait

39. Naïve Deadlock Resolution Using Timeout
Transaction T Transaction U
Operations Locks Operations Locks
a.deposit(100);write lock A
b.deposit(200)write lock B
b.withdraw(100)
waits for U’s
a.withdraw(200);waits for T’s
lock on B lock on A
(timeout elapses)
T’s lock on Abecomes vulnerable,
unlock A, abort T
a.withdraw(200);write locks A
unlock A
,
B
Disadvantages?

40. Strategies to Fight Deadlock
Lock timeout (costly and open to false positives)
Deadlock Prevention: violate one of the necessary
conditions for deadlock (from 2 slides ago), e.g.,
lock all objects before transaction starts, aborting
entire transaction if any fails
Deadlock Avoidance: Have transactions declare
max resources they will request, but allow them to
lock at any time (Banker’s algorithm)
Deadlock Detection: detect cycles in the wait-for
graph, and then abort one or more of the
transactions in cycle

41. Optimistic Concurrency Control
(Kung and Robinson)
•We have seen locking has some problems
•OCC based on the following simple idea:
–Don’t worry about the conflicts, keep on doing
whatever you’re doing, if there’s a problem
worry about it later.

42. Optimistic Concurrency Control
(Kung and Robinson)
•Algorithm
–Each transaction has the following phases
»Working phase
•Each transaction has a tentative version of
each object that it updates
•Tentative version allows the trans. to abort
w/o affecting the object
»Validation phase
•transaction is validated to see if any conflicts
with other trans.
»Update phase
•if a trans. is validated all tentative objects are
made permanent

43. Optimistic Concurrency Control:
Earlier committed
transactions
Working ValidationUpdate
T
1
T
v
Transaction
being validated
T
2
T
3
Later active
transactions
active
1
active
2
Validation of transactions

44. Validation Rules
Tv Ti Rule
writeread1. Ti must not read objects written by Tv
readwrite2. Tvmust not read objects written by Ti
writewrite3. Ti must not write objects written by Tvand
Tvmust not write objects written by Ti

45. Validation of Transactions
Backward validation of transaction T
v
boolean valid = true;
for (int T
i= startTn+1; T
i<= finishTn; T
i++){
if (read set of T
vintersects write set of T
i) valid = false;
}
Forward validation of transaction T
v
boolean valid = true;
for (int T
id= active1; T
id<= activeN; T
id++){
if (write set of T
vintersects read set of T
id) valid = false;
}

46. Summary
•Increasing concurrency important because it
improves throughput at server
•Applications are willing to tolerate temporary
inconsistency and deadlocks in turn
–Need to detect and prevent these
•Driven and validated by actual application
characteristics –mostly-read transactions abound