Transaction and Concurrency Control

Transaction and Concurrency Control

Transactions and Nested Transactions

- Transaction is a sequence of requests to a server by clients that ensures all the objects to remain in consistent state.
- Atomic transaction is necessary when:
1. It must be free from interference by other operations.
2. Either all operations must be completed successfully or they must have no effect in case of server crash.
- A transaction is created and managed by a coordinator, which implements coordinator interface.

 

Operations:
     openTransaction() --> trans;
              //starts new transaction and delivers unique TID trans.
    closeTransaction(trans) --> (commit, abort);
            // commit return value indicates transaction has committed.
           // abort return valuue indicates transaction has aborted.
    abortTransaction(trans);
            //abort the transaction

 

---

Problems of Concurrent Transaction

1. Lost update problem:
- Assume initial banance of A,B and C be 100$, 200$ and 300$.

Transaction T:	Transaction U:
balance = b.getBalance();	balance = b.getBalance();
b.setBalance(balance*1.1);	b.setBalance(balance*1.1);
a.withdraw(balance/10);	c.withdraw(balance/10);
balance = b.getBalance(); //$200
	balance = b.getBalance(); //$200
	b.setBalance(balance*1.1); //$220
b.setBalance(balance*1.1); //$220
a.withdraw(balance/10); //$80
	c.withdraw(balance/10); //$280

 

2. Inconsistent Retrieval Problem:
- Initial balance of A and B be 200$ and 200$.

Transaction T:	Transaction U:
a.withdraw(100);	aBranch.branchTotal();
b.deposit(100);
a.withdraw(100); //$100	total = a.getBalance(); //$100
	total = total + b.getBalance(); //$300
b.deposit(100); //$300

 

---

Nested Transaction

- The transaction which is composed of other transactions as per the requirement is called nested transaction.
- The outermost transaction is called top level transaction and others are called sub-transactions.
- The sub-transactions at same level can run concurrently but their access to common objects is serialized.

---

Rules for commit

1. A transaction may commit or abort only after its child transactions have completed.
2. When a sub-transaction completes, it makes independent decision either to commit provisionally or to abort.
3. When a parent aborts, all of its sub-transactions are aborted.
4. When a sub-transaction aborts, parent can decide whether to abort or not.
5. If top-level commits, all the sub-transactions that have provisionally committed can commit if none of their ancestors has aborted.

---

Locks

- The use of exclusive locks helps to serialize access to the objects.
- The server attempts to lock any object that is about to be used by any operation of a client's transaction.
- If client requests access to locked object, it must wait.

 

Consider example of Tand U as before:

 

Transaction T: Transaction U:
Operations Locks Operations Locks
-------------------------------------------------------------------------------------------------
openTransaction
balance = b.getBalance(); Lock B
b.setBalance(balance*1.1); openTransaction
a.withdraw(balance/10); Lock A balance = b.getBalance(); Wait for T's lock on B

closeTransaction Unlock A,B
Lock B
b.setBalance(balance*1.1);
c.withdraw(balance/10); Lock C
closeTransaction Unlock B,C

 

- A transaction is not allowed any new locks after it has released a lock.
- First phase is growing phase and second phase is shrinking phase.

- For concurrent transaction reading or single transaction writing but not both; two locks are used as read lock and write lock

---

Lock Compatibility

 

			Lock Requested
		Read	Write
	None	Ok	Ok
Lock already set	Read	Ok	Wait
	Write	Wait	Wait

 

 

---

Deadlock

- The use of locks can lead to deadlock.
- The situation in which two transactions are waiting and each is dependent on the other to release a lock so as to resume is called deadlock.

Deadlock Prevention:
- Lock all the objects used by a transaction when it starts.

Deadlock Detection:
- A wait for graph is analyzed to detect deadlock by finding cycles.
- If deadlock is present, a transaction is selected for abortion.

---

Optimistic Concurrency Control

- Transactions are allowed to proceed as though there were no possibility of conflict with other clients until it completes its task and issues a closeTransaction request.
- If conflict arises, some transaction will be aborted and should be restarted by the client.
- Each transaction has three phases:
1. Working phase
2. Validation phase
3. Update phase

---

Working phase

-Each transaction get copy of most recently committed version of the object.
- Read operation is performed immediately.
- Write operation record new values as tentative values.
- A same object can have several tentative values.

---

Validation Phase

- When closeTransaction is received, the transaction is validated to confirm whether or not there is conflicts.
- On successful validation, transaction can commit.

---

Update Phase

- If transaction is validated, all the tentative values are made permanent.

---

Problems

- Starvation prevails.

---

Validation of Transaction

- Each transaction is assigned a transaction number when it enters validation phase.
- A transaction with number Ti precedes a transaction with number Tj if i < j.
- For transaction Tv to be serializable with respect to Ti, their operations must conform the rules as:
1. Tv - write and Ti - read
- Ti must not read objects written by Tv
2. Tv - read and Ti - write
- Tv must not read objects written by Ti
3. Tv - write and Ti - write
- Ti must not write objects written by Tv and vice versa.

---

Timestamp Ordering

- Each transactions's operation is validated when it is carried out.
- If operation can not be validated, the transaction is aborted.
- Each transaction is assigned a unique timestamp value when it starts.
- 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 earlier transactions.

---

Write Rule

 

if (Tc >= maximum read timestamp on D && Tc > write timestampon committed version of D ):
         perform write operation on tentative version of D with write time stamp Tc
else
         abort Tc

 

---

Read Rule

 

if (Ti write timestamp on committed version of D) {
           Let Dsel be version of D with max write timestamp <= Ti
           if (Dsel is committed)
                  perform read on Dsel
          else
                 wait or abort then reapply
}
else
         abort Ti

 

---

Comparison of Concurrency Control Methods

- Timestamp and lock use pessimistic approach.
- Time stamp is better than lock for read only transactions.
- Lock is better when operations are predominantly updates.
- Time stamp aborts transaction immediately.
- Locking makes the transaction wait.
- With optimistic, all transactions are allowed to proceed.

---

Introduction to Distributed Transaction

- Those transactions that access objects managed by multiple servers is called distributed transaction.
- It requires either all of the servers involved commit the transaction or all of them abort the transaction.
- One of the servers acts as a coordinator which ensure same outcome at all the servers.

---

Flat and Nested Distributed Transaction

- In flat transaction, a client makes requests to more than one server.
- It completes each of its requests before going on to next one, accessing server objects sequentially.

- In nested transaction, the top level open sub transactions; each of which can further open sub transactions.
- The sub transactions at same level run concurrently.

---

Atomic Commit Protocol

Two Phase Commit Protocol

- In first phase (voting phase)
1. The coordinator sends 'canCommit?' request to each participants in the transactions.
2. When participants receive 'canCommit?' request, it replies with Yes or No to the coordinator. Before voting Yes, it prepares to commit by saving objects in permanent storage. If the vote is No, the participants abort immediately.

- In second phase (completion phase)
1. The coordinator collects votes including its own vote. If all the votes are Yes, the coordinator sends 'doCommit' to each of the participants. Otherwise the coordinator sends 'doAbort to all the participants that voted Yes.
2. When participants receive 'doCommit' or 'doAbort', they act accordingly. If they receive 'doCommit' request, then they make 'haveCommitted' call as confirmation to the coordinator.