Granted Patent B2

US 7,155,464 · App. 10/349,369 · Granted Dec 26, 2006

Abstract

Claims (93)

1. A method of performing file system recovery in an object-based data storage system that includes one or more object-based devices that store data files, comprising:

storing a list of objects representing at least attributes of the data files that are stored in said data storage system in a memory in said data storage system;

performing a dynamic check on each object in said list as part of said file system recovery, wherein said dynamic check includes using at least said attributes to verify all parent-child relationships between two or more objects contained in said list; and

removing from said list in said memory each such object whose corresponding dynamic check has been completed, and deleting from said memory corresponding object-related information for each object removed from said list without affecting the data files stored in the data storage system;

wherein storing said list includes storing in said memory corresponding object-related information for each object listed in said list, and performing said dynamic check includes verifying that a forward pointer in said corresponding object-related information for a parent object in said list linking said parent object to a child object in said list has a matching backward pointer in said corresponding object-related information for said child object, and vice versa.

2. The method of claim 1 , wherein said object-related information includes at least one of the following attributes of a respective object:

a first attribute identifying an entity in said data storage system responsible for storing said respective object;

a second attribute identifying an object group containing said respective object;

and

a third attribute identifying said respective object.

3. A computer-readable storage medium containing a program code, which, upon execution by a processor in an object-based distributed data storage system that includes one or more object-based devices that store data files, causes said processor to perform the following as part of file system recovery in said object-based data storage system:

store a list of objects representing at least attributes of the data files that are stored in said data storage system in a memory in said data storage system;

perform a dynamic check on each object in said list, wherein said dynamic check includes using at least said attributes to verify all parent-child relationships between two or more objects contained in said list; and

remove from said list in said memory each such object whose corresponding dynamic check has been completed, and delete from said memory corresponding object-related information for each object removed from said list without affecting the data files stored in the data storage system;

wherein said list stored in said memory includes corresponding object-related information for each object listed in said list, and said dynamic check includes verifying that a forward pointer in said corresponding object-related information for a parent object in said list linking said parent object to a child object in said list has a matching backward pointer in said corresponding object-related information for said child object, and vice versa.

4. An object-based data storage system that includes one or more object-based devices that store data files, comprising:

means for storing a list of objects representing at least attributes of the data files that are stored in said data storage system in a memory in said data storage system;

means for performing a dynamic check on each object in said list as part of file system recovery in said object-based data storage system, wherein said dynamic check includes using at least said attributes to verify all parent-child relationships between two or more objects contained in said list; and

means for removing from said list in said memory each such object whose corresponding dynamic check has been completed and deleting from said memory corresponding object-related information for each object removed from said list without affecting the data files stored in the data storage system;

wherein said means for storing said list includes means for storing in said memory corresponding object-related information for each object listed in said list, and said means for performing said dynamic check includes means for verifying that a forward pointer in said corresponding object-related information for a parent object in said list linking said parent object to a child object in said list has a matching backward pointer in said corresponding object-related information for said child object, and vice versa.

5. A method of performing file system recovery in an object-based data storage system that includes one or more object-based devices that store data files, comprising:

dividing all objects stored in said data storage system among a plurality of segments with each of said plurality of segments containing a non-overlapping portion of said stored objects;

storing an object list representing at least attributes of the data files and containing a list of all objects in a first segment in said plurality of segments in a memory in said data storage system;

performing a dynamic check on each object in said object list as part of said file system recovery, wherein said dynamic check includes using at least said attributes to verify all parent-child relationships between two or more objects contained in said first segment and also between a first object in said first segment and a second object in a second segment in said plurality of segments;

removing from said object list in said memory each such object whose corresponding dynamic check has been completed, and deleting from said memory corresponding object-related information for each object removed from said list without affecting the data files stored in the data storage system;

listing a corresponding different object from a third segment in said plurality of segments in place of each object removed from said object list; and

further performing said dynamic check on each object from said third segment that is listed in said object list;

wherein storing said object list includes storing in said memory a corresponding object-related information for each object listed in said object list, and

wherein performing said dynamic check includes verifying one of the following:

that a first forward pointer in said corresponding object-related information for a first parent object in said first segment linking said first parent object to a first child object in said second segment has a matching first backward pointer in said corresponding object-related information for said first child object; and

that a second backward pointer in said corresponding object-related information for a second child object in said first segment linking said second child object to a second parent object in said second segment has a matching second forward pointer in said corresponding object-related information for said second parent object.

6. The method of claim 5 , wherein said object-related information includes at least one of the following attributes of a respective object:

a first attribute identifying an entity in said data storage system responsible for storing said respective object;

a second attribute identifying an object group containing said respective object;

and

a third attribute identifying said respective object.

7. A method of performing file system recovery in an object-based data storage system that includes one or more object-based devices that store data files, comprising:

dividing all objects stored in said data storage system among a plurality of segments with each of said plurality of segments containing a non-overlapping portion of said stored objects;

establishing a plurality of link databases, wherein each link database in said plurality of link databases corresponds to a different one of said plurality of segments;

performing a first dynamic check on each object in a first segment in said plurality of segments as part of said file system recovery, wherein said first dynamic check includes verification of all parent-child relationships between two or more objects contained in said first segment and also between one object in said first segment and another object in a second segment in said plurality of segments;

identifying one or more linked objects in said first segment, wherein each linked object in said first segment has a parent-child relationship with one or more other objects in one or more other segments in said plurality of segments; and

populating a first link database corresponding to said second segment with a respective entry for each linked object in said first segment that has a corresponding destination object in said second segment, wherein each said destination object in said second segment has said parent-child relationship with a respective linked object in said first segment, and wherein each said entry in said first link database contains information describing how each said destination object in said second segment is linked to said respective linked object in said first segment via a forward or a backward link;

further comprising storing a list of objects in said first segment and corresponding object-related information representing at least attributes of at least one of the data files for each object in said list in a memory in said data storage system prior to performing said first dynamic check;

wherein performing said first dynamic check includes using at least said attributes to verify one of the following:

that a first forward pointer in said corresponding object-related information for a first parent object in said first segment linking said first parent object to a first child object in said second segment has a matching first backward pointer in said corresponding object-related information for said first child object; and

that a second backward pointer in said corresponding object-related information for a second child object in said first segment linking said second child object to a second parent object in said second segment has a matching second forward pointer in said corresponding object-related information for said second parent object; and

removing from said list in said memory each such object whose corresponding dynamic check has been completed and deleting from said memory corresponding object-related information for each object removed from said list without affecting the data files stored in the data storage system.

8. The method of claim 7 , wherein said object-related information includes at least one of the following attributes of a respective object:

a first attribute identifying an entity in said data storage system responsible for storing said respective object;

a second attribute identifying an object group containing said respective object;

and

a third attribute identifying said respective object.

9. The method of claim 7 , further comprising:

storing a list of objects in said second segment and a corresponding object-related information for each object in said list in a memory in said data storage system;

further storing at least a portion of said first link database corresponding to said second segment in said memory; and

performing a second dynamic check on each object in said list of objects using said corresponding object-related information therefor, wherein said second dynamic check includes verification of all parent-child relationships between two or more objects contained in said second segment and also between one object in said second segment and another object in said first segment.

10. The method of claim 9 , wherein performing said second dynamic check includes performing said second dynamic check on each object in said list using said corresponding object-related information therefor and using, when needed, each said respective entry stored in said portion of said first link database, and wherein the method further comprises:

removing from said list in said memory each such object whose corresponding second dynamic check has been completed;

deleting from said memory said corresponding object-related information for each object removed from said list; and

removing from said portion of said first link database each said respective entry that corresponds to said object removed from said list.

11. The method of claim 9 , wherein said object-related information includes at least one of the following attributes of a respective object:

a first attribute identifying an entity in said data storage system responsible for storing said respective object;

a second attribute identifying an object group containing said respective object;

and

a third attribute identifying said respective object.

12. The method of claim 9 , wherein performing said second dynamic check includes verifying one of the following:

that a first forward pointer in said corresponding object-related information for a first parent object in said second segment linking said first parent object to a first child object in said first segment has a matching first backward pointer in said corresponding object-related information for said first child object; and

that a second backward pointer in said corresponding object-related information for a second child object in said second segment linking said second child object to a second parent object in said first segment has a matching second forward pointer in said corresponding object-related information for said second parent object.

13. The method of claim 9 , further comprising:

identifying one or more linked objects in said second segment, wherein each linked object in said second segment has a parent-child relationship with one or more other objects in one or more other segments in said plurality of segments; and

populating a second link database corresponding to a third segment in said plurality of segments with a respective entry for each linked object in said second segment that has a corresponding destination object in said third segment, wherein each said destination object in said third segment has said parent-child relationship with a respective linked object in said second segment, and wherein each said entry in said second link database contains information describing how each said destination object in said third segment is linked to said respective linked object in said second segment via a forward or a backward link.

14. A computer-readable storage medium containing a program code, which, upon execution by a processor in an object-based distributed data storage system that includes one or more object-based devices that store data files, causes said processor to perform the following:

divide all objects stored in said data storage system among a plurality of segments with each of said plurality of segments containing a non-overlapping portion of said stored objects;

establish a plurality of link databases, wherein each link database in said plurality of link databases corresponds to a different one of said plurality of segments;

perform a dynamic check on each object in a first segment in said plurality of segments as part of file system recovery, wherein said dynamic check includes verification of all parent-child relationships between two or more objects contained in said first segment and also between one object in said first segment and another object in a second segment in said plurality of segments;

identify one or more linked objects in said first segment, wherein each linked object in said first segment has a parent-child relationship with one or more other objects in one or more other segments in said plurality of segments; and

populate a link database corresponding to said second segment with a respective entry for each linked object in said first segment that has a corresponding destination object in said second segment, wherein each said destination object in said second segment has said parent-child relationship with a respective linked object in said first segment, and wherein each said entry in said link database contains information describing how each said destination object in said second segment is linked to said respective linked object in said first segment via a forward or a backward link;

store a list of objects in said first segment and a corresponding object-related information representing at least attributes of at least one of the data files for each object in said list in a memory in said data storage system prior to performing said first dynamic check;

wherein said dynamic check includes using at least said attributes to verify one of the following:

that a first forward pointer in said corresponding object-related information for a first parent object in said first segment linking said first parent object to a first child object in said second segment has a matching first backward pointer in said corresponding object-related information for said first child object; and

that a second backward pointer in said corresponding object-related information for a second child object in said first segment linking said second child object to a second parent object in said second segment has a matching second forward pointer in said corresponding object-related information for said second parent object; and

remove from said list in said memory each such object whose corresponding dynamic check has been completed and delete from said memory corresponding object-related information for each object removed from said list without affecting the data files stored in the data storage system.

15. An object-based data storage system that includes one or more object-based devices that store data files, comprising:

means for dividing all objects stored in said data storage system among a plurality of segments with each of said plurality of segments containing a non-overlapping portion of said stored objects;

means for establishing a plurality of link databases, wherein each link database in said plurality of link databases corresponds to a different one of said plurality of segments;

means for performing a dynamic check on each object in a first segment in said plurality of segments, wherein said dynamic check includes verification of all parent-child relationships between two or more objects contained in said first segment and also between one object in said first segment and another object in a second segment in said plurality of segments;

means for identifying one or more linked objects in said first segment, wherein each linked object in said first segment has a parent-child relationship with one or more other objects in one or more other segments in said plurality of segments; and

means for populating a link database corresponding to said second segment with a respective entry for each linked object in said first segment that has a corresponding destination object in said second segment, wherein each said destination object in said second segment has said parent-child relationship with a respective linked object in said first segment, and wherein each said entry in said link database contains information describing how each said destination object in said second segment is linked to said respective linked object in said first segment via a forward or a backward link;

means for storing a list of objects in said first segment and a corresponding object-related information representing at least attributes of at least one of the data files for each object in said list in a memory in said data storage system prior to performing said first dynamic check;

wherein said dynamic check includes using at least said attributes to verify one of the following:

that a first forward pointer in said corresponding object-related information for a first parent object in said first segment linking said first parent object to a first child object in said second segment has a matching first backward pointer in said corresponding object-related information for said first child object; and

that a second backward pointer in said corresponding object-related information for a second child object in said first segment linking said second child object to a second parent object in said second segment has a matching second forward pointer in said corresponding object-related information for said second parent object; and

means for removing from said list in said memory each such object whose corresponding dynamic check has been completed and deleting from said memory corresponding object-related information for each object removed from said list without affecting the data files stored in the data storage system.

Assignments (8)