Concurrency Control

What You'll Learn This Week

• Concurrency Control
  • Locking
  • Two Phased Locking (2PL)
  • Timestamp Ordering Concurrency Control
  • Optimistic Concurrency Control
• Deadlock
  • Deadlock Prevention
  • Deadlock Detection
• Waiting Schemes for Locking
• Concurrency Control in Oracle
• Concurrency Control in Microsoft SQL Server

Concurrency Control

Elmasri/Navathe (3rd ed.)	Elmasri/Navathe (2nd ed.)	Connolly, Begg (3nd ed.)	McFadden (5th ed.)
Chapter 20	Chapter 18	Chapter 19 (19.2)	Chapter 13

• If we insist only one transaction can execute at a time, in serial order, then performance will be quite poor.

• Concurrency Control is a method for controlling or scheduling the operations of transactions in such a way that concurrent transactions can be executed safely (i.e., without causing the database to reach an inconsistent state).
• Recall the problems of lost update, Dirty Read, Incorrect Summary and Non-Repeatable Read.
  Concurrency control helps us to avoid these problems.

• If we do concurrency control properly, then we can maximize transaction throughput while avoiding any chance of corrupting the database.

• Transaction throughput: The number of transactions we can perform in a given time period. Often reported as Transactions per second (TPS) or Transaction per minute (TPM).

  See the Transaction Processing Performance Council web site for more information.

Locking

• We need a way to guarantee that our concurrent transactions can be serialized. Locking is one such means.

• Locking is done to data items in order to reserve them for future operations.
• Locks may be applied to data items in two ways:
  Implicit Locks are applied by the DBMS
  Explicit Locks are applied by application programs.

• Locks may be applied to:
  1. a single data item (value)
  2. an entire row of a table
  3. a page (memory segment) (many rows worth)
  4. an entire table
  5. an entire database
  This is referred to as the Lock granularity
• Many DBMS perform what is called lock escalation where a collection of locks at one level are replaced by fewer locks at larger granularity. For example:
  1. Suppose a table contains 100 rows.
  2. An UPDATE statement begins to work on the table by successively locking rows.
  3. At some point, the lock manager may decide to escalate the locks to the table level. i.e., a single table-level lock is applied and the individual row level locks are released.
• Lock escalation can reduce the overhead required for transaction processing.
  • Suppose data items a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z are all on the same page.
  • A transaction starts locking a, b, c, d, e, etc. individually. In all, the DBMS would need to take 26 locks.
  • However, if the DBMS recognizes all of these items are on the same page, it might "escalate" the granularity of the locks from the individual item to the page level.
  • Thus only one page level lock would need to be help (in place of the 26 item level locks).
• There are situations, however, where lock escalation can cause deadlocks to occur.
• Oracle supports row-level and table-level locking without lock escalation.
  Sybase and SQL Server support lock escalation.

• Locks may be of two types depending on the requirements of the transaction:
  1. An Exclusive Lock prevents any other transaction from reading or modifying the locked item.
  2. A Shared Lock allows another transaction to read an item but prevents another transaction from writing the item.

Two Phased Locking (2PL)

• The most commonly implemented locking mechanism is called Two Phased Locking or 2PL. 2PL is a concurrency control mechanism that ensures serializability.

• 2PL has two phases: Growing and shrinking.
  1. A transaction acquires locks on data items it will need to complete the transaction. This is called the growing phase.
  2. Once one lock is released, all no other lock may be acquired. This is called the shrinking phase.

• Consider our prior example, this time using locks:

  User A places an exclusive lock on the balance
  User A reads the balance
  User A deducts $100 from the balance
  
  User B attempts to place a lock on the balance 
         but fails because A already has an exclusive lock
         User B is placed into a wait state
  User A writes the new balance of $100
  User A releases the exclusive lock on the balance
  
  User B places an exclusive lock on the balance
  User B reads the balance
  User B deducts $100 from the balance
  User B writes the new balance of $100
  

• Here is a more involved example:

  User A places a shared lock on item raise_rate
  User A reads raise_rate
  User A places an exclusive lock on item Amy_salary
  User A reads Amy_salary
  
  User B places a shared lock on item raise_rate
  User B reads raise_rate
  
  User A calculates a new salary as Amy_salary * (1+raise_rate)
  
  User B places an exclusive lock on item Bill_salary
  User B reads Bill_salary
  User B calculates a new salary as Bill_salary * (1+raise_rate)
  User B writes Bill_salary
  
  User A writes Amy_salary
  User A releases exclusive lock on Amy_salary
  
  User B releases exclusive lock on Bill_Salary
  User B releases shared lock on raise_rate
  
  User A releases shared lock on raise_rate
  

• Here is another example:

  User A places a shared lock on raise_rate
  
  User B attempts to place an exclusive lock on raise_rate
         Placed into a wait state
  
  User A places an exclusive lock on item Amy_salary
  User A reads raise_rate 
  User A releases shared lock on raise_rate
  
  User B places an exclusive lock on raise_rate
  
  User A reads Amy_salary
  
  User B reads raise_rate
  
  User A calculates a new salary as Amy_salary * (1+raise_rate)
  
  User B writes a new raise_rate
  User B releases exclusive lock on raise_rate
  
  User A writes Amy_salary
  User A releases exclusive lock on Amy_salary
  
  

• In basic 2PL, transactions get locks as they need them and release them as soon as possible.
• Two variations of 2PL: Conservative and Strict
  • With Conservative 2PL, the transaction pre-declares which items it will work with and it acquires all locks before any work is done.
  • With Strict 2PL, once all operations are completed, all of the locks are released after commit.
• Consider T: Ra Wa Rb Wb Rc Wc Rd Wd

  R = Read. W = write. L = Lock. U = Unlock.

  Conservative:  
    TLa TLb TLc Tld TRa Twa TUa Rb Wb TUb Rc Wc TUc Rd Wd TUd
  
  Strict:
     TLa TRa Twa TLb TLc Rb Wb TLd Rc Wc Rd Wd TUa TUb TUc TUd
  
  

Timestamp Ordering

• The timestamp of a transaction T is the time at which that transaction was initiated in the DBMS: TS(T)
• We can use clock time or an incremental identifier (counter) for TS(T)
• Two timestamps are also associated with each data item x.
  1. read_TS(x) is the TS(T) of the last transaction T to read from x.
  2. write_TS(x) is the TS(T) of the last transaction T to write to x.

• Two simple rules to follow:
  1. Before T issues a write(x), check to see if
     TS(T) < read_TS(x) or if
     TS(T) < write_TS(x)
     If so, then abort transaction T.
     If not, then perform write(x) and set write_TS(x) = TS(T).
  2. Before T issues a read(x), check to see if
     TS(T) < write_TS(x) Then abort transaction T.
     if TS(T) >= write_TS(x) then execute read(x) and set read_TS(x) = TS(T) only if TS(T) is greater than the current read_TS(x).
• When a transaction is aborted, it is the restarted and issued a new TS(T).

• Note that with timestamp ordering, deadlock can not occur.
• However, starvation is possible i.e., a transaction keeps getting aborted over and over.

• Timestamp ordering can also produce cascading rollbacks:
  • Assume transaction T begins executing and performs some read and write operations on data items a, b and c
  • However, T then reaches a data item it can not read or write and T must then be aborted.
  • Any effects of transaction T must then be rolled back.
  • Before T aborts, however, other transactions (T1, T2 and T3) have read and written data items a, b and c so these other transactions must also be rolled back.
  • There may be other transactions (T4 and T5) that worked with data items read or written by T1, T2 and T3, etc.

Optimistic Concurrency Control

• Two Phase Locking (2PL) and Timestamp Ordering (TO) are pessimistic concurrency control protocols - they assume transactions will conflict and take steps to avoid it.
• i.e., they address the concurrency issues before while the transaction is executing and before the transaction commits.
• 2PL and TO are also syntactic concurrency control protocols as they deal only with the syntax (set of read and write operations) of the transactions.
• In an optimistic concurrency control protocol, we assume that most of the time, transactions will not conflict thus all of the locking and timestamp checking are not necessary.
• There are a number of different optimistic CC protocols. Elmasri/Navathe describe an optimistic/syntactic concurrency control protocol.
• Three stages:
  1. Read Stage: Transactions can read any data item. Writes are done to a local copy of the data item e.g., recorded in a log.
  2. Validation stage: Transactions containing Write operations that are about to commit are validated to see if the schedule meets the serializability requirements.
  3. Write stage: If the transaction will not conflict with other transactions, then it will be committed (writes to local copy applied to the database). Otherwise, the transaction will be rolled back.

• There are also a number of optimistic/semantic concurrency control protocols that take into account the semantics of the database application and schedule transactions accordingly.
• Examples include databases that are "read mostly" or "read only".

Deadlock

• Locking can cause problems, however.
• Consider:

  Transaction A places an exclusive lock on item 1001
  Transaction B places an exclusive lock on item 2002
  Transaction A attempts to place an exclusive lock on item 2002
         Transaction A placed into a wait state
  Transaction B attempts to place an exclusive lock on item 1001
         Transaction B placed into a wait state
  ...
  
  

• This is called a deadlock. One transaction has locked some of the resources and is waiting for locks so it can complete. A second transaction has locked those needed items but is awaiting the release of locks the first transaction is holding so it can continue.

• Two main ways to deal with deadlock.
  1. Prevent it in the first place by giving each transaction exclusive rights to acquire all locks needed before proceeding.
  2. Allow the deadlock to occur, then break it by aborting one of the transactions.

• If we employ conservative two phase locking, then deadlocks will not occur.
• That is, we acquire all locks needed for the entire transaction at the beginning,

Deadlock Prevention

• Timestamp all transactions TS(T).
• Assume Tj acquires a lock and then Ti comes along and tried to lock the same item:
  1. Wait-die - If TS(Ti) < TS(Tj) then allow Ti to wait for Tj to release its lock.
     Otherwise, abort and restart Ti with the same timestamp.
  2. Wound-wait - If TS(Ti) < TS(Tj) then abort Tj and restart Tj with the same timestamp
     Otherwise, let Ti wait for Tj to release its lock.
  start start attempt Tx Ty TyLa TxLa +--------+--------+--------+--------+--------+--------+ 1 2 3 4 5 6 7... time -> Tx starts at time 1 so TS(Tx) = 1
  Ty starts at time 2 so TS(Ty) = 2
  Ty has already locked item a and now Tx attempts to lock item a.

  Under Wait-Die: TS(Tx) < TS(Ty) so Tx will wait for Ty to release the lock.
  In other words, since Tx started first, it gets the privilege of waiting.

  Under Wound Wait: TS(Tx) < TS(Ty) so Ty will be aborted.
  In other words, since Tx started first, it has the privilege of kicking Ty out of the way by aborting it. So now Tx can proceed.

• Without timestamps:
  1. No wait - If Ti tries to access a data item that Tj has locked, Ti is aborted.
  2. Cautious Waiting - If Ti tries to access a data item that Tj has locked then
     If Tj is not waiting on another resource, allow Ti to wait for Tj to release the lock.

Deadlock Detection

• Another approach is to allow deadlocks to occur. Then detect them and abort one of the transactions to break the deadlock.

• We can use Timeouts to abort and transaction that is active for more than a given period of time,

• A Wait-for graph can be constructed:
  1. For each transaction T currently running, draw a node.
  2. If Transaction Ti is waiting for a resource transaction Tj has locked, draw a directed arc from Ti to Tj.
  3. When Tj releases the lock, erase the arc.
  4. If we can find a cycle, then a deadlock exists.
  5. Abort one of the transactions to break the cycle.

• Example:

  T1: Ra Wa Rb Wb Rc Wc Rd Wd Re We
  T2: Re We Ra Wa Rb Wb Rh Wh
  T3: Rf Wf Rb Wb 
  
  T1 has done the following:      Ra Wa Rb Wb Rc Wc Rd Wd
  T2 has done the following:      Re We 
  T3 has done the following:      Rf Wf
  

• So we have T1 waiting for T2 to release data item e
  T2 is waiting for T1 to release data item a
  and T3 is waiting for T1 to release data item b
• The above situation results in the following wait-for graph:

  

  Since we see a directed cycle between T1 and T2, we know there is a deadlock condition between those two transactions (note there is no deadlock between T1 and T3).

• Oracle uses the wait-for graph method.

• Problem: Which transaction should we abort ? i.e., how do we choose a victim ?
• One approach: Keep track of how much work transactions have done (read/write operations) and abort the transaction with the least done.
  
• Look at number of operations completed as a percentage of total operations. For example:

  T1: Ra Wa Rb Wb Rc Wc Rd Wd Re We
  T2: Re We Ra Wa Rb Wb Rh Wh
  T3: Rf Wf Rb Wb 
  
  T1 has done the following:     Ra Wa Rb Wb Rc Wc Rd Wd
  T2 has done the following:     Re We 
  
  Which should we abort? Which has done the most work?
  

• Starvation occurs when a transaction is repeatedly chosen as the victim (aborted).

  In the above example, suppose we choose to abort T2. Before T2 gets a chance to start again, T3 executes: Rf Wf
  Can T2 proceed?

Waiting Schemes for Locking

• A waiting scheme is the mechanism for arbitrating the locking order of a data item for multiple transactions.
• Assume T2 and T3 are both waiting for T1 to release a lock on some data item.
  Which transaction should get to lock the data item next?
  • First In First out (FIFO)
    If T2 was submitted to the system before T3, then T2 should get to lock the item once T1 is done
  • Order according to amount of work to be done.
    Suppose T2 has 100 operations of which it has completed 2.
    Suppose T3 has 10 operations of which is has completed 8.
    We let T3 get the data item next since it is closest to completion (80% done as opposed to T2 which has only done 2%)
• Livelock occurs when a transaction can not proceed but other transactions continue normally. This can be due to an unfair waiting scheme.

  In the above example, T2 may be kept waiting forever if other transactions are allowed to go before it.

  Note that T2 is never aborted (as is the case in starvation), it just makes no forward progress.

Oracle Implementation of Concurrency and Transaction Isolation

• For a general overview of how Oracle handles recovery see Chapter 27 Database Recovery in the book Oracle9i Server Concepts
  • Oracle maintains Rollback segments that store the old values of active transactions (what we called Before images). This allows any transaction to see a consistent state of the database by either viewing current data in the data files or prior data in the rollback segment.
  • Caching of reads and writes is a major performance feature of Oracle. The System Global Area (SGA) contains (among other things) a cache of recently used data. Recently used data can be data that was just read or written.
    Thus if a failure occurs, and writes have not been flushed from the cache to disk, data would be lost...however, see REDO log:
  • Oracle also maintains a REDO log containing all changes made to the database whether these are made to data on disk or to the cache. This is recorded for both active and committed transactions.
    A transaction must record its operations in the REDO log first (what we called Write Ahead Logging - WAL).
  • The REDO log allows Roll forward by applying any changes to the data files.
  • The Rollback Segment allows rolling back of transactions that did not yet commit (were active) at the time of failure.
  • The Oracle Recovery manager maintains a recovery catalog that keeps track of all this stuff...

• Oracle provides several mechanisms for controlling how transaction are executed (this also affects recovery).
• In general, Oracle provides an Optimistic approach to CC
• With Discrete Transactions, all changes to data are deferred until the transaction commits.
• At the same time, no other transaction may read any items locked by the discrete transaction.
• The discrete transaction mode can be set as an option in the database engine.
• To use discrete transactions, a special stored procedure is invoked as in this PL/SQL example:

  BEGIN
    dbms_transaction.begin_discrete_transaction;
    UPDATE employee 
    SET    salary = salary * 1.02
    WHERE  dno = 5;
    EXCEPTION 
      WHEN dbms_transaction.discrete_transaction_failed
      THEN 
        ROLLBACK; 
      END; 
  END;
  

• The TRANSACTION ISOLATION level can also be set:
  • SERIALIZABLE - Highest level of isolation. Other transactions can not see the effects until after commit. Also provides repeatable reads (Same as Degree 3 in last week's notes)
  • READ COMMITTED - Other transactions can read the effects as the transaction is running. This is the default.
• The SET TRANSACTION ISOLATION statement can be used to specify the isolation level for each transaction.

• For more details, see Data Concurrency and Consistency in the Oracle8i Concepts Release 2 (8.1.6) Part number: A76965-01
• Also see Database Backup and Recovery in the same document: Oracle8i Concepts Release 2 (8.1.6) Part number: A76965-01

MS SQL Server Support for Locking

• Within SQL Server Enterprise Manager, one can see which processes are holding locks on which items (not the LOCK TYPE, MODE and STATUS).

  

• According to the MS SQL Server 2000 on-line manuals:
• Lock Type:
  • RID Row identifier. Used to lock a single row individually within a table.
  • KEY Key; a row lock within an index. Used to protect key ranges in serializable transactions.
  • PAG Data or index page.
  • EXT Contiguous group of eight data pages or index pages.
  • TAB Entire table, including all data and indexes.
  • DB Database.
• Lock Mode:
  • Lock mode Shared (S) Used for operations that do not change or update data (read-only operations), such as a SELECT statement.
  • Update (U) Used on resources that can be updated. Prevents a common form of deadlock that occurs when multiple sessions are reading, locking, and then potentially updating resources later.
  • Exclusive (X) Used for data modification operations, such as UPDATE, INSERT, or DELETE. Ensures that multiple updates cannot be made to the same resource at the same time.
  • Intent Used to establish a lock hierarchy.
  • Schema Used when an operation dependent on the schema of a table is executing. There are two types of schema locks: schema stability (Sch-S) and schema modification (Sch-M).
  • Bulk update (BU) Used when bulk copying data into a table and the TABLOCK hint is specified.
  • RangeS_S Shared range, shared resource lock; serializable range scan.
  • RangeS_U Shared range, update resource lock; serializable update scan.
  • RangeI_N Insert range, null resource lock. Used to test ranges before inserting a new key into an index.
  • RangeX_X Exclusive range, exclusive resource lock. Used when updating a key in a range.
• Lock Status:
  • GRANT - Lock was obtained.
  • WAIT - Lock is blocked by another process.
  • CNVT - Lock is being converted to another lock. A lock being converted to another lock is held in one mode but is waiting to acquire a stronger lock mode (for example, update to exclusive). When diagnosing blocking issues, a CNVT can be considered similar to a WAIT.