Transcript What is a Transaction?

9
What is a Transaction?
• Logical unit of work
• Must be either entirely completed or aborted
• No intermediate states are acceptable
Figure 9.1
Database Systems: Design, Implementation, & Management, 5th Edition, Rob & Coronel
1
9
Example Transaction
• Examine current account balance
SELECT ACC_NUM, ACC_BALANCE
FROM CHECKACC
WHERE ACC_NUM = ‘0908110638’;
• Consistent state after transaction
• No changes made to Database
Database Systems: Design, Implementation, & Management, 5th Edition, Rob & Coronel
2
9
Example Transaction
• Register credit sale of 100 units of product X to
customer Y for $500
UPDATE PRODUCT
SET PROD_QOH = PROD_QOH - 100
WHERE PROD_CODE = ‘X’;
UPDATE ACCT_RECEIVABLE
SET ACCT_BALANCE = ACCT_BALANCE + 500
WHERE ACCT_NUM = ‘Y’;
• Consistent state only if both transactions are fully
completed
• DBMS doesn’t guarantee transaction represents
real-world event
Database Systems: Design, Implementation, & Management, 5th Edition, Rob & Coronel
3
9
Transaction Properties (ACID)
• Atomicity
– All or nothing
• Consistency provided
– Database is consistent before and after transaction
– Database not guaranteed consistent during a
transaction
• Isolation
– Transaction data isolated from other transactions
until its execution is complete
• Durability
– Permanently recorded in DB and must be protected
Database Systems: Design, Implementation, & Management, 5th Edition, Rob & Coronel
4
9
Transaction Management with SQL
• Transaction support
– COMMIT
– ROLLBACK
• Transaction begins with a BEGIN TRANSACTION
and ends with COMMIT or ROLLBACK
• At COMMIT point (synch point) all updates made
permanent and locks released
• Requires the use of a log or journal
Database Systems: Design, Implementation, & Management, 5th Edition, Rob & Coronel
5
9
Transaction Log
• Tracks all transactions that update database
• Needed in ROLLBACK operation
• May be used to recover from system failure
• Log stores
– Record for beginning of transaction
– Each transaction component
•
•
•
•
Type of action (insert, delete, update)
Names of objects involved
Before and after images of affected objects
Pointers to previous and next entries
– Commit Statement
Database Systems: Design, Implementation, & Management, 5th Edition, Rob & Coronel
6
9
Transaction Log Example
Table 9.1
Write-ahead Log Rule: Log is physically written
before COMMIT completes to enable restart
Database Systems: Design, Implementation, & Management, 5th Edition, Rob & Coronel
7
9
Checkpoints
• How to know at restart time which transactions to
undo and which ones to redo?
• Checkpoints periodically taken
• “Taking a checkpoint” involves force-writing
buffers and writing a checkpoint record to the log
consisting of all transactions in progress at
checkpoint time
• For example ...
Database Systems: Design, Implementation, & Management, 5th Edition, Rob & Coronel
8
9
Algorithm for Undo/Redo
• At restart from checkpoint, set UNDO list to
transactions that were in progress at the time
• Set REDO list to null
• Search forward through log starting from
checkpoint
• If BEGIN TRANSACTION found, add to UNDO list
• If COMMIT found, move from UNDO to REDO
Database Systems: Design, Implementation, & Management, 5th Edition, Rob & Coronel
9
9
Concurrency Control
• Coordinates simultaneous transaction execution
in multiprocessing database
• Potential problems in multiuser environments
– Lost updates
– Uncommitted data
– Inconsistent retrievals
Database Systems: Design, Implementation, & Management, 5th Edition, Rob & Coronel
10
9
Lost Updates
Table 9.2 Normal execution of two transactions
Table 9.3 Lost update
Database Systems: Design, Implementation, & Management, 5th Edition, Rob & Coronel
11
9
Uncommitted Data
Table 9.4
Table 9.5
Database Systems: Design, Implementation, & Management, 5th Edition, Rob & Coronel
12
9
Inconsistent Retrievals
• Also known as “dirty reads” or “unrepeatable
reads”
• Occurs when a transaction reads several values,
some of which are being updated
• Example: T1 sums the total quantity on hand
while T2 transfers an amount on hand from one
item to another (correcting an incorrect posting,
for instance)
Database Systems: Design, Implementation, & Management, 5th Edition, Rob & Coronel
13
9
Inconsistent Retrievals
The two transactions
T2
Database Systems: Design, Implementation, & Management, 5th Edition, Rob & Coronel
14
9
Inconsistent Retrievals
Results with interleaved transactions
Table 9.8
Database Systems: Design, Implementation, & Management, 5th Edition, Rob & Coronel
15
9
Serializability
• It is possible for T1 followed by T2 to result in a
different state than T2 followed by T1
• But both would be correct (consistent) from the
DB point of view
• Transaction serializability means that
transactions executing concurrently must be
interleaved in such a way that the resulting DB
state is equal to some serial execution of the
same transactions
• Goal is to avoid the concurrency problems (lost
update, uncommitted data, inconsistent retrieval)
Database Systems: Design, Implementation, & Management, 5th Edition, Rob & Coronel
16
9
The Scheduler
• Establishes order of concurrent transaction
execution
• Interleaves execution of database operations to
ensure serializability
• Uses a protocol for producing serializable
schedules:
– Locking
– Time stamping
– Optimistic
• Ensures efficient use of computer’s CPU
Database Systems: Design, Implementation, & Management, 5th Edition, Rob & Coronel
17
9
Concurrency Control
with Locking Methods
• Lock guarantees current transaction
exclusive use of data item
• Acquire lock prior to access
• Lock released when transaction is
completed
• DBMS automatically initiates and enforces
locking procedures
• Lock granularity indicates level of lock use
Database Systems: Design, Implementation, & Management, 5th Edition, Rob & Coronel
18
9
Locks
• Read (sharing) or Write (exclusive)
• At various levels: DB, table, page, row, field
• Many Read locks simultaneously possible for a
given item, but only one Write lock
• Transaction that requests a lock that cannot be
granted must wait
• Possible to upgrade Read lock to Write lock or
downgrade Write lock to Read lock
• Locks released at commit point (or earlier)
Database Systems: Design, Implementation, & Management, 5th Edition, Rob & Coronel
19
9
Shared/Exclusive Locks
• Shared (Read)
– Exists when concurrent transactions granted
READ access
– Issued when transaction wants to read and
exclusive lock not held on item
• Exclusive (Write)
– Exists when access reserved for locking
transaction
– Used when potential for conflict exists
– Issued when transaction wants to update unlocked
data
Database Systems: Design, Implementation, & Management, 5th Edition, Rob & Coronel
20
9
Problems with Locking
• Transaction schedule may not be serializable
– Managed through two-phase locking
• Schedule may create deadlocks
– Managed by using deadlock detection and
prevention techniques
Database Systems: Design, Implementation, & Management, 5th Edition, Rob & Coronel
21
9
Two-Phase Locking Protocol (2PL)
• Growing phase: acquire all locks needed
• Shrinking phase: after releasing a lock, acquire
no new locks
• Consequently
– No unlock operation can precede a lock operation
in the same transaction
– No data are affected until all locks are obtained
• 2PL solves the 3 problems of concurrency
Database Systems: Design, Implementation, & Management, 5th Edition, Rob & Coronel
22
9
Two-Phase Locking Protocol
Figure 9.6
Database Systems: Design, Implementation, & Management, 5th Edition, Rob & Coronel
23
9
Deadlock
• Also called deadly embrace
• “Occurs when two transactions wait for each other
to unlock data”
• Wrong!
– eg, T1 waits for T2, T2 waits for T3, T3 waits for
T1
• Notation: T1  T2 means T1 waits for data held
by T2
• A system is in deadlock if there is a set of waiting
transactions {T0, T1, …, Tn} such that T0  T1,
T1  T2, … , Tn  T0
Database Systems: Design, Implementation, & Management, 5th Edition, Rob & Coronel
24
9
Deadlock Detection
• Wait-for-graph
Transaction
Data items locked
T1
X2
Data items waiting
for
X1, X3
T2
X3, X10
X7, X8
T3
X8
X4, X5
T4
X7
X1
T5
X1, X5
X3
T6
X4, X9
X6
T7
X6
X5
Database Systems: Design, Implementation, & Management, 5th Edition, Rob & Coronel
25
9
Recovery from Deadlock
One or more transactions must be aborted
1 Determine transactions to roll back
• Want to incur minimum “cost”
• May be based on time running, time left, amount of
data used, how many transactions are involved in
rollback (cascades)
2 Total or partial rollback
3 Starvation
• Can happen that same transaction is always
chosen as victim
• Use the number of times rolled back in determining
the cost
Database Systems: Design, Implementation, & Management, 5th Edition, Rob & Coronel
26
9
Deadlock Prevention
• Could require all locks to be acquired at once
– but may not always know what is needed
– potentially inefficient -- many items locked
unnecessarily for possibly long time
• Ordering of data items
– once a transaction locks an item, it cannot lock
anything occurring earlier in the ordering
• Preemption and rollback with timestamps
– wait-die
– wound-wait
Database Systems: Design, Implementation, & Management, 5th Edition, Rob & Coronel
27
9
Concurrency Control with Time
Stamping Methods
• Assigns global unique time stamp to each
transaction
• Produces order for transaction submission
• Properties
– Uniqueness
– Monotonicity
• Some time stamping necessary to avoid
“livelock”: where a transaction cannot acquire
any locks even though the DBMS is not
deadlocked (eg, unfair waiting algorithm)
Database Systems: Design, Implementation, & Management, 5th Edition, Rob & Coronel
28
9
Deadlock Prevention with Time Stamps
• Wait-die
– If T1 requests item locked by T2, then T1 is allowed
to wait only if it is older than T2 (smaller time
stamp). Otherwise T1 is rolled back (dies)
• Wound-wait
– If T1 requests item locked by T2, then T1 is allowed
to wait only if T1 is younger than T2 (larger time
stamp). Otherwise T2 is rolled back (wounded by
the older transaction)
• Both avoid starvation, since eventually a failing
transaction will be the oldest
Database Systems: Design, Implementation, & Management, 5th Edition, Rob & Coronel
29
9
Concurrency Control with
Optimistic Methods
• Assumes most database operations do not conflict
• Transaction executed without restrictions until
committed
• Transactions execute in 3 Phases in order:
– Read Phase
– Validation Phase
– Write Phase
• Transactions are still interleaved, but may have to
be rolled back
Database Systems: Design, Implementation, & Management, 5th Edition, Rob & Coronel
30
9
Phases in Validation-based Control
• Read phase
– Transaction reads data and stores in local variables
– Any writes are made to local variables without
updating the actual DB
• Validation phase
– Validation test performed to see whether DB can be
changed without violating serializability
– Relies on time stamping each transaction at each
phase
• Write phase
– If the validation test is successful, the transaction
updates the actual DB. Otherwise it is rolled back.
Database Systems: Design, Implementation, & Management, 5th Edition, Rob & Coronel
31
9
Database Recovery Management
• Restores a database to previously consistent
state
• Based on the atomic transaction property
• Level of backup
– Full backup
– Differential
– Transaction log
Database Systems: Design, Implementation, & Management, 5th Edition, Rob & Coronel
32
9
Transaction Recovery
• Deferred-write and Deferred-update
– Changes are written to the transaction log
– Database updated after transaction reaches
commit point
• Write-through
–
–
–
–
Immediately updated by during execution
Before the transaction reaches its commit point
Transaction log also updated
Transaction fails, database uses log information
to ROLLBACK
Database Systems: Design, Implementation, & Management, 5th Edition, Rob & Coronel
33