Chapter 13:
Transactions and Concurrency Control
From
Distributed Systems: Concepts and Design
By
Coulouris, Dollimore and Kindberg
Edition 4, © Addison-Wesley 2005
Transactions and Concurrency Control
13.1 Introduction
13.2 Transactions
13.3 Nested transactions
13.4 Locks
13.5 Optimistic concurrency control
13.6 Timestamp ordering
13.7 Comparison of methods
18.8 Summary
Introduction
Goal: ensure that all objects managed by a server remain in a consistent state when they are accessed or when the server crashes.
Recoverable objects: These objects can be recovered after the server crashes.
Transactions: A transaction are specified by a client as a set of operations on objects to be performed as an indivisible unit by the servers.
In this chapter a banking example will be used to illustrate these concepts.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Introduction
In the example used in this chapter we have a banking example.
Each account is represented by a remote object whose interface Account provides operations for making deposits and withdrawals and for enquiring about and setting the balance
Each branch of the bank is represented by a remote object whose interface Branch provides operations for creating a new account, for looking u an account by name and for enquiring about the total funds at that branch.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Figure 13.1
Operations of the Account interface
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
Operations of the Branch interface
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
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
13.1.1 Simple synchronisation ( without transaction)
Atomic operations at the server:
If you are not careful you may have more than strange results when the same object is accessed.
the use of multiple threads improve performance
the use of threads allows operations to run concurrently and possibly access the same object.
In Java the keyword synchronized is use to ensure that only one thread at a time can access an object.
In practice the object is locked.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
13.1.1 Simple synchronisation ( without transaction)
Atomic Operations:
Operations that are free from interference from concurrent operations being performed in other threads are called atomic operations.
Enhancing client cooperation by synchronization of server operations.
In many applications it is sufficient to make sure that threads do not interfere with one another. The previous method take care of that. This does not work in all cases.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
13.1.1 Simple synchronisation ( without transaction)
Java wait and notify method:
In a producer-consumer context threads may have to
The java wait and notify method used within synchronized methods of an object can achieve this requirement.
A thread call wait on an object so as to suspend itself. Another thread can execute a method on that object.
Access to an object under this scheme is still atomic. To be verify as an exercice.
communicate together and maintain consistency.
A thread call notify to let know any other threads waiting on that object that it has changed some of its data.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
13.1.2 Failure model for transactions
There exists failure models for distributed transactions. We wil return to one of such model in the next section.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Introduction to transactions
The goal of transactions
the objects managed by a server must remain in a consistent state
⌧when they are accessed by multiple transactions and ⌧in the presence of server crashes
Recoverable objects
can be recovered after their server crashes (recovery in Chapter 13) objects are stored in permanent storage
Failure model
transactions deal with crash failures of processes and omission failures of
communication
Designed for an asynchronous system
It is assumed that messages may be delayed
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
•
Operations of the Account interface
deposit(amount)
Used as an example. Each Account is represented by a remote object whose interface Account provides operations for making deposits and withdrawals and for setting and getting the balance.
deposit amount in the account
withdraw(amount)
withdraw amount from the account
getBalance() → amount
return the balance of the account
setBalance(amount)
Figure 13.1
set the balance of the account to amount
Operations of the Branch interface
and each Branch of the bank is represented by a remote object whose interface Branch provides operations for creating a new account, looking one up by name and enquiring about the total funds at the branch. It stores a correspondence between account names and their remote object
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
Instructor’s Guide for Coulouris, Dollimore and Kindberg
© Addison-Wesley Publishers 2005
: Concepts and Design Edn. 4
Distributed Systemsreferences
•
Atomic operations at server
first we consider the synchronisation of client operations without transactions
when a server uses multiple threads it can perform several client operations
concurrently
if we allowed deposit and withdraw to run concurrently we could get inconsistent results
objects should be designed for safe concurrent access e.g. in Java use synchronized methods, e.g.
public synchronized void deposit(int amount) throws RemoteException
atomic operations are free from interference from concurrent operations in other
threads.
use any available mutual exclusion mechanism (e.g. mutex)
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
•
Client cooperation by means of synchronizing server operations
Clients share resources via a server
e.g. some clients update server objects and others access them
servers with multiple threads require atomic objects
but in some applications, clients depend on one another to progress e.g. one is a producer and another a consumer
e.g. one sets a lock and the other waits for it to be released
it would not be a good idea for a waiting client to poll the server to see whether a resource is yet available
it would also be unfair (later clients might get earlier turns)
Java wait and notify methods allow threads to communicate with one another and to solve these problems
e.g. when a client requests a resource, the server thread waits until it is notified that the resource is available
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
•
Failure model for transactions
Lampson’s failure model deals with failures of disks, servers and communication. algorithms work correctly when predictable faults occur.
but if a disaster occurs, we cannot say what will happen
Writes to permanent storage may fail
e.g. by writing nothing or a wrong value (write to wrong block is a disaster) reads can detect bad blocks by checksum
Servers may crash occasionally.
when a crashed server is replaced by a new process its memory is cleared and then it carries out a
recovery procedure to get its objects’ state
faulty servers are made to crash so that they do not produce arbitrary failures
There may be an arbitrary delay before a message arrives. A message may be lost, duplicated or corrupted.
recipient can detect corrupt messages (by checksum)
forged messages and undetected corrupt messages are disasters
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
•
Transactions (Section 13.2)
Some applications require a sequence of client requests to a server to be atomic in the sense that:
1. they are free from interference by operations being performed on behalf of other concurrent clients; and
2. either all of the operations must be completed successfully or they must have no effect at all in the presence of server crashes.
Transactions originate from database management systems
Transactional file servers were built in the 1980s
Transactions on distributed objects late 80s and 90s
Middleware components e.g. CORBA Transaction service.
Transactions apply to recoverable objects and are intended to be atomic.
Servers ‘recover’ – they are restated and get their objects from • Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4
permanent storage
© Addison-Wesley Publishers 2005
A client’s banking transaction
Transaction T: a.withdraw(100); b.deposit(100); c.withdraw(200); b.deposit(200);
This transaction specifies a sequence of related operations involving bank accounts named A, B and C and referred to as a, b and c in the program
the first two operations transfer $100 from A to B
the second two operations transfer $200 from C to B
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
•
13.2 Transactions
ACID properties:
Härder and Reuter [1983] suggested the mnemonic
ACID to remember the properties of transactions
Atomiticity; all or nothing
Consistency: a transaction takes the system from one consistent state to another consistent state.
Isolation Durability
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
13.2 Transactions . . .
Serializable:
Transactions that are allowed to execute concurrently have the same effect as a serial execution are said to be serially equivalent or serializable.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Atomicity of transactions
The atomicity has two aspects All or nothing:
1.
2.
permanent storage. Isolation:
it either completes successfully, and the effects of all of its operations are recorded in the objects, or (if it fails or is aborted) it has no effect at all. This all-or-nothing effect has two further aspects of its own:
failure atomicity:
⌧ the effects are atomic even when the server crashes;
durability:
⌧ after a transaction has completed successfully, all its effects are saved in
Each transaction must be performed without interference from other transactions – there must be no observation by other transactions of a transaction’s intermediate
effects
Concurrency control ensures isolation
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
•
More on transactions
When transactions are provided as middleware, the TID can be passed implicitly within all remote invocations between openTransaction and closeTransaction.
This is what CORBA transaction service does.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Operations in the Coordinator interface
transaction capabilities may be added to a server of recoverable objects
each transaction is created and managed by a Coordinator object whose interface
follows:
The coordinator gives to each transaction an identifier or TID
The client invokes the openTransaction of the coordinator to introduce a new transaction
A TID is allocated and returned
At the end of the transaction the client invokes the closeTransaction method to indicate its end.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
•
Figure 13.3
Operations in Coordinator interface
openTransaction() -> trans;
starts a new transaction and delivers a unique TID trans. This identifier will be used in the other operations in the transaction.
closeTransaction(trans) -> (commit, abort);
ends a transaction: a commit return value indicates that the transaction has committed; an abort return value indicates that it has aborted.
abortTransaction(trans);
aborts the transaction.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Transaction . . .
State of a transaction:
A transaction is either successful or it is aborted.
The client abort using abortTransaction call to the server or
The server abort it.
See next figure
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Transaction failures
Service actions related to process crashes:
if a servers crashes it is replaced
Client actions related to server process crashes
If a server crashes while a transaction is in progress the client will know when one of the operations returns an exception after a timeout.
New server process abort any uncommitted transactions
A recovery procedure is used to restore the values of the objects
If the client crashes the server can put a time expiration on the transaction
If a server crashes and is replaced in the middle of a transaction the client must be informed the next time.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Figure 13.4
Transaction life histories
operation operation
operation operation
operation operation
Successful
Aborted by client
Aborted by server
openTransaction
openTransaction
openTransaction
operation closeTransaction
operation abortTransaction
operation ERROR reported to client
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design © Addison-Wesley Publishers 2005
Edn. 4
server aborts transaction
Transaction life histories Fig:13.4
Why might a server abort a transaction?
Successful
Aborted by client
Aborted by server
openTransaction operation operation
openTransaction operation operation
openTransaction operation operation
operation closeTransaction
operation abortTransaction
operation ERROR reported to client
A transaction is either successful (it commits)
the coordinator sees that all objects are saved in permanent storage
or it is aborted by the client or the server
make all temporary effects invisible to other transactions
how will the client know when the server has aborted its transaction?
the client finds out next time it tries to access an object at the server.
•
server aborts transaction
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
13.2.1 Concurrency control
We will illustrate the ‘lost update’ and the ‘inconsistent retrievals’ problems which can occur in the absence of appropriate concurrency control
a lost update occurs when two transactions both read the old value of a variable and use it to calculate a new value
inconsistent retrievals occur when a retieval transaction observes values that are involved in an ongoing updating transaction
we show how serial equivalent executions of transactions can avoid these problems
we assume that the operations deposit, withdraw, getBalance and setBalance are synchronized operations – that is, their effect on the account balance is atomic.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
•
13.2.1 Concurrency control
Example of the lost update problem;
In both cases we want to increase the amount of B by 10%. The final value expected: 242$.
A,B,C are bank accounts
Initial balance 100$, 200$ and 300$ respectively
Transaction T transfers an amount from account A to account B Transaction U transfers an amount from account C to account B
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
13.2.1 Concurrency control . . .
Example of the lost update problem . . .
It these two transactions run concurrently we obtain 240$ incorrect.
Both transactions have read the old value before either write the new value.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Figure 13.5
The lost update problem
Transaction T:
Transaction U:
balance = b.getBalance(); b.setBalance(balance*1.1); a.withdraw(balance/10)
balance = b.getBalance(); b.setBalance(balance*1.1); c.withdraw(balance/10)
balance = b.getBalance();
$200
b.setBalance(balance*1.1); a.withdraw(balance/10)
$220 $80
balance = b.getBalance(); $200
b.setBalance(balance*1.1);
$220
c.withdraw(balance/10)
$280
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
The lost update problem
the net effect should be to increase B by 10% twice – 200, 220, 242.
Transaction T:
but it only gets to 220. T’s update is lost. Transaction U:
balance = b.getBalance(); b.setBalance(balance*1.1); a.withdraw(balance/10)
balance = b.getBalance(); b.setBalance(balance*1.1); c.withdraw(balance/10)
balance = b.getBalance();
$200
b.setBalance(balance*1.1); a.withdraw(balance/10)
$220 $80
the initial balances of accounts A, B, C are $100, $200. $300 both transfer transactions increase B’s balance by 10%
balance = b.getBalance(); $200
b.setBalance(balance*1.1);
$220
c.withdraw(balance/10)
$280
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
•
13.2.1 Concurrency control . . .
Inconsistent retrievals:
In this example the transaction V transfer a sum from account A to account B and transaction W invokes the branchTotal to obtain the balance of all accounts
Initial balance are 200$.
Total obtained 300$ ( values are read at the wrong time).
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Figure 13.6
The inconsistent retrievals problem
TransactionV: a.withdraw(100) b.deposit(100)
Transaction W: aBranch.branchTotal()
a.withdraw(100);
$100
b.deposit(100)
$300
total = a.getBalance() $100 total = total+b.getBalance() $300 total = total+c.getBalance()
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
The inconsistent retrievals problem
we see an inconsistent retrieval because V has only done the withdraw part when W sums balances of A and B
TransactionV: a.withdraw(100) b.deposit(100)
Transaction W: aBranch.branchTotal()
a.withdraw(100);
$100
b.deposit(100)
$300
V transfers $100 from A to B while W calculates branch total (which should be $600)
total = a.getBalance() $100 total = total+b.getBalance() $300 total = total+c.getBalance()
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
•
Transaction . . .
Serial equivalence:
If each of the transactions produce the correct result then we can assume that if all the transactions arre performed in a certain order the correct result will be produced.
The use of serial equivalence as a critarion for correct concurrent execution prevents the occurrence of lost update and inconsistent retrievals.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Serial equivalence
The transactions are scheduled to avoid overlapping access to the accounts accessed by both of them
if each one of a set of transactions has the correct effect when done on its own
then if they are done one at a time in some order the effect will be correct
a serially equivalent interleaving is one in which the combined effect is the same as if the transactions had been done one at a time in some order
the same effect means
the read operations return the same values
the instance variables of the objects have the same values at the end
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
•
Serial equivalence
In the next figure an interleaving of two transactions are illustrated. Transaction T does all its operation on account B before U does.
Another interleaving of T and U that has this property is one in which transaction U complete its operation before T starts.
Next figure
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Figure 13.7
A serially equivalent interleaving of T and U
Transaction T:
Transaction U:
balance = b.getBalance() b.setBalance(balance*1.1) a.withdraw(balance/10)
balance = b.getBalance() b.setBalance(balance*1.1) c.withdraw(balance/10)
balance = b.getBalance() b.setBalance(balance*1.1)
$200 $220
a.withdraw(balance/10)
$80
balance = b.getBalance() $220 b.setBalance(balance*1.1) $242
c.withdraw(balance/10) $278
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
A serially equivalent interleaving of T and U
(lost updates cured)
their access to B is serial, the other part can overlap
Transaction T:
balance = b.getBalance()
Transaction U:
balance = b.getBalance()
b.setBalance(balance*1.1) a.withdraw(balance/10)
b.setBalance(balance*1.1) c.withdraw(balance/10)
balance = b.getBalance() b.setBalance(balance*1.1)
$200 $220
a.withdraw(balance/10)
$80
c.withdraw(balance/10) $278 if one of T and U runs before the other, they can’t get a lost update,
the same is true if they are run in a serially equivalent ordering
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
•
balance = b.getBalance() $220 b.setBalance(balance*1.1) $242
Serial equivalence and the iniconsistent retrievals problem.
This kind of problem can occur when a retireval transaction runs concurrently with an update transaction.
It cannot occur if the retrieval transaction is performed before or after the update transaction.
A serially equivalent interleaving of a retireval transaction and an update transaction wil prevent inconsistent retrievals occuring.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Figure 13.8
A serially equivalent interleaving of V and W
Transaction V: a.withdraw(100);
Transaction W: aBranch.branchTotal()
b.deposit(100)
a.withdraw(100); b.deposit(100)
$100 $300
total = a.getBalance()
$100 $400
total = total+b.getBalance()
total = total+c.getBalance() …
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
A serially equivalent interleaving of V and W (inconsistent retrievals cured)
Transaction V: a.withdraw(100);
we could overlap the first line of W with the second line of V Transaction W:
b.deposit(100)
aBranch.branchTotal()
a.withdraw(100); b.deposit(100)
$100 $300
if W is run before or after V, the problem will not occur
therefore it will not occur in a serially equivalent ordering of V and W the illustration is serial, but it need not be
total = a.getBalance()
$100 $400
total = total+b.getBalance()
total = total+c.getBalance() …
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
•
Conflicting operations
When the result of a pair of operations depends on the order of the operation we say that the pair of operations conflicts.
In the next example we use a pair of operation read and write.
The effect of an operation refers to the value of an object set by a
write operation and the result returned by a read operation.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Figure 13.9
Read and write operation conflict rules
Operations of different Conflict transactions
Reason
read read No read write Yes
Because the effect of a pair of read operations does not depend on the order in which they are executed
Because the effect of a read and a write operation depends on the order of their execution
write write Yes
Because the effect of a pair of write operations depends on the order of their execution
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Read and write operation conflict rules Operations of different Conflict
Reason
transactions
read read No
Because the effect of a pair of read operations does not depend on the order in which they are executed
Because the effect of a read and a write operation depends on the order of their execution
read write Yes write write Yes
Because the effect of a pair of write operations depends on the order of their execution
Conflicting operations
a pair of operations conflicts if their combined effect depends on the order in which they were performed
e.g. read and write (whose effects are the result returned by read and the value set by write)
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
•
Non-serially equivalent interleaving of operations
Serially equivalent:
For two transactions to be serially equivalent it is necessary and sufficient that all pairs of conflicting operations of the two transactions be executed in the same order at all of the objects they both access.
Now consider the following example
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Non-serially equivalent interleaving of operations
T: x = read(i) ; write( I, 10); write (j, 20);
U: y =read(j) ; write (j, 30); z = read(i);
Now look at the interleaving of their executions
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Figure 13.10
A non-serially equivalent interleaving of operations of transactions T and U
Transaction T: x = read(i)
Transaction U: y = read(j)
write(i, 10) write(j, 20)
write(j, 30) z = read (i)
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Serial equivalence
defined in terms of conflicting operations
For two transactions to be serially equivalent, it is necessary and sufficient that all pairs of conflicting operations of the two transactions be executed in the same order at all of the objects they both access
Consider
T: x = read(i); write(i, 10); write(j, 20); U: y = read(j); write(j, 30); z = read (i);
–serial equivalence requires that either
T accesses i before U and T accesses j before U. or U accesses i before T and U accesses j before T.
Serial equivalence is used as a criterion for designing concurrency control schemes
Which of their operations conflict?
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
•
T and U access i and j
A non-serially equivalent interleaving of operations of transactions T and U
Transaction T: x = read(i)
Transaction U: y = read(j)
write(i, 10) write(j, 20)
write(j, 30) z = read (i)
Each transaction’s access to i and j is serialised w.r.t one another, but T makes all accesses to i before U does
U makes all accesses to j before T does
therefore this interleaving is not serially equivalent
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
•
Non-serially equivalent interleaving of operations
Remark on serial equivalence:
Serial equivalence is used as a criterion for the derivation of
concurrency control protocols.
These protocols attemp to serialize transactions in their access to objects.
Three alternatives have been developed
Optimistic concurrency control Locking Timestamp
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
13.2.2 Recoverability from aborts
We remember that servers must record the effects of all committed transactions and none of the effects of aborted ones.
Servers must make sure that if a transaction abort that transaction must not affect any other concurrent transaction.
Two problems
Dirty reads and Premature writes.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Recoverability from aborts (12.2.3)
if a transaction aborts, the server must make sure that other concurrent transactions do not see any of its effects
we study two problems:
‘dirty reads’
an interaction between a read operation in one transaction and an earlier write operation on the same object (by a transaction that then aborts)
a transaction that committed with a ‘dirty read’ is not recoverable ‘premature writes’
interactions between write operations on the same object by different transactions, one of which aborts
(getBalance is a read operation and setBalance a write operation)
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
•
13.2.2 Recoverability from aborts . . .
Dirty reads:
We recall that the isolation property of a transaction requires that a given
transaction does not see the uncommitted state of other transactions.
The dirty read problem is caused by an interaction between a read operation in one transaction and an earlier write operation in another transaction on the same object.
See next figure
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Figure 13.11
A dirty read when transaction T aborts
Transaction T: a.getBalance()
Transaction U: a.getBalance()
a.setBalance(balance + 10)
a.setBalance(balance + 20)
balance = a.getBalance() a.setBalance(balance + 10)
$100 $110
abort transaction
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
balance = a.getBalance() $110 a.setBalance(balance + 20) $130
commit transaction
13.2.2 Recoverability from aborts . . .
The two previous transactions are serially equivalent.
Now if T aborts.
U sees a value that never existed and the transaction is committed
IT CANNOT BE UNDONE
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
A dirty read when transaction T aborts Transaction T:
What is the problem?
a.getBalance() a.setBalance(balance + 10)
Transaction U: a.getBalance()
balance = a.getBalance() $100 a.setBalance(balance + 10) $110
U reads A’s balance (which was set by T) and then commits
T subsequently aborts. abort transaction
commit transaction
U has performed a dirty read U has committed, so it cannot be undone
These executions are serially equivalent
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
•
a.setBalance(balance + 20)
balance = a.getBalance() $110 a.setBalance(balance + 20) $130
13.2.2 Recoverability from aborts . . .
HOW CAN WE SOLVE THIS PROBLEM.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Recoverability of transactions
If a transaction (like U) commits after seeing the effects of a transaction that subsequently aborted, it is not recoverable
For recoverability:
A commit is delayed until after the commitment of any other transaction whose state has been observed
e.g. U waits until T commits or aborts if T aborts then U must also abort
So what is the potential problem?
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
•
Cascading abort
In the figure 13.11, we suppose transaction U delays committing until after T aborts. No problem but T must abort as well. Now we have a problem.
Suppose that S is waiting for T to commit before comitting. Now T abort S must abort We have a cascading aborts
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Cascading aborts
For recovability – delay commits
Suppose that U delays committing until after T aborts.
then, U must abort as well.
if any other transactions have seen the effects due to U, they too must be aborted.
the aborting of these latter transactions may cause still further transactions to be aborted.
Such situations are called cascading aborts.
To avoid cascading aborts
transactions are only allowed to read objects written by committed transactions.
to ensure this, any read operation must be delayed until other transactions that applied a write operation to the same object have committed or aborted.
e.g. U waits to perform getBalance until T commits or aborts
Avoidance of cascading aborts is a stronger condition than recoverability
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
•
Premature Writes
In this case we are considering two write operations on the same object by two different transactions.
The next figure illustrate the situation: two setBalance transactions on the same account A.
Before the transaction Account A is at 100$
The two transactions are serially equivalent with T setting the balance at 105$ and U setting the balance at 110$.
If U aborts and T commits the balance should be 105$
Here are the transactions
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Figure 13.12
Overwriting uncommitted values
Transaction T: a.setBalance(105)
Transaction U: a.setBalance(110)
a.setBalance(105)
$100 $105
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design © Addison-Wesley Publishers 2005
Edn. 4
a.setBalance(110)
$110
Premature Writes . . .
Suppose U commits and then T aborts. In this case the balance should be 110$. But:
If the image before is written we get 100$. WRONG answer.
To ensure correct results in a recovery scheme that uses before images write operations must be delayed until earlier transactions that updated the same object have either committed or aborted.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Premature writes – overwriting uncommitted values
Transaction T: a.setBalance(105)
before T and U the balance of A was $100
Transaction U: a.setBalance(110)
serially equivalent executions of T and U
a.setBalance(105)
$100 $105
interaction between write operations when a transaction aborts
a.setBalance(110) $110 some database systems keep ‘before images’ and restore them
after aborts.
–e.g. $100 is before image of T’s write, $105 is before image of U’s write
–if U aborts we get the correct balance of $105,
–But if U commits and then T aborts, we get $100 instead of $110
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
•
Strict executions of transactions
In general it is required that transactions delay both their read and write operations to avoid;
Dirty reads and premature writes.
The execution of these transactions are called strict.
The strict execution of transaction enforces the property of isolation
More on the same subject
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Strict executions of transactions
Curing premature writes:
⌧if a recovery scheme uses before images
• writeoperationsmustbedelayeduntilearliertransactionsthat updated the same objects have either committed or aborted
Strict executions of transactions
to avoid both ‘dirty reads’ and ‘premature writes’.
⌧delay both read and write operations
executions of transactions are called strict if both read and write operations on an object are delayed until all transactions that previously wrote that object have either committed or aborted.
the strict execution of transactions enforces the desired property of isolation Tentative versions are used during progress of a transaction
objects in tentative versions are stored in volatile memory
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
•
Tentative versions
As said:
To recover from an aborted transactions the server must be able to remove any updates of objects that have been updated by transactions that have not been completed.
Therefore all updates operations performed during a transaction are done in tentative versions in volatile memory.
Each transaction has its own private set of tentative versions.
The tentative versions are transferred to the objects only when the transactions
commits.
At that time it is in permanent storage.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
13.3 Nested transactions
In this model we allowed transaction made of other transactions. Many transactions may be started from within a transaction.
The outemost transaction is called the top-level
The other are called subtransactions,
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Figure 13.13 Nested transactions
T1 :
openSubTransaction
T1 = openSubTransaction openSubTransaction
T2 :
T2 = openSubTransaction commit
T 11
:
T : 12
prov. commit T
21 :
abort T211 : prov. commit
prov. commit
prov. commit
T :top-leveltransaction
Instructor’s Guide for Coulouris, Dollimore and Kindberg
© Addison-Wesley Publishers 2005
Distributed Systems: Concepts and Design Edn. 4
openSubTransaction
openSubTransaction
prov.commit
Nested transactions
T1 :
openSubTransaction
T2 :
T abort
T 11
:
T : 12
prov. commit prov. commit
21 :
prov. commit
openSubTransaction
T211 : prov. commit
T1 = openSubTransaction openSubTransaction
T2 = openSubTransaction commit
transactions may be composed of other transactions
several transactions may be started from within a transaction
T :top-leveltransaction
we have a top-level transaction and subtransactions which may have their own subtransactions
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
•
openSubTransaction
prov.commit
13.3 Nested transactions . . .
In the previous case we talk about flat transactions: open –commit or abort. Everything is at the same level.
It is important to remember that we never commit or abort part of it.
Why Nested transactions
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Nested transactions . . .
The main advantages are:
This means you can run these concurrent transactions on different servers in parallel.
More on parallel computing. Not here unfortunately not enough time. Subtransactions can commit or abort independently.
Subtransactions at one level and its descendant may run concurrently with other subtransactions at the same level.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Nested transactions (12.3)
To a parent, a subtransaction is atomic with respect to failures and concurrent access
transactions at the same level (e.g. T1 and T2) can run concurrently but access to common objects is serialised
a subtransaction can fail independently of its parent and other subtransactions when it aborts, its parent decides what to do, e.g. start another subtransaction or give
up
The CORBA transaction service supports both flat and nested transactions
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
•
Advantages of nested transactions (over flat ones)
Subtransactions may run concurrently with other subtransactions at the same level.
this allows additional concurrency in a transaction.
when subtransactions run in different servers, they can work in parallel.
⌧e.g. consider the branchTotal operation
⌧it can be implemented by invoking getBalance at every account in the branch.
• these can be done in parallel when the branches have different servers
Subtransactions can commit or abort independently.
this is potentially more robust
a parent can decide on different actions according to whether a subtransaction has aborted or not
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
•
Commitment of nested transactions
A transaction may commit or abort only after its child transactions have completed.
A subtransaction decides independently to commit provisionally or to abort. Its decision to
abort is final.
When a parent aborts, all of its subtransactions are aborted.
When a subtransaction aborts, the parent can decide whether to abort or not.
If the top-level transaction commits, then all of the subtransactions that have provisionally committed can commit too, provided that none of their ancestors has aborted.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
•
Summary on transactions
We consider only transactions at a single server, they are: atomic in the presence of concurrent transactions
which can be achieved by serially equivalent executions
atomic in the presence of server crashes
they save committed state in permanent storage (recovery Ch.13) they use strict executions to allow for aborts
they use tentative versions to allow for commit/abort
nested transactions are structured from sub-transactions they allow concurrent execution of sub-transactions
they allow independent recovery of sub-transactions
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
•
13.4 Locks
Introduction: We have seen that transactions must be scheduled is such a way that their effect on share data is rerially equivalent.
The next figure illustrate how serial equivalence can be achieved with some concurrency.
The important point to remember is the fact that transaction T complete its access to account B before U starts accessing it.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Figure 13.7
A serially equivalent interleaving of T and U
Transaction T:
Transaction U:
balance = b.getBalance() b.setBalance(balance*1.1) a.withdraw(balance/10)
balance = b.getBalance() b.setBalance(balance*1.1) c.withdraw(balance/10)
balance = b.getBalance() b.setBalance(balance*1.1)
$200 $220
a.withdraw(balance/10)
$80
balance = b.getBalance() $220 b.setBalance(balance*1.1) $242
c.withdraw(balance/10) $278
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Locks …
A simple example of a serializing mechanism is the use of exclusive lock.
In this scheme the server attempts to lock any object that is about to be used by
any operation of a client operation.
If a client request access to an object already lock due to another transaction then the request is suspended until the object is unlocked.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Figure 13.14
Transactions T and U with exclusive locks
Transaction T:
balance = b.getBalance()
Transaction U:
balance = b.getBalance()
b.setBalance(bal*1.1) a.withdraw(bal/10)
b.setBalance(bal*1.1) c.withdraw(bal/10)
Operations
Locks lock B
Operations
Locks
openTransaction
bal = b.getBalance()
b.setBalance(bal*1.1) a.withdraw(bal/10)
lockA unlock A, B
openTransaction bal= b.getBalance()
waitsforT’s lock on B
closeTransaction
When transaction T is about to use account B it locks it
lock B b.setBalance(bal*1.1)
c.withdraw(bal/10) closeTransaction
lock C unlock B, C
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Locks. . .
We start here with the balances on account A, B and C not locked. Next U wants to use B but it is locked then it has to wait.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Figure 13.14
Transactions T and U with exclusive locks
Transaction T:
balance = b.getBalance()
Transaction U:
balance = b.getBalance()
b.setBalance(bal*1.1) a.withdraw(bal/10)
b.setBalance(bal*1.1) c.withdraw(bal/10)
Operations
Locks lock B
Operations
Locks
openTransaction
bal = b.getBalance()
b.setBalance(bal*1.1) a.withdraw(bal/10)
lockA unlock A, B
openTransaction bal= b.getBalance()
waitsforT’s lock on B
closeTransaction
When transaction U want to use B it is locked and it must wait because it is locked
lock B b.setBalance(bal*1.1)
c.withdraw(bal/10) closeTransaction
lock C unlock B, C
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Figure 13.14
Transactions T and U with exclusive locks
Transaction T:
balance = b.getBalance()
Transaction U:
balance = b.getBalance()
b.setBalance(bal*1.1) a.withdraw(bal/10)
b.setBalance(bal*1.1) c.withdraw(bal/10)
Operations
Locks lock B
Operations
Locks
openTransaction
bal = b.getBalance()
b.setBalance(bal*1.1) a.withdraw(bal/10)
lockA unlock A, B
openTransaction bal= b.getBalance()
waitsforT’s lock on B
closeTransaction
When transaction T is committed then it is unlocked and then U can access B
lock B b.setBalance(bal*1.1)
c.withdraw(bal/10) closeTransaction
lock C unlock B, C
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Two phases locking
Serial equivalence requires that all of a transaction’s access to an object be serialized with respect to access by other transactions.
All pairs of conflicting operations of two transactions should be executed in the same order.
To ensure this a transaction is not allowed to any new locks after it has released a lock
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
More on locks .. .
Two-phase lock
The first phase is a growing phase: during that phase the transaction acquired
The second phase is a shrinking phase: during that phase the locks are
released.
Strict two-phase locking
new locks
We have seen what is required to prevent dirty read and premature write.
Because transactions may abort strict executions are needed to prevent dirty reads and premature writes. Under this regime a transaction that need to read or write an object must be delayed until other transactions that wrote the same object have committed or aborted. To enforce this rule any locks applied during the progress of a transaction are held until the transaction commit or abort.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
More on locks .. .
Concurrency and granularity:
A server may contains a large number of objects. A transaction may access only a few of them. Therefore the granularity with which the concurrency control can be applied is very important.
You do not want to lock the whole bank to update a single account.
This means that the portion of an object that must be serialized must be as small as possible.
Concurrency control
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Concurrency Control and Granularity
Concurrency control are designed to deal with conflicts between operations in defferent transactions on the same object.
The conclicts rules for read and writes are givent in the next figure
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Read and write operation conflict rules Operations of different Conflict
Reason
transactions
read read No
Because the effect of a pair of read operations does not depend on the order in which they are executed
Because the effect of a read and a write operation depends on the order of their execution
read write Yes write write Yes
Because the effect of a pair of write operations depends on the order of their execution
Conflicting operations
a pair of operations conflicts if their combined effect depends on the order in which they were performed
e.g. read and write (whose effects are the result returned by read and the value set by write)
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
•
Concurrency Control and Granularity
A pair of reads do not conflict
Using exclusive lock for both read and write is a bit of a waste. Too strong.
Many readers-single writer scheme
Two types of locks are used Read locks and write locks
All transactions reading the same object share its read lock sometimes called shared locks.
Conflict rules dictate the management of the locks
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
More on locks and conflicting rules
If a transaction T has already performed a read operation on a given object the a concurrent transaction U must not write that object until T commits or abort.
If a transaction T has already performed a write operation on a particular object the a concurrent transaction U must not read or write that object until T commits or abort.
In order to enforce the first rule a request for a write lock on an object is delayed by a read lock that belongs to another transaction
To enforce the second rule a request for eithe a read lock or a write lock on an object is delayed by the presence of a wite lock belonging to another transaction.
Summary of the rules: next figure
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Figure 13.15 Lock compatibility
For one object Lock already set
Lock requested
read write
none read write
OK OK OK wait wait wait
On the left the locks already set for that object may be none. On the right you have the lock requested and the effect on the transaction.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Lost updates and locks
A lost update occurs when two transactions read a value of an object and the use it to recalculate a new value.
Lost updates are prevented by making later transactions delay their reads until the earlier ones have completed.
How to do that:
Each transaction set a read lock and promote it to a write lock before writing
the same object.
Problem
What do you do with a transaction that shares its read lock with another one?
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Lost updates and locks
In such a case you cannot promote your read lock to a write lock because you will create a conflict with the read locks held by the other transaction.
You use a write lock and wait to have the read lock of the other transaction released.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Lock promotion
Definition: Lock promotion refers to the conversion of a lock to a stronger lock.
You rarely demote a lock. why ?
The rules for the use of locks in a two-phase locking implementation are summarized in the next figure.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Figure 13.16
Use of locks in strict two-phase locking
1. When an operation accesses an object within a transaction:
(a) If the object is not already locked, it is locked and the operation proceeds.
(b) If the object has a conflicting lock set by another transaction, the
transaction must wait until it is unlocked.
(c) If the object has a non-conflicting lock set by another transaction, the
lock is shared and the operation proceeds.
(d) If the object has already been locked in the same transaction, the lock will
be promoted if necessary and the operation proceeds. (Where promotion
is prevented by a conflicting lock, rule (b) is used.)
2. When a transaction is committed or aborted, the server unlocks all objects it
locked for the transaction.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Corba and transaction
CORBA concurrency Control Service can be used to apply concurrency control on behalf on transactions
This service provide a means of associating a collection of locks (lockset) with a resource.
A lockset allows locks to be acquired or released.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Lock implementation
The granting of locks will be implemented by a separate object in the server called the lock manager.
Each lock is an instance of the class Lock and is associated with a particular object.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Figure 13.17 Lock class
public class Lock {
private Object object;
// the object being protected by the lock // the TIDs of current holders
// the current type
private Vector holders;
private LockType lockType;
public synchronized void acquire(TransID trans, LockType aLockType ){
} }
while(/*another transaction holds the lock in conflicing mode*/) { try {
wait();
}catch ( InterruptedException e){/*…*/ }
}
if(holders.isEmpty()) { // no TIDs hold lock
holders.addElement(trans);
lockType = aLockType;
} else if(/*another transaction holds the lock, share it*/ ) ){
if(/* this transaction not a holder*/) holders.addElement(trans); } else if (/* this transaction is a holder but needs a more exclusive lock*/)
lockType.promote();
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Continues on next slide
Figure 13.17 continued
public synchronized void release(TransID trans ){ holders.removeElement(trans);
// remove this holder
}
// set locktype to none
notifyAll(); }
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Lock implementation . . .
Each instance of Lock maintains the following information in its instance variables
The identifier of the locked object
The transaction identifiers of the transsactions that currently hold the lock A lock type
The methods of locks
The methods of Lock are synchronized so that the threads attempting to acquire or release a lock will not interfere with one another.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
The acquire method
The acquire method carries out the rules given if fig. 13.15 and 13.16
Its argument specify a transaction identifier and the type of lock required by that
transaction.
The method tests whether the request can be granted. For instance if another transaction holds the lock in a conflicting mode it involves wait.
The consequence of calling wait is that the caller thread will be suspended until a corresponding notify.
If no other transaction holds the lock just add the given transaction to the holders and set the type unless it is already a holder.
Else if another transaction holds the lock share it by adding the given transaction to the holders Else if this transaction is a holder but requesting a more exclusive lock promote the lock.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
The class Lock manager
All request to set locks and to release them on behalf of transactions are sent to an instance of LockManager.
The setLock method argument
The unLock method argument
The methods
specify the object that the given transaction wants the lock and the type of lock. It finds a lock for that object in its hashtable or if necessary creates one. Then it invokes the acquire method of that lock.
Specifies the transactions that is releasing its locks. It finds all of the locks in the hastable that have the given transactions as a holder.
For each one it call the release method.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4
© Addison-Wesley Publishers 2005
Figure 13.18 LockManager class
public class LockManager { private Hashtable theLocks;
public void setLock(Object object, TransID trans, LockType lockType){
}
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
}
}
foundLock.acquire(trans, lockType);
Lock foundLock; synchronized(this){
// find the lock associated with object
// if there isn’t one, create it and add to the hashtable
// synchronize this one because we want to remove all entries public synchronized void unLock(TransID trans) {
} }
while(e.hasMoreElements()){
Lock aLock = (Lock)(e.nextElement());
if(/* trans is a holder of this lock*/ ) aLock.release(trans);
Enumeration e = theLocks.elements();
Some remarks
When several threads wait on the same locked item, the semantic of the wait make sure that each transaction gets its turn.
What is the consequence for write transactions in the presence of a steady trickle of request for read lock.
Alternative implementation?
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Locking rules for nested transactions
The aim in this case of nested transactions is to serialize access to object so that:
1- Each set of nested transactions is a single entity that must be prevented from observing the partial effect of any other set of nested transactions
2- Each transaction within a set of nested transactions must be prevented from observing the partial effects of the other transactions in the set.
The implementation is such that these rules are enforced
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
13.4.1 Deadlocks
The use of locks can create situation where we have deadlocks. Example:
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Figure 13.19
Deadlock with write locks
Operations
Locks
Operations
Locks
a.deposit(100); b.withdraw(100)
write lock A
Transaction T
Transaction U
waits for U’s lock on B
waitsfor T’s lock on A
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design © Addison-Wesley Publishers 2005
Edn. 4
b.deposit(200) a.withdraw(200);
write lock B
Deadlocks . . .
Definition of deadlocks:
A deadlock is a state in which each member of a group of transaction
is waiting for some other member to release a lock.
A wait-for graph can be used to represent the situation. In such a graph the nodes represent the transaction and the edges the wait-for relationshiop between transactions.
There is an edge from node T to node U when transaction T is waiting for transaction U to release a lock.
Example
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Figure 13.20
The wait-for graph for Figure 13.19
TU
T
Held by
Waits for U
Waits for
B
Held by
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design © Addison-Wesley Publishers 2005
Edn. 4
A
Figure 13.21
A cycle in a wait-for graph
T
V
U
In this figure suppose that each transaction is waiting for the next transaction in the cycle. All these transactions are blocked. In fact all these transaction are deadlocked. Now suppose transaction U abort. It will release the lock on an object that V is waiting for and V will no longer be waiting for T.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Another example.
Now we consider three transactions T,U and V and all three share a read lock on object C.
Transaction W holds a write lock on object B on which transaction V is waiting to obtain a lock.
The transaction T and W the request a write lock on object C
We have a deadlock situation.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Figure 13.22
Another wait-for graph
T
U
C
Held by
T,U and V share a read lock on object C. transaction V is waiting to obtain a lock
Transaction W hold a write lock on object B on which
V
Held by
T Held by
W
W
Waits for
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Held by V
B U
Deadlock prevention
On simple solution to prevent deadlock is to lock all objects use by a transaction when it starts.
Question : Is it a good solution ?
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Upgrade locks and Deadlock detection
CORBA Concurrency Control Service introduces a third type of lock. This type of lock is called upgrade.
Deadlocks may be detected by finding cycles in the wait-for graph.
Having detected a cycle, a transaction must be selected for abortion to break the cycle.
How to resolve deadlocks: Timeouts
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Figure 13.23
Resolution of the deadlock in Figure 13.19
Operations
Locks
Operations
Locks
a.deposit(100); b.withdraw(100)
write lock A waits for U’s
b.deposit(200) a.withdraw(200);
write lock B waits for T’s
Transaction T
Transaction U
lock on B (timeout elapses)
lock on A
T’s lock on A becomes vulnerable, unlock A, abort T
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design © Addison-Wesley Publishers 2005
Edn. 4
a.withdraw(200);
write locks A unlock A, B
Timeouts to resolve deadlocks
Each lock is given a limited period in which it is invulnerable.
After this period the lock becomes vulnerable.
Provided that no other transaction is competing for the object that is locked, an object with a vulnerable lock remains locked.
If any other transaction is waiting to access the object protected by a vulnerable lock, the lock is broken and the waiting transaction resumes.
Normally the transaction with the broken lock aborts.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Increasing concurrency in locking schemes
The locking rules are based on the conflicts between read and write operations and the granularity at which they are applied is as small as possible.
There is still room to increase the concurrency. Two approaches are used :
Hierarchic locks: mixed-granularity locks are used
Two –version locking: the setting of exclusive locks is delayed until a transaction commits
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Two-version locking
One transaction write a tentative version of objects while other transactions read from the committed version of the same object.
Read operation wait only if another transaction is committing the same object This schem allow more concurrency than read-write locks but…
Writing transaction may have to wait or even risk rejection when trying to commit. The transaction will not be able to commit if other transactions have read lock on the same object.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Figure 13.24
Lock compatibility (read, write and commit locks)
For one object
Lock to be set
read write commit
Lock already set none
read OK
OK wait wait
wait
write OK commit wait
OK OK OK
When the transaction coordinator receives a request to commit a transaction it attempts to convert all that transaction’s write locks to commit locks. If any of the objects have outstanding read locks the transaction must wait until the transactions that set these locks have completed and the locks released.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Hierarchic locks
The idea behind this scheme is the fact that the granularity suitable for one operation is not appropriate for another operation.
Example: operation on a single bank account and an operation of the branch like balance of the branch that will require a lock on all accounts.
To reduce locking overhead it would be useful to allow locks of mixed granularity to coexist.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Hierarchic locks . . .
At each level the setting of a parent lock as the same effect as setting all the equivalent child locks. This reduce the number of locks to be set.
Example: Agenda Month week day period during the day.
In this scheme each node in the hierarchy can be locked giving the owner of
lock explicit access to the node an implicit access to its children
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Figure 13.25
Lock hierarchy for the banking example
ABC
Account
Branch
The branchTotal operation requests a read lock on the branch which implicitly sets read locks on all the accounts. A deposit operation needs to set a write lock on a balance, but first it attemps to set an intention to write lock on the branch. These rules prevent these operations to run concurrently.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Figure 13.26
Lock hierarchy for a diary
Week
Monday Tuesday Wednesday Thursday Friday
time slots 9:00–10:00 10:00–11:00 11:00–12:00 12:00–13:00 13:00–14:00 14:00–15:00 15:00–16:00
The mixed granularity of locks could allow each transaction to lock a portion whose size is chosen according to its need.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Hierarchic locks . . .
The compatibility tables and the rules form promoting locks are more complex. The rules are illustrated in the next table.
Remark
CORBA Concurrency Control Service supports variable granularity locking with intention to read and intention to write lock types
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Figure 13.27
Lock compatibility table for hierarchic locks
Lock already set
none read write I-read I-write
OK OK OK OK OK wait OK wait wait wait wait wait
For one object
Lock to be set
read write I-read I-write
Instructor’s Guide for Coulouris, Dollimore and Kindberg
© Addison-Wesley Publishers 2005
OK wait OK wait wait OK
OK OK
Distributed Systems: Concepts and Design
Edn. 4
13.5 Optimistic concurrency control
Locking has desadvantages
Lock maintenance represents an overhead that is not present in systems that
do not support concurrent access to shared data.
The use of locks can result in deadlock. Deadlock prevention reduces concurrency severely.
To avoid cascading aborts locks cannot be released until the end of the transaction . This may also reduce the potential of concurrency.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
13.5 Optimistic concurrency control . .
The alternative approach is based on the observation that most of the time, the likelihood of two client transaction accessing the same object is low.
Transaction are allowed to proceed as though there were no possibility of conflict until the client completes its task and issues a closeTransaction request.
When a conflict arises the transaction is generally aborted and need to be restarted.
The different phases of the Transactions
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
13.5 Optimistic concurrency control . . .
Each transactions has the following phases:
Working Phase –
Validation phase –
If the validation is successful then the transaction commit
During the working phase each transaction has a tentative version of the objects that it updates. This is the most recent version that has been committed.
When the closeTransaction request is received the transaction is validated to establish whether or not its operation on objects conflicts with operation of other transactions on the same object.
If the validation fails some form of conflict resolution scheme may be used. Some transaction will have to be aborted.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
13.5 Optimistic concurrency control . . .
Each transactions has the following phases . . . Update phase –
If a transaction is validated all of the changes recorded in its tentative versions are made permanent.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
More on the validation of transactions. . .
Validation uses read-write conflict rules to ensure that the scheduling of a particular transaction is serially equivalent with respect to all other overlapping transactions
To help in this process each transaction is given a transaction number which is an integer, allowing ordering of the transaction in time.
The validation test on transaction Tv is based on conflicts between operations in pairs of transaction Ti and Tv. For transaction Tv to be serializable with respect to an overlapping transaction Ti their operation must conform to the following rules.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Table on page 547
Serializability of transaction T with respect to transaction Ti
Tv Ti Rule
write read read write
1. Ti must not read objects written by Tv 2. Tv must not read objects written by Ti
write write
3. Ti must not write objects written by Tv and Tv must not write objects written by Ti
The validation of a transaction must ensure that the rules 1 and 2 are obeyed by testing for overlaps between the objects of pairs of transactions Tv and Ti. There are two forms of validation backward and forward.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Backward validation
All the read operations of earlier overlapping transactions were performed before the validation of Tv started.
They cannot be affected by the writes of the current transaction (rule 1 is satisfied)
Rule 1- Ti must not read objects written by Tv
The validation of transaction Tv checks whether its read set overlap with any of the writes sets of earlier overlapping transactions Ti (rule 2) If there is any overlap the transaction fails.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Figure 13.28
Validation of transactions
T1
T2
Earlier committed transactions
Later active transactions
active1
Working
Validation Update
Transaction being validated
T
T3
v
Instructor’s Guide for Coulouris, Dollimore and Kindberg
© Addison-Wesley Publishers 2005
active2
Distributed Systems: Concepts and Design
Edn. 4
Figure 13.28
Validation of transactions
T1
T2
Earlier committed transactions
Later active transactions
active1
Working
Validation Update
Transaction being validated
T
T3
v
active2
Time increases from left to right. The earlier committed transactions are T1, T2 and T3. T1 commits before Tv started. T2 and T3 committed before Tv finished its working phase. Start Tn +1 = T2 and FinishTn = T3.
In backwawrd validation the read set of Tv must be compared with the write sets of T2 and T3.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Forward validations
In forward validation of the transaction Tv, the write set of Tv is compared with the read sets of all overlapping active transactions.
The overlapping active transactions are those that are still in their working phase (rule 1).
Rule 2 is automatically fulfiled because the active transactions do not write until after Tv has completed.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Page 547-548
Validation of Transactions
Backward validation of transaction Tv boolean valid = true;
for (int Ti = startTn+1; Ti <= finishTn; Ti++){
if (read set of Tv intersects write set of Ti) valid = false; }
Forward validation of transaction Tv boolean valid = true;
for (int Tid = active1; Tid <= activeN; Tid++){
if (write set of Tv intersects read set of Tid) valid = false; }
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
13.6 Timestamp ordering
Introduction - In concurrency control schemes based on timestamp ordering each operation in a transaction is validated when it is carried out.
If the operation cannot be validated the transaction is aborted
immediatley. starts.
Each transaction is assigned a unique timestamp value when it
The basic timestamp ordering rule is based on operation conflicts
A transaction’s request to write an object is valid only if that object was last read and written by earlier transactions. A transaction’s request to read an object is valid only if that object was last written by an earlier transaction.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
13.6 Timestamp ordering . . .
The approach described here follows the method adopted in the SDD-1 system.
2- Every object has a write timestamp and a set of tentative versions each of which has a write timestamp associated with it. And a set of read timestamp.
3- The write timestamps of the committed object is earlier than that of any of its tentative versions and the set of read timestamps can be represented by its maximum member.
1- The write operations are recorded in tentative versions of objects and are invisible to other transactions until a closeTransaction request is issued and the transaction is committed.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
13.6 Timestamp ordering . . .
The approach described here follows the method adopted in the SDD-1 system...
5 - A transaction read operation is directed to the version with the maximum write timestamp less than the transaction timestamp.
4 - Whenever a transaction’s write operation on an object is accepted the server creates a new tentative version of the object with write timestamp with write timestamp set to the transaction timestamp.
6 - Whenever a transaction read operation on an objecct is accepted the timestamp of the transaciton is added to its set of read timestamps.
7- when a transaction is committed the values of the tentative versions become the values of the objects and the timestamps of the tentative verisons become the timestamps of the corresponding objects.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Conflict rules.
A request by the current transaction Tc can conflict with previous operations done by other transacitons Ti whose timestamps indicate that they should be later than Tc.
The rules are described in the next figure.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Figure 13.29
Operation conflicts for timestamp ordering
Rule Tc Ti 1. write read
Tc must not write an object that has been read by any Ti where Ti >Tc this requires that Tc ≥ the maximum read timestamp of the object.
2. write write
3. read write
Tc must not write an object that has been written by any Ti whereTi >Tc this requires that Tc > write timestamp of the committed object.
Tc must not read an object that has been written by any Ti whereTi >Tc this requires that Tc > write timestamp of the committed object.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Timestamp ordering write rule
Combining rule 1 and 2 the following rule to decide whether or not to accept a write operation requested by transaction Tc on object D.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Page 551
Timestamp ordering write rule
if (Tc ≥ maximum read timestamp on D &&
Tc > write timestamp on committed version of D)
perform write operation on tentative version of D with write timestamp Tc else /* write is too late */
Abort transaction Tc
If a tentative version with write timestamp Tc already exists the write operation is addressed to it otherwise a new tentative version is created and given write timestamp Tc.
Note that any write that arrives too late is aborted.
Too late in the sense that a transaction with a later timestamp has already read or written the object
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Timestamp ordering write rule . . .
In the next figure we have the action of a write operation by transaction T3 in cases where T3 ≥ maximum read timestamp on the object.
In the cases a and c T3> write timestamp on the committed version of the object.
A tentative version with write timestamp T3 is inserted at the ap propriate place in the list of tentative versions ordered by their transaction timestamps.
In case d T3< write timestamp on the committed version of the object and the transaction is aborted.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Figure 13.30
Write operations and timestamps
(a) T3 write
(b) T3 write
Before T2
Before After
T1 T1
T2 Key: Ti
After
T2 T3
T2 T3
Committed Ti
(c) T3 write
(d)T3 write
object produced
Before After
T1 T4
T1 T3 T4
T4 After T4
T1
let Dselected be the version of D with the maximum write timestamp ≤ Tc if (Dselected is committed)
perform read operation on the version Dselected else
Wait until the transaction that made version Dselected commits or aborts then reapply the read rule
} else
Abort transaction Tc
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Remark
If transaction Tc has already written its own version of the object this will be used.
A read operation that arrives too early waits for the earlier transaction to complete.
if the earlier transaction commits then Tc will read from its committed version. If it aborts then Tc will repeat the read rule ( and select the previous version) This prevents dirty reads.
A read operation that arrives too late will be aborted. It is too late in the sense that a transaction with a later timestamp has already written the object.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
An example
In the example we consider the action of a read operation by transaction T3.
In each case a version whose write timestamp is less than or equal to T3 is
selected.
In cases a and b the read operation is directed to a committed version – In a it is the only version and in b there is a tentative version belonging to a later transaction
In case c the read operation is directed to a tentative version and must wait until the transaction that made it commits or aborts.
In case d there is no suitable version to read and transaction T3 is aobrted.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Figure 13.31
Read operations and timestamps
(a) T3 read
(b) T3 read
T2 Selected
read proceeds
T2 T4
read proceeds
Ti
(c) T3 read
Tentative
T1 T2
read waits Selected
T 4
Transaction aborts
object produced
by transaction Ti
(with write timestamp Ti)
Selected Time
Time
Committed
Time
Time
(d) T3 read
Ti
Instructor’s Guide for Coulouris, Dollimore and Kindberg
© Addison-Wesley Publishers 2005
Distributed Systems: Concepts and Design Edn. 4
T1 < T2 < T3 < T4
Key:
Remark
The timestamp ordering algorithm that we have described is a strict one
The arrangement to commit versions in order ensures that the execution of a transaction’s write on any object is delayed until all transactions that had previously written that object have committed or aborted.
It ensures strict execution of transactions. The timestamp ordering read rule delays a transaction read operation on any object until all transactions that had previously written that object have committed or aborted.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn. 4 © Addison-Wesley Publishers 2005
Back to the previous example : Two concurrent banking transactions
The columns headed A, B and C refer to information about accounts with those names.
Each account has an entry RTS that records the maximum read timestamps and an entry WTS that records the write timestamp of each version.
Timestamp of committed versions are represented in bold.
Initially all accounts have committed versions written by transaction S and the
set of read timestamp is empty.
Itisassumed S