The recovery manager of such a system in turn ease the task of writing fault-tolerance application programs

introduction

A collection of s u c h s t a t e m e n t s is r e q u i r e d to m a k e a c o n s i s t e n t t r a n s f o r m a t i o n o f t h e d a t a b a s e . T o t r a n s f e r f u n d s f r o m o n e a c c o u n t to a n o t h e r , for e x a m p l e , r e q u i r e s t w o S Q L s t a t e m e n t s : o n e to d e b i t t h e first a c c o u n t a n d o n e t o c r e d i t t h e seco n d a c c o u n t . I n a d d i t i o n , t h e t r a n s a c t i o n p r o b a b l y r e c o r d s t h e t r a n s f e r in a h i s t o r y file for l a t e r r e p o r t i n g a n d for a u d i t i n g p u r poses.

the needs of consistency

ensures its correctness by ensuring that it performs the desired transformation on both the database state and the outside world

[!PDF|yellow] [[The Recovery Manager of a Data Management System.pdf#page=2&selection=85,2,92,22&color=yellow|The Recovery Manager of a Data Management System, p.2]] atomic: either all actions are performed (the transaction has an effect) or the results of all actions are undone (the transaction has no effect);

[!PDF|yellow] [[The Recovery Manager of a Data Management System.pdf#page=2&selection=94,3,98,7&color=yellow|The Recovery Manager of a Data Management System, p.2]] urable: once the transaction completes, its effects cannot be lost due to computer failure

[!PDF|yellow] [[The Recovery Manager of a Data Management System.pdf#page=2&selection=100,2,111,9&color=yellow|The Recovery Manager of a Data Management System, p.2]] consistent: the transaction occurs as though it had executed on a system which sequentially executes only one transaction at a time

where is "isolation" property?

the SQL programmer brackets the transformations with the SQL statements, BEGIN__ TRANSACTION to signal the beginning of the transaction and COMMIT__ TRANSACTION to signal its completion. If the programmer wants to return to the beginning of the transaction, the command RESTORE__TRANSACTION will undo all actions since the issuance of the BEGIN__TRANSACTION command

semantic

System R generally runs several transactions concurrently. The concurrency control mechanism of System R hides such concurrency from the programmer by a locking technique [EswA76, GRAY78, NAUM78] and gives the appearance of a consistent system

support for concurrency

System R consists of an external layer called the Research Data System (RDS), and a completely internal layer called the Research Storage System (RSS)

structure

The external layer provides a relational data model, and operators thereon. It also provides catalog management, a data dictionary, authorization, and alternate views of data.

User-facing relational model

The RSS is a nonsymbolic record-at-atime access method. It supports the notions of file, record type, record instance, field within record, index (B-tree associative and sequential access path), parent-child set (an access path supporting the operations PARENT, FIRST__CHILD, NEXT__SIBLING, PREVIOUS__SIBLING with direct pointers),

low-level internal

also responsible for recovering the data to their most recent consistent state in the event of transaction, action, system, or media failure or a user request to cancel the transaction.

transaction and recovery at RSS level

The recovery manager eases the task of writing fault-tolerant programs.

motivation

The transaction model is an unrealizable ideal. At best, careful use of redundancy minimizes the probability of unrecoverable failures and consequent loss of committed updates

redundant copies are needed

Each RSS action is atomic-it either happens or has no effect--and consistent--if any two actions relate to the same object, they appear to execute in some serial order. These two qualities are ensured by (1) undoing the partial effects of any actions which fail and (2) locking necessary RSS resources for the duration of the action.

atomic + consistency

In a multiuser environment, transactions take on the additional attribute that any two transactions concurrently operating on common objects appear to run serially (i.e., as though there were no concurrency). This property is called consistency and is handled by the RSS lock subsystem [ESWA76, GRAY76, GRAY78, NAUM78].

concurrency enforced using lock

The RSS defines the additional notion of transaction save point. A save point is a firewall which allows transaction undo to stop short of undoing the entire transaction

save point

This model of recovery is a subset of the recovery model formulated by Davies and Bjork [BJOR73, DAVI73]

references

Unlike their model, System R transactions have no parallelism within a transaction (i.e., if multiple nodes of a network are needed to execute a single transaction, only one node executes at a time). Further, System R allows only a limited form of transaction nesting via the use of save points (each save point may be viewed as the start of an internal transaction). These limitations stem from our inability to find an acceptable implementation for the more general model.

no acceptable implementation

All persistent System R data are stored in files.

persistent data = file as 4096-byte pages

A buffer manager maps all the files into a virtual memory buffer pool shared

buffer pool map files to memory, volatile

Nonshadowed files have no automatic recovery. T h e user is responsible for making and storing redundant copies of these files. System R simply updates nonshadowed file pages in the buffer pool. Changes to nonshadowed files are recorded on disk when the pages are r e m o v e d from the buffer pool (by the L R U algorithm) and when the file is saved or closed

temporary scratch file, intermediate files

The RSS maintains two online versions of shadowed files, a shadow version and a current version [!PDF|important] [[The Recovery Manager of a Data Management System.pdf#page=8&selection=123,0,125,30&color=important|The Recovery Manager of a Data Management System, p.8]] R S S actions affect only the current version of a file and never alter the shadow version

current version = working copy, shadow version = backup copy

when a shadow page is updated in the buffer pool for the first time, a new disk page frame is assigned to it. Thereafter, when that page is written from the buffer pool or read into the buffer pool, the new frame is used

only modified page get new page frame

The paper by Lorie [LoRI77] describes the implementation in greater detaft.

reference

shadow-version/current-version dichotomy has strong ties to the old-master/ new-master dichotomy common to most batch EDP systems

[!PDF|yellow] [[The Recovery Manager of a Data Management System.pdf#page=9&selection=85,12,87,40&color=yellow|The Recovery Manager of a Data Management System, p.9]] his technique does not seem to generalize to concurrent transactions on a shared file

need additional mechanism for transaction

he shadow mechanism is combined with an incremental log of all the actions a transaction performs

incremental log for transaction

transaction modifies a logged file, a new record is appended to the log.

log mechanism

The transaction log is written to disk before the shadow database is replaced by the current database state

transactions's effect is durable

The transaction commit action writes a commit log record in the log buffer and then forces all the transaction's log records to disk

undo uncommitted update + transaction redone from the shadow stage

The effect of any uncommitted transaction can be undone by reading the log of that transaction backward, undoing each action in turn.

undo mechanism

One can easily restore a transaction to its beginning by undoing all its updates and then releasing all its locks and dropping all its cursors

transaction save points

To restore to a save point, the recovery manager must know the name and state of each active cursor and the name of each lock held at the save point

what RSS needs for save point

checkpoint records information on disk which helps locate the end of the log at restart and correlates the database state with the log state. A checkpoint saves all logged shadow files so that no work prior to the checkpoint will have to be redone at restart

system checkpoints limit the amount of work at restart

The RSS uses a lower level of consistency, augmented by a transaction log, to produce a transaction-consistent state. The RSS implements checkpoints which are snapshots of the system at a time when no RSS actions are in progress

RSS approach to system checkpoint instead of quiescing

Checkpoints are taken after a specified amount of log activity or at system operator request. At checkpoint, a checkpoint record is written in the log. The checkpoint record contains a list of all transactions in progress and pointers to their most recent log records

how system checkpoint works

is essential that all transactions lock all updates in exclusive mode and hold all such locks until the transaction is committed or undone. In fact System R automatically acquires b

recovery safety

nnot tolerate deadlock (we do not want to have to undo undo's)

2nd issue in recovery

ks because other RSS actions are in progress and because RSS actions release some locks at the end of each RSS action (e.g., physical page locks when logical rec

lockings are required

deadlock victims; whenever they get into a deadlock with some other transactions, the other transactions are preempted.

golden txn has higher priority

Writing recoverable actions (ones which can undo and redo themselves) is quite hard. Subjectively, writing a recoverable action

implementation cost

Each transaction commit adds two I/Os to the cost of the transaction

IO overhead

n another application in which the database is all resident in central memory, the log accounts for all of the disk I/O. IMS Fast Path solves this problem by logging several transactions in one I/O so that one gets less than one log I/O per transaction. The shadow mechanism when used with large databases often implies extra I/O, both during normal operation and at check-point.