Karteikarten
Ohne Titel
Karten in diesem Stapel (45)
- 1Two Views of the System1. Application Programmer's View
Start
sequence of SQL statements
Commit or Rollback
2. System developer's View
Start
sequence of Reads and Writes
Commit or Abort - 2AtomicityEither all the operations associated with a transaction
happen or none of them happens
Mechanism: Logging
o Recovery… - 3ConsistencyIt satisfies the integrity constraints on the database at the
transaction's boundaries
Checks, Assertions, Triggers, etc. - 4IsolationThe result of the execution of concurrent transactions is
the same as if transactions were executed serially
Serializability: Operations may be interleaved, but execution must
be equivalent to some sequential (serial) order of transactions
mechan9smm: Concurrency Control Techniques - 5DurabilityThe effects of completed transactions become permanent
surviving any subsequent failures
Mechanism: Logging
o Recovery… - 6Concurrency GoalExecute a sequence of SQL
statements so they “
appear
” to be running in
isolation - 7Interleaved processing:concurrent execution of processes
is interleaved in a single CPU - 8Parallel processing:processes are concurrently executed in
multiple CPUs. - 9Transaction PrimitivesSTART
COMMIT
ROLLBACK (alias Abort) - 10STARTnforms the system that a new transaction starts to execute.
n The transaction becomes active - 11COMMITInforms the system that a transaction has successfully
completed its task.
n The system makes the effects of the transaction durable.
n After this the transaction is committed. - 12ROLLBACK (alias Abort)Informs the system that a transaction has terminated abnormally.
n The system must undo all the effects of the transaction.
n The transaction is aborted. - 13concurrency control is needed?Answer: to avoid the following anomalies:
1. The lost update problem
2. The dirty read problem
3. The unrepeatable read problem - 14Conflicting OperationsA conflict happens if we have two operations such that:
1. they belong to two different transactions, and
2. they both operate on the same data item,
3. and one of them is a write - 15SchedulesWhen transactions are executing concurrently, the
order of execution of operations from all transactions
is known as a schedule (or history) - 16Scheduling TransactionsSerial schedule: Schedule that does not interleave
the actions of different transactions
Serializable schedule: A schedule that is equivalent
to some serial execution of the transactions - 17Result Equivalent schedules:S1 is identical to the
state produced by executing S2 - 18Basic Two Phase Locking (2PL)A Growing phase
Whenever the scheduler receives an operation on any
item, it must acquire a lock on that item before
executing the operation.
n No locks can be released in this phase
A Shrinking phase
n Once a scheduler has released a lock for a transaction,
it cannot request any additional locks on any data item
for this transaction - 19Two Phase Locking (2PL): VariantsBasic 2PL:
n Tx locks data items incrementally (growing phase)
n This may cause deadlock: deal with it!
Conservative 2PL:
n locks all desired data items before Tx begins execution
n If any item cannot be locked, Tx does not lock any item
o Waits until all items are available for locking
n Deadlock-free protocol
n Difficult to use in practice: hard to predeclare items! - 20Granularity of LocksLocking granularity is the size of the data item being
locked. Examples:
n block
n table
n tuple (record)
n field in a tuple - 21Dealing with deadlocks1. Deadlock Prevention
2. Deadlock Detection
3. Timeout - 22Deadlock Prevention:Tx locks all its data items before it begins execution
n Prevents deadlock since Tx never waits for a data item
n The conservative two-phase locking uses this approach - 23Deadlock DetectionDeadlock Detection:
n Deadlocks are allowed to happen!
n A wait-for-graph is used for detecting cycle - 24Deadlock Detection: Victim SelectionThe cost of aborting a transaction
How long a transaction has been running?
How long it will take a transaction to finish?
How many deadlocks will be resolved if a particular
transaction is aborted
How many times this transaction was already
aborted due to deadlocks? - 25TimeoutGuess a deadlock rather than detecting it!
The scheduler checks periodically if a transaction has
been blocked for too long
Advantage: very simple algorithm - 26Long timeout:Long timeout:
o fewer mistakes by the scheduler, but
o a deadlock may exist unnoticed for long periods - 27Short timeout:quick deadlock detection, but
o more mistakes are possible (aborting transactions not
involved in a deadlock) - 28Strict 2PL:Does not release exclusive (write) locks until after a
transaction terminates (commits or aborts)
What is the advantage?
n Strict 2PL simplifies the recovery process
o Only rollback the aborted transaction
o Other transactions are not affected since they couldn’t
read any updates made by the aborted transaction - 29Conflict equivalent:Two schedules are said to be
conflict equivalent if the order of any two conflicting
operations is the same in both schedules. - 30Conflict serializable (CSR):A schedule S is said to
be conflict serializable if it is conflict equivalent to
some serial schedule S’. - 31Testing CSRTest for CSR by analyzing the precedence graph SG(H),
called a serialization graph, derived from history H. - 32Purpose of Database RecoveryoTo bring the database into the last consistent state,
which existed prior to the failure
oTo preserve transaction properties:
n Atomicity & Durability - 33Types of Failuresn Transaction failure:
o Incorrect input, deadlock, etc.
n System failure:
o Addressing error, application error, operating system
fault, RAM failure, etc.
n Media failure:
o Disk head crash, power disruption, etc. - 34The goals of Recovery1. When a transaction T commits
n Make the updates permanent in the database so that they
can survive subsequent failures
2. When a transaction T aborts
n Obliterate any updates on data items by aborted transaction
in the database
n Obliterate the effects of T on other transactions; i.e.,
transactions that read data items updated by T
3. When the system crashes after a system failure
n Bring the database to its most recent consistent state. - 35Recovery Actionsn Undo action :
o required for atomicity
undo update
n Redo action:
o required for durability
redo update - 36Recovery ConceptsLog or Journal
o Caching
o Checkpoints
o Recovery Techniques - 37LoggingA Log or journal is a sequence of records which represent
all modifications to the database in the order in which they
actually occurred
o Log records may describe either physical changes or
logical database operations
o state before change, before image
A logical log represents higher level operations; e.g.,
insert a record. - 38Buffer ManagerThe goal of Cache or Buffer Manager is to maximize the
likelihood that a block of data needed by a transaction is
in main memory
o The main memory is partitioned into buffer blocks or
buffer pages (or simply buffers, blocks or pages) - 39Types of log record:1. [start_transaction,T]: Records that transaction T has
started execution
2. [write_item,T,X,old_value,new_value]: Records that
transaction T has changed the value of database item
X from old_value to new_value.
3. [read_item,T,X]: Records that transaction T has read
the value of database item X
4. [commit,T]: Records that transaction T has completed
successfully
5. [abort,T]: Records that transaction T has been aborte - 40Cache Flushingn Steal: A cache page can be flushed before
transaction commits – when?
n No-Steal: A cache cannot be flushed before
transaction commits
n Force: Cache is flushed to disk when transaction
commits
n No-Force: Otherwise! So when is it flushed? - 41Write-Ahead Logging (WAL)The Write-Ahead Logging (WAL) protocol states that:
n For Undo:
o Before a data item’s AFIM is flushed to the database disk
(overwriting the BFIM) its BFIM must be written to the log and
the log must be saved on a stable store (log disk)
n For Redo:
o Before a transaction executes its commit operation, all its
AFIMs must be written to the log and the log must be saved
on a stable store - 42Commit Point of a Transactiono A transaction T reaches its commit point when:
1. all its operations have been executed successfully
2. the effect of all the transaction operations on the
database has been recorded in the log. - 43Simplest Recovery Managero Force
n No redo of committed transactions
o No-Steal
n No undo of incomplete transactions - 44Simplest Recovery Manager -- problemsForce
n High I/O costs!
o No-Steal
n Large cache! - 45Practical RecoveryNo-Force
n Need to Redo
o Steal
n Need to Undo
Informationen
- Beschreibung
- Karteikarten am Ohne Titel, erstellt von 101ldaniels . am 05/11/2016.
- Erstellt von
- 101ldaniels .
- Aufrufe
- 1
- Bewertung