Isolation Concepts (Chp 7: Transaction processing book)

- March 20, 2024

Continuing with our Transaction book reading, this week we look at the first part of the Isolation concepts. The book gets conceptual to provide the theory behind isolation of transactions. Finally we are getting some protocol action.

The first part of the chapter covers the following: Introduction to Isolation, The Dependency Model of Isolation (Three Bad Dependencies), Isolation: The Application Programmer’s View, and Isolation Theorems.

A couple things immediately pop out. Chapter 7 equates Serializability (SER) with Isolation, whereas today snapshot isolation (SI) is the most popular isolation level, and we have a bunch of other weaker isolation levels.

Secondly, Chapter 7 equates two-phase-locking (2PL) with the isolation implementation techniques, whereas today MVCC and OCC are also popular implementation techniques. Although optimistic concurrency control (OCC) was established by 1980, the book did not consider OCC mechanisms at all.

This is normal, when we consider the database context of the 1980s.

Let's start with equating SER with isolation. This is indeed how the isolation semantics evolved over time. I would have guessed the semantics had become more stricter over time. No, on the contrary, they evolved to be more relaxed to meet performance and scalability expectations. Transactions started with Serializable isolation and due to performance reasons the isolation got relaxed gradually from there.

Now let's consider the 2PL versus OCC comparison. I asked my dear friend Pat Helland again, and got the context for this.

OCC works well when each individual transaction is "minding its own business". In 1980s, everything in OLTP space was high concurrency updates to the same stuff. So naturally, OCC looked like would flounder and thrash.

There is a tension between purity of concept and practicality of "just making it work". OCC works great but ONLY when your app behaves in a certain way. Apps up until that point largely had smaller datasets and higher concurrency per record. For the majority of existing applications, OCC was a disaster (at that time).

Data has been getting colder for many decades. Churn rate as a portion of data size has been dropping. Hence, OCC continues to become more practical over time. Back in the 1970s and 1980s, it could be a mess. Things evolve. Old concepts evolve, too.

Finally, what about multiversion concurrency control (MVCC). Again although the concept of MVCC was known, due to the hardware restrictions they had to deal with it wasn't a viable thing to employ. Chapter 5 mentioned this: "At the time these systems were developed, main memories tended to be small (less than 1 MB), yet the number of different transaction programs to be kept available was increasing." That is one megabyte people! A one minute audio file takes up one megabyte.

Although Chapter 7 mentioned versions of objects, these seem to be conceptual only to explain the dependency graph and isolation semantics. Except for temporarily in the working memory and or in WAL for recovery, we don't have multiversion storage employed/mentioned in Chapter 7. Ain't nobody got the memory and disk space for that.

Ok, let's give brief summaries of the sections in the first half of Chapter 7 by borrowing text from the book. At the end, I also provide a brief overview of Chapter 6, which we skipped.

Introduction to Isolation

This chapter and the next cover the concepts and techniques associated with transaction isolation. This topic is variously called consistency (the static property), concurrency control (the problem), serializability (the theory), or locking (the technique).

The system state consists of objects related in certain ways. These relationships are best thought of as invariants about the objects. E.g., "If a program changes the account balance, it must record the change in the ledger.", "The checksum field of each page, P, must be CHECKSUM(P)."

The system state is said to be consistent if it satisfies all these invariants. Often, the state must be made temporarily inconsistent while it is being transformed to a new, consistent state. Almost any transformation involving updates to several objects temporarily invalidates their mutual consistency.

To cope with these temporary inconsistencies, sequences of actions are grouped to form transactions that preserve the consistency constraints. A transaction that is started with a consistent system state may make the state temporarily inconsistent, but it will terminate by producing a new consistent state. Transactions, then, are units of consistency. This is the C (consistency) of the transaction ACID property. If some action of the transaction fails, the system can automatically undo the actions of the transaction to return to the original consistent state. Defining transaction boundaries within application programs is a major part of application design.

If transactions are run one at a time in isolation, each transaction sees the consistent state left behind by its predecessor. However, if several transactions execute concurrently, the inputs and consequent behavior of some may be inconsistent, even though each transaction executed in isolation is correct. Concurrent transaction execution must be controlled so that correct programs do not malfunction.

First Law of Concurrency Control: Concurrent execution should not cause application programs to malfunction.

Many approaches to providing automatic isolation have been tried. There is consensus on one feasible solution: locking.

Second Law of Concurrency Control: Concurrent execution should not have lower throughput or much higher response times than serial execution.

The simplest lock protocol associates a lock with each object. Whenever a transaction accesses an object, the underlying resource manager automatically requests and holds the object’s lock for that transaction until the transaction completes. If the lock is granted to another transaction at the moment, the transaction waits for the lock to become free. Locks are a serialization mechanism that assure that only one transaction accesses an object at any given time.

The main contribution of transaction systems to concurrency control has been to refine these ideas to include automatic locking and to combine the locking algorithms with the transaction undo/redo algorithms. This approach gives application programmers a simple model of concurrency and exception conditions.

The Dependency Model of Isolation (Three Bad Dependencies)

A transaction is a sequence of read and write actions on objects. Two write actions to an object by the same transaction do not violate consistency because the ACID property assumes that the transaction knows what it is doing to its data; the ACID property assumes that if the transaction runs in isolation, it will correctly transform the system state. Consequently, only write-related interactions between two concurrent transactions can create inconsistency or violate isolation.

The set of transactions {Ti} can run in parallel with no concurrency anomalies if their outputs are disjoint from one another’s inputs and outputs.

FIGURE 7.1 The three forms of transaction dependencies. The leftmost column shows transaction T2 writing version 〈o,2〉, of object o after T1 reads version 〈o,1〉,. This READ→ WRITE dependency is shown in the graph below the execution sequence. The other two columns show the other two forms of dependency WRITE→ READ and WRITE→ WRITE

The main result of the isolation theorems is that any dependency graph without cycles implies an isolated execution of the transactions. On the other hand, if the dependency graph has cycles, the transactions were not executed in isolation. This is fairly intuitive: if the dependency graph has no cycles, then the transactions can be topologically sorted to make an equivalent execution history in which each transaction ran serially, one completing before the next began. This implies that each transaction ran in isolation, as though there were no concurrency; it also implies that there were no concurrency anomalies. If there is a cycle, such a sort is impossible, because there are at least two transactions, such that T1 ran before T2, and that T2 ran before T1.

FIGURE 7.2 Four transaction dependencies. Versions of a single object, o, are shown being read and written by two transactions, T1 and T2. The kinds of dependencies are WRITE→ WRITE (can cause lost updates), WRITE→ READ (can cause dirty reads), READ→ WRITE (can cause unrepeatable reads), and READ→ READ (causes no inconsistency).

Lost update. Transaction T1’s write is ignored by transaction T2, which writes the object based on the original value 〈o,1〉. A READ-WRITE-WRITE sequence is shown in the diagram, but a WRITE-WRITE-WRITE sequence forms the same graph and is equally bad. To give a simple example of a lost update: suppose you and I are writing a program together. We both make a copy of the program and change it independently. We then return the program to the program library. If each of us is unaware that the other has updated the program, and if there is no control on updates, then the program will end up with only my changes or only your changes. One of our updates will be lost.

Dirty read. T1 reads an object previously written by transaction T2, then T2 makes further changes to the object. The version read by T1 may be inconsistent, because it is not the final (committed) value of o produced by T2. To continue the programming example, suppose you tentatively install a version of the program in the library, and I use that program. Then you realize that the program is wrong and reverse the change, creating a new version of the program. My read of your tentative program was a dirty read.

Unrepeatable read. T1 reads an object twice, once before transaction T2 updates it and once after committed transaction T2 has updated it. The two read operations return different values for the object. To continue the program example, suppose I use version 1 of your program, and you later install and commit a new version of it (version 2). If I read your program again, it will be the new version that I read. Thus, my first read was not repeatable.

If there were no concurrency, none of these anomalous cases would arise. As a result, these cases definitely violate the first law of concurrency. The surprising thing is that these three generic forms of inconsistency are the whole story. If they can be prevented, then there will be no concurrency anomalies, and the transaction will appear to run in isolation. This is the idea behind the isolation theorems.

Isolation: The Application Programmer’s View

Isolation: user’s definition 1. The transaction processing system may run transactions in parallel, but it behaves as if it has run transactions in sequence. As far as the application programs are concerned, it is as though the transactions were run with no parallelism; the exact ordering of the transactions is controlled by the system. The behavior of the system is equivalent to some serial execution of the transactions, giving the appearance that one transaction ran to completion before the next one started.

Isolation: user’s definition 2. This more mechanistic application programming definition states that transaction T is isolated from other transactions if:

(0) T does not overwrite dirty data of other transactions.
(1) T’s writes are neither read nor written by other transactions until COMMIT WORK.
(2) T does not read dirty data from other transactions.
(3) Other transactions do not write (dirty) any data read by T before T completes.

Clauses 0 and 1 preclude lost updates, clause 2 isolates the transaction from dirty reads, and clause 3 prevents unrepeatable reads.

These two definitions are almost equivalent.

Isolation Theorems

The theorems indicate how locking can achieve serializability: lock everything you access and hold all locks until commit. 2PL transactions have a grow phase where locks are acquired, followed by a shrink phrase where they are released.

A transaction is said to be well-formed if all its READ, WRITE, and UNLOCK actions are covered by locks, and if each lock action is eventually followed by a corresponding UNLOCK action.

Each step of the history 〈t,a,o〉 is action a by transaction t on object o. A history for the set of transactions {Tj} is a sequence, each containing transaction Tj as a subsequence and containing nothing else. A history lists the order in which actions were successfully completed. For example, if a transaction requests a lock at the beginning of the history but has to wait, and is finally granted the lock near the end of the history, that lock request will appear near the end of the history.

FIGURE 7.4 Three execution histories of simple transactions T1 and T2. Each history was chosen to demonstrate the differences between legal and serial histories. The third history contains an XLOCK action by T2 in bold type. That action violates the lock protocol, since T1 already has B locked. That is why the history is not legal. The diagrams at the bottom show how the history threads the execution steps of each transaction. Note that it is not possible to have a serial history that is not legal.

It may appear that this is a centralized view of transactions. What if many computers execute the transactions in parallel? How can such parallel execution be viewed as a single sequential history? There are two answers: (1) Imagine a global, universal clock precise to 10–100 seconds. Each action at each machine gets a timestamp from this clock when it completes. These timestamps give a sequential ordering (history) of all the actions. (2) Alternatively, each computer can linearly order its actions into a local history, and when two machines interact by X sending a message to Y, they synchronize their histories so that all X actions prior to the send precede all Y actions after the receive. The resulting partial ordering can be transformed into a global sequential history.

FIGURE 7.5 The dependencies induced by history fragments. Each graph shows the two transaction nodes T1 and T2 and the arcs labeled with the object 〈name,version〉 pairs. Outgoing read dependencies are not shown (see Exercise 3).

FIGURE 7.6 The dependencies among a set of transactions induced by two different execution histories. The graph on the left has no cycles and, consequently, no wormhole transactions. It allows the serial history T1,T2,T3,T4,T5,T6. The figure on the left shows that the sets of transactions {T1,T3} {T2, T4,T5}, and many other subsets, do not directly interact at all and may therefore be run concurrently without any risk of violating isolation. The graph on the right has two cycles. Transactions T3, T4, T5, and T6 are wormhole transactions that ran both before and after one another.

The implication of all these results is that a transaction should:

Be well-formed: it should cover all actions with locks.
Set exclusive mode locks on any data it dirties (writes).
Be two-phase: it should not release locks until it knows it needs no more locks.
Hold exclusive locks until COMMIT or ROLLBACK.

If these rules are followed, there will be no wormholes, and all execution histories will be equivalent to some serial execution history, giving each transaction the illusion it is running in isolation. In addition, rollback will work automatically, without needing to acquire locks and running the consequent risk of creating a wormhole. On the other hand, if any of the above rules are violated, then it is possible that the image ordering has a cycle and that the transaction may have inconsistent inputs or outputs.

Brief summary of Chapter 6

We skipped the discussion of Chapter 6. Here is a brief summary of that.

We were confused about TPMonitor in Chapter 5, Chapter 6 goes into detailed explanations of TPMonitor and implementation. It talks about transaction RPCs first, durable queue management to hold the TRPCs next. So Chapter 6 has very much an OS book appearance.

Here is the book's summary. "This chapter has described the TP monitor from an implementation-oriented perspective. It becomes clear that the TP monitor is a resource manager that manages other resource managers and processor resources such as processes, threads, access rights, programs, and context. In that respect, the TP monitor is very much like an operating system, but there are important differences. For one thing, a conventional operating system allocates resources to requests on a long-term basis (a logon creates a session that can be expected to go on for minutes or hours), while a TP monitor has to allocate resources on a per-request basis. This leads to the second difference: all the administrative tasks an operating system carries each time a session is created (or opened) must be performed by the TP monitor upon each request. This applies to authentication, authorization, process allocation, and storage allocation. Not only is the rate of these tasks much higher in a transaction system, but doing these things on a per-request basis also introduces more dimensions to the decision space. This is illustrated in the complex authorization criteria a TP monitor has to apply. A third difference between operating systems and TP monitors has to do with consistency: a TP monitor must support all applications and resource managers upon restart after a crash; an operating system, on the other hand, typically takes care of its own system files (catalog, and so on) and lets everybody else do what they please."

One thing is for sure, this chapter did make TPMonitor concept more concrete. Even load balancing was the duty of the TPMonitor. These all moved out when database are decoupled from applications and abstracted away. Databases conceded ground to OS and cloud services. We got much better algorithms and tools for load balancing, authentication, authorization, so these are simpler and more established concepts now. Today, only maybe for a serverless cloud database, creating/load-balancing query processing nodes is still a database service role.