Transaction processing

Contents:

Definition
Sample TP program
ACID properties:

Atomicity
Consistency
Isolation
Durability

-Q&A: Why do we need TP ?

-TP manager :

- Recovery:

- Transaction Recovery:

- Commit

- Save point in the TX

RollBack

- Log on tape or disk ( Active log and archive log)

- Write ahead log-rule

Two–Phased Commit:

- System Recovery:

Global failure

- undo or redo list

- Check point record

Concurrency:

Typical three-Problems without concurrency

Lost update
Uncommitted dependency
Inconsistent analysis

Resolution to concurrency problem

- Locking

Exclusive locks

Shared locks

Locking protocol

Locking problem: Deadlock

Serializability

Two-phased locking

Isolation level

Intent locking

Transaction processing ( TP ):

Definition: Transaction processing is logical unit of work. It performs a set of database operations and transforms the DB from one consistent state to another consistent state.

1)_Single user System :

If you are the only user of your DB, then creating a TP would not make a whole lot of difference. Let’s say you write a TP that changes the Emp.Salary when SSN=111. You could have done one operation at a time. If you make a mistake( ssn=112) you can always go back and change it.

Multiple concurrent users System:

If you are buying a book from Amazon.com, even you are sending one request, it encapsulates many database operations and the system sees more than one request. Therefore, the system needs to know that those distinct operations are part of the same transaction. The BEGIN TRANSACTION, COMMIT AND ROLLBACK operations are provided for this purpose.

Sample Pseudocode of a TP:

BEGIN TRANSACTION /* declare the start of TP */

Update name /* subsequent operations */

Select ssn

Update salary

IF no error

THEN COMMIT /* normal termination */

ELSE ROLLBACK /* abnormal termination */

End IF

Sample TP in SQL:

ComputeInterest()

{ real interest_rate; /* declaration */

receive (interest_rate); /* monthly interest rate */

exec sql begin work; /* start the transaction */

exec sql UPDATE checking_accounts

SET account_balance =

account_balance*(1+interest_rate);

/* modify all accounts */

send ("done"); /* notify client */

exec sql commit work; /* declare victory */

return;

};

ACID properties: ( desired )

Atomicity: A transaction’s changes to the state are atomic: either all happens or none happens. This changes include database changes, messages and actions on transducers.

Consistency: A transaction is a correct transformation of the state. The actions taken as a group do not violate any of the integrity constraints associated with the state. TP preservers the DB consistency by transforming one consistent state to another consistence state. It does not necessarilly preserve consistency at all intermediate points.

Isolation: Even though transactions execute concurrently, it appears to each transaction T, that others executed either before T or after T. None of the other transactions can see T’s update until T commits its update. For any two dictinct transactions T1 and T2, T2 might see T1‘s update( after T1 commits) OR T1 might see T2‘s update( after T2 commits) but certainly not both. If both can see each other’s update then there will be a high interference and data will be over written and inconsistent.

Durability: Once a transaction commits successfully, the updates persist in the database, even if there is a subsequent system crash.

Why do we need TP ?

Let’s see what may happens if we don’t have TP system:

-Orders will be lost

-Accounts will not balance

-Credit cards will not be authorized

-Stores will run out of stock

-Reservations will not be honored

-ATM’s will refuse to dispense cash

-Your pizza will not be delivered

-Life will be sweet :-)

Transaction Manager :

The A and C of the ACID property say that our DB have to be consistent and transaction have to be atomic. In the real world systems are geographically distributed, heterogeneous ( HW and SW from many vendors), continuously available ( no scheduled downtime ) and have stringent response time requirements. There are too many variables and too many steps where things can go wrong. A transaction may make some updates and then, terminate abnormally at any step of the processing. We need to make sure that those updates made before failure are undone. A Transaction Manager just does that for us.

Transactions Manager (TM) is an extension of the OS that understands transactions and provides the Atomicity during TP. It is also called Transaction Processing Monitor or TP Monitor. In addition to many other tasks, TM must handle recovery and concurrency issues.

Recovery

Transaction Recovery: When TX fails before the normal COMMIT or ROLLBACK.

Commit :

Format: COMMIT [ WORK] [COMMENT text];

Example: COMMIT;

COMMIT WORK;

COMMIT COMMENT ‘ This is a comment’;

Signals successful end of termination
Saves all outstanding updates since the last COMMIT or ROLLBACK.
DB is in a consistent state and changes are persistent.
Release all the row and table locks
New changes are seen by other users or TX
Removers the savepoints issued since the last COMMIT or ROLLBACK

Savepoint of a Transaction: It corresponds to the end of a logical unit of work and beyond this point the DB should be in a consistent state. It is also called Commit Point or Synchpoint.

Save point: The Basic Idea

Consider the trip planning example:

BEGIN WORK
S1: book flight from San Francisco to Frankfurt

S2: book flight from Frankfurt to Milan, same day

S3: book flight from Milan to Pisa, same day
Problem: There is no way to get to Pisa from Millan the same day, except in a rental car. But you do not want to drive at night?

In that case, it would help if we could do a partial rollback rather than aborting the entire transaction.

Option#1: Rollback to the state S2, we would be back to Milan

Option#2: Rollback to the state S1, would get us back to Frankfurt, while still being in the same transaction.

Solving the reservation problem using Savepoints:

If we assume the savepoint mechanism, a solution to the travel agent’s problem might look like this:

Begin_Work();

book flight from San Francisco to Frankfurt

step1 := Save_Work(some_data);

book flight from Frankfurt to Milan, same day

step2 := Save_Work(some_data);

book flight from Milan to Pisa, same day

step3 := Save_Work(some_data);

if (problem) then { some_data := Rollback_Work(step1);

book flight from Frankfurt to Genoa;

step4 := Save_Work(some_data);

book train from Genoa to Viareggio;

}

Commit_Work();

Savepoint: Why is it good?

Savepoints can be used to structure a transaction into a sequence of partial executions that can be rolled back individually.

Because none of the actions a transaction has executed become "visible" before the end of the transaction, they can be revoked at any time.

Since a transaction must be prepared to roll back completely, a partial rollback does not add anything new, technically.

When a transaction rolls back to an internal savepoint, the actions that are undone appear like they had never happened - even to the transaction itself.

When an external error occurs, the entire transaction gets rolled back - independent of any savepoints.

RollBack

Format:

ROLLBACK [WORK] [TO [SAVEPOINT] savepoint_name];

Example:

ROLLBACK;

ROLLBACK WORK;

ROLLBACK TO begin_cleanup;

Signals unsuccessful end of termination
Erases all outstanding changes since the last COMMIT or ROLLBACK
Release all the row and table locks

Q&A: HOW DOES ROLLBACK WORK?

A transaction may do 3 updates and fail on the 4^th update. How does a TP Manager know the old values before update and which updates to be recovered?

The system maintains a Log or Journal that details all the updates.

Rollback Cont:

The log is kept on disk ( active log), so it is not affected by any type of failure except for disk or catastrophic failure. In addition, the log is periodically backed up on tape ( archive log) to guard against such catastrophic failure.

Type of entries in a log when T refers to a unique transaction-id.

[ start_tran, T]: records that T has started execution

[ write_item, T, X,old_value, new_value]: records T changed value of X from old_value to new_value.

[ read_item, T, X]: records that T has read the value of database item X

[ commit, T]: records that T has completed successfully.

[ abort, T]: records that T has been aborted

Two–Phase Commit:

It is very important elaboration of the basic commit/rollback concept. It important when the system is distributed, heterogeneous and the transaction interacts with multiple independent Resource Managers (RM). Even though the transaction interacts with multiple RMs, there is a single system-wide Global COMMIT (or ROLLBACK) which is handled by an additional system component called the Coordinator.

Resource Managers (RM): It has its own set of recoverable resources and logs. A database system is an example of RM.

Coordinator: It makes sure that all the resources managers commit or rollback the updates that they are responsible for in unison.

Example:We have a transaction running on a an IBM mainframe that updates both an IMS and a DB2 database. If a transaction fails, updates in both DB have to do ROLLEDBACK. Let’s say we have a successful transaction. Therefore, the system will send a global COMMIT. On receiving that COMMIT request, the Coordinator will go through the following two-phase process.

Phase-1:

Coordinator instructs the participants to "go either way" on the transaction
RMs forces the all log entries for the local resources out to its own physical log on disk
Now each RM has a permanent record of the work it did for the transaction
RM Sends back a "OK" signal it the force-write is successful. Sends ‘ Not OK’ otherwise

Phase-2:

- Upon receiving the replies from all RMs, coordinator forces an entry to its own physical log recording its decision regarding the transaction.

If all replies are OK then the decision is COMMIT, otherwise rollback.

Coordinator let each RM know about its decision

Each RM must Commit or rollback the transaction locally

Note: If the system fails at some point during the overall process, the restart procedure will look for the decision record in the Coordinator’s log. If it finds the decision, then the two-phase commit process can pick up where it left of. If the decision is not found, restart assumes the decision was rollback.

System Recovery:

A global failure affects all the transactions in progress during the failure. It has a system-wide impact. It falls into two categories:

System failure:

Affects all transactions in progress but do not damage the physical database

- example: power outage, network problem

Media Failure:

damage the DB or a portion of it and affects al least those transaction currently using that part of database
example: head crash on the disk, bad disk

System recovery Cont:

Key point during system failure: The content of the main memory buffer is lost and therefore, the precise state of the transaction during the failure is unknown.

Q&A: What should be done to the transaction that was not successfully done before the failure?

Undo or ROLLBACK them after the restart

Q&A: What should be done to the transaction that was successfully done before the failure but could not manage to transform the updates from database buffer to the physical database?

Redo them after the restart

Q&A: At the restart, how does the system know which transaction to undo and which to redo?

- Read the Checkpoint Record in the physical log

The recovery manager of the DBMS decide a certain interval when the system takes a checkpoint. This interval could be measured in time – say, every m minutes – or the number of commit transaction since the last checkpoint. Taking a checkpoint involves two steps:

Force-writing the contents of the database buffer out to the physical database.
Physically writing a checkpoint record out to the physical log. This checkpoint record lists all the transactions that were in progress at the time the checkpoint was taken.

[ Please refer to the class note for this figure]

Start with two lists of transaction, the UNDO list and the REDO list. UNDO list should have all the transaction at the latest checkpoint and REDO should be empty.

UNDO{ T2, T3, T4, T5} and REDO{ }

Search through the log starting from the checkpoint record

If a BEGIN TRANSACTION is found for transaction T, then add T to UNDO list

UNDO{ T2, T3, T4, T5} and REDO{ }

If a COMMIT log is found for transaction T, then move T from UNDO to REDO list

UNDO{ T3, T5} and REDO{ T2, T4 }

Once the system has both list, it starts backward (backward recovery) through the log undoing the transaction in UNDO list and then, works forward (forward recovery)again to redo the transaction in REDO list.

Concurrency:

The term concurrency refers to the fact that DBMS typically allows many transactions to access the same DB at the same time. In such a system, we need a concurrency control mechanism in order to provide some level of isolation for the interleaved Transactions and make sure that concurrent transactions interfere with each other at a low level.

In a concurrent system, we typically experience the following three concurrency problems.

The Lost Update problem:

This occurs when two transactions accessing the same database item have their operation interleaved in a way that makes the value of the item incorrect. If, at the beginning X=80, N=5 and M=4, then correct value of X after T1 and T2 transactions is 79 not 84.

[ Please refer to the class hand-out for this figure]

The Temporary Update ( Dirty Read) problem:

This occurs when one transaction T1 updates an item and then fails for some reason. The temporarily updated item is accessed by another transaction T2 before the value was changed back to the original value.

[ Please refer to the class hand-out for this figure]

The Incorrect Summary problem:

If one transaction is calculating an aggregate summary on a number of records while another transaction is updating some of these records, the aggregate function may calculate some values before they are updated and others after they are updated.

[ Please refer to the class hand-out for this figure]

Concurrency Cont:

Resolution to concurrency problem:

All the concurrency problems mentioned above can be solved by a concurrency control technique called Locking. After locking a record, the transaction have an assurance that the record will not change until it commits or rollbacks.

There are two types of locks:

Exclusive or X-locks:

It grant the holder exclusive access to that variable; if any other transaction tries to acquire any kind of lock on that variable, that transaction must wait until any and all locks on the variable have been released.

[ Please refer to the class hand-out for this figure]

Shared or S-locks:

These are good enough if only read access is required. This is because multiple S-locks may be acquired on the same variable at the same time. However, no other transaction may acquire a X-lock while at least one S-lock has been acquired. We WILL allow the sole holder of an S-lock to UPGRADE the lock to an X-lock.

[ Please refer to the class hand-out for this figure]

Data Access Protocol or Locking Protocol:

It lets you use the X-lock and S-lock to guarantee that the concurrency problems described above can not occur.

A transaction that wishes to receive a tuple must first get a S-lock on that tuple
A transaction that wishes to update a tuple must first get a X-lock on that tuple. If it is already holding a S-lock ( as it will in Retrieve, Update sequence), then it must promote that S-lock to X-lock.
If a lock request from transaction B is denied because it conflicts with the lock already held by A, transaction B will go into a wait state and wait until A release the lock.
X-lock is held until the end of the transaction (COMIT or ROLLBACK). So is S-lock

Now let’s revisit those three basic problems using locking protocol. Locking introduces its own problem DEADLOCK.

DEADLOCK: A situation in which two or more transaction are in simultaneously wait state, each of them waiting for one of the other to release a lock before it can proceed. It is desirable that the system detects the deadlock. In order to detect deadlock, detect a cycle in Wait-For-graph. Then choose the lowest cost victim and roll that back and free its lock. Some system do not detect deadlock and simply uses timeout and proceed again with the transactions.

Serializability

Serializibility is a generally accepted criterion of correctness for the execution of a given set of transactions.

The argument is : if (a) individual transaction is correct and (b) a set of transactions running one at a time in serial order is correct results in a consistent database state, then an interleaved execution of that set of transactions should also be correct and produce the same consistent database state.

Reffering to the 3 basic conn. Problems, we see that locking is one way to make execution serialized but it does not work always.

Terminology:

Schedule: Given a set of transactions, any execution of those transactions is called a Schedule.

Serial Schedule: If execution is one at a time in serial order then it is called Serial Schedule.

Interleaved Schedule: If execution is interleaved and non-serial then it is Interleaved Schedule.

Equivalent Schedule: Two schedules are called Equivalent if they are guaranteed to produce the same result, independent of the initial database state.

Serializability Cont:

Two schedules S1 and S2 involving the same set of transactions (A, B) might well produce different results. Let’s say X=10 and A =( Add 1 to X) and B=( Double X), then

For schedule S1(A,B): X= ((10+1) *2) = 22

For schedule S2(B,A): X= ((10*2) + 1) = 21

In order resolve this issue we need Two-Phase Locking protocol:

Two-Phase Locking theorem: If all transactions obey the Two-Phase Locking protocol, then all possible interleaved schedules are serializable.

Two-Phase Locking protocol:

Before operating on an object ( e.g. a tuple), a transaction must acquire a lock on that object
After releasing the lock, a transaction must never go on to acquire any more lock

Isolation level

Isolation level refers to the degree of interference that a given transaction is prepared to tolerate on the part of the concurrent transaction. The higher the isolation level is, the less the interference ( and concurrency). In order to guarantee serializability, we need the maximum isolation.

[ Please refer to the class hand-out for additional notes on Isolation Level]

Intent locking

So far we assumed that the unit for locking purpose is the tuple. Locking granularity says here is no reason why we can not put a lock on an individual field or on the entire table.

Trade off: the finer the granularity, the greater the concurrency and the larger the granularity, the fewer locks are required and less overhead as well.

If a transaction T request a lock on relvar R, how does the system know if there is already a lock on some tuples or not? Lock at relvar level à intent lock.

Intent locking protocol says all transaction must acquire an intent lock on the relvar before acquiring a lock on its tuple.

Intent locking protocol:

Before a transaction can acquire an S-lock on a tuple, it must first an IS or stronger lock on the relvar containing that tuple.

Before a transaction can acquire an X-lock on a tuple it must first an IX or stronger lock on the relvar containing that tuple.

References:

www.research.microsoft.com/~gray/

2) www.oracle.com/

3) Intro to Database System: by C. J. Date

4) Fundamentals of Database Systems: by Elmasri and Navathe

5) Oracle PL/SQL Programming: Steven Seuerstein