Recovery Full

RECOVERY IN DATABASES

Lecture Series By :

Er. Kanwalvir Singh Dhindsa Deptt. of CSE & IT Website ::

http://dhindsa.myblogsite.com DBMS by Er. K.S.Dhindsa © 2006

Terminology : Recovery Process  Blocks (or Physical Blocks) -- Disk partitioned into fixed length storage units (Units of data transfer to and from the disk)  Buffer Blocks -- Blocks residing temporarily on main memory  Disk Buffer – Area of memory where block reside temporarily

DBMS by Er. K.S.Dhindsa © 2006

Terminology : Recovery Process  Input Operation  Output Operation

Buffer Block

Physical Block

A

A

Disk Buffer

MAIN MEMORY

HARD DISK DBMS by Er. K.S.Dhindsa © 2006

Recovery Process  ( I ) Read Operation :

Read(A,a)

 Find data block in disk where A resides (A in X)  System search for block in main memory  Input X command issued : Block copied from D to M  A copied to temporary variable,a  Now, a=5000  a=a-1000  Now, a =4000 (local temporary variable value)

DBMS by Er. K.S.Dhindsa © 2006

Recovery Process  Read Operation :

Read(A,a)

a = a-1000

5000

A

4000

a

MAIN MEMORY

Program Variable

5000 A

HARD DISK DBMS by Er. K.S.Dhindsa © 2006

Recovery Process  (II) Write Operation :

Write (A,a)

 Find data block in disk where A resides (A in X)  System search for block in main memory  Input X command issued : Block copied from D to M  a copied to Database variable, A  Now, A=4000  Result updated ,now stored in main memory

DBMS by Er. K.S.Dhindsa © 2006

Recovery Process  Write Operation :

Write (A,a)

5000 to 4000

A

4000

a

MAIN MEMORY

Program Variable

5000 A

HARD DISK DBMS by Er. K.S.Dhindsa © 2006

Recovery Process  ( III ) Output (X)  Block X residing in main memory overwritten in disk 

Value of data item A=4000 is copied to disk permanently

 Result of Transaction saved

DBMS by Er. K.S.Dhindsa © 2006

Recovery Process  Output(X)

5000 to 4000

A

4000

a

MAIN MEMORY

5000 to 4000A

Program Variable

HARD DISK DBMS by Er. K.S.Dhindsa © 2006

Types of Recovery Techniques  In-Place Updating  System writes data item in the same location, thus overwriting the old value of data item on disk  Single copy of each data item maintained on the disk  Shadowing  System writes new data item at a different location  Multiple copies of data item maintained on disk

DBMS by Er. K.S.Dhindsa © 2006

SHADOW PAGING •

Transactions are execute serially

•

Maintain two page tables during the lifetime of a transaction –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

DBMS by Er. K.S.Dhindsa © 2006

SHADOW PAGING

1 2 3 4 5 6 7 8 9 10 11 Page Table DBMS by Er. K.S.Dhindsa © 2006

ENVIRONMENT USED IN SHADOW PAGING SCHEME

     

DB partitioned into fixed length blocks -- pages Assume n pages( numbered 1 through n ) which do not need to be stored in any particular order on disk There must be a way to find the ith page of the database for any given i Page table is used ,having n entries one for each database page Each page of the database has second entry pointing to the second page and so on. the logical order of database pages does not need to correspond to the physical order in which the pages are placed on disk DBMS by Er. K.S.Dhindsa © 2006

SHADOW PAGING : Write Operation •

• • • • • •

Suppose that the transaction performs a write (X) operation and that X-resides on the page, the write operation is executed as follows: If the ith page(that is, the page on which X resides ) is not already in main memory, then issue input(I) If it is the first write performed on the ith page by this transaction, then modify the current page table as follow : Find an unused page on the disk. Typically, the database system has access to a list of unused (free) pages Delete the page found in step 2a from the list of free page frames Modify the current page table such that the ith entry points to the page found in step 2a Assign the value of xj to X in the buffer page DBMS by Er. K.S.Dhindsa © 2006

SHADOW PAGING : COMMIT OPERATION • • •

•

Ensure that the buffer pages in the main memory that have been changed by the transaction are output to disk Output the current page table to disk { Shadow page table should not be overwritten, since it might be needed for recovery from a crash } Output the disk address of the current page table to the fixed location in stable storage containing the address of the shadow page table. This action overwrites the address of the old shadow page table. Therefore, the current page table has become the shadow page table, & the transaction is committed If the crash occurs prior to the completion of step 3, we revert to the state just prior to the execution of the transaction. If the crash occurs after the completion of step 3, the effects of the transaction will be preserved; no redo operation need to be invoked. DBMS by Er. K.S.Dhindsa © 2006

Advantages : SHADOW PAGING  ADVANTAGES OF SHADOW PAGING TECHNIQUE

• •

•

Overhead of log-record output is eliminated. Recovery from crashes is significantly faster(since no undo or redo operations are needed) It does not require the use of log, thus no undo/redo technique is required. This makes the recovery process simple.

DBMS by Er. K.S.Dhindsa © 2006

DISADVANTAGES : SHADOW PAGING 

COMMIT OVERHEAD

The commit of a single transaction using shadow paging requires: • To copy the actual data block from RAM to hard disk by output operation • To copy the current page table from the main memory(RAM) to the disk by output operation • Change the disk address of the current page table  Data Fragmentation : • In case of Shadow Paging,it is difficult to keep related database pages close together on disk,which results into disk fragmentation DBMS by Er. K.S.Dhindsa © 2006

DISADVANTAGES : SHADOW PAGING  Not suitable for multi-user environment For concurrent application,multiple transactions are running in parallel.Each transaction needs separate shadow and current page tables,which makes system very complex 

Garbage Collection Each time a transaction commits,database pages containing the old version of data changed by the transaction become inaccessible.In fig 11.14,page containing the old values of A and B i.e 2nd and 2rd page of disk will become inaccessible once the transaction of that example commits.Such pages are considered garbage,since they are not part of free space and donot contain useful information

 Periodically,it is necessary to find all the garbage pages,and to add them to the list of free pages.This process called garbage collection imposes additional overhead and complexity on the system DBMS by Er. K.S.Dhindsa © 2006

SHADOW PAGING 1

1

2 3

Current Page Table 1

2

4

2

3

5

3

6

4

4 5

7 8

5

6

9

6

7

10

7

8

11

8

12

9

9

13

10

14

10

11

15

11

16

Shadow Page Table

DBMS by Er. K.S.Dhindsa © 2006

SHADOW PAGING **************

1

1000

2

3000

3

A

B

*********

4

B

C

**********

5

C

2000

6

A

Current Page Table

7 ********* *********

Unused Pages on Disk : 7,11,13,14,15,16

*********

*********

8 9 10 11 12 13 14 15

Shadow Page Table

16

DBMS by Er. K.S.Dhindsa © 2006

SHADOW PAGING **************

1

1000

2

3000

3

A

B

*********

4

B

C

**********

5

C

2000

6

900

7

*********

8

*********

9

A

Unused Pages on Disk : 13,14,15,16

*********

2100 *********

Current Page Table

10 11 12 13 14 15

Shadow Page Table

16

DBMS by Er. K.S.Dhindsa © 2006

SHADOW PAGING  

• • • • • • •

Example of banking system Let T1 be a transaction that transfers Rs. 100 from account A to account B & T2 be transaction that withdraws Rs. 200 from account C. the initial values of A,B and C are Rs. 1000, Rs . 2000 and Rs. 3000 respectively. The sequence of operations is as follows : T1 read(A,a) T2 read(C,c) a=a-100 c=c-200 write(A,a) write(C,c) write(B,b) b=b+ 100 write(B,b) When the transaction starts the shadow page table stored in the disk is copied on to main memory and becomes current page table.

DBMS by Er. K.S.Dhindsa © 2006

SHADOW PAGING   • • •  • • • • •

T1 Read (A,a) The block containing the data item A is shifted from hard disk to RAM by input (X) operation and copied the value A to a i.e. 1000. a=a-100 Deduction of 100 is done in local variable a,now a contain 900. Write(A,a) if block contain data item A is not available in RAM, then input(X) operation is performed. (a) Find the unused space on the disk e.g. 7th page as shown in figure (b) Delete the page found in step 2 i.e. 7th page from the list of free page frame. Now the free page list becomes 11,13,14,15,16……. (c) Modify the current page as shown in figure such that the current page table entry for A now points to page 7th instead of page 2. 3. Assign the value of 900 to data item A in main memory.

DBMS by Er. K.S.Dhindsa © 2006

SHADOW PAGING  Read(B,b)

• • • • •

•

Block containing data item B, shifted to main memory and copied the value of B to b. B=b+100 {100 is added to local variable b} Write(B,b) Block containing B moved in RAM and a free page i.e. 11 is selected. The value of B i.e. 2100 is copied in page 11. Then 11th page is deleted from free page list and free page list becomes 13,14,15,16…. Modify the current page table such that B now points to page 11 instead of page 6

DBMS by Er. K.S.Dhindsa © 2006

SHADOW PAGING  COMMIT: •

All buffer pages in RAM that have changed by transaction T1 are output to the disk i.e. A’s value 1100 stored at page 7 and B’s value 2100 stored at page 11

•

Output the current page table to disk without overwriting the shadow page table

•

Output the disk address of current page table(suppose 20000) to the fixed location in storage table containing the address of the shadow page table, which change the address of old shadow page table (suppose 10000) to 20000. therefore, current page table now becomes shadow page table and transaction is completed DBMS by Er. K.S.Dhindsa © 2006

SHADOW PAGING  •

•

 •

CASE I System crash occurs before commit of transaction T1. then the current page table stored in main memory is also erased. If the system fails before the commit of a transaction Ti, we will get the previous state of data item from the shadow table CASE II If the system fails after the commit of transaction Ti, then , when the system recover it get the address of shadow page table from fixed location i.e. 20000.This table now point to modified value of A and B. So,there is no need to re-execute the transaction and it recover the data successfully.

DBMS by Er. K.S.Dhindsa © 2006

RECOVERY IN DATABASES

Lecture Series By :

Er. Kanwalvir Singh Dhindsa Deptt. of CSE & IT Website ::

http://dhindsa.myblogsite.com DBMS by Er. K.S.Dhindsa © 2006