COMP9315 Week 09 Thursday Lecture

COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [0/49]
❖ Things To Note

COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [1/49]
❖ Transactions: the story so far

Transactions should obey ACID properties

Isolation can be compromised by uncontrolled concurrency

Serializable schedules avoid potential update anomalies

Styles of concurrency control

COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [2/49]
❖ Lock-based Concurrency control

Synchronise access to shared data items via following rules:

These rules alone do not guarantee serializability.

Need two-phase locking protocol for serializability.

Other issues with locking: starvation, deadlock

COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [3/49]
❖ Deadlock

Deadlock occurs when two transactions are waiting for a lock on an item held by the other.

Example:

T1: Lw(A) R(A)            Lw(B) ......
T2:            Lw(B) R(B)       Lw(A) .....

How to deal with deadlock?

COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [4/49]
❖ Deadlock (cont)

Handling deadlock involves forcing a transaction to "back off"

COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [5/49]
❖ Deadlock (cont)

Methods for managing deadlock

COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [6/49]
❖ Deadlock (cont)

Properties of deadlock handling methods:

COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [7/49]
❖ Exercise: Deadlock Handling

Consider the following schedule on four transactions:

T1:  R(A)      W(C)                          W(D)
T2:       R(B)                     W(C)
T3:                 R(D)      W(B)
T4:                      R(E)           W(A)

Assume that:

Show how the wait-for graph for the locks evolves.

Show how any deadlocks might be resolved via this graph.

COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [8/49]
❖ Optimistic Concurrency Control

Locking is a pessimistic approach to concurrency control:

Costs: lock management, deadlock handling, contention.

In scenarios where there are far more reads than writes ...

Optimistic concurrency control (OCC) is a strategy to realise this.
COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [9/49]
❖ Optimistic Concurrency Control (cont)

Under OCC, transactions have three distinct phases:

Timestamps are recorded at points S, V, F :

[Diagram:Pics/txproc/occ-phases.png]

COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [10/49]
❖ Optimistic Concurrency Control (cont)

Data structures needed for validation:

Use the V  timestamps as ordering for transactions
COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [11/49]
❖ Optimistic Concurrency Control (cont)

Two-transaction example:

Case 0: serial execution ... no problem

[Diagram:Pics/txproc/occ0.png]

COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [12/49]
❖ Optimistic Concurrency Control (cont)

Case 1: reading overlaps validation/writing

[Diagram:Pics/txproc/occ1.png]

COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [13/49]
❖ Optimistic Concurrency Control (cont)

Case 2: reading/validation overlaps validation/writing

[Diagram:Pics/txproc/occ2.png]

COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [14/49]
❖ Optimistic Concurrency Control (cont)

Validation check for transaction T

If this check fails for any Ti, then T  is rolled back.
COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [15/49]
❖ Optimistic Concurrency Control (cont)

OCC prevents:   T  reading dirty data,   T  overwriting Ti's  changes

Problems with OCC:

** "Roll back" is relatively cheap
COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [16/49]
❖ Optimistic Concurrency Control

Locking is a pessimistic approach to concurrency control:

Costs: lock management, deadlock handling, contention.

In scenarios where there are far more reads than writes ...

Optimistic concurrency control (OCC) is a strategy to realise this.
COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [17/49]
❖ Optimistic Concurrency Control (cont)

Under OCC, transactions have three distinct phases:

Timestamps are recorded at points S, V, F :

[Diagram:Pics/txproc/occ-phases.png]

COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [18/49]
❖ Optimistic Concurrency Control (cont)

Data structures needed for validation:

Use the V  timestamps as ordering for transactions
COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [19/49]
❖ Optimistic Concurrency Control (cont)

Two-transaction example:

Case 0: serial execution ... no problem

[Diagram:Pics/txproc/occ0.png]

COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [20/49]
❖ Optimistic Concurrency Control (cont)

Case 1: reading overlaps validation/writing

[Diagram:Pics/txproc/occ1.png]

COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [21/49]
❖ Optimistic Concurrency Control (cont)

Case 2: reading/validation overlaps validation/writing

[Diagram:Pics/txproc/occ2.png]

COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [22/49]
❖ Optimistic Concurrency Control (cont)

Validation check for transaction T

If this check fails for any Ti, then T is rolled back.
COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [23/49]
❖ Optimistic Concurrency Control (cont)

OCC prevents: T reading dirty data, T overwriting Ti's changes

Problems with OCC:

** "Roll back" is relatively cheap
COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [24/49]
❖ Multi-version Concurrency Control

Multi-version concurrency control (MVCC) aims to

Achieves this by Main difference between MVCC and standard locking:
COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [25/49]
❖ Multi-version Concurrency Control (cont)

WTS = timestamp of tx that wrote this data item

Chained tuple versions:   tupoldest → tupolder → tupnewest

When a reader Ti  is accessing the database

COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [26/49]
❖ Multi-version Concurrency Control (cont)

When a writer Ti  attempts to change a data item


Some MVCC versions also maintain RTS (TS of last reader)
COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [27/49]
❖ Multi-version Concurrency Control (cont)

Advantage of MVCC

Disadvantages of MVCC Despite apparent disadvantages, MVCC is very effective.
COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [28/49]
❖ Multi-version Concurrency Control (cont)

Removing old versions:

When to make this check? PostgreSQL uses the latter (vacuum).
COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [29/49]
❖ Concurrency Control in PostgreSQL

PostgreSQL uses two styles of concurrency control:

From the SQL (PLpgSQL) level:
COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [30/49]
❖ Concurrency Control in PostgreSQL (cont)

PostgreSQL provides read committed and serializable isolation levels.

Using the serializable isolation level, a select:

Using the serializable isolation level, an update fails: The transaction containing the update must then rollback and re-start.
COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [31/49]
❖ Concurrency Control in PostgreSQL (cont)

Implementing MVCC in PostgreSQL requires:

COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [32/49]
❖ Concurrency Control in PostgreSQL (cont)

Rules for a tuple to be visible to Ti :

For details, see: utils/time/tqual.c
COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [33/49]
❖ Concurrency Control in PostgreSQL (cont)

Tx's always see a consistent version of the database.

But may not see the "current" version of the database.

E.g. T1 does select, then concurrent T2 deletes some of T1's selected tuples

This is OK unless tx's communicate outside the database system.

E.g. T1 counts tuples; T2 deletes then counts; then counts are compared

Use locks if application needs every tx to see same current version

COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [34/49]
❖ Exercise: Locking in PostgreSQL

How could we solve this problem via locking?


create or replace function
    allocSeat(paxID int, fltID int, seat text)
    returns boolean
as $$
declare
    pid int;
begin
    select paxID into pid from SeatingAlloc
    where  flightID = fltID and seatNum = seat;
    if (pid is not null) then
        return false;  -- someone else already has seat
    else
        update SeatingAlloc set pax = paxID
        where  flightID = fltID and seatNum = seat;
        commit;
        return true;
    end if;
end;
$$ langauge plpgsql;

COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [35/49]
❖ Implementing Atomicity/Durability

COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [36/49]
❖ Atomicity/Durability

Reminder:

Transactions are atomic

Transaction effects are durable
Implementation of atomicity/durability is intertwined.
COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [37/49]
❖ Durability

What kinds of "system failures" do we need to deal with?

The last requires off-site backup; all others should be locally recoverable.

COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [38/49]
❖ Durability (cont)

Consider following scenario:

[Diagram:Pics/txproc/crash.png]

Desired behaviour after system restart:

COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [39/49]
❖ Durability (cont)

Durabilty begins with a stable disk storage subsystem


We can prevent/minimise loss/corruption of data due to:
COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [40/49]
❖ Dealing with Transactions

The remaining "failure modes" that we need to consider:


Standard technique for managing these:
COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [41/49]
❖ Architecture for Atomicity/Durability

How does a DBMS provide for atomicity/durability?


[Diagram:Pics/txproc/arch.png]

COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [42/49]
❖ Execution of Transactions

Transactions deal with three address spaces:

Each of these may hold a different "version" of a DB object.


PostgreSQL processes make heavy use of shared buffer pool

⇒ transactions do not deal with much local data.

COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [43/49]
❖ Execution of Transactions (cont)

Operations available for data transfer:

READ/WRITE are issued by transaction.

INPUT/OUTPUT are issued by buffer manager (and log manager).

INPUT/OUTPUT correspond to getPage()/putPage() mentioned above

COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [44/49]
❖ Execution of Transactions (cont)

Example of transaction execution:

-- implements A = A*2; B = B+1;
BEGIN
READ(A,v); v = v*2; WRITE(A,v);
READ(B,v); v = v+1; WRITE(B,v);
COMMIT

READ accesses the buffer manager and may cause INPUT.

COMMIT needs to ensure that buffer contents go to disk.

COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [45/49]
❖ Execution of Transactions (cont)

States as the transaction executes:


t   Action        v  Buf(A)  Buf(B)  Disk(A)  Disk(B)
-----------------------------------------------------
(0) BEGIN         .      .       .        8        5
(1) READ(A,v)     8      8       .        8        5
(2) v = v*2      16      8       .        8        5
(3) WRITE(A,v)   16     16       .        8        5
(4) READ(B,v)     5     16       5        8        5
(5) v = v+1       6     16       5        8        5
(6) WRITE(B,v)    6     16       6        8        5
(7) OUTPUT(A)     6     16       6       16        5
(8) OUTPUT(B)     6     16       6       16        6

After tx completes, we must have either
Disk(A)=8, Disk(B)=5   or   Disk(A)=16, Disk(B)=6

If system crashes before (8), may need to undo disk changes.
If system crashes after (8), may need to redo disk changes.

COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [46/49]
❖ Transactions and Buffer Pool

Two issues arise w.r.t. buffers:

Ideally, we want stealing and not forcing.
COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [47/49]
❖ Transactions and Buffer Pool (cont)

Handling stealing:

COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [48/49]
❖ Transactions and Buffer Pool (cont)

Handling no forcing:


Above scenario may be a problem, even if we are forcing
COMP9315 24T1 ♢ Week 9 Thursday Lecture ♢ [49/49]


Produced: 11 Apr 2024