Transaction processing¶

Transaction¶

Finite ordered set of operations (workflow)
Properties (ensured by transactions)
Integrity (ensure data integrity)
Fail Safety (immune to system failures)
Interface contract: Start / Commit / Rollback
Properties (ACID)
Atomicity
Consistency
Isolation
Durability

ACID: Atomicity¶

Transaction is executed completely or not at all.
Uninterruptible single operation
All effects materialized (only on commit)
Problem: Dirty Read
Read uncommitted changes of another transaction
T1 writes, T2 reads, T1 rollback

ACID: Consistency¶

Transaction lead from one consistent state to another.
Integrity constraints always valid
Integrity may be violated during transaction
Transactions without consistency: Abort
Problem: Inconsistent read problem (with no isolation)
Intertwinted write and read records
T1 writes, T2 reads and writes, T1 reads inconsistent data

ACID: Isolation¶

Transactions do not interfere with each other.
Effect always the same (execution alone)
Read only consistent data
Problem: Lost update
Concurrent write lead to information loss
Problem: Non-reproducible read / Phantom problem
Reading same data item in one transaction -> different values
T1 reads, T2 writes, T1 reads again -> Problem

ACID: Durability¶

After a commit all changes are guaranteed to survive system failures.
Written on disk / recovery measures
Incomplete transactions must survive crash
Problem: System crash
After commit: Everything written to disk

Page Model¶

Operations on page level (read/write)
Performed in buffer
Write operation indivisible
Definition: Transaction is totally-ordered finite sequence of actions r(x) or w(x) where x is a record of a database instance.
Note
Relaxation to partial order possible (if effect is unchanged)
Order necessary: Two ops, same item

Transaction Manager¶

Task: Concurrency control
Concurrent transactions -> Potential problems
Gets transactions from users/apps
—Image 36—

Schedule¶

Schedule/history: Sequence of operations (all and only operations of transactions)
Serial schedule: Permutation exists, where transactions occur one after another
Serial schedule
no concurrency problem
No performance
Ensuring atomicity, consistency, isolation
Goal: Find safe schedules fast
Problem: Different transaction, same data item

Final state equivalent¶

Equivalence two schedules:
Same set operations
Final state equivalence (same instance after execution)

Schedule serializability¶

Serializable schedule:
It exists an equivalent serial schedule
Advantage: Same effect, concurrent execution
Test for serializability
NP-complete
O(#TA!)

Schedule classes¶

—Image—

Conflict serializability¶

Conflict serializable schedule
It exists a conflict equivalent serial schedule
Test for conflict equivalence: Conflict graph
Example non-conflict serializable schedule: Lost update problem
Good correctness criterion
No commits/rollbacks -> Dirty read possible
Commit serializability necessary

Conflict equivalence¶

Conflicting operations
Access same data item
At least one write
Conflict relation: All pairs of conflicting operations (remove aborted)
Conflict equivalence two schedules
Same set operations
Same conflict relation
Or: Identical conflict graphs

Conflict serializability: Conflict graph¶

Goal: Check for conflict equivalence
Nodes: All committed transactions
Edge (t1, t2) iff conflicting pair (p, q) with p in t1 and q in t2
— Example 51—
Non-conflict serializable schedule: Cyclic
—Image 52—
Theorem:
Schedule is conflict serializable iff conflict graph is acyclic
Major advantage: Finding cycle ein O(n^k)

Scheduler¶

Transaction manager: Give operations to scheduler
Concerns: Isolation + Consistency
Scheduler:
List of transactions: Active, commited, aborted
Accept transactions / operations
Decide to abort (if non-serializable)
Per transaction:
Output operation to storage manager: Active
Reject operation: Abort
Block operation: Waiting

Locking Scheduler¶

Largest class of schedulers
Set / remove locks on data items
Lock
Atomic
Lock granularity (record, page, etc…)
Lock is set: Item not available to other transactions
Lock conflict:
Scheduler checks requested locks
Requesting transaction blocked
Legal schedule
Item locked before access
All locks released
No unnecessary locks

Lock modes¶

Lock types:
Read locks / shared locks
Write locks / exclusive locks
Lock conversion
Upgrade read lock to write lock
Unlock concurrent shared locks

Two-Phase Locking Protocol¶

Generate subset of conflict-serializable schedule
Prominent: Two-Phase Locking (2PL)
Growing phase
Shrinking phase
Growing phase:
Abort transactions (usually)
Lost amount of work small
Shrinking phase:
Write data physically (transaction can commit)
Weak points
Conflicts
Two transactions competing fo the same lock
Abort in shrinking
T1 releases, T2 acquires, T1 rolled back (T2 also, cascading rollback)
Variants:
Conservative locking
Strict two-phase locking

Two-Phase Locking Protocol: Variants¶

Conservative locking / static locking
Pessimistic approach
Acquire all locks before first operation
Restricts concurrency
Improves commit changes
Strong strict two-phase locking (SS2PL)
Hold lock until commit
Output: Strict and cascade less schedules
Easy to recover
No cascading rollbacks
Avoid dirty reads

Deadlocks¶

Deadlock: Transactions mutually wait for each other
Criteria
Mutual exclusion (resource cannot be shared)
Hold-and-wait (Thread holds resource)
No preemption (resource only released voluntarily)
Circular wait (wait-for-graph)
Handle deadlocks
Ignore (easy)
Detection (allow, detect, resolve)
Prevention (ensure criteria not fulfilled)
Avoidance (prevent unsafe situations)

Deadlocks: Ignore¶

„Ostrich algorithm“
Reasonable
Deadlock occurs rarely
Expensive to prevent
Not good for critical database system

Deadlocks: Detection¶

Waiting-For-Graph
Vertex: Transaction
Edge: Waiting-For-Relation
Deadlock: Cycle
Detect cycle in O(n^2) or Floyd-Warshall algorithm
When to test?
Continuously: Immediately after transaction inserted (expensive)
Periodic: Time cycle (time interval decision critical)

Deadlocks: Resolving¶

Usually abort last transaction
Victim selection
Last blocked (causing transaction)
Random
Youngest (abort which started most recently, minimize wasted work)
Minimum locks (transaction with fewest locks, minimize wasted work)
Minimum work (abort with least amount of work, CPU, I/O)
Most cycles (abort transaction with most cycles)
Most edges (abort transaction with most edges)

Deadlocks: Livelocks¶

Starvation
Repeatedly eliminating the same transaction => will never finish
Solution: Choose another (priorities)
Example without deadlock:
Transaction waits for a lock but never receives it

Deadlocks: Prevention¶

Techniques
Wait and die
Wound and wait
Immediate restart (restart conflicting transaction immediately)
Running priority (abort old transaction, give locks to new one)
Timeout
Wait-and-die
Use timestamps
Older transaction => higher priority
Old TX waits for young TX
Young TX dies
Wound-and-wait
Old TX restarts young TX (wound)
Younger TX waits
Timeout
Start timer after blocking
Timeout => deadlock => termination

Deadlocks: Avoidance¶

Simulation and trajectories
Avoid unsafe states
Change scheduler for potential unsafe states
Example: Banker’s algorithm
Expensive, rarely used
—Image 22—

Altruistic Locking¶

Disadvantage 2PL
Long-running transaction => many short-lived locks => unnecessary
Solution: Altruistic locking (return not-used locks)
Idea: Short transactions needing a subset of locks of long transaction for obtaining
Transaction donates lock (tell scheduler)
2PL: Donated lock <> unlocked
Stay-in-wake-rule: Ensure consistency (avoid lost update)

Altruistic Locking: Wake / Dept¶

Being in the wake:
Operation in the wake of Ti when item is donated by Ti
Transaction Tj is in wake of Ti if one operation is in the wake of Ti
Transaction Tj is completely in the wake of Ti if all operation are in the wake of Ti
Being indebted:
Transaction Tj is indebted to Ti if Tj get lock of Ti and there is a conflict between them

Altruistic Locking: Rollback¶

Transaction must roll back -> All transaction in the wake must roll back (Cascading roll-back)
Very expensive

Altruistic Locking: Rules¶

Conflicting locks may not be hold simultaneously (either unlock or donate)
Once lock is donated -> Data item cant be accessed again
Transaction acquiring lock must unlock
Tj indebted to Ti, it must remain completely in wake to Ti (until unlocking)

Predicate Locking¶

Lock semantic entities
Idea: Dont lock table, lock subset of table referring to predicate
Intensional locking (on WHERE Statement)
Currently not supported
Locking:
Conditions form hyperplane (all values satisfying condition)
Lock includes non-existing records
Predicate conditions define which records to lock
Lock mode; shared/exclusive
Compatible locks
Both shared
No intersection of hyperplane
Compatibility test
Lock requests reaches scheduler
Expensive: NP-complete

Non-Locking Schedulers¶

Serialize transaction without locking
Timestamp ordering
Serialization graph testing
Optimistic protocols
Less efficient
Aborting transactions
Suitable for distributed systems (distributed locks difficult)

Non-Locking Schedulers: Timestamp ordering¶

Annotate transaction with timestamp (monotonically increasing)
Operations of transaction inherit timestamp
Order conflicting ops by timestamp
Timestamp ordering rule
pi(x) is executed before qj(x) iff ts(ti) < ts(tj)
Transaction too late -> abort
Pessimistic
Performance decrease
Timestamps for each data item
max-r-scheduled(x)
max-w-scheduled(x)
Transaction arrives
Compare to max-q-schedule for conflict operations q

Non-Locking Schedulers: Serialization graph¶

Idea: Dynamically maintain conflict graphs + check for cycle
Extend graph before performing operations
Abort transaction responsible for cycle
-> Deadlock avoidance
Impractical for real apps
O(#TA^2)
Continuous detection expensive

Non-Locking Schedulers: Optimistic protocol¶

Assumption: Probably no conflict will happen anyway
Pessimistic: Conflicts happen often, Immediately detect and resolve conflicts
Three phases
Read phase
- Just execute action, isolated copy for writing
Validate phase
- Transaction wants to commit
- Validate execution (conflict serialization, order of conflicting operations)
- Backward-oriented: Watch all transactions that are committed
- Forward-oriented: Watch all transactions in read phase
Write phase
- Write isolated copy to DB

Locking Protocols¶

—Image 49—

Lock Implementation¶

Commercial systems: S2PL
Flexibility
Robustness
Locker Manager’s Task: Bookkeeping
Check granted locks
Release locks at one
Resume transactions with lock conflicts
Checking/releasing/resuming
In-memory structure required
Single-key hash tables
Map abstract resource to concrete resource (RCB)

Lock Implementation: Blocks¶

Resource Control Blocks
Represent page, records, index entries
Linked together for the same value
Lock Control Block
Important: Shared locks simultaneously hold
Bookkeeping: List of LCBs
Ordered by arrival time
Avoid starvation: Shared locks don’t pass queued exclusive locks
Transaction Control Block
For releasing: Identify LCBs for transaction
Per transaction
Traverse LCBs and remove from RCB
Check RCBs for resuming
—Image 55—

Lock Implementation: Granularity¶

Lock granularity -> changes number of RCBs and LCBs
Multiple lock granularity (different granularities)
Detect conflicts: Intention locks
Intention locks
Coarse lock desired -> set intention locks to all smaller granularities
Before granting coarse lock: Small locks must be granted
Lock escalation (transaction not sure how much locks)
Convert fine-grained locks to coarse lock
Grant coarse lock -> Release fine-grained lock
Commercial system triggers lock escalation

Isolation Levels¶

Relaxation from S2PL
Control locks on application / transaction level
Locking style operation: Isolation level
Isolation levels
Read uncommitted (dirty-read level)
Write locks acquired/released by S2PL
Dirty read possible (ok for statistical apps)
Read committed (cursor stability level)
Write locks acquired/released by S2PL
Read locks are held duration read
Long periods between waits: Lost update
Serializable (CRS)
Avoid long-running transactions (User-dialog performance killer)
Transaction chopping
Application responsible

MPL¶

Concurrency increases throughput
Data contention: Transactions compete for locks
Data contention thrashing: Waiting time increases
Deadlocks: CPU / disk contention (restarted transaction)
-> Multiprogramming level: Max. Number of concurrent transactions
MPL Tuning
Short, frequent transactions, mostly read -> High MPL
Long transactions -> Low MPL
Transactions always same records: Low MPL
Variability query length (constant->high MPL, varying->low MPL)
MPL per transaction class
Dynamic MPL
Conflict ratio below: Admit immediately
Surpass: Admission control
Conflict ratio
Homogenous workload: Fraction of blocked transactions (~25%)
Inhomogenous workload: #LocksHeld / #LockHeldByNonBlockedT

Transaction Recovery¶

Concerns atomicity + durability
Complete entirely or not (rollback)
Committed transaction -> persistent
Protect against hardware crash + failures
Aborted transaction
Undo all changes (not enforced by serializability)

System Crash: Soft crash¶

Database server down
Stable data survives (probably inconsistent)
Soft crash recovery
Return to last consistent state
Redo interrupted transactions
Cause
Human-cause (admin)
Software failure (OS/DBMS/Bugs)
Power failure

System Crash: Hard crash¶

Corrupt secondary storage
Measure
N-Plex systems
Emergency Backup System (UPS)
Parity system
Hard crash recovery
Rebuild storage
Perform soft crash recovery
Causes
Environment (fire, flood, sabotage)
Operation (admin)
Maintenance (repair facility)
Hardware
Software
Process (strike, panic)
Cyber Attack (malware)

System Crash: N-Plex system¶

Redundant approach
Similar systems parallel (geographically distributed)
Tasks performed by all
Voting result -> Detect faulty systems
No consensus -> repeat
Basic vs. recursive failsafe N-plex vs. Version N-plex

Recovery concepts¶

Log / error type¶

System crash: Transaction state lost
Concern: Physical database correct state?
Problem: Which part of transaction executed/which not?
Error type
Local error in transaction (rollback by user)
Error with volatile memory loss (power outage)
Error with stable memory loss (hardware failure)
Log File
Undo-log: Old values (before write, for rollback)
Redo-log: New values (after write, for re-applying)
System checkpoint (special log entry)
Write committed write-ops to disk
Periodically
Method: Hold transactions, force-write data + log, resume

Recovery concepts: Stealing, forcing, Images¶

Stealing policy
Page can be evicted by other transaction (intermediate results written)
Page pinned/dirty: Page modified
Flush page iff page dirty
Force policy
Write immediately or later
Before image (BFIM): Old value
After image (AFIM): New value
In-place updating
Overwrite original copy (only one copy)
Log necessary
Shadow paging
New item at different location
No log necessary (both images on disk)
Write-ahead logging (WAL): First write BFIM to UNDO, overwrite BFIM, not commit until REDO

Recovery components¶

DB page: Stable content of DB
DB cache: Excerpt stable DB (operations, explicitly flush to DB)
Stable log (log entry for uncommitted write operation)
Log buffer
—Image 25—

Recovery without logs¶

Shadow paging (No-undo/no-redo, force/no-steal)
Idea
Store AFIM and BFIM of disk
Two page tables during transaction (current, shadow)
Workflow
Shadow PT never changed (+non-volatile)
Read/write on current PT (AFIM separate copy)
Rollback: Delete current PT + AFIM
Commit: Force-write current PT to shadow PT
Advantage
Avoid logging overhead
Recovery fast (everything written)
Disadvantage
Commit overhead: Lot of writes
Fragmented data (maintain indexes?)
Garbage collection overhead

Recovery with logs¶

Two techniques
Deferred update
Write everything at commit point
No-force / No-steal
No-undo / redo
Immediate update
Write everything immediately
Force / steal
Undo / no-redo

Recovery with logs: Deferred updates¶

No-undo / redo + no-force/no-steal
Write at commit point
Write (during transaction) to private copy
Commit: First write to log, then to database
Rollback: Delete private copy
Possible: Redo committed changes (Crash between log and DB writing)
Advantage
No rollbacks necessary
No dirty read possible
Disadvantage:
Limits concurrency
Improvement: Only perform last write command

Recovery with logs: Immediate updates¶

Undo/no-redo + force/steal
Write directly
Read operation in undo log (cascading rollback -> avoid dirty read)
Rollback: Undo changes
S2PL: Commit ordering / being-in-the-wake
More general algorithm: undo/redo + no-force/steal
Undo effects of active transactions
Redo effect committed transaction (since checkpoint)

Recovery protocols¶

—Table 42—

ARIES¶

Algorithmus for Recovery and Isolation Exploiting Semantics
Summarized experiences (DB2/SysR)
Steal/no-force algorithms
Used by every database
Concepts
Write-ahead logging
Repeating history during redo: Bring system back to crash situation, Undo uncommitted transactions
Logging changes during undo
Analyze phase
Redo phase
Undo phase
Necessary information
Log
Transaction table
Dirty page table

ARIES: Data structure¶

Log record
Has log sequence number LSN
Page has latest LSN which changed page
Contains
previous LSN of transaction (chain)
Transaction ID
Type (write, commit, abort, undo, end)
Transaction table
One record pre active transaction
Store: TID, latest LSN, status
Dirty page table
Entry per modified page
Store: Page ID, earliest LSN

ARIES: Phases¶

Analyze phase
Scan log starting with latest checkout
Access transaction table
Remove transaction with „end“ log entry
Add logs to transactions if missing
Access dirty page table
Log modifies table -> add
Set correct LSN
Redo phase
Idea: Don’t redo already written changes (smallest LSN in dirty page table)
Redo operations (if necessary)
Result: Same state when crash happened
Undo phase
Undo set: Active transactions from analyze phase
Scan log backwards + undo changes
Write compensating log entry for each undo (recover crashes in this phase)

Catastrophic recovery¶

Single-media failure
Corrupted hard drive
Easily recoverable (RAID)
No interruption of operations but increased vulnerability
Multiple-media failure / catastrophic failure
Catastrophes: Fire, flood
Massive hardware failure
Human-caused damage
Virus infections
Remedy
Geographic N-Plexing: Highly available distributed storage
Backup: Backup whole database + logs (tertiary storage), Backup logs more often (smaller, easier)

Application Recovery¶

Scenario: Transaction correctly fails
Stateless application
Request-response
Queue requests (persistent)
Information user if fail
Stateful application
Problem: Long-running transactions (user input)
Idea: Break down to chained transactions
Queued conversational transactions
No real ACID (atomicity violated)
Queue response, user interaction, enqueue new request