CMSI 486: Welcome to Week 05

This Week's Class Agenda

• Transaction Processing
• That's all
• …but that's enough…

Transaction Processing

As we've seen previously, when performing any of the CRUD operations on a database, we need to have some method of being able to insure the ACID conditions are followed and maintained. For example, if we are following the idea that operations on the database must be atomic, we are doing things to make sure that operations happen in their entirety or not at all. The best way to insure this state of affairs is to keep a log of each step of a database operation and if any of them fail, at any point in the process, ROLL BACK to the previously known good state. This philosophy will help assure that the data remains consistent, that all transactions are isolated from each other, and that it can be depended upon to be durable and reliable.

So, the idea of a single, atomic database operation becomes wrapped in the language that treats each and every one of those operations as a transaction, and the database operations as a set are known as transaction processing. The concept is easily explained by the analogy of buying an item from a store. The buyer goes in for a jar of mustard, takes it to the register, and the transaction begins. The mustard is placed on the belt; the belt moves it to the checker; the checker scans it; you provide the checker with sufficient funds; the checker provides you with your change; you take your change and your mustard home. That sequence of events constitutes a transaction. If any of the steps in that process fails, you have to eat your balogna sandwich on dry bread. The upside of this situation is that unless the entire process completes successfully, the status quo of the system is maintained; the store still has its mustard, and you still have your money. Transaction processing ensures that the resources are not updated unless and until ALL OPERATIONS within that transaction are successful.

Transaction processing provides several things:

• Maintains system integrity by ensuring the system is always in a known consistent state
• Ties multiple individual operations together into a single transaction
• Ensures that EITHER all operations are successful OR all operations fail
• Can roll back all of the operations of the transaction including successful operations
• Helps manage issues of concurrency, so that multiple users' data is consistent
• Guards against hardware errors and software errors that might create inconsistencies
• Guarantees that a conflict-free outcome results from interleaved concurrent operations
• Tries to produce and maintain maximum throughput of transactions for efficient results

Other things that transaction processing systems provide:

• Performance: measured in transactions per second, this is a measure of the response time of the system.
• Availability: this is a measure of the period of time when the users can access the system; it is often considered to be 24/7/365. For example, you would not be a happy camper if you had insomnia, wanted to check your gmail at 4:00 AM, and the database was down so you can't get to your data.
• Data integrity: the system needs to make sure data isn't corrupted, including when there are any hardware or software failures; multiple users rely on the isolation principle of ACID for this aspect of performance.
• Ease of use: this aspect is a bit of a slippery slope, since what is easy for one user is not the same as for another user. However, the system SHOULD be simple to understand, so that most users will not have difficulty being able to use it.
• Modular growth: the system should be able to be scaled according to the needs of the business for which it is applied.

Don't forget:

All database systems that have any idea of multiple simultaneous users [i.e., concurrency] WILL HAVE TO HAVE some idea of transaction-based processing. The reasons should be apparent, but if they are not, the discussion on this page should make it clear.

Transaction Engines all provide the following operations and principles, although different systems may use different names:

• Rollback: This is kind of what it sounds like; a transaction is rolled back to its original state before the start of that transaction. Note the subtlety here: the system is put into its state before the transaction began. The transaction must be completely and totally undone to maintain the idea of atomicity from the ACID concepts. A frequently-used way to do this is to freeze a snapshot of what is in machine memory before the transaction can make any modifications to it, which can be used to recover and return to the exact state in which the system was before anything was started.
• The complement to that is Rollforward: to accomplish this the database may make a set of journals which store all the transactions. When the database is backed up, some of the transactions may not be caught in the backed up data, especially if the database is a live one. Thus, if there is a failure like the power goes out, or an earthquake hits, restoring the database from a backup will not provide a complete restoration – any transactions that have occurred since the backup would be lost. The journal files allow these transactions to be re-applied after the recovery operation to bring the data back to the proper consistent state to support durability from the ACID concepts.
• Deadlocks: This is the familiar situation in which two [or more!] concurrent processes each hold a lock on an asset that the other needs to be able to continue processing. For example, if process A holds a lock on one section of the database, and process B holds a lock on another section, when A needs access to what B is holding, it cannot proceed, so it cannot release its lock on its own resource. Likewise, B can't proceed with its operation, needing access to the resource being held by A. Transaction processing systems are designed to detect these conditions and rectify the situation. There are several ways to fix this, such as stopping one process and rolling it back, which lets the other one complete, using the built-in rollback facility [fake failure and retry].
• Asset Locking: This is another mechanism which facilitates Atomicity and Isolation in the ACID criteria. Processes are given exclusive access to a database resource, such as a table, for the duration of the transaction operation. This method helps to ensure that all the resources the process requires are available to complete the transaction so it will succeed as a unit. Locking has several types, and is discussed in its own section below.
• Finally, compensating: This is a kind of transaction [often designed into Web Services] that allow long-lived transactions, such as user input on a web page, in which some of the data may be committed to the database before the transaction actually is fully complete; in this case, if the user cancels the operation or changes her mind on one or more selections, the committed data must be taken out and either the updated data put in, or the entire transaction cancelled. This is a bit different from a normal rollback, since it has already violated the principle of Atomicity somewhat -- some data has been committed but the entire transaction is not complete.

Note that there are two different types of transaction processing systems, interleaved and concurrent. These are exactly related to the similar idea in operating systems. The first one uses a system much like a round-robin system to make it look like all transactions are happening simultaneously, but in fact they are a series of sequential time slices, so that each transaction process gets a certain amount of time to work. This also means that if there is no meaningful work done during that time slice, the process [and hence the user's transaction] must wait until the *next* time slice to do anything. On the good side of this is the fact that the CPU is kept busy so that when a process is waiting for things that take a long time, like I/O operations, the processor isn't sitting idle.

The second type, concurrent, requires that there be multiple CPUs in the system so that each CPU can perform the steps needed for a transaction, independently of whether the other CPUs in the system are doing anything. This concurrency provides much faster throughput than the interleaved version, but at the cost of increased expense to buy the higher-performing hardware. There are also issues with concurrency and deadlock, as described above, which you can expect with any such system. Another such problem might be called [as in your book] the lost update problem. This situation can occur when two [or more] transactions are interleaved in a way that can lead to incorrect data, such as when one transaction makes an update but another transaction over-writes it. This is what happens with my time-worn example of my wife and me both trying to take out our last $20. If the interleaving processes leave the database in an inconsistent state, it's even possible that neither of us will get the money and the bank will STILL show us as broke!

Another problem: what happens if a database transaction fails in the middle, but during the failure, another transaction has accessed the interim data as if it were the golden copy? This is what is known as the inconsistent retrieval problem, also known as a dirty read. This situation can also lead to inconsistencies in the database which are very hard to detect, since the interrupted transaction will be rolled back as if it never occurred, while the successful second transaction has no idea that it has the wrong information!

Yet another possible source of inconsistency: what happens if one transaction is calculating some value based on some data, and at the same time other transactions are updating that data? We could end up in this case with inconsistencies because some of the values are updated [and correct] and others are NOT updated [and are thus INcorrect]. This is known as the uncommitted data problem also known as the incorrect summary problem. Finally, as is detailed in your Elmasri book, there is the unrepeatable read problem, in which one process changes data between another process's read transactions, so that the two reads which SHOULD produce the same data, do NOT produce the same data.

Databases that are used in transaction processing systems should provide the following features:

• should be designed to access patterns of data from many simultaneous users
• should enable transactions that are as short as possible to help avoid concurrency issues
• should have backups scheduled during periods of low usage to minimize user impact
• should be well-normalized to reduce redundancy and speed access, which improves concurrency
• should have hardware configured properly to handle multiple users and provide fast response
• should archive little-used data to backups or to archive databases to keep the main data sets small for quicker access and faster backups

How does transaction processing actually work?

There are several steps to a transaction, as has been alluded to above. Your Elmasri book provides a set of five steps, which are summarized below.

1. BEGIN_TRANSACTION: this is just the start of the transaction, but it marks a specific point in time at which the transaction actually begins. It will be stored in the journal file so that the DBMS knows when it started for rollback purposes.
2. READ OR WRITE: these steps specify the read or write operations that are executed as part of this transaction. Note that there may actually be several operations that are part of this transaction step, which are still treated as part of the single transaction, and are therefore considered atomic. Of course, that makes things more difficult, because if there is a failure, the abort operation must roll ALL of these operations back.
3. END_TRANSACTION: this step marks the actual end of the transaction execution. At this point it is necessary to check that the changes made by this transaction are consistent, so that the data will be permanently stored in the affected tables. If this is not true, the commit step will be skipped and a rollback step will be executed instead.
4. COMMIT_TRANSACTION: this step signifies a successful completion of this transaction; any changes that are made by this transaction can now be safely made a permanent part of the database.
5. ROLLBACK_TRANSACTION [OR ABORT]: this step signifies an unsuccessful completion of this transaction; any changes made by this transaction must now be rolled back so that the database remains in a known-good consistent state.

This diagram shows a flow or state transition diagram of what happens, and assumes that most of the concurrency problems are not applicable.
	The BEGIN_TRANSACTION step starts at the right. The transaction is active as long as the READ or WRITE step is active. If any of the operations fail, the ABORT or ROLLBACK_TRANSACTION leg is taken. Once all operations are completed, the END_TRANSACTION leg exits from the active state, and the changes can be considered partially committed. The checks are performed to ensure all operations were successful, and then the COMMIT_TRANSACTION operation can occur.
If anything has failed up to this point, the ABORT or ROLLBACK_TRANSACTION leg is taken. Finally, if all is well, the committed data becomes the new state of the data and the transaction is completed.

How does recovery actually work?

A transaction process may fail for many reasons, such as hardware failure, software application errors, computer viruses, system failure, human errors, incorrect or invalid data, or even natural or man-made disasters. Since it is not feasible to think we can prevent all failures of all types, a transaction processing system must be able to detect and correct errors when they occur so as to cope with those failures. A transaction processing system will thus be required go through a database recovery operation, which may involve the backup, journaling, checkpointing, and recovery oerations, including:

• Journaling: A journal maintains an audit trail of transactions and database changes. Transaction logs and database change logs are used, to record all the essential data for each transaction, including data values, the time of each transaction, the type of data involved, the operation requested, and terminal or IP address of the computer that initiated the transaction. The database change log contains before-and-after copies of records that have been modified by these transactions, and provides a link to the journal so that the data can be restored or rolled back as is appropriate.
• Checkpoint: Checkpointing provides a snapshot of the data within the database, which is any identifier or other reference that identifies the state of the database at a point in time. Modifications to the database are performed in memory and are not necessarily written to disk after every operation [as we've seen above]. Therefore, the DBMS must periodically perform a checkpoint operation to write these updates [which are being held in memory] to disk. Writing these updates to storage media creates a point in time at which the database system can apply changes contained in a transaction log during recovery after an unexpected shut down or crash. If a checkpoint is interrupted and a recovery is required, then the database system must start the recovery from a previous successful checkpoint.
• Checkpointing can be either transaction-consistent or non-transaction-consistent [also known as fuzzy checkpointing]. Transaction-consistent checkpointing produces a persistent database image that is sufficient to recover the database to the state that was externally perceived at the moment of starting the checkpointing. A non-transaction-consistent checkpointing results in a persistent database image that is insufficient to perform a recovery of the database state, which means that to perform such a recovery, additional information is needed. This information is typically contained in the transaction logs.
• Transaction consistent checkpointing refers to a consistent database, which doesn't necessarily include all the latest committed transactions, but does contain all updates made by transactions that were committed at the time the checkpoint creation was started. A non-consistent transaction refers to a checkpoint which is not necessarily a consistent database state, and cannot be recovered to such a state without all log records generated for open transactions included in the checkpoint.
• A Recovery Manager is a program which restores the database to a correct condition which allows transaction processing to be restarted. Depending on how the system failed, there can be two different recovery procedures used. Generally, the procedures involve restoring data that has been collected from a backup device and then running the transaction processing again. This two-step process restores the data that is contained in the backup, then adds on [updates] the data with whatever has happened since the last backup. Of course, this implies that the transaction and checkpoint logs are both viable and complete up to the point at which the failure occurred; there may be some operations that have not completed, and it is expected that the logs would show which transactions were in process but NOT complete so that these transactions would be ignored in the restoration process.
• There are two types of recovery: Backward recovery is used to undo unwanted changes to the database. It reverses the changes made by transactions which have been aborted. Forward recovery, in contrast, starts with a backup copy of the database, which the transaction will then reprocess according to the transaction journal that occurred between the time the backup was made and the present. THESE ARE NOT MUTUALLY EXCLUSIVE, but will be used together to ensure ACIDity.

Checkpointing Details

At a specific point in time [which is usually defined by the Data Base Administrator [DBA]], a checkpoint operation is performed. There are three steps to this process: The DBMS forces content from main memory to the physical database, meaning that the data which has been held in RAM is actually written to disk The DBMS writes to one of the logs [either transaction log or checkpoint log or both] that a checkpoint was forced on the database, so that the latest checkpoint time and conditions are saved. The DBMS writes a snapshot of all ongoing transactions to the logs so that there is a record of what transactions are/were in process at that particular point.

Here are the steps in a hypothetical checkpointing process:

1. At time t1, there is nothing to do. All operations [T1] have completed successfully before the checkpointing operation is due to occur.
2. At time t2, a transaction starts [T2], just ahead of the checkpoint.
3. At time t3, another transaction [T3] begins, which continues for a while.
4. At time tc, the checkpoint occurs.
5. At time t2a, the transaction which began at T2 finishes; this is AFTER time tc so it was in process when the checkpoint was created.
6. At time t4, another transaction begins [T4].
7. At time t5, another transaction begins [T5].
8. At time t4a, transaction T4 completes.
9. At time tf, there is a system failure, such that transactions T3 and T5 are not able to complete.

The result of this hypothetical situation is that Transaction T1 has no problem; it has completed successfully. However, transactions T3 and T5 must be rolled back, since they failed at time Tf, and we don't know how far their processing went before the failure. To ensure data consistence, any interim changes that were written to disk will need to be undone and the entire transactions must be restarted. Additionally, transactions T2 and T4 must be re-done; They completed between the checkpoint and the failure, so the logs will not have a certain record of whether they completed successfully or not. All we know about T2 is that it was in process during the checkpoint; we have no knowledge of its completion state, although it is possible that it was logged in the transaction log, so we could go check there. As far as the checkpoint log goes, we have no knowledge at all of T4; we MUST check the transaction logs for any information there.

Checkpointing Algorithm

There is actually a set of steps for checkpointing. There are different versions, depending on the DBMS and the optimizations that may be applied, but it goes something like this:

1. At reboot, two empty lists are created – the undo list and the redo list
2. On the undo list, log all transactions that are ongoing during the checkpoint
3. Go forward through the log from the checkpoint. If you find a begin trans flag, add that transaction to the undo lists. If you find a commit trans flag, move that transaction from the undo list to the redo list
4. When you reach the end of the log, the DBMS uses the two lists to undo/redo by first going back into the log and undoing the undos from the undo list, then going forward through the log and redoing all the redos from the redo list

In Class Exercise: Transaction Processing Example

Coming up…

Concurrency and Locking methods

MIDTERM EXAMINATION IN TWO WEEKS!!