Please enable JavaScript.
Coggle requires JavaScript to display documents.
Transaction Concurrency (Transaction Concurrency Problem (Simultaneous…
Transaction Concurrency
Transaction Concurrency Problem
Simultaneous
execution
of multiple transactions over the
same
database
Possibility of
conflicts
and
inconsistent
states for the data(i.e. non validity of the ACID properties)
i.e.
anomalies
Lost update
Dirty read
Non-repeatable read
Phantom update
Phantom insert
Nested (one starting and finishing amidst another) or interleaved transactions (one starts after another and finishes after it)
Transaction Concurrency Management in DBMSs
The
scheduler
sequences read and write operations in an anomaly-free way
Simplifying assumption:
a priori
schedules and commit projection
Taxonomy of possible schedules
Serializable
: equivalent to serial - no concurrency problems by design
View
-
serializable
: view-equivalent to a serial schedule
Deciding it is an NP problem (there are reduced versions)
Conflict-serializable
: conflict-equivalent to a serial schedule
Method of the
conflict
graph
to check (not practically feasible)
2PL-serializable
: well formed and using 2PL
Mantaining the conflict graph has very low cost
Solution in practice
Locking
Simple Locking
Before accessing a resource, a transactions asks to be granted its
lock
w_lock
primitive to get an exclusive lock
unlock
r_lock
primitive to get a shared lock
Not
enough
to guarantee ACID properties
The
Lock
Manager
is the part of the scheduler overseeing locks
Logic implemented by means of a
conflict
table
and locks tracked with a
lock
table
(including counters for shared)
If it denies a lock, the transaction is suspended and queued
Risk of
Deadlocks
Problem
1 more item...
Solutions
3 more items...
Limiting their occurrence
3 more items...
Starvation
Problem
1 more item...
Well-formed transactions ask for locks and release them explicitely for read and write operations
Two-Phase Locking (2PL)
Transactions acquire no more locks after they released the first one
There is a growing phase and a shrinking phase in the number of owned locks in time (Two-Phase)
2PL-serializability
Still
not
enough
because
dirty
read
and
phantom
insert
anomalies are still possible
Strict Two-Phase Locking
It adds to 2PL that locks are released only after commit or rollback
All locks disappear altogether
Still
not
enough
because
phantom
insert
anomalies are still possible
Predicate Locks
A transaction gets a lock as in Strict 2PL, but on resources satisfying a given predicate (e.g. table rows where attribute A = 1).
They solve all anomalies
Specifying isolation level for transactions (strict 2PL always applied for writes)
Hierarchical Locking
Resources with different granularities, organized into a hierarchy: usually
file
,
page
,
tuple
and
value
.
Transaction require locks specifying the layer - Determining the needed one starting from the lowest
Lock assignment in top-down order, lock release in bottom-up order
Introduce three new lock types
Intentional Shared Lock (ISL)
Intentional eXclusive Lock (IXL)
Shared Intentional eXclusive Lock (SIXL)
No commit projection hypotesis anymore
Alternative solution
Timestamping
For
events
:
event-id.node-id
Avoiding anomalies
Two counters per resource:
RTM()
and
WTM()
With
read(x, ts)
, if
ts < WTM(x)
rejected - Else granted and
RTM(x) = max {ts, RTM(x)}
3a. (Standard technique) With
write(x, ts)
, if
ts < RTM(x)
or
ts < WTM(x)
rejected - Else granted and
WTM(x) = ts
3b. (Thomas' rule) With
write(x, ts)
, if
ts < RTM(x)
rejected; if not, if
ts < WTM(x)
"skip the write" - Else granted and
WTM(x) = ts
This technique kills many transactions and without the commit-projection hypoteses it requires buffering all writes.
Multi-version
timestamping
Writes create new versions of the resource, many replicas are kept and discarded when not needed anymore.
For
transactions
: unique numeric identifier for a transaction indicating its starting time.