## 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