L9: Transactions Flashcards
Transactions in SQL:
Basic Structure
- Transactions are typically “ad-hoc”
- Each statement is treated as one transaction
- But in a program, multiple statements can be grouped as a single transaction
- Must begin with START TRANSACTION
- Can have multiple UPDATE calls
- End with COMMIT
START TRANSACTION
UPDATE table_name
SET field = new_value
WHERE
COMMIT
Two Schemes/Approaches
for preventing
Deadlock
Wait-Die Scheme
Wound-Wait Scheme
*These schemes prevent deadlock and “starvation”
Preventing Deadlock:
Wait-Die Scheme
Wait-Die Scheme
- Non-preemptive
- Older transaction waits for the younger transaction to release lock
- Younger transactions never wait, they are rolled back instead
Preventing Deadlock:
Wound-Wait Scheme
Wound-Wait Scheme
- Preemptive
- Older Transaction “wounds” younger transaction
- Forces rollback instead of waiting
- Younger transactions wait for older transactions
Log Based Recover:
Basic Idea
- Keep a “log” of every operation on stable storage
- __Maintains a record of update activities on database
- When a transaction( T ) starts, it registers itself in the log
- <t></t>
- Before executing a write, noted in log
- <t></t>
- Whe T is done, commits the change
- <t></t>
Log Based Recovery:
Concepts/Points covered
- Basic Idea
- Checkpointing
- Modification Variants:
- Deferred Modification
- Immediate Modification
- Recovery Operations
- Undo
- Redo
- How disk is shared
- Locking Assumption
Log Based Recovery:
Checkpointing
- During recovery, only need to consider the most recent transaction that started before the checkpoint
- And consider all transactions after the most recent transaction (what?)
- Scan backwards from end of log to find checkpoint
- Only transactions that are in L, or started after the checkpoint need to be recovered
- Continue scanning back to find the start of all transactions in L
Log Based Recovery:
Recovery Operations
Undo( T )
Writes old value to X: <t></t>
Log updated with <t> and</t>
ended with <t> after transaction is finished</t>
Redo( T )
Writes new value to X: <t></t>
No log output for Redo
Log Based Recovery:
When to use
Undo
Undo needs to be performed IF:
- T contains the record <t></t>
- But does not contain <t> or <t></t></t>
Basically, the transaction was started but not finalized or aborted
Sometimes, if multiple failures occur,
then the actions of undoing operations may need to be performed AGAIN.
Log Based Recovery:
When to use
Redo
Redo needs to be performed IF:
- T contains the record <t></t>
- AND either <t> or <t></t></t>
basically, the Transaction was Started and Finished,
but is wrong.
Log Based Recovery:
Types of Modification
- Immediate Modification
- Updates written to disk before transaction commits
- Deferred Modification
- Updates written to disk when transaction is committed
Log Based Recovery:
Types of Modification:
Deferred Modification
Deferred Modification
- Only performs updates to buffer and disk at the time of the transaction commit
- Simplifies some of the recovery aspects
- Needs to store more local copies in the transactions
Log Based Recovery:
Types of Modification:
Immediate Modification
Immediate Modification
- Allows updates of uncommitted transaction to be made to buffer or disk before transaction commits
- Update log must be written before Database item written
- Assume log record is output directly to stable storage
- In reality, output to stable storage can take place at any time
- Order in which blocks are output can be different from the order in which they are written to the buffer
Log Based Recovery:
How disk and log access is allotted
All transactions share disk and the log
Log Based Recovery:
Multiple Transactions attempting modification
Assume that if
some transaction has modified an item,
no other transaction can modify the item
until
the original transaction has committed or aborted.
Log Based Recovery:
Log Update Visibility
Updates of other transactions should not be visible
Transactions:
Topics/Concepts
- Transaction syntax
- Granularity
- Disk Access
- Lock Compatibility Table
- Deadlock and deadlock prevention
- Log Based Recovery
- Recover Algorithm
Granularity:
Overview
- Can increase Concurrency by providing levels of granularity to the access
- Coarse or Fine granularity
- Accomplished with Hierarchical, lockable units
- Examples:
- Database, Relations/Files, Pages, Tuples, Attributes, etc
- Examples:
- Need to create a collision path:
- Locks different levels of access
- Intention Locks
- Locks different levels of access
Accessing Data on Disk:
Components
Components:
- Physical Blocks:
- Blocks of data on Disk
- Buffer Blocks:
- Blocks of data residing in memory
*We assume that each data item fits into a single block
Accessing Data on Disk:
Commands
Commands
- Input
- Get data from disk, into buffer
- Output
- Get data from buffer, onto disk
Locks:
Possible Lock Statuses
- NL : Not Locked
- S : Shared
- X : Exclusive
- IS : Intentional Shared
- IX : Intentional Exclusive
- SIX : Intentional Shared and Exclusive
Lock Status:
NL
Not Locked (NL)
Compatibilities:
Compatible with all other Lock Statuses
Lock Status:
IS
Intentional Shared
Compatibilities:
Compatible with all other Lock Statuses, except for
Exclusive (X)
Lock Status:
IX
Intentional Exlusive
Compatible with:
- Not Locked (NL)
- Intentional Shared (IS)
- Intentional Exlusive( IX)
Lock Status:
S
Shared(S)
Compatible With:
- Not Locked (NL)
- Intentional Shared (IS)
Lock Status:
SIX
Intentional Shared and Exlusive (SIX)
Compatibilities:
- Not Locked (NL)
- Inentional Shared (IS)
Lock Status:
X
Exclusive (X)
Compatibilities:
- Only compatible with Not Locked(NL)
Recover Algorithm:
Two Phases
-
Redo Phase:
- Replay all transactions
- Whether they committed, aborted or were incomplete
-
Undo Phase:
- Undo all incomplete transactions
Recover Algorithm:
Redo Phase
Idea:
Replay all transactions, whether they committed, aborted or are incomplete
- Find last checkpoint <checkpoint></checkpoint>
- Set Undo List to L
- Scan forward from above <checkpoint></checkpoint>
- When a write record is found, redo it
- When a start record is found, add T to Undo LIst
- When a commit or abort record found, remove T from Undo List
Recover Algorithm:
Undo Phase
Idea:
Undo all incomplete Transactions
- Scan Log backwards from the end
- When write record found
- where T is on the Undo List, perform Undo and write to Log
- When start record found
- where T is in Undo List,
- write abort to Log and remove T from the Undo List
Transactions:
Definition
Transactions
are a programming abstraction that enables the DBMS to handle recovery and concurrency for users.
A Transaction(TXN) is a sequence of one or more operations(reads or writes)
which reflects a single real-world transaction
Problems with Transactions
- Failures can occur during the transaction
- hardware, software crash for example
- Need to handle concurrent execution of multiple actions
- To preserve data, a DBMS must adhere to a set of rules
Transaction
Properties
Acronym: ACID
- Atomic
- State shows either all the effects of a TXN, or none of them
- Consistent
- TXN moves from a state where integrity holds to another where integrity holds
- Isolated
- Effect of TXNs doesn’t change depending on the order they are completed
- Durable
- Once a TXN has committed its effects, those effects remain in the database
Transaction Rules:
Consistency Requirements
Consistency Requirements include:
- Explicit Integrity Restraints(constraints?)
- e.g. Primary and Foreign Keys
- Implicit Integrity Restraints
- e.g. Sum of balances on all accounts, etc
Generally:
- TXN must start with consistent database
- During TXN, database may be inconsistent
- After TXN, database MUST be consistent again
5 Possible
States of a Transaction
- Active
- Initial State, TX stays here while executing
- Partially Committed
- After final statement executed
- Committed
- After successful completion of transaction
- Failed
- After discovering that normal execution cannot proceed
- Aborted
- After DB has been rolled back and restored to prior state
Transaction States:
Possible “Travel” from each state
- Active, can go to:
- Partially Committed
- Failed
- Partially Committed can go to:
- Committed
- Failed
- Committed
- Nowhere, is a final state
- Failed, can go to
- Aborted
- Aborted
- Nowhere, is a final state
Two Possible Outcomes
for a Transaction
Transaction Commits:
all the changes are made
or
Transaction Aborts:
no changes are made
Note: TXN activities are Atomic; all or nothing
Concurrent Executions
Multiple transactions are allowed to run concurrently on the system
Benefits:
- Increased processor and disk utilization
- Reduced average response time
Concurrency Control Schemes
Concurrency Control Schemes
- used to achieve isolation of transactions
- Controls interaction between transactions to protect the integrity and consistency of database
- Major CCS: Schedules
Concurrent Transactions:
Schedule
Schedule:
A sequence of instructions that specify chronological order of instructions from concurrent transactions
- Must consist of all instructions in the transactions
- Must preserve order of instructions in original transactions
Concurrent Transactions:
Schedule Assumptions
- Each transaction preserves consistency
- All serializable transactions do preserve database consistency
- A (possibly concurrent) schedule is serializable if it is equivalent to a serial schedule
- Simplicity:
- Ignore other operations besides reads and writes
Concurrent Transactions:
Schedule Conflicts
Conflicts can occur between two operations
*Only read-read concurrencies do not conflict
Conflicts:
- read-write
- X=read(Q) , Y=write(Q)
- write-read
- X=write(Q) , Y=read(Q)
- write-read
- X=write(Q) , Y=read(Q)
- write-read
Concurrent Transactions:
Conflict Serializability
Assume we have a schedule S.
If S can be transformed into schedule S’
by a series of non-conflicting swaps of operations,
then S and S’ are Conflict Equivalent.
S is Conflict Serializable
if it is Conflict Equivalent to a serial schedule.
Locking Instructions
Basic Overview
- Use locking mechanisms to control access to data item
- Two Modes:
-
Exclusive, Lock-X Instruction
- Can be read or write
-
Shared, Lock-S Instruction
- Can only be read
-
Exclusive, Lock-X Instruction
- A transaction can only proceed if a lock is granted
- Infinite shared locks available, only one exclusive lock
- If lock cannot be granted, transaction waits until a lock is granted
What are
Deadlocks?
Deadlocks
When two or more transactions block each other by having exclusive locks on data that the other needs
Example:
T1 gets lock on item B
T2 gets lock on item A
T2 tries to get lock on item B, but needs to wait for T1 to release lock
But T1 has a schedule instruction to get a lock on item A, before it releases B.
Each transaction is waiting on the other.
In this event, the Database must be rolled back
Concurrent Transactions:
Two Phase Locking (2PL)
Ensures conflict-serializable schedules, but does not prevent deadlocks
Phase 1: Growing Phase
- Transaction may obtain locks
- Transaction may not release locks
- May upgrade Locks (S to X)
Phase 2: Shrinking Phase
- Transaction may not obtain locks
- Transaction may release locks
- May downgrade Locks(X to S)
Concurrent Transactions:
Two Phase Locking:
Strict 2PL
Rigorous 2PL
Strict 2PL
- Transaction must hold all of its locks until it commits or aborts
- Prevents cascading rollbacks
Rigorous 2PL
- Even more strict
- All locks must be held until transaction commits/aborts
- Can be conflict serializable schedules that cannot be obtained if two-phase locking is used
