[SOLVED] CS Information Management

Information Management
Transaction Management (slides provided by Prof. Samarati)

Universita degli Studi di (1)

Copyright By Assignmentchef assignmentchef

Transaction
Elementary unit of work executed by an application, characterized by
specific properties of correctness, robustness, and isolation Transactional system
Systems that provide a mechanism for the definition and execution of transactions by different concurrent transactions

Transaction (2)
Syntactically
A transaction is a procedure included between two commands begin transaction (bot)
end transaction (eot)
Within a transaction, one of the following commands is executed exactly once
commit work (commit): to terminate with success
rollback work (abort): to undo the procedure execution

Transaction (3)
A transaction is said to be well formed if
it starts with begin transaction
or equivalent, depending on the language
it ends with end transaction
it includes only one between commands commit and rollback
there is access operation (read/write) to the database after the execution of command commit or rollback

Transaction: example (1)
begin transaction x := x 10 y := y + 10
z := z y if z < 50 then commit work else rollbackend transaction Transaction: example (2)begin transactionupdate Accountset Total = Total – 100 where AccountNum= 123456update Accountset Total = Total + 100 where AccountNum = 123457commit workend transactionTransactions: propertiesTransactions should satisfy ACID properties Atomicity Consistency Isolation Durability A transaction is an atomic unit of work It cannot leave the database in an intermediate state a failure or an error before commit causes the UNDO of the work done up to that point a failure or an error after commit may require to REDO the work previously done, if its permanence on the database is not guaranteedPossible transaction: commit: usual behavior (99.9%) rollback requested by the application: suicide rollback requested by the system: homicide ConsistencyThe execution of a transaction should not violate integrity constraints defined for the database Integrity checks can be: immediate: during the transaction (the operation causing the violation is deferred: at the end of the transaction (if constraints are violated, the whole transaction is refused)The execution of a transaction should be independent from the execution of any other concurrent transaction Concurrent execution of a set of transactions should lead to the same result as an arbitrary sequential execution of the same transactionsDurabilityThe effects of a transaction that executed commit should not be lost The system should guarantee persistency of data even in case of failures and malfunctioning Transactions and system modules (1)ACID properties are checked and guaranteed by DBMS modules Atomicity: reliability manager Consistency: DDL compiler generates the verification activities enforced at transaction execution time Isolation: concurrency manager Durability: reliability manager Transactions and system modules (2) Transaction manager Coordinates activities related with transactions through the execution ofbegin transaction, commit, and rollback operations Reliability manager Guarantees atomicity and persistency by interacting with Access methods manager (to keep track of requested operations) Buffer manager (to request, whenever necessary, write operations on disks) Concurrency manager Manages isolation by filtering and possibly reorganizing accesses (requested by the access manager) Transactions and system modules (3)Query and update managerAccess methods manager Concurrency manager Transaction manager Buffer managerReliability manager Secondary storage manager Secondary storageReliability managerResponsible for: Execution of transactional commands begin transaction (B) commit (C) rollback (A, for Abort) Restart after malfunctions warm restart cold restartGuarantees atomicity and persistencyPersistent storageFailure resistant storage It is an abstraction No storage device can guarantee 0% failure probability Replication and robust write protocols can provide failure probability close to 0% Organized in different ways depending on the critical aspects of the application, for instance: atapeandadisk two mirrored disksA failure of persistent storage is considered catastrophic and impossible Sequential file that registers, in chronological order, the actions executed by different transactions Written on persistent storage (permanent archive) Managed by the reliability manager Enables undo and redo operations metaphors: Ariannas wire, Hansel and Gretels pieces of bread, …Log organization (1)Sequential file Records in chronological order Log organization (2)Two kinds of records: transaction begin, B(T) insert, I(T,O,AS) delete, D(T,O,BS) update, U(T,O,BS,AS) commit, C(T) abort, A(T) dump, (rare) checkpoint, (more frequent) Log organization (3)Checkpoint Checkpoint BUUCRecords of transaction TTop of the logLog organization (4) Transaction records include, for operations (insert, delete, update) before state (BS) State of the object before the operation after state (AS) State of the object afer the operation it is possible to perform undo and redo of operationsTo undo an action: update: undo(U(T,O,BS,AS)) copies value BS into object O delete: undo(D(T,O,BS)) recovers object O with value BS insert: undo(I(T,O,AS)) deletes object O To redo an action: update: redo(U(T,O,BS,AS)) copies value AS into object O delete: redo(D(T,O,BS)) deletes object O insert: redo(I(T,O,AS)) recovers object O with value AS Undo and Redo: idempotencyUndo and redo have idempotency property: an arbitrary number of undo/redo of the same action is equivalent to executing once the undo/redo of the action undo(A) … undo(A) = undo(A) redo(A) … redo(A) = redo(A)Idempotency guarantees correctness even in case of repeated execution of undo and redo operationsCheckpointSystem operation executed by the reliability manager with the coordination of the buffer manager Logs active transactions Updates secondary storage according to all the completedtransactions It is executed periodically Checkpoint execution Suspends accepting write, commit and abort operations from transactions Transfers (force) to secondary storage all the dirty pages of the buffer relative to transactions that have already committed Writes on the log in a synchronous manner (force) a checkpoint record CK(T1,…,Tn) containing the identifiers of active transactions Restarts accepting operations from transactions Compete copy of the database stored on persistent storage (backup) Created when the system is not operating inmutualexclusionwithalltheothertransactions Typically on tapeAt the end of the dump, a dump record (DUMP) is written in the log to signal that a backup has been executed at a given point in time and that identifies the copy Log record writeMust obey two rules: Write Ahead Log Commit-Precedence Write Ahead LogThe before state part of the log record should be written in the log before executing the corresponding operation on the database permits to undo write operations executed by transactions that did not commit permits to recover in case of failure after the execution of the operation on the database if the log was not written before the operation, the preceding value would be lost Commit-precedenceThe after state part of the log record should be written in the log before the commit permits to redo write operations that have already been decided by transactions that have committed, but whose updated pages have not been yet written on secondary storage by the buffer manager Write log recordsEven if the rules refer to before state and after state, practically the components of log records are written at the same timeA simplified version of the rules requires that logs are written: before the corresponding records in the database before executing commit Commit recordWritten, in a synchronous manner (force), in the log record by the transactions that chose to terminate successfully Failure before commit undo of the executed actions and restore of the initial status of the database Failure after commit redo of the actions to reconstruct the final status of the transactionAbort recordDefines the choice of abort (produced by system) Without modifying the decisions of the reliability manager, it can be: written asynchronously in the buffer containing the current block of the log later asynchronously rewritten on the log (flush) Combined writing: log and database (1)We distinguish three schemas, depending on whether the updates on the database performed by a transaction are executed (force of the buffer manager) Before commit After commit Some before and some after commit Combined writing: log and database (2)Database modified before commit no need of redo operationsB(T) U(T,X,BS,AS) U(T,Y,BS,AS) C(T)w(x) w(y)Writes on the logWrites on the database Combined writing: log and database (3)Database modified after commit no need of undo operationsB(T) U(T,X,BS,AS) U(T,Y,BS,AS) C(T)w(x) w(y) Combined writing: log and database (4)Database modified at any time (before and after) commit requires both undo and redo operations It is most commonly used because it allows the buffer manager tooptimize flush operations independently from the reliability managerB(T) U(T,X,BS,AS) U(T,Y,BS,AS) C(T)w(x) w(y)Two classes System failures: software bugs (e.g., of the operative system) or interruption of the working of devices (e.g., electric power failure) Device failures: failures of mass storage devices (e.g., scratches of the disk) System failuresSoftware bugs (e.g., of the operative system) or interruption of the working of devices (e.g., electric power failure) Central memory (and all buffers) content is lost The content of secondary storage is not lost warm restartDevice failuresFailures of mass storage devices (e.g., scratches of the disk) Central memory (and all buffers) content is lost Secondary memory content is lost Persistent storage content is not lost cold restart Failure managerFail-stop model: if the system identifies a failure forces the complete stop of transactions forces the correct working of the operative system (boot) performs a restart warm (for system failures) cold (for device failures) becomes usable again empty buffer Fail-stop modelNormal WorkingEnd recovery Restart: classification of transactionsConsidering a failure, there are two classes of transactions committed their actions should be repeated (redo) uncommitted their actions should be undone (undo) Warm restart (1)Phase 1: determine the set of transactions that need to be undone (UNDO) and repeated (REDO) read the log backward from the end till the most recent checkpoint initialize UNDO e REDO UNDO := transactions in the checkpoint REDO := read the log forward: for each B(T) UNDO := UNDO E {T} for each C(T) UNDO := UNDO – {T} REDO := REDO E {T}Warm restart (2)Phase 2: recovery read the log backward for each action A of transactions in UNDO undo(A)go back till the first action of the oldest transaction in UNDO E REDO read the log forward for each action A of transactions in REDO redo(A)Warm restart (3) atomicity: all the active transactions at the time of failure leave the database in the initial or final status persistency: all the pages of active transactions are written on secondary storage Warm restart: example (1)B(T1), B(T2), I(T2,O1,A1), B(T3), I(T3,O2,A2), D(T1,O3,B3), B(T4), U(T3,O2,B4,A4), I(T4,O4,A5), U(T4,O2,B6,A6), C(T2), CK(T1,T3,T4), C(T4), B(T5), D(T5,O4,B7), U(T1,O2,B8,A8), A(T3), C(T1), failure determine UNDO and REDO setsWarm restart: example (1)B(T1), B(T2), I(T2,O1,A1), B(T3), I(T3,O2,A2), D(T1,O3,B3), B(T4), U(T3,O2,B4,A4), I(T4,O4,A5), U(T4,O2,B6,A6), C(T2), CK(T1,T3,T4), C(T4), B(T5), D(T5,O4,B7), U(T1,O2,B8,A8), A(T3), C(T1), failure determine UNDO and REDO sets Warm restart: example (2)B(T1), B(T2), I(T2,O1,A1), B(T3), I(T3,O2,A2), D(T1,O3,B3), B(T4), U(T3,O2,B4,A4), I(T4,O4,A5), U(T4,O2,B6,A6), C(T2), CK(T1,T3,T4), C(T4), B(T5), D(T5,O4,B7), U(T1,O2,B8,A8), A(T3), C(T1), failure UNDO {T3,T5} Warm restart: example (2)B(T1), B(T2), I(T2,O1,A1), B(T3), I(T3,O2,A2), D(T1,O3,B3), B(T4), U(T3,O2,B4,A4), I(T4,O4,A5), U(T4,O2,B6,A6), C(T2), CK(T1,T3,T4), C(T4), B(T5), D(T5,O4,B7), U(T1,O2,B8,A8), A(T3), C(T1), failure UNDO {T3,T5} Warm restart: example (2)B(T1), B(T2), I(T2,O1,A1), B(T3), I(T3,O2,A2), D(T1,O3,B3), B(T4), U(T3,O2,B4,A4), I(T4,O4,A5), U(T4,O2,B6,A6), C(T2), CK(T1,T3,T4), C(T4), B(T5), D(T5,O4,B7), U(T1,O2,B8,A8), A(T3), C(T1), failure UNDO {T3,T5} record actionD(T5,O4,B7) U(T3,O2,B4,A4) I(T3,O2,A2)Warm restart: example (2)B(T1), B(T2), I(T2,O1,A1), B(T3), I(T3,O2,A2), D(T1,O3,B3), B(T4), U(T3,O2,B4,A4), I(T4,O4,A5), U(T4,O2,B6,A6), C(T2), CK(T1,T3,T4), C(T4), B(T5), D(T5,O4,B7), U(T1,O2,B8,A8), A(T3), C(T1), failure UNDO {T3,T5}D(T5,O4,B7) U(T3,O2,B4,A4) I(T3,O2,A2)insert O4, O4:=B7 O2:=B4Warm restart: example (3)B(T1), B(T2), I(T2,O1,A1), B(T3), I(T3,O2,A2), D(T1,O3,B3), B(T4), U(T3,O2,B4,A4), I(T4,O4,A5), U(T4,O2,B6,A6), C(T2), CK(T1,T3,T4), C(T4), B(T5), D(T5,O4,B7), U(T1,O2,B8,A8), A(T3), C(T1), failure REDO {T1,T4} Warm restart: example (3)B(T1), B(T2), I(T2,O1,A1), B(T3), I(T3,O2,A2), D(T1,O3,B3), B(T4), U(T3,O2,B4,A4), I(T4,O4,A5), U(T4,O2,B6,A6), C(T2), CK(T1,T3,T4), C(T4), B(T5), D(T5,O4,B7), U(T1,O2,B8,A8), A(T3), C(T1), failure REDO {T1,T4}D(T1,O3,B3) I(T4,O4,A5) U(T4,O2,B6,A6) U(T1,O2,B8,A8)Warm restart: example (3)B(T1), B(T2), I(T2,O1,A1), B(T3), I(T3,O2,A2), D(T1,O3,B3), B(T4), U(T3,O2,B4,A4), I(T4,O4,A5), U(T4,O2,B6,A6), C(T2), CK(T1,T3,T4), C(T4), B(T5), D(T5,O4,B7), U(T1,O2,B8,A8), A(T3), C(T1), failure REDO {T1,T4}D(T1,O3,B3) I(T4,O4,A5) U(T4,O2,B6,A6) U(T1,O2,B8,A8)insert O4, O4:=A5 O2:=A6Warm restart: exercise DUMP, B(T1), B(T2), B(T3), I(T1,O1,A1), I(T2,O2,A2), C(T1), B(T4), D(T4,O3,B3), CK(. . . ), U(T2,O4,B4,A4), D(T3,O5,B5), B(T5), A(T4), U(T5,O6,B6,A6), CK(. . . ), D(T5,O7,B7), C(T2), B(T6), I(T6,08,A8), A(T5), C(T3), FAILURE Cold restartPhase 1: recover the database in the same status as at the time of failure access the dump and selectively copy all the damaged parts of the database access the most recent dump record registered in the log read the log forward applying, for the damaged part, both the actions of the database and commit/abort actions Execute warm restart CS: assignmentchef QQ: 1823890830 Email: [email protected]