A while ago we were introduced to process synchronization in operating systems. Today let us look at the concurrency control in database management systems. We often find ourselves producing errors more speedily when we try to juggle multiple things at once, or when we try to work with others on the same task without adequate communications. It happens that computers are just like us. Disasters come if we try to enjoy (exploit) their powerful resources without thinking carefully how to orchestrate them that guarantees no conflicts.

As a powerful and considerate framework, Rails of course has built-in methods that let us handle our model objects (which are linked to database objects) with more ease. The built-in transaction method provided by ActiveRecord, for example, escorts our data’s integrity through a series of operations. For example:

ActiveRecord::Base.transaction do
  A.withdraw(300)
  B.deposit(300)
end

Wrapping the operations in the transaction block guarantees if something unfortunately goes wrong, the worst case scenario would be a rollback–undo all already-processed operations in the transaction, and the records in the database will keep their original states like nothing ever happened.

This example demonstrates a transfer event: this is what goes behind the curtain when A is transferring $300 to B. If for some reason the connection breaks in the middle of the transaction, say whenA.withdraw(300) is done but not yet B.deposit(300), then when exiting the transaction block A.withdraw(300) will be undone.

A brief note on the usage of this transaction method: we can actually use it on various objects, not necessarily as an ActiveRecord class method. I’ll leave a reference here so we can enjoy all the detailed usage in our own time.

But diligent as we are, knowing how to properly call a method clearly cannot satisfy us. How is this apparently highly abstracted function implemented? To answer that, let us first understand how transactions work in the database level.

Concurrency Control: An Overview

In the context of database systems, a transaction is a set of database operations induced by a single user or application that should be considered as one undividable unit of work. For a database management system to have a valid transaction mechanism, it is important that it has the ACID (Atomicity, Consistency, Isolation, Durability) properties.

A transaction manager in the database management system takes responsibility for coordinating transaction executions. When new, to-be-executed transactions come, the transaction manager will put them in a scheduler.

Serial Schedule and Serializable Schedule

There are two types of a scheduler, serial schedule and serializable schedule. Yes, they do seem like synonyms but are in fact more like antonyms.

In a serial schedule, all statements of the same transaction are executed consecutively, without any interleave with statements from a different transaction.

On the other hand, serializable schedules have two characteristics: (1) they are non-serial schedules, which allow concurrent executions of different transactions (2) they still produce correct results.

The Goal

With a serial schedule, the ACID properties can be easily achieved. However, in our current world where parallelism and concurrency is the norm, using a serial schedule would seriously under-exploit the potential these hardware technologies provide.

So we aim at serializable schedules, which have the integrity of a serial schedule as well as the advantage of efficiency.

The study of concurrency control, then, is to coordinate transactions that execute simultaneously in a way that guarantees these transactions do not cause any data inconsistencies from mutual interference.

Typical Concurrency Problems

Any design in the field of concurrency control would be tested against these five typical interference problems:

1. The Lost Update Problem
2. The Uncommitted Dependency Problem
3. The Inconsistent Analysis Problem
4. Non-repeatable Read
5. Phantom Read

Let us look at them one by one.

Lost Update Problem

happens when two transactions access and update the same data simultaneously, and the result of one is overwritten by another. For example, both transaction T1 and T2 is adding 3 to a variable x, whose original value is 0. The operations in both transactions are as follows:

1. Read the value of x.
2. Add 3 to the value.
3. Assign it back to x.

Now, in a concurrent environment, what might happen is T1 and T2 read the value of x, which is 0, at the same time. They both add 3 to that value and return. When all operations are done, our x now has the value 3, when it should have been 6.

This problem results in an inconsistent database state.

Uncommitted Dependency Problem (Dirty Read Problem)

Suppose today we have a data that is being updated and eventually rolled back in a transaction. A dirty read occurs when another transaction, running concurrently, reads that data at the exact point when it is updated but not yet rolled back.

This problem results in either an inconsistent database or incorrect query result, depending on what of that dirty-reading transaction is.

Inconsistent Analysis Problem

Inconsistent analysis happens when a transaction reads a data which another transaction is still updating. It is almost the same problem with lost update, except that the final database state is actually consistent, because that other transaction does not modify the data. Nevertheless, the query result is still incorrect.

Non-repeatable Read

Non-repeatable read occurs when a transaction reads the same row multiple times but obtains different subsequent values, because another transaction is updating the row at the same time.

Phantom Read

Phantom read is a problem when a transaction is executing insert or delete operations on a set of rows that are being read by another transaction.

In the following sections, we will discuss how the different solutions respond to these problems.

Locking: Techniques in Practice

To protect the integrity of data during transaction, locking is a popular strategy. Since concurrency is really a big, as well as inevitable, deal, you can see pretty much the same struggle and similar responses across different areas of computer science, for example The Dining Philosophers Problem.

The basic concept of locking is this: when an operation attempts to access a database object, it would first have to acquire a lock on that object. If currently the lock is unavailable, the operation waits until it gets the lock. Then the operation can be executed with safety and everybody is happy.

In the case of database transaction, we use two types of locks: exclusive locks and shared locks.

Exclusive Locks (x-locks; write-locks)

An exclusive lock is also called a x-lock or a write-lock. If a transaction acquires an exclusive lock, that transaction has the sole privilege to interact with that specific database object until it releases the lock.

Shared Locks (s-locks; read-locks)

A shared lock, also called a s-lock or a read-lock, guarantees that no other transactions will update the same database object for as long as the lock is held, but others transactions are still allowed to read from the object.

Jobs of a Locking Manager

When we invoke a transaction, the database management system will implicitly handle the request and release processes on behalf of the transaction. In these requests, read operations will induce s-locks and write operations will induce x-locks. A commit or rollback releases the lock.

The roles involved in implicit locking are the transaction manager (introduced above) and the locking manager. The locking manager interacts with the transaction manager and has the following responsibilities:

• implementation of a locking protocol
• management of a lock table, which contains information about which locks are currently held by which transaction, which transactions are waiting to acquire certain locks, etc
• avoiding starvation, where some transactions wait endlessly for the required exclusive locks

The Two-Phase Locking Protocol (2PL)

A locking protocol is a set of rules that determine what locks can be granted in what situation. The two-phase locking protocol, a.k.a 2PL, is one of the most well-known locking protocol in a standalone database context. Its rules are as follows:

1. Before a transaction can read a database object, it should acquire a shared lock on that object.
2. The lock manager determines whether requested locks do not cause any conflicts and can be granted, based on the compatibility matrix. Transactions whose locking requests cannot be granted are put on hold until the request can be granted.
3. For each transaction, acquiring and releasing locks occurs in two phases: the growth phase and the shrink phase. In the growth phase, new locks can be acquired but no locks can be released. In the shrink phase, locks are gradually released, and no additional locks can be acquired.

These are the general concepts, but there are several variants that differ in when exactly to move to the next phase.

Variants of the 2PL

• Basic 2PL: A transaction can enter the shrink phase before it has attained the “committed” state. With basic 2PL, the lost update problem is successfully solved, but the uncommitted dependency problem still exists, which would invoke cascading rollbacks.
• Static 2PL (conservative 2PL): A transaction acquires all its locks right at the start of the transaction. Since it is not always possible to predict which locks will be required, the transaction would grab all the locks that may be needed.
• Rigorous 2PL: The transaction holds all its locks until committed.

Although the 2PL provides a fairly robust locking guideline, we cannot neglect its negative impact on transaction throughput, because the level of transaction isolation offered by 2PL is quite stringent. To optimize the efficiency, let us first try to understand different isolation levels. Afterwards, we will look at the concept of lock granularity and the Multiple Granularity Locking Protocol (the MGL protocol).

Isolation Levels

Most Database Management Systems allow different isolation levels, most commonly read uncommitted, read committed, repeatable read, and serializable.

1. Read Uncommitted: The lowest isolation level. It just happily assumes concurrency conflicts do no occur or have no impact whatsoever. This level is only safe for read-only transactions.
2. Read Committed: It uses long-term (transaction level) write locks + short-term (operation level) read locks, and guarantees that no transactions can read any data that are still being updated by another yet-uncommitted transaction. It resolves the lost update and the uncommitted dependency problem, but would fail the test of inconsistent analysis problem, non-repeatable reads and phantom reads.
3. Repeatable Read: It uses long-term locks for both write and read, offering solutions to all problems except phantom reads.
4. Serializable: The strongest isolation level. It roughly corresponds to an implementation of 2PL.

Lock Granularity

Supposedly we can put a lock on any database objects, which can be a tuple, a column, a table, a table space or a disk block. On the one hand, locking at a fine-grained level (e.g., an individual tuple) has the least negative impact on throughput. On the other hand, if many tuples are involved in the transaction, locking each individual tuple causes a huge overhead.

To guarantee an optimized lock granularity for transactions, many database management systems now implement the Multiple Granularity Locking (MGL) Protocol.

Multiple Granularity Locking Protocol

The purpose of this protocol is to guarantee serializability when locks can be placed at multiple granularity levels. It ensures that if two (or more) database objects are interrelated hierarchically, the respective transactions that acquired locks on these objects cannot conflict with one another.

Before introducing its rules, there are some additional types of locks (besides x-locks and s-locks) that needs our attention. They are

• Intention Shared Lock (is-lock): only conflicts with x-locks
• Intention Exclusive Lock (ix-lock): conflicts with both x-locks and s-locks
• Shared and Intention Exclusive Lock (six-lock): conflicts with all except is-lock

This is how the game is played: an intention lock is placed on all coarser-grained objects encompassing x, to ensure that locks are held (or granted later) on coarser-grained database objects that (1) encompass object x (2) may conflict with the lock type requested on x.

Rules of the MGL Protocol

1. All compatibilities are respected as represented in the compatibilities matrix.
2. An initial lock should be placed on the root of the hierarchy.
3. Before a transaction Ti can acquire an s-lock or an is-lock on an object x, it should acquire an is-lock or an ix-lock on the parent of x.
4. Before Ti can acquire an x-lock, six-lock, or an ix-lock on an object x, it should acquire an ix-lock or a six-lock on the parent of x.
5. Ti can only acquire additional locks if it hasn’t released any locks yet (cf. 2PL).
6. Before Ti can release a lock on x, it should have released all locks on all children of x.

Right. If we don’t really know what just happened, take this home: the MGL protocol introduces the concept of intentional locks, and all the locks are acquired top-down, but released bottom-up in the hierarchy. This maximizes the transaction efficiency while still ensuring integrity of the database objects involved.

That’s it. The concurrency and locking problems are really a mesmerizing topic to be delightfully overwhelmed, isn’t it!

文章同步發表於 Medium。