Method and apparatus for shadowing a hierarchical file system index structure to enable error recovery
First Claim
1. A method for updating a tree-arranged index to an hierarchical file system (HFS), said index including at least one index value (i.e., an index page) logically positioned between an index anchor value and a sequence page, and including a root page therebetween, said sequence page including an index record, logical positioning of an index page determined by one or more pointers, said method comprising the steps of:
- a) responding to an index update request by making an update shadow copy of (i) a sequence page to be updated and (ii) any other index pages, up to and including said root page;
b) updating said shadow copy of said sequence page in accord with said update request;
c) updating said root page and each shadowed index page, in a path to said updated, shadowed sequence page, that reside in successive index levels and collectively comprise a path thereto;
d) if a cancel or error indication occurs prior to step c), releasing shadowed copies of said sequence page, each index page and root page;
or e) to otherwise updating said index anchor value to point to said updated root page.
1 Assignment
0 Petitions
Accused Products
Abstract
The method of the invention updates a tree arranged index for an hierarchical file system (HFS). The index includes at least one index value, i.e., an index page, that is logically positioned between an index anchor value and a sequence page. The sequence page includes actual index data. Logical positioning of the index page is determined by one or more pointers. The method initially responds to an index update request by making an update “shadow” copy of (i) a sequence page and (ii) any other index pages, up to and including a root page, that are to be updated in accord with the update request. Thereafter, an index manager updates the shadow copy of the sequence page in accord with the update request. The index manager further updates the root page and each shadowed index page that is present in a path to the updated sequence page to indicate that the path has been updated and includes the most current data. If a cancel or error indication occurs prior to updating of the index path, the shadowed copies of the sequence page, index page and root page are released, enabling the system to return to the non-updated pages. Otherwise, the index manager updates the index anchor value to point to the updated root page, thereby indicating that the index update has been successfully accomplished. Periodically, the new index anchor value, sequence page, index and root pages are written to disk.
43 Citations
10 Claims
-
1. A method for updating a tree-arranged index to an hierarchical file system (HFS), said index including at least one index value (i.e., an index page) logically positioned between an index anchor value and a sequence page, and including a root page therebetween, said sequence page including an index record, logical positioning of an index page determined by one or more pointers, said method comprising the steps of:
-
a) responding to an index update request by making an update shadow copy of (i) a sequence page to be updated and (ii) any other index pages, up to and including said root page;
b) updating said shadow copy of said sequence page in accord with said update request;
c) updating said root page and each shadowed index page, in a path to said updated, shadowed sequence page, that reside in successive index levels and collectively comprise a path thereto;
d) if a cancel or error indication occurs prior to step c), releasing shadowed copies of said sequence page, each index page and root page;
ore) to otherwise updating said index anchor value to point to said updated root page. - View Dependent Claims (2, 3, 4, 5)
f) responding to a change request to a shadowed, updated sequence page, by using said change array to access said shadowed, updated sequence page;
g) updating said shadowed, updated sequence page to reflect a further change; and
h) altering a virtual storage address in said change array to point to the sequence page updated in step g).
-
-
5. The method as recited in claim 1, comprising the further step of:
f) periodically writing to disk updated copies of said shadowed sequence page and each shadowed index and root page, and freeing corresponding current index pages.
-
6. A memory media for controlling a processor to update a tree-arranged index to an hierarchical file system (HFS), said index including at least one index value (i.e., an index page) logically positioned between an index anchor value and a sequence page, and including a root page therebetween, said sequence page including an index record, logical positioning of an index page determined by one or more pointers, said memory media comprising:
-
a) means for controlling said processor to respond to an index update request by making an update shadow copy of (i) a sequence page to be updated and (ii) any other index pages, up to and including said root page;
b) means for controlling said processor to update said shadow copy of said sequence page in accord with said update request;
c) means for controlling said processor to update said root page and each shadowed index page in a path to said updated, shadowed sequence page that reside in successive index levels and collectively comprise the path thereto;
d) means for controlling said processor to respond to a cancel or error indication that occurs prior to completion of the functions performed by means c), by releasing shadowed copies of said sequence page, each index page and root page; and
e) means for controlling said processor to otherwise update said index anchor value to point to said updated root page. - View Dependent Claims (7, 8, 9, 10)
f) means for controlling said processor to respond to a change request to an already shadowed, updated sequence page, by using said change array to access said shadowed, updated sequence page;
g) means for controlling said processor to update said shadowed, updated page to reflect a further change; and
h) means for controlling said processor to alter a virtual storage address in said change array to point to the sequence page updated in accord with said further change.
-
-
10. The memory media as recited in claim 6, further comprising:
f) means for controlling said processor to periodically write to disk updated copies of said shadowed sequence page and each shadowed index and root page, and to free corresponding current index pages.
Specification