Transcript Recovery

1
UU - DIS - UDBL
DATABASE SYSTEMS - 10p
Course No. ??
A second course on development of
database systems
Kjell Orsborn
Uppsala Database Laboratory
Department of Information Science, Uppsala University,
Uppsala, Sweden
Kjell Orsborn
2016-04-02
2
UU - DIS - UDBL
Introduction to Recovery Techniques
Elmasri/Navathe ch 21
Lecture 9
Kjell Orsborn
Department of Information Science
Uppsala University, Uppsala, Sweden
Kjell Orsborn
2016-04-02
3
UU - DIS - UDBL
Lecture 9
(Elmasri/Navathe ch. 21)
• Recovery techniques (ch. 21)
Kjell Orsborn
2016-04-02
4
UU - DIS - UDBL
Recovery
–
–
–
–
Recovery is needed after aborted transactions.
The goal is to restore the database to an earlier and consistent state.
Is possible by saving a log file.
The recovery manager is a subsystem of the (DBMS that handles
these problems.
– Strategy:
– a) If the disc crasches, fetch the latest backup copy of the
database and use the log file to reproduce the latest uppdates.
– b) If some other type of failure has caused the inconsistency,
eleminate (undo) the updates that led to the inconsistency.
Kjell Orsborn
2016-04-02
5
UU - DIS - UDBL
Recovery . . .
– To be able to keep the atomicty principle for the transactions the system
must handle different typesof failure that can cause that the execution of
a transaction is aborted.
– The system must reassure that either:
• all operations in a transaction succeed completely and their intended effect is
registered in the database, or
• the transaction is aborted without any side effect.
– The following operations are required:
• Rollback:
• Undo:
• Redo:
Kjell Orsborn
eleminate side effects of a failured
transaction.
eleminate a single operation.
redo one/several operations (transactions).
2016-04-02
6
UU - DIS - UDBL
System log - the log file
• During the execution of transactions the following följande
information is stored on the log (file):
(Start, T)
(Write,T,X,old_val,new_val)
(Read, T, X)
(Commit, T)
(Check point)
Kjell Orsborn
Marks the start for transaction T.
Marks that T changes the value of X
from old_val to new_val.
Marks that T reads the value of X.
Marks that T is finished with all
accesses and its effect can be
introduced in the database.
A feature described later.
2016-04-02
7
UU - DIS - UDBL
Commit point for a transaction
• When a transaction is finished with all its operations (and no
errors have ocurred) it reaches its commit point.
• Failured transactions do not reach their commit point.
Read/Write
Begin
Active
Commit
Partially
Committed
Committed
Failed
Kjell Orsborn
2016-04-02
Terminated
8
UU - DIS - UDBL
Rollback - cascading rollback
• Rollback: when a transaction fails to reach its commit point, its
effects must be eleminated, i.e. all values that have been
changed by the operations in the transaction must be restored.
• Cascading rollback: when rollback is applied to a transaction
T, we must apply rollback to all transactions S that have read
item values that has been updated by T. We must then do the
same for transactions that have read values that each such S has
updated and so forth.
• (Read, T, ...) records in the log file are used to decide if
cascading (recursion) is required or not.
Kjell Orsborn
2016-04-02
9
UU - DIS - UDBL
Deferred update
(or no-undo/redo)
• A recovery method that defers actual database updates until a
transaction reaches its commit point.
• Under the execution of the operations, updates are registered in
the log file. When the commit point is reached, first the log file
is updated on secondary memory and thereafter the actual
updates is written to the database.
• If a transaction fails before it reaches the commit point, no undo
operations are required since the database has not been effected.
Kjell Orsborn
2016-04-02
10
UU - DIS - UDBL
Recovery using the deferred update
model
• Recovery according to the deferred update model:
1. Start from the last record in the log file and traverse backwards. Create
two lists:
• C
• NC
transactions that have reached their commit points
transactions that have not reached their commit points.
2. Start from the beginning of the log file and redo all (Write,T,...) for all
transactions T in the list C.
3. Restart all transactions in the list NC.
• If the log file is long, step 2 will take long time. An
improvement of this method is accomplished by introducing
what’s called check points.
Kjell Orsborn
2016-04-02
11
UU - DIS - UDBL
Check points
• Check points are special records stored in the log file to
mark that all write operations (for committed transactions)
to this point have been introduced in the database.
• This means that it is not necessary to redo operations
before this point when a crasch ocurres.
• The recovery manager decides when a check point should
be created.
Kjell Orsborn
2016-04-02
12
UU - DIS - UDBL
Creating check points
The creation of a check point usually include:
1. Initiation of new transactions is temporarily stopped.
2. Wait until all active transactions reach their commit points or are aborted.
3. Identify all block in primary memory that have been uppdated but not
rewritten to secondary memory.
4. All these blocks are written to secondary memory.
5. A check point record is stored in the log file and then the log file is
written to disc.
6. Continue with the transactions.
Kjell Orsborn
2016-04-02
13
UU - DIS - UDBL
Recovery using deferred updates
with check pointing
• Recovery according to the deferred update model with check
points:
1. Start from the last record in the log file and traverse backwards until a
check point is reached. Create two lists:
• C
• NC
transactions that have reached their commit points
transactions that have not reached their commit points.
2. Start from the position after the check point in the log file and redo all
(Write,T,...) for all transactions T in the list C.
3. Restart all transactions in the list NC.
• Step 2 is much cheaper now since the set C is much smaller.
Kjell Orsborn
2016-04-02
14
UU - DIS - UDBL
Immediate uppdates
(or undo/redo)
• In this update model, the effect of update operations is
introduced in the database even before there commit point
has been reached. Operations are registered in the log file
(on disc) before they are applied to the database.
• If a transaction is aborted before the commit point, its side
effects must be eliminated (rollback).
• To UNDO, i.e. eleminate, an operation means that the
value of item X is reset to old_value.
– (Write,T,X,old_value,new_value)
Kjell Orsborn
2016-04-02
15
UU - DIS - UDBL
Recovery using immediate updates
• Recovery according to the immediate update model:
1. Start from the last record in the log file and traverse backwards until a
check point is reached. Create two lists:
• C
• NC
transactions that have reached their commit points
transactions that have not reached their commit points.
2. Create a list R with transactions that has read an item updated by a
transaction in NC. (OBS that this step must be applied recursively).
3. Start from the last record in the log file and apply the UNDO procedure
to all (Write,T,...) where T NCR.
4. Start from the check point and REDO all transactions (Write,T,...) such
that T C and T R.
5. Restart all failured transactions.
Kjell Orsborn
2016-04-02
16
UU - DIS - UDBL
Shadow paging
• Alternative to log-based recovery
• Idea: maintain two page tables during the lifetime of a trans-action the current page table, and the shadow page table
• Store the shadow page table in nonvolatile storage, such that state of
the database prior to transaction execution may be recovered. Shadow
page table is never modified during execution
• To start with, both the page tables are identical. Only current page
table is used for data item accesses during execution of the
transaction.
• Whenever any page is about to be written for the first time, a copy of
this page is made onto an unused page. The current page table is then
made to point to the copy, and the update is performed on the copy
Kjell Orsborn
2016-04-02
17
UU - DIS - UDBL
Shadow paging cont’d
• To commit a transaction:
1. Flush all modified pages in main memory to disk
2. Output current page table to disk
3. Make the current page the new shadow page table
– keep a pointer to the shadow page table at a fixed (known) location on
disk.
– to make the current page table the new shadow page table, simply update
the pointer to point to current page table on disk
• Once pointer to shadow page table has been written, transaction is
committed.
• No recovery is needed after a crash — new transactions can start right
away, using the shadow page table.
• Pages not pointed to from current/shadow page table should be freed
(garbage collected).
Kjell Orsborn
2016-04-02
18
UU - DIS - UDBL
Shadow paging cont’d
• Advantages of shadow-paging over log-based schemes – no
overhead of writing log records; recovery is trivial
• Disadvantages :
– Commit overhead is high (many pages need to be flushed)
– Data gets fragmented (related pages get separated)
– After every transaction completion, the database pages containing old
versions of modified data need to be garbage collected and put into the
list of unused pages
– Hard to extend algorithm to allow transactions to run concurrently
Kjell Orsborn
2016-04-02
19
UU - DIS - UDBL
Database security and authorization
• A DBMS normally includes a subsystem for security and
authorization that is responsible for security against
unauthorized access to the database.
• The reasons behind the introduction of restrictions on the
availability of data varies a lot but e.g.:
– legal or ethical reasons (e.g. person databases).
– policy reasons within govermental, public, or industrial organisations
(e.g. credit validation and medical information).
– system-related reasons to prevent unauthorized access to database
systems.
– security levels within organisations (secret vs. free info)
Kjell Orsborn
2016-04-02
20
UU - DIS - UDBL
Hence, one would like to protect
the database ...
•
Against who and/or what?
– Corrupt, disloyal, naughty, evil, wily, malicious, despiteful, hateful
malevolent, vicious and maybe simply hostile users.
– Erroneuous data and program errors.
– Failure in hardware/software that cause corrupeted data.
• How?
– Introduce integrity constraints in the database.
– Introduce recovery system.
– Introduce security mechanisms.
Kjell Orsborn
2016-04-02
21
UU - DIS - UDBL
Security mechanisms
• Several of the security questions that exist in database systems
are not unique for the database field but also exist in other types
of systems.
– e.g. in the design of operative systems
• Security mechanisms:
– Discretionary access control (or privilige-based security mechanisms)
issuing priviliges to users for access rights to certain data.
– Mandatory access control (or multi-level security mechanisms) using
security classes.
– Access control - user accounts and passwords to prevent access to the
system itself.
– Statistical database security - säkerhetsmekanismer mot missbruk av
statistiska databaser.
Kjell Orsborn
2016-04-02
22
UU - DIS - UDBL
Security mechanisms . . .
• Security mechanisms cont’d...
– Data encryption - e.g. for data transported overcommunication
networks.
– Physical protection - e.g. secure procedures for storage and
handling of hard disks and backup copies.
– Mechanisms (e.g. fire walls and virus prevention/repair software)
for providing protection against data virus.
Kjell Orsborn
2016-04-02
23
UU - DIS - UDBL
Security administration
• The database administrator is responsible for the management of
the database security :
–
–
–
–
Create accounts and passwords
Grant priviliges
Revoke priviliges
Assign security levels
• Logging of user activities
– The database log must contain user data
– The audit trail - a database log used mainly for security handling and
subsequent analysis.
Kjell Orsborn
2016-04-02
24
UU - DIS - UDBL
Privilige-based mechanisms
• A common method for discretionary access control in
database systems is to grant and revoke priviliges.
• Two types of privilige levels exists:
– the account level, general priviliges for single users (not in SQL92)
(create schema, create table, create view, alter, drop, modify,
select)
– the relation level, priviliges for specific relations and views. Even
priviliges on attribute level exists. (supported in SQL92)
Kjell Orsborn
2016-04-02
25
UU - DIS - UDBL
Privilige-based mechanisms ...
• The acccess matrix model
– Access matrix: M(s,o) -> p
where s, subject, are rows in the matrix (users, accounts, program),
and o, object, are columns in the matrix (relation, tuple, column,
view, operations), and p is the privilige type (read, update)
• Every relation is owned by an account
– e.g. account that created the relation.
• The owner has complete access rights
• The owner can delegate access rights to other subjects
Kjell Orsborn
2016-04-02
26
UU - DIS - UDBL
Priviliges in SQL92
• In SQL92 the following priviliges exist on the relation
level:
– SELECT
– MODIFY (dvided further into UPDATE, DELETE, INSERT)
• INSERT and UPDATE also on attribute level
– REFERENCES
• also on attribute level
• Priviliges can be retracted by ...
– REVOKE
Kjell Orsborn
2016-04-02
27
UU - DIS - UDBL
Priviliges in SQL92 . . .
• Example :
• DBA:
CREATE SCHEMA EXAMPLE AUTHORIZATION A1;
• A1:
CREATE TABLE EMPLOYEE(...)
CREATE TABLE DEPARTMENT(...)
• GRANT: Delegate priviliges to subject (i.e. set element in the
access matrix)
• Syntax:
GRANT privilige types ON object TO subject
Kjell Orsborn
2016-04-02
28
UU - DIS - UDBL
Priviliges in SQL92 . . .
• Example:
• A1:
GRANT INSERT,DELETE ON EMPLOYEE,DEPARTMENT TO
A2;
• OBS: A2 can not forward priviliges
GRANT SELECT ON EMPLOYEE,DEPARTMENT TO A3 WITH
GRANT OPTION;
• => A3 can forward priviliges to other accounts.
Kjell Orsborn
2016-04-02
29
UU - DIS - UDBL
Priviliges in SQL92 . . .
• A3:
GRANT SELECT ON EMPLOYEE TO A4
• A2:
REVOKE SELECT ON EMPLOYEE FROM A3
•
•
•
•
=> A4 can not either access EMPLOYEE!
GRANT and REVOKE can also be applied on views.
One can be granted priviliges from more than one source
Actual priviliges = the union of all priviliges recieved
Kjell Orsborn
2016-04-02
30
UU - DIS - UDBL
Multi-level mechanisms
• Security mechanisms based on classification of data and users
into security classes are called multi-level security control or
mandatory access control.
• Not supported in commercial system.
• There is demand within , military, and intelligence organizations
as well as in industrial and service enterprises.
• Usually, a combination of priviliges and multi-level control is
used.
Kjell Orsborn
2016-04-02
31
UU - DIS - UDBL
Multi-level mechanisms ...
• One classifies subject and object into security classes such
as: TS (top secret), S (secret), C (confidential), U
(unclassified), incorporating an order TS > S > C > U.
• An extended access matrix: M(s,o) -> <p,c>,
– where s, subject, are rows in the matrix (users, accounts, program),
and o, object, are columns in the matrix (relation, tuple, column,
view, operations),
and p is privilige iype (read, update),
and c is security class.
Kjell Orsborn
2016-04-02
32
UU - DIS - UDBL
Multi-level mechanisms ...
• Classification of subject - object are denoted by:
– class(s) and class(o) respectively.
• Two restrictions are forced upon data at access based on
subject/object classification .
– A subject S is not allowed to have read access for an object O if
not class(s) ≥ class(o) holds. This is called simple security
property.
– A subject S is not allowed to have write access for an object O if
not class(s) ≤ class(o) holds. This is called *-property or star
property.
Kjell Orsborn
2016-04-02
33
UU - DIS - UDBL
Authorization using views
• Views can also be used as a security mechanism.
• Transformation of DML queries for certain users.
– e.g. add a selection and projection to each query that WALMART
employees asks. The DBA provide:
CREATE TABLE SUPPLIES( STORE CHAR,
ITEM CHAR,
PRICE DECIMAL(10,2),
PRIMARY KEY(STORE, ITEM))
CREATE VIEW WMSUPPLIES AS
SELECT STORE, ITEM, PRICE
FROM SUPPLIES
WHERE STORE = ‘WALMART’
Kjell Orsborn
2016-04-02
34
UU - DIS - UDBL
Authorization using views . . .
• Priviliges are granted:
–
GRANT SELECT, INSERT, DELETE ON
WMSUPPLIES TO WALLIES
• WALLIES can not access SUPPLIES only WMSUPPPLIES
–
SELECT PRICE
FROM WMSUPPLIES S
WHERE S.ITEM = ‘TOMATOES’
• Translated to:
–
Kjell Orsborn
SELECT PRICE
FROM SUPPLIES S
WHERE S.ITEM = ‘TOMATOES’ AND
S.STORE = ‘WALMART’
2016-04-02
35
UU - DIS - UDBL
Authorization using views . . .
• Advanced security policies can be accomplished with views
• OBS! views are not always updatable
• The key in the base table must be included in the view definition
Kjell Orsborn
2016-04-02
36
UU - DIS - UDBL
Statistical database security
• Statistical databases often include sensitive information about single
individuals that must be protected from unallowed use.
• However, statistical information should be extractable from the
database.
• Statistical database security must prohibit access of individual data
elements.
• Three main security mechanisms: conceptual, restriction-based, and
perturbation-based. Examples:
– prohibit queries on attribute level
– only queries for statistical aggregation (statistical queries)
– statistical queries are prohibited when the selection from the population is
to small.
– prohibit repeated statistical queries on the same tuples.
– introduce distortion into data.
Kjell Orsborn
2016-04-02