Skip to main content

The Database Systems Course Book

11 Concurrency Control

Week 11: April 17 - April 23, 2022

  • Transactions and Serializability Overview: COWS Sections 16.1-3, 17.1
  • 2PL and Locking: COWS Sections 16.4-16.6, 17.1-17.5

The DBMS relieves application developers from the burden of managing concurrent updates to a database. At the core of concurrency control is the most basic unit of DBMS change known as a transaction. In this module, we will understand (i) the different problems that could occur with poor concurrency control, (ii) the reasons for supporting concurrent updates to a DBMS, (iii) the basic properties of a transaction and (iv) how perhaps analogous to the concept of query plan optimization given a declarative query, the DBMS does not guarantee a certain ordering of transactions to enable their flexible execution in a way that maximizes parallelism.

11.1 Transactions

A transaction is the execution of a sequence of one or more operations (e.g., SQL queries) on a shared database to perform some higher level function. They are the basic unit of change in a DBMS. Transactions are atomic: i.e. partial transactions are not allowed.

What forms a transaction is determined by the application: e.g. a transaction can be a series of operations that transfer money from one bank account to another, or the purchase of a ticket, or updating a store’s inventory, etc.

The four correctness criteria are defined by the acronym ACID. These criteria are not axiomatic per se and some notions are more vaguely defined than other but they are a good way to define the basic properties that are supported by any DBMS that claims to be an ACID transactional DBMS.

  • Atomicity: All operations within a transaction happen or not happen. “All or nothing”
  • Consistency: If each transaction is consistent and the database is consistent at the beginning, the database remains consistent after the transaction. “It looks correct to me”
  • Isolation: The execution of one transaction is isolated from that of other transactions. “As if alone”
  • Durability: If a transaction commits, then its effects in the database persist: “Change survives failure”

In general there are two approaches to achieving atomicity:

  • Shadow Paging: Each transaction makes updates to a local of copy of relevant pages that are made visible (replace original) when the transaction commits.
  • Logging: A DBMS logs all the actions of a transaction to undo them if the transaction aborts. We will look more into this in the module on Recovery. Most DBMS opt for the logging approach.

Given today’s multi-core hardware architecture and the memory-storage/network imbalance, we scale our DBMS by running multiple transactions concurrently, whose operations may interleave. This interleaving of the operations within transactions that touch the same database objects can create anomalies:

  • Inconsistent Reads: A transactions A reads a partial update of another transaction B.
  • Lost Updates: A transaction A overwrites the uncommitted data of another transaction B.
  • Dirty Reads: A transaction A sees the write effects of another transaction B before B commits its changes.

The goal of concurrency control is eliminate these anomalies.

11.2 CC Formalism

A Transaction in SQL is defined by a sequence of queries within a BEGIN, and ABORT or COMMIT keywords.

  • If a transaction BEGIN, all of a transaction’s changes are saved in the database.
  • If it aborts, all its changes are rolled-back (undone) as if the transaction never happened.

The application logic needs to correctly handle exceptions caused by a transaction abort such as re-executing the transaction. The scope of the transaction is only inside a transaction, i.e. changes to the world outside the database cannot be rolled back! Just because, you reached the COMMIT statement in a transaction doesn’t mean it will commit, the result of the COMMIT command can either be a commit or an abort.

From the perspective of the concurrency control manager, a transaction is a series of read R(A) and write W(B) operations where A, B, C, … etc are named database objects. A, B, C can be tuples (usually), tables, columns, indexes, or even whole databases.

Transaction isolation is an illusion that the DBMS provides that each transaction runs alone in the system without other interleaving concurrent transactions.

If transactions are executed in serial order (one after the other, one transaction at a time) then we would get true isolation without the illusion. But we need the interleaving of concurrent transactions to get better performance.

11.2.1 Serializability

A serial schedule does not interleave the actions of different transactions.

Two schedules are equivalent if for any database state, the effect of execution the one schedule is identical to the effect of executing the other schedule.

A schedule that is equivalent to some serial execution of the transactions is serializable.

11.2.2 Conflict Serializability

Looking back at the anomalies we described earlier, we can map them to conflicts or conflicting interleaving of concurrent transactions.

  • Inconsistent Reads: Read-Write conflicts.
  • Lost Updates: Write-Write conflicts
  • Dirty Reads: Write-Read conflicts

Read-Read doesn’t create any conflict or anomalies and therefore the order of reads across two transactions can be interchanged without any difference in the result. This intuition gives rise to conflict-serializability.

Conflict-serializable schedules are equivalent to some serial schedule.

Schedule \(S\) is conflict serializable if you are able to transform \(S\) into a serial schedule by swapping consecutive non-conflicting operations of different transactions.

Not all serializable schedules are Conflict serializable, but most DBMS support this particular notion of serializability because it is the most efficient to enforce!

We can verify that a schedule is conflict-serializable using either the swapping method or dependency graphs.

Dependency Graphs (aka “precedence graph”):

  • One node per transaction \(T_i\).
  • Edge from \(T_i\) to \(T_j\) if an operation \(O_i\) of \(T_i\) conflicts with an operation \(O_j\) of \(T_j\) and \(O_i\) appears earlier in the schedule than \(O_j\) .
  • A schedule is conflict serializable if and only if its dependency graph is acyclic

11.3 CC Protocols

A concurrency control protocol is how the DBMS decides the proper interleaving of operations from multiple transactions. There are two categories of concurrency control protocols:

Pessimistic: The DBMS assumes that transactions will conflict, so it doesn’t let problems arise in the first place. We will learn more about 2-phase locking in the next module, which is a pessimistic concurrency control scheme.

Optimistic: The DBMS assumes that conflicts between transactions are rare, so it chooses to deal with conflicts when they happen. You can learn more about these schemes from the textbook.

The order in which the DBMS executes operations is called an execution schedule. The goal of a concurrency control protocol is to generate an execution schedule that is is equivalent to some serial execution.

11.3.1 Pessimistic CC with 2PL

Now that we have looked at the theory and motivation behind transactions and concurrency control. We will look at a specific, pessimistic, locking-based concurrency control mechanism known as two-phase locking or 2PL. Optionally, you can also study an optimistic concurrency control scheme, OCC, that assumes the best and handles the worst-case scenarios through aborts and roll-backs.

Two-Phase locking (2PL) is a pessimistic concurrency control protocol that determines whether a transaction is allowed to access an object in the database on the fly i.e. it does not need to know all the operations within the transactions a priori. It has two phases:

  • Growing Phase: each transaction requests the locks that it needs from the DBMS’s lock manager. The lock manager grants/denies lock requests.
  • Shrinking Phase: After releasing the first lock, the transaction enters this phase, after which it cannot acquire any new locks and can only release previously acquired lock

2PL guarantees conflict serializability: the precedence graph of the schedules is acyclic. It can result in cascading aborts however: when a transaction aborts, another may have to be rolled back resulting in wasted work.

11.3.1.1 Strict 2-Phase Locking

In this scheme, the transaction only releases locks when it finishes: it isn’t quite a shrinking phase, more of a release all at once. A schedule is strict if a value written by a transaction is not read or overwritten by other transactions until that transaction finishes. This eliminates cascading aborts.

2PL is even stricter than the class of conflict serializable schedules: i.e. potential conflict serializable schedules may not be allowed by 2PL in the first place thus limiting concurrency.

11.3.2 The Lock Manager

The DBMS contains a centralized lock manager that decides whether a transaction can have a lock or not. The lock manager thus has a global view of whats going on inside the DBMS. There are two main locks:

  • Shared Lock (S-LOCK): A lock that allows multiple transactions to read the same object at the same time. If one transaction holds a shared lock, then another transaction can acquire that same shared lock.
  • Exclusive Lock (X-LOCK): Allows a transaction to modify an object. This lock is not compatible with any other lock. Only one transaction can hold an exclusive lock at a time.

We will later see other locks that a typical DBMS supports. In general, we execute transactions with locks as follows:

  • Transactions request a lock (or upgrades it from S to X) from the lock manager.
  • The lock manager grants or blocks requests based on what locks are currently held by other transactions.
  • Transactions release locks when they no longer need them.
  • The lock manager updates its internal lock-table and then gives locks to waiting transactions.

11.3.3 Multiple Lock Granularity

If a transaction wants to update a billion tuples, it has to ask the DBMS’s lock manager for a billion locks. This will be slow because all the transactions have to go through the lock manager’s internal lock table data structure. Instead, we want to use a lock hierarchy that allow a transaction to take more coarse-grained locks in the system. Acquiring a lock for something in this hierarchy implicitly acquires a lock for all its children.

Intention locks allow a higher level node to be locked in shared or exclusive mode without having to check all descendant nodes. If a node is in an intention mode, then explicit locking is being done at a lower level.

  • Intention-Shared (IS): Indicates explicit locking at a lower level with shared locks.
  • Intention-Exclusive (IX): Indicates explicit locking at a lower level with exclusive or shared locks.
  • Shared+Intention-Exclusive (SIX): The subtree rooted at that node is locked explicitly in shared mode and explicit locking is being done at a lower level with exclusive-mode locks.

11.3.4 Dealing with Deadlocks

A deadlock is a cycle of transactions waiting for locks to be released by each other.

While there are many deadlock prevention schemes that ensure deadlocks never occur in the first place, for example, an OS can enforce an order in which locks can be acquired to prevent deadlocks (e.g. keyboard, screen, printer), such schemes are not practical in a DBMS as transactions may need to acquire locks out of order depending on the run-time behavior of the transaction.

These schemes prevent one of the four conditions of a deadlock from never occuring:

  • Mutual Exclusion
  • Hold and wait
  • No Preemption
  • Circular Wait

For example, a preeemption deadlock prevention scheme works as follows. First, it assigns priorities based on timestamps (e.g., older means higher priority). When a transaction \(T_1\) attempts to acquire a lock from \(T_2\), it can either dependening on the policy implemented:

  • Wait-Die (“Old waits for Young”): If \(T_1\) has higher priority, \(T_1\) waits for \(T_2\). Otherwise \(T_1\) aborts
  • Wound-Wait (“Young waits for Old”): If \(T_1\) has higher priority, \(T_2\) aborts. Otherwise \(T_1\) waits.

These schemes guarantee no deadlocks because only one type of direction is allowed when waiting for a lock. When a transaction restarts, its (new) priority is its old timestamp. Why so?

In a deadlock detection and resolution scheme, the DBMS creates a waits-for graph: * Nodes are transactions, with * an edge from \(T_i\) to \(T_j\) if transaction \(T_i\) is waiting for transaction \(T_j\) to release a lock.

The system will periodically check for cycles in waits-for graph and then make a decision on how to break it. You can control how often a DBMS checks for cycles in the wait-for graph as this can be an expensive operation.

When the DBMS detects a deadlock it will select a “victim” transaction to abort to break the cycle. The victim transaction will either restart or abort depending on how the application invoked it

There are multiple transaction properties to consider when selecting a victim. There is no one choice that is better than others. 2PL DBMSs all do different things:

  • By age (newest or oldest timestamp).
  • By progress (least/most queries executed).
  • By the # of items already locked.
  • By the # of transactions that we have to rollback with it.
  • By the # of times a transaction has been restarted in the past

After selecting a victim transaction to abort, the DBMS can also decide on how far to rollback the transaction’s changes. Can be either the entire transaction or just enough queries to break the deadlock.

11.4 Isolation Levels

Serializability is useful because it allows programmers to ignore concurrency issues. It comes with a cost on performance when enforced: little concurrency.

Many DBMS support and allow weaker levels of consistency to improve scalability. By choosing weaker isolation levels, you can control the extent to which a transaction is exposed to the effects of other concurrent transactions. You, thus, get greater concurrency but at the cost of: dirty reads, unrepeatable (or inconsistent) reads, etc.

In general, we have four standard isolation levels that many DBMS support some subset of:

  • Serializable: All reads are repeatable, no dirty reads. To support this, you impose a strict 2PL scheme with index locks (these protect against a special anomaly known as Phantom reads that we haven’t discussed).
  • Repeatable reads: Same as above but without the index locks.
  • Read committed: Phantoms and unrepeatable reads may happen. S-locks are released immediately. (How does this lead to greater concurrency? Well, now another transaction may acquire an X-lock).
  • Read uncommitted: all of the anomalies may happen. No S-locks!

In the SQL-92 standard, you set a transaction’s isolation level before you execute any queries in that transaction but not all DBMS support all isolation levels.

If you would like to know what isolation level Postgres and other DBMS support and what the default isolation levels are, check this blog post by Peter Bailis.