Concurrency Control Flashcards
Ghost update type b: when does it happen.
Can it be managed with 2PL?
On insert or group by.
2PL cannot managed it, predicate locking yes.
Definition of transaction
A sequence of read and write operations characterized by the same TID
Schedule definition
sequence of read/write operations presents by concurrent transactions
Concurrency control accepts or rejects schedules to avoid anomalies, the scheduler though has to accept or reject op. execution without knowing the outcome of the transactions (abort/commit)
Serializable schedule
Si is serializable when Si is equivalent to an arbitrary serial shedule of the same transactions.
View equivalence and view serializable schedule
Two schedules are view equivalent if they have the same reads-from set and the same final write set.
A schedule is view serializable if it is view equivalent to an arbitrary serial schedule of the same transactions.
Prevents: lost update: inconsistent read, ghost update (a).
Detecting view equivalence to a given schedule is O(n).
Detecting view equivalence to an arbitrary serial schedule is NP-complete (not feasible).
Scheduler
- Block of the concurrency control maanger
- is in charge of deciding if and when read/write requests can be satisfiedd
Without a scheduler we may have correctness problems
Lost Update
Dirty Read
Inconsistent read
Value is read 2 times, and reads different values during the same T.
Ghost update (a)
T1 only partially observes the effect of T2.
All objects are already present.
Ghost updates result from inconsistent reads.
Ghost update (b)
Inconsistent read.
A new set of objects are inserted by another transaction.
Commit projection
Is a simplifying hypothesis: the schedule contains only transactions performing commit
Equivalence classes
- View equivalence
- Conflict equivalence
- 2PL
- Timestamp equivalence
Each detecs a set of acceptable schedules, and is characterized by a different complexity in detecting equivalence.
Conflict equivalence, conflict serializable
Conflicting actions: Action Ai is in conflict with Aj (i != j) if both action operate on the same object and at least one of them is a write:
- Read-Write conflicts (RW or WR)
- Write-Write conflicts
Two schedules are conflict equivalent if they have the same conflict set and each conflict pair is in the same order in both schedules.
Conflict serializable: if it is equivalent to an arbitrary serial schedule of the same transactions.
CSR: conflict serializable schedules.
Detecting conflict serializability is possible through a conflict graph.
CSR is a subset of VSR.
Conflict graph
A node for each transaction.
An edge Ti -> Tj if:
- there exist at least a conflict between the two
- Ai preceeds Aj
Checking for cycles is O(V + E).
2PL
2 Phase Locking
A lock may block others from accessing a resource.
Locks: Write-Lock, Read-Lock.
Read-Locks are shared.
Write-Locks are exclusive.
Lock escalation: R-Lock followed by W-lock on the same data.
Used by most DBMS.
Characterized by two phases:
- Growing: needed locks acuired
- Shrinking: all locks are released.
2PL is a subeset of CSR.
2PL: Lock manager
Scheduler becomes lock manager:
- receives transaction requests and grants locks based on locks already granted.
- when the lock is not granted the transaction is put in waiting state, the wait terminates when the locked resource is freed.
- when a timeout runs out while a transaction is still waiting: extracts the transactions from waiting list, resumes it, returns an error code.
- in the latter case the transaction may perform rollback (and possibly restart) or request again the same lock after some time (without releasing currently held resources)
Lock manager exploits a lock table and the conflict table.
Strinct 2PL
Transactions locks may be releasd only at the end of the transaction (after commit/abort). -> at the end of the transaction data is stable (this avoids dirty read completely).
Allows the dropping of the commit projection hypothesis.
2PL: Probability of conflict
K * M / N
K = active transactions
M = average number of objects accessed by a transaction
N = is the number of objects in the database
Hierarchical locking
Table locks can be acquired at different granularities:
- Table
- Group of tuples (fragment): physical or logical
- Single tuple
- Single field in a tuple
It is an extension of traditional locking, charaterized by a larger set of primitives:
Shared lock (SL)
eXclusive lock (XL)
Intention of Shared Lock (ISL): intention of shared locking on node lower in the hierarchy.
Intention of eXclusive Lock (IXL): same as ISL, but for exlusive lock
Shared lock and Intention of eXclusive Lock(SIXL): shared lock of current object and intetion to get exlusive lock of lower level nodes.
Locks are requested startinf from the root, relelased starting from the leafs.
To request a SL or ISL need to own ISL or IXL on parent.
To request a XL, IXL or SIXL, need own a IXL or SIXL, on its parent.
Selction of lock granularity
Depends on application type.
If it performs localized reads or updates few objects -> detailed granularity
if it performs massive reads or updates -> near root -> rough granularity
Effects of granularity:
too coorse -> reduces concurrency
too fine -> forces overhead on lock manager.
Predicate locking
The only solution capable of addressing Ghost (insert) Update (b).
For 2PL a read operation is not in conflict with an insert op. -> new tuple cannot be locked in advance
Predicate locking allows locking all data satisfying a given predicate. -> implemented in real systems using locking indices
SQL2 Standard: Locking
There are two transaction types:
- read-write
- read only: no data or schema modifications, just SL.
Isolation levels:
- Serializable: predicate locking
- Repeatable Read: strict 2PL (no predicate locking) -> repeated reads of existing objects can be correctly repeated, no protection gainst ghost update (b)
- Read committed: no 2PL, read lock released ASA object is read. -> data is read only it is committed, dirty reads aboided
- Read Uncommitted: only allowed for read only transactions. -> dirty read allowed.
Syntax:
SET TRANSACTION
[ISOLATION LEVEL]
[READ ONLY]
[READ WRITE]
Isolation level may be reduced only for read statements, since write operations are always executed with XLs.
Deadlock: solutions, how to prevent it, how to detect it
Solving: Timeout
- Most used solution in commercial systems
- After time expires the transaction receives a negative answer and performs rollback.
- Particular attention should be taken when choosing the timeout interval: too long (long waiting for resolving deadlock), short (many false positives, overloads the system)
Preventing: Pessimistic/Conservative 2PL
- All locks are acquired before the transaction starts (may not be possible)
- Only younger transactions are allowed to wait
Detection: Wait graph
- nodes are transactions
- a cycle represents a deadlock
- used in distributed DBMS
