#Practical Session 9 - Transaction Processing & Concurrency Control
###By Dr Edmund Sadgrove
### University of New England
---
## Reading
* Chapter 20 from ***Fundamentals of Database Systems*** by Elmazri and Navathe
---
## Summary
* Introduction
* Transaction Processing
* Concurrency Control
* Locking Techniques
* Two Phase Locking
* Timestamp Ordering
* Deadlock
## Introduction
* Transaction processing is required to aid recovery from interleaved transactions. We will recap some of this weeks lectures and look at a few examples.
## Transaction Processing
* A **transaction** forms a logical unit of processing within the database.
* Transaction operations can be:
* **Read-only**:
* Retrieves data only.
* **Read-write**:
* Retrieves and manipulates data.
* Transactions are composed of two basic operations:
* **read_item(X)**:
* Read data item *X* into the main memory for processing.
* Where *X* is a program variable - e.g. record.
* **write_item(X)**:
* Copy a data item *X* from main memory into the database on disk.
* The **read_item(X)** operation can be broken down into a series of individual operations:
1. Find the address of the **disk block** that contains item X.
2. Copy that disk block into a **buffer** in main memory.
3. Copy item X from the buffer to the program variable named X.
* The **write_item(X)** operation can be broken down into a series of individual operations:
1. Find the address of the disk block that contains item X.
2. Copy that disk block into a **buffer** in main memory.
3. Copy item X from the program variable named X into the correct **buffer**.
4. Store the updated block from the buffer back **to disk**.
* Problem 1: The lost update problem.
* The operations are interleaved in such a way that an outdated value is written back to the database.
## Concurrency Control
* Problem 2: The temporary update problem.
* A value is read by T2 before a failed transaction (T1) has been rolled back.
* Problem 3: The incorrect summary problem.
* Values in an aggregate operation are updated during the execution.
* Problem 4: The unrepeatable read problem:
* **Occurs when**:
* Transaction *T* reads the same item twice.
* The item is changed by another transaction *T* between the two reads.
* E.g. item availability in online sales.
* The transaction processing system needs to be implemented so that actions in response to database values are executed *atomically* with the read operation.
## Locking Techniques
* The first **concurrency control technique** we will look at involves using ***locks***:
* A variable associated with a data item that describes its status.
* These are used to *synchronise access* to the associated data items.
* The simplest locking scheme uses *binary locks*.
* **Binary locks** have two states:
* **Locked** - not accessible.
* **Unlocked** - accessible.
* Two operations **`lock(X)`** and **`unlock(X)`** is used to implement a **critical section**.
* These cannot be interleaved.
* **`lock(X)`**:
* Called when a transaction is executed on *X*.
* If another operation holds the lock on *X*
* The `lock(X)` operation is forced to wait.
* **`unlock(X)`**:
* Called once the transaction is completed.
* This is usually implemented as a variable with values of **`0`** for unlocked and **`1`** for locked.
* Rules that govern the **critical section**:
1. A transaction *T* must issue the operation **`lock_item(X)`** before any **`read_item(X)`** or **`write_item(X)`** operations are performed in *T*.
2. A transaction *T* must issue the operation **`unlock_item(X)`** after all **`read_item(X)`** and **`write_item(X)`** operations are completed in *T*.
3. A transaction *T* will not issue a **`lock_item(X)`** operation if it already holds the lock on item *X*.
4. A transaction *T* will not issue an **`unlock_item(X)`** operation unless it already holds the lock on item *X*.
* A **problem**: Binary locking is too restrictive:
* Only one transaction can access an individual data item at a time.
* This is not scalable - should allow **concurrent/shared** reads.
* A **transaction** should still require an **exclusive lock** for *write* operations.
* This introduces **shared/exclusive** locking.
* It has three operations:
* **`read_lock(X)`**
* **`write_lock(X)`**
* **`unlock(X)`**
* This scheme will usually be implemented by keeping track of the number of items that have a read lock on the item.
* Pseudocode for **`read_lock(X)`** algorithm.
```
read_lock(X):
B: if LOCK(X) = “unlocked”
then begin
LOCK(X) ← “read-locked”;
no_of_reads(X) ←1
end
else if LOCK(X) = “read-locked”
then
no_of_reads(X) ← no_of_reads(X) + 1
else begin
wait (until LOCK(X) = “unlocked”
and the lock manager wakes up the transaction);
go to B
end;
```
* This records the number of reads, each `unlock` will decrement `no_of_reads`. This means `read_lock`s will not interfer with eachother.
* Pseudocode for **`write_lock(X)`** algorithm.
```
write_lock(X):
B: if LOCK(X) = “unlocked”
then LOCK(X) ← “write-locked”
else begin
wait (until LOCK(X) = “unlocked” and the lock manager wakes up the transaction); go to B
end;
```
* A locked item causes a `sleep` operation, this is the default behavour, but more advanced options are available - discussed later.
* Pseudocode for **`unlock(X)`** algorithm.
```
unlock(X):
if LOCK(X) = “write-locked”
then begin
LOCK(X) ← “unlocked”;
wakeup one of the waiting transactions, if any
end
else if LOCK(X) = “read-locked”
then begin
no_of_reads(X) ←no_of_reads(X) −1;
if no_of_reads(X) = 0
then begin
LOCK(X) = “unlocked”;
wakeup one of the waiting transactions, if any
end;
end;
```
* `Write_lock`s are unlocked, while `read_lock`s are decremented so that other `read_lock`s are not interrupted.
* The read/write locking scheme can be modified to include the option of **lock conversion**.
* A **read lock** conversion:
* If a transaction is the only one to hold a **read lock** on an item:
* This item can be upgraded to a **write lock**.
* A transaction can also **down-grade** a **lock** from a **write lock** to a **read lock**.
* **Problem**: These locking rules do not guarantee a **serialisable** schedule.
* The order of the **lock/unlock** block pairs is not controlled under the current scheme.
* Additional rules are required:
* This will ensure that the schedules are serialisable.
* E.g. the order of the **lock/unlock** blocks is actually enforced.
* This can be solved by using a *two phase* locking scheme.
* **Two phase locking** scheme:
* **Expansion phase**:
* New read/write locks on items can be obtained but none released.
* **Shrinking phase**:
* Locks on items are released and none can be obtained.
* It can be proved that if *every* transaction in a schedule uses this scheme, the schedule is guaranteed to be **serialisable**.
* Two-phase locking limits concurrency:
* Requires some transactions to wait for locks.
* Restricts the order operations execute - forcing consistent results.
* **Deadlocks** can occur due to order restrictions.
## Deadlock
* **Deadlocks** can occur when:
1. A transaction *T1* is waiting for an item that is **locked** by *T2*.
2. A transaction *T2* is waiting for an item that is **locked** by *T1*.
3. Both *T2* and *T2* cannot release **locked** items until the read/wait process is complete.
* The situation will never resolve itself - one needs to be aborted.
## Timestamp Ordering
* **Serialisability** can be achieved by ordering based on a **timestamp** value.
* Two values are maintained:
* **`read_TS(X)`**:
* The newest timestamp of a transaction to have executed a read on *X*
* **`write_TS(X)`**:
* The newest timestamp of a transaction to have executed a write on *X*
* This alleviates the occurrence of **dead locks**. Another option is to simply use a **serial number** that is incremented for each new transaction.
* **Timestamp** ordering works by comparing **`read_TS(X)`** or **`write_TS(X)`**:
* If the transactions timestamp is *older* than `read_TS(X)` or `write_TS(X)`:
* An order **violation** has occurred and the **transaction** is aborted.
* A younger transaction has already written/read the item.
* The aborted transaction must be re-run with a new timestamp.
* One variation on this approach is *strict timestamp ordering*:
* The transaction is delayed until the last updated on item *X* is committed.
* This avoids complex cascading **roll-back** operation.
## Deadlock
* Transaction **Timestamps** can be used to decide which transaction to **abort**:
* **Wait-die**:
1. If TS(Ti) < TS(Tj), Ti is allowed to wait;
2. Otherwise Ti is aborted.
* **Wound-wait**:
1. If TS(Ti) < TS(Tj), then abort Tj and restart it later with same timestamp;
2. Otherwise Ti is allowed to wait.
* Other options:
* **No-waiting**: Transactions unable to obtain a **lock** are immediately **aborted** and restarted later. on.
* **Cautious waiting**: If Ti requests an item lock from a blocked transaction Tj, Ti is **aborted**.
---
## Exercises for You
Examine the following transaction problems and provide feedback based on the individual exercises.
### For each of the following transactions, name the problem found and identify a potential solution.
### 1. Problem 1:
Initial state: X = 100
Intent:
- T1: add +50 to X
- T2: add +10 to X
Outcome: Final X = 110
| Step | T1 (Operations) | T2 (Operations) |
|:----:|:--------------------------------------------------|:--------------------------------------------------|
| 1 | x1 := read(X) -- x1=100 | |
| 2 | | x2 := read(X) -- x2=100 |
| 3 | x1 := x1 + 50 -- x1=150 | |
| 4 | write(X := x1) -- DB X=150 | |
| 5 | | x2 := x2 + 10 -- x2=110 |
| 6 | | write(X := x2) -- DB X=110 (overwrites 150) |
| 7 | commit | |
| 8 | | commit |
Final DB: X = 110 (T1’s +50 lost)
### 2. Problem 2:
Initial state: X = 100, Y = 0 (Y is derived using X; e.g., Y stores a computed tax)
Intent:
- T1: temporarily raises X by +50, but later aborts
- T2: reads uncommitted X and computes Y = 10% of X
| Step | T1 (Operations) | T2 (Operations) |
|:----:|:--------------------------------------------------|:--------------------------------------------------|
| 1 | x := read(X) -- x=100 | |
| 2 | x := x + 50 -- x=150 | |
| 3 | write(X := x) -- DB X=150 (UNCOMMITTED) | |
| 4 | | x2 := read(X) -- sees 150 (dirty read) |
| 5 | | y := 0.10 * x2 -- y=15 |
| 6 | | write(Y := y) -- DB Y=15 |
| 7 | abort (rollback X to 100) | |
| 8 | | commit |
Final DB: X = 100 (rolled back), Y = 15 (committed from dirty read) → inconsistent
### 3. Problem 3:
Initial state: A = 100, B = 100 (T2 transfers 10 from A to B; total should remain 200)
Intent:
- T1: compute SUM(A, B)
- T2: transfer 10 from A to B (A := A-10; B := B+10)
| Step | T1 (Operations) | T2 (Operations) |
|:----:|:--------------------------------------------------|:--------------------------------------------------|
| 1 | sum := 0 | |
| 2 | a := read(A) -- a=100 | |
| 3 | sum := sum + a -- sum=100 | |
| 4 | | a2 := read(A) -- 100 |
| 5 | | a2 := a2 - 10 -- 90 |
| 6 | | write(A := a2) -- DB A=90 |
| 7 | | b2 := read(B) -- 100 |
| 8 | | b2 := b2 + 10 -- 110 |
| 9 | | write(B := b2) -- DB B=110 |
| 10 | b := read(B) -- b=110 | |
| 11 | sum := sum + b -- sum=210 | |
| 12 | output(sum=210) | commit |
| 13 | commit | |
Final DB: A=90, B=110, total=200; T1 reported 210
### 4. Problem 4:
Initial state: P = 100 (price)
Intent:
- T1: reads P twice
- T2: updates P in between
| Step | T1 (Operations) | T2 (Operations) |
|:----:|:--------------------------------------------------|:--------------------------------------------------|
| 1 | p1 := read(P) -- p1=100 | |
| 2 | (do other work) | |
| 3 | | p2 := read(P) -- 100 |
| 4 | | p2 := 120 |
| 5 | | write(P := p2) -- DB P=120 |
| 6 | | commit |
| 7 | p3 := read(P) -- p3=120 (differs from p1=100) | |
| 8 | commit | |
Final DB: P=120;
### 5. Problem 5:
Initial state: A = 100, B = 100
Intent:
- T1: transfer 10 from A to B
- T2: transfer 20 from B to A
| Step | T1 (Operations) | T2 (Operations) |
|:----:|:--------------------------------------------------|:--------------------------------------------------|
| 1 | read_lock(A) -- granted | |
| 2 | a1 := read(A) -- 100 | |
| 3 | | read_lock(B) -- granted |
| 4 | | b2 := read(B) -- 100 |
| 5 | request write_lock(B) -- WAIT (T2 holds read) | |
| 6 | | request write_lock(A) -- WAIT (T1 holds read) |
| 7 | | |
| 8 | (victim chosen: T2 aborted, releases locks) | abort; unlock(B) |
| 9 | write_lock(B) -- now granted | |
| 10 | upgrade A: write_lock(A) -- granted | |
| 11 | a1 := a1 - 10 -- 90 | |
| 12 | write(A := 90) | |
| 13 | b1 := read(B) -- 100 | |
| 14 | b1 := b1 + 10 -- 110 | |
| 15 | write(B := 110) | |
| 16 | commit; unlock(A); unlock(B) | |
Final DB: A=90, B=110;