[Bernstein09] Section 7.6. Shadow-paging Algorithm

7.6.

Shadowpaging is a simple way to implement a recovery manager. It is one ofthe easiest recovery algorithms to implement because it does notrequire a log manager, which is a relatively complex component. It isnot widely used in commercial products because it does not scale up tohigh transaction rates as well as logging. However, since it’s simple,we’ll describe it first.

Themain idea is to store all of a transaction’s updates in a shadow copyof the database. There is also a master copy of the database, whosestate represents the execution of all committed transactions and noaborted ones. When the transaction commits, the shadow copy is swappedwith the master copy of the database, thereby installing the updates.

Toenable this strategy, the master database is structured as a tree ofpages. Let’s assume that the database consists of a set of files, whereeach file is a sequence of pages. In this case, the root page of themaster database contains pointers to the root page of each file. Theroot page of a file is a page table that contains a sequence ofpointers to the pages of the file. To keep things simple, let’s assumethat files are small enough that pointers to all of the pages of a filecan fit in the file’s root page. For example, in Figure 7.12 the database has two files, named A and B. File A has a page table identified by A_Pt,m, where “m” means “master.” The figure shows pointers to the first two pages of the file, A₁ and A₂.

Figure 7.12. Tree-structured Database for Shadow Paging. There are two files, A and B. A_Pt,m is the master copy of file A’s page table that points to the pages of file A, such as A₁ and A₂.

Tokeep this description simple, let’s assume that transactions executeserially. Thus, at most one transaction is active at any given time.

Inmain memory each transaction has a cached copy of the page table ofeach file it reads or writes. For example, the cached page tables fortransaction T_i are shown in Figure 7.12.Initially, the contents of these cached page tables is the same astheir content in stable storage. As the transaction executes, pages arefetched into main memory. The transaction updates some of those pages.When one of those dirty pages is flushed, it is written to an unusedlocation of stable storage. That is, the previous copy of the page isnot overwritten. Then, the copy of the page table in main memory isupdated to point to the updated page in stable storage, and the updatedpage table entry is marked as “updated.” For example, Figure 7.13 shows the result of flushing a new version of page A₂, where A_2,old is the original copy of the page before transaction T_i performed its update and A_2,new is the version of the page that includes the update.

Figure 7.13. The Result of Flushing a Dirty Page. An updated version of page A₂has been flushed to stable storage into an unused location. The mainmemory page table is updated to point to it and is marked as updated.

To commit a transaction, do the following:

1. For each page P that the transaction updated, if P is dirty in cache, then flush it as described earlier.

2. Initialize a list called UpdatedFiles to include the name of every file updated by the transaction.

3. For each file F in UpdatedFiles, do the following:

   • Set a write lock on F’s root page. Let L be its location in stable storage.

   • Read F’s root page into cache. Call this the shadow copy of F’s page table.

   • For each page of F that is marked as updated in F’s cached page table, copy that page’s entry from F’s cached page table into its shadow page table.

   • Write the shadow copy of F’s page table to an unused location L′ of stable storage.

   • Replace L by L′ in the entry for F in UpdatedFiles.

For example, if a transaction updated page A₂ of file A, and B₁ of file B, then at the end of this procedure, the state of main memory and stable storage would be as shown in Figure 7.14.

Figure 7.14. System State after Partial Commit. Transaction T_i updated pages A₂ and B₁. In the first part of the commit procedure, shadow page tables A_Pt,s and B_Pt,s are constructed and flushed, and UpdatedFiles points to them.

When this is done, we repeat essentially the same process for the root page of the database, as follows:

1. Set a write lock on the root page of the database.

2. Read the root page of the database into cache. Call this the shadow copy of the database’s page table.

3. For each file F in UpdatedFiles, copy the associated pointer (to F’s shadow page table in stable storage) into F’s entry in the database’s shadow page table.

4. Overwrite the database’s root page in stable storage with the shadow copy of the database’s root page. This write operation of a single page causes all the transaction’s updated pages to become part of the master database.

5. Release all the locks that the transaction obtained on data pages, file page tables, and the database’s root page. Discard the UpdatedFiles list and the transaction’s cached copies of page tables.

As a result of step 4 (shown in Figure 7.15) the shadow page tables of Figure 7.14 are now master page tables. The former master page tables are now garbage and hence are labeled “g” in the figure (A_Pt,g and B_Pt,g). The old versions of pages updated by the transaction are also garbage, that is, pages A_2,old and B_1,old.

Figure 7.15. System State after Commit. The shadow page tables of Figure 7.14are now master page tables. The former master page tables are nowgarbage. The UpdatedFiles list and transaction’s cached page tableshave been deallocated.

Toabort a transaction, simply discard all its updated pages in stablestorage and cache. Since the database root page and the page tables itpoints to are unchanged, none of the pages updated by the abortedtransaction are part of the master database. Therefore, there isnothing to undo.

Oneloose end in this story is how to manage available space in stablestorage. One approach is to use a list of available space, call itAvail, and treat it as another file. For example, Avail could be a bitmap, a binary array where each bit Avail[j] indicates whether page j of stable storage is available.

SupposeAvail fits in one page, and a pointer to Avail is stored in thedatabase’s root page. When a transaction flushes a page P for the firsttime, it needs to allocate a page in stable storage to hold the shadowcopy of P. To do this, it reads a copy of Avail into cache (if it isnot already there), identifies a page k that is available, clears the bit in Avail, marks Avail[k] as updated, and stores the shadow copy of P in location k. When the transactioncommits, the updated entries in the cached copy of Avail are copiedinto the shadow copy of its page table, which is written to stablestorage.

Anotherloose end is how to allow two or more transactions to executeconcurrently. In this case, each transaction has a private copy of thepage table of each file it updates. This allows each transaction tokeep track of the pages it updated. In addition, to ensure that eachtransaction reads the last committed value of each page it accesses, aglobal copy of the master page table is also maintained in cache. Whena transaction reads a page for the first time, it uses the pointer inthe global cached master page table, not the one in itstransaction-local cached page table. To see why, suppose there are twoactive transactions, T₁ and T₂, and the following sequence of operations executes:

1. T₁ updates page A₁ of file A.

2. T₂ updates page A₂ of file A.

3. T₂ commits.

4. T₁ reads page A₂ of file A.

In step (4), T₁ should read the value of A₂ produced by T₂. However, after T₂ commits, T₁’s page table still has a pointer to the original value of A₂, not the one written by T₂. Therefore, when T₁ reads A₂, it needs to use the pointer to A₂ in the master page table.

Webegan this section by commenting that shadow paging is not used oftenin commercial products because it does not scale up to high transactionrates. The reason is step one of the commit procedure, which requiresthat all pages updated by the transaction be written to the stabledatabase. This is a lot of random I/O, which is relatively expensive.

Dueto the force-at-commit rule, we cannot avoid writing all thetransaction’s updates to stable storage before the transaction commits.However, we can do it more efficiently than in shadow paging byappending those updates to a log, which is a sequential file.Sequential writes to disk can be done about 100 times faster thanrandom writes to disk, because they avoid disk head movement androtational latency. Therefore, a system can reach a much highertransaction rate by writing sequentially to a log than writing randomlyto the stable database. Eventually, all updated pages need to bewritten back to the stable database. However, this can be done lazily,so the rate of random writes has a smaller effect on transactionthroughput. The details of making this work are the subject of the nexttwo sections.