shadow paging diagram

For example, if a failure (e.g., disk failure, power loss, machine crash) occurs midway through writing pages to the database, the database is still in a consistent state. 0000026576 00000 n 0000010188 00000 n 4 is an illustration of a portion of a database header page, In an exemplary embodiment, logical ID are assigned such that the type of page to which the logical ID refers (i.e., header, directory, mapping table, or user data page) can be deduced from the logical ID references. 1 is an illustration of a memory page structure utilized to perform shadow paging, in accordance with an exemplary embodiment of the present invention; FIG. Generally, program modules include routines, programs, objects, components, data structures, etc. The methods and apparatus of the present invention may also be practiced via communications embodied in the form of program code that is transmitted over some transmission medium, such as over electrical wiring or cabling, through fiber optics, or via any other form of transmission, wherein, when the program code is received and loaded into and executed by a machine, such as an EPROM, a gate array, a programmable logic device (PLD), a client computer, a video recorder or the like, or a receiving machine having the signal processing capabilities as described in exemplary embodiments above becomes an apparatus for practicing the invention. subsequent to said act of repeating, said page allocation indicator indicates that said second portion of said maintenance pages are unused pages. Therefore, the present invention should not be limited to any single embodiment, but rather should be construed in breadth and scope in accordance with the appended claims. Thus, a page can be moved to a different location in the database file without changing its logical identifier, by simply updating the appropriate entries in the directory page and mapping tables. a database header page for maintaining a location of said directory page. reading each entry in the database header page, This allocation bitmap can be stored in the database file. a compress code segment for causing said computer processor to compress contents of said maintenance pages. 0000001841 00000 n 0000010991 00000 n 0000022574 00000 n This technique is analogous to the use of address translation tables in a virtual memory system. An atomic transaction is a transaction that is never partially committedit is performed either fully or not at all. 0000021971 00000 n FIG.

0000001523 00000 n The contents of another portion (database header page) of the maintenance pages are stored in the persistent memory, and the contents of the first shadow pages and the second shadow pages are stored in the persistent memory again. 15, an exemplary system for implementing the method and system for shadow paging includes a general purpose computing device in the form of a computer, The drives and their associated computer storage media, discussed above and illustrated in FIG. In an exemplary embodiment, shadow paging may be utilized when a database with the structure shown in FIG. a store again code segment for causing said computer processor to store said contents of said first shadow pages and said second shadow pages in said second database memory a second time. 1. In an exemplary method for performing shadow paging, the contents of selected pages of the database file are stored in unused pages of the database file (referred to as first shadow pages).

A technique for performing atomic and durable transactions and providing a means to reliably recover from unexpected failures in a device having a limited amount of memory is desired. 0000018632 00000 n indicate said selected pages as unused pages. indicating said selected pages as unused pages. Hb```f``?X,[00s` MICROSOFT CORPORATION, WASHINGTON, Free format text: compressing contents of said maintenance pages. The technique for allocating a physical page address is almost the same as allocating a logical page ID. 8 illustrates pages, FIG. Once the bitmap has been read into memory, or computed by scanning the page entries, allocating and freeing pages can be accomplished by counting the number of bits in the bitmap until the bit that corresponds to the page to be allocated/freed is encountered. 0000025393 00000 n Logical IDs may be mapped to physical addresses in any appropriate manner.

In an exemplary embodiment, a bit set to 1 indicates that the physical page address is allocated. Shadow paging as described herein provides a technique for accessing and controlling memory, such as in a database, while mitigating the detrimental effects of unexpected faults, such as power failures, disk crashes, and/or processor failures. ReadPage(ofDirectoryPage * PAGESIZE, &directoryPage); // the least significant 10 bits are an index into the directory. The system comprises a workspace (first database memory), Overview Of A Suitable Computing System Environment, FIG. iEntry = GetLeastSignificant10Bits(idPage); // get the physical address of the corresponding mapping table page. The method and system for shadow paging may also be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network or other data transmission medium. 0000018912 00000 n A system for implementing this method includes the database file, the persistent memory, a controller, and a page allocation indicator. However, mobile database products have limited memory. During a transaction, the pages affected by the transaction are copied from the database file into a workspace, such as volatile memory, and modified in that workspace. 0000016805 00000 n storing said contents of said first shadow pages and said second shadow pages in said second database memory a second time. 10 illustrates the mapping table page being written to unused page, Next the directory page is written to an unused page, (page, FIG. a generate bitmap code segment for causing said computer processor to generate a bitmap for indicating whether each page in said first database memory is used or unused; and. 4 is an illustration of a portion of a database header page showing a logical ID mapped to the physical location of the directory pages, in accordance with an exemplary embodiment of the present invention; FIGS. 0000012224 00000 n // go to the next user data page in this mapping table, idPage = MakePageId(i /* high 10 bits */, j /* low 10 bits, // mark the user data page id and address as allocated, // at this point the page id bitmap and address bitmap represent the, // current set of allocated / free logical page ids, and the current. The difference is that if no existing physical page is free, then the database file is grown (i.e., some number of physical pages is added to the end of the file) and the new physical page addresses appended to the database file are marked as free physical page addresses in the address bitmap. 15 illustrates an example of a suitable computing system environment in which the method and system for shadow paging in accordance with an exemplary of the present invention may be implemented. In another embodiment, the bitmap is not stored in the database file, and is initialized when the database is opened. In an exemplary embodiment, to ensure that transactions are atomic (e.g., a sector is never partially written), the physical page address of the directory page is stored in the first sector of the database header page, which is stored at the start (e.g., in the first sector) of the database file. This improves concurrency by allowing multiple transactions to allocate and free page IDs in a database at the same time. addressBitmap.SetBit(headerPage.DirectoryPageAddress, 1); ReadPage(headerPage.DirectoryPageAddress * PAGESIZE, // enumerate through the mapping table pages referenced. %x'J40(*uP.

PATENTED CASE, Owner name: Important features of database products include the ability to perform atomic and durable transactions.

storing contents of selected pages of a first database memory of said database in first shadow pages, wherein said first shadow pages comprise unused pages of said first database memory; maintaining locations of said selected pages and said first shadow pages in maintenance pages of said database; storing contents of said first shadow pages and a first portion of said maintenance pages in a second database memory of said database; storing contents of a second portion of said maintenance pages in said second database memory; and. The various techniques described herein may be implemented in connection with hardware or software or, where appropriate, with a combination of both.

0000016826 00000 n Physical page addresses are allocated when a transaction commits and pages are shadowed on disk, and when replacing a dirty page in a shadow pool. The pages depicted in FIG. Within the database, pages are accessed and tracked via logical IDs. an update bitmap code segment for causing said computer processor to update said bitmap in accordance with said acts of indicating. indicating said selected pages as used pages; responsive to said act of storing said contents of said selected pages in said first shadow pages, indicating said first shadow pages as used pages; storing contents of a first portion of said maintenance pages in second shadow pages, wherein said second shadow pages comprise unused pages of said first database memory; responsive to said act of storing said contents of said first portion of said maintenance pages in said second shadow pages, indicating said second shadow pages as used pages; storing contents of said first shadow pages and said second shadow pages in said second database memory; and. For example, using the page sizes and database structure described in the above example, a page ID corresponding to use data pages can be allocated by finding the first bit greater than or equal to bit. 0000021733 00000 n In this case, the bitmap has one bit for each physical page address in the database file. updating said bitmap in accordance with said acts of indicating.

Owner name: In a distributed computing environment, program modules and other data may be located in both local and remote computer storage media including memory storage devices. During a transaction, the pages affected by the transaction are copied from the database file into a workspace, such as volatile memory, and modified in that workspace. 8 through 13. The first shadow pages are declared as used pages. This technique uses relatively little software code, thus making it especially suitable for electronic devices having limited amounts of memory or limited speed, such as hand held devices, and/or mobile database products (e.g., SQL-CE).