The ACID Test

The ACID test for transaction processing is that the system be Atomic, Consistent, Isolated and Durable.

Atomic

Atomic — indivisible — an effect is atomic if it cannot be partially implemented

Every transaction must be indivisible. The system must either complete the transaction or return to a state that is indistinguishable from the state it was in before the transaction began. We say that the transaction is atomic. Of course, a transaction takes system resources even if it aborts. It clearly has an effect on the database, if only on its performance. When we say it has no effect on the database, we mean that none of the tables in the database are changed, none of the ID's are used or retired etc. It is as if you went to sleep for a few milliseconds and nothing happened — the transaction had no permanent effects on the system (usually meaning the database). Other transactions might have been processed during the same time, and these might have affected the database, but the point is that the effects that these other transactions have on the database are the same as if the aborted transaction had never existed.

Atomic transactions are designed to leave the database in a consistent state — the information in each of the tables is consistent with the information in all of the other tables. Transaction-based systems become complicated in multi-tasking environments; so the developer must take steps to protect the integrity or consistency of the database tables.

Consistent

It is assumed that a database is initially consistent and that all transactions leave it consistent. This assumption is realized in the database world through the use of integrity constraints. In the object world, we assume that the objects represented in the database satisfy all of the constraints that are defined in the static object model (as described in Chapter 3).

Isolated

We have been speaking about transactions as if they were processed one at a time. No system processing transactions could afford to do this: it would make the cost-per-transaction of the software and hardware an order of magnitude higher. Instead, transactions are interleaved like any other activity in a modern multi-user multi-tasking computer system.

That said, the effects of a transaction must be the same whether it is run alone or at the same time as other transactions. A set of transactions which could run one after the other, that is in series, is said to be serializable. A system is isolated if each transaction is serializable. That is, to the system, it appears as if this transaction occurred in isolation of all the other transaction. Nothing in this transaction requires any activity in another transaction. If no other transaction occurred, this transaction would remain consistent and valid.

Business rules define which actions in a domain have to happen together (for example, payment is a combination of debiting my account and crediting your account). Together, these activities make a single transaction.

Implementing Isolation

The mechanism that is usually used in database systems to implement isolation is locking. Isolation theory is based on the idea of constraints, consistency and concurrency.

Constraints are the invariants of the domain; that is, they dictate what must be true within this domain for the object to be valid.

An example of a constraint is, "The relationship between the customer and his membership ID is one-to-one." This constraint would prevent a single customer from having more than one membership ID, or one ID being shared among two or more members.

An object model is consistent if all of the constraints of the model are satisfied. All object models should be consistent before they are written to the database. This is reinforced to some extent by the data integrity mechanisms that the object or relational database supports.

Every transaction must end with the system in a consistent state. This is fundamental to the idea of transaction processing. Transactions are assumed to have a pre-condition which states that the object model is in a consistent state. They supply the post-condition that the object model is in a consistent state. In the middle of a transaction, anything goes.

If each transaction is consistent, then any serial ordering of them must be consistent. That is, if the object model is consistent before the set of transactions start, and each transaction is consistent, then the object model will be consistent at the end of the stream of transactions. This is not necessarily true, however if the transactions are interleaved, as they may update shared data.

To support multi-tasking, systems that process transactions must meet two requirements: concurrent execution must not cause inconsistency, and must not lower throughput or raise response time significantly compared to serial execution.

Violating Isolation

There are three ways concurrent transactions can violate isolation:

Lost Update: this can result from one thread reading, a second thread writing and then the first thread overwriting that work with its own write.
Dirty read: this can result from one thread writing, a second thread reading what the first thread wrote and then the first thread overwriting what it originally wrote. The second thread has now read incorrect data.
Unrepeatable read: this happens when the first thread reads data, the second thread overwrites that data and then the first thread re-reads the data. The data is not the same as the first read.

If the algorithm used can be shown to avoid lost updates, dirty reads and unrepeatable reads, then concurrent execution of transactions is guaranteed to be consistent.

The following set of rules is sufficient to ensure that these three types of anomalies are avoided:

Other transactions do not write any data read by any transaction before that transaction completes
Other transactions do not read or write any data written by any transaction before that transaction completes
A transaction does not read dirty data from any other transaction, nor overwrite dirty data of any other transaction

Dirty data is data that has been altered in any way

If these rules are followed then transactions will be isolated, the database will be consistent, committed transactions will be durable, and aborted transactions will be ephemeral.

Implications of Isolation Theory

A transaction can be implemented by read, write, lock (shared and exclusive) and unlock operations, without commit and abort. A transaction is called well-formed if each read, write and unlock action is under control of a lock, and if every lock is released by the end of the transaction. A transaction is called two-phase if it acquires all of its locks before it releases any of them.

A history of a set of transactions is a way in which they could possibly have been run together. A history is serial if it is possible to run the transactions sequentially, and legal if it obeys the locking rules (that is, does not grant conflicting locks).

A transaction T1 is dependent on transaction T2 if T1 reads data that T2 writes. That is, T1's actions are dependent on the data it reads, and some of that data was written by T2. A history defines such a dependency relationship.

Dependency relationships determine an ordering of the transactions and pinpoint transactions which are not isolated. If T1 is dependent on T2, then T1 must run after T2 in any serialized ordering of T1 and T2. In order to keep transactions isolated, we should consider combining T1 and T2 into one overall transaction.

Degrees of Isolation

Isolation is sometimes compromised for performance reasons. For instance, there is a tension between queries and updates in a database system. Queries run for a relatively long time and touch many rows. They therefore set many locks, and this can cause performance to deteriorate.

Therefore, some systems employ strategies that do not have fully guaranteed isolation. A taxonomy of degrees of isolation has been developed. For each degree of isolation, a corresponding lock protocol has been developed, with a guarantee that following the protocol will result in the required degree of isolation.

We can define four degrees of isolation:

Degree 3 isolation is true isolation — no lost updates, no dirty reads, no unrepeatable reads. The lock protocol is two-phase and well formed as previously described.
Degree 2 isolation, known in databases as cursor stability, has no lost updates and no dirty reads, but may have unrepeatable reads. The locking protocol is two-phase for exclusive locks and well formed.
Degree 1 isolation, known as browse mode, has no lost updates.
Degree 0 isolation is only limited to not overwriting the data of any other transaction that is of degree 1 isolation or greater. The locking protocol is well formed for writes.

Lower degrees of isolation reduce the time for which locks are held and therefore increase concurrency. The locks are of short duration, as opposed to locks that are held to the end of the transaction, which are called long duration. Usually, write locks are long duration and read locks are short duration.

Durable

Once a transaction commits, the effect it has on the database is permanent. It does not matter if the hardware or software fails — the effects are permanent. This can be accomplished through redundancy, backups and so forth. No failure of memory, disk storage or system software should be able to undo the effects of a transaction. The transaction is durable.

It is possible to create this durability by ensuring that the transaction can be replicated. That is, if you know the starting state before corruption and you know the details of the transaction, you may be able to restore the transaction by re-enacting it. In any case, when restoration is complete, the transaction's effects have been sustained.