Fast connectivity recovery for a partitioned namespace

• US 7,941,709 B1
• Filed: 09/04/2008
• Issued: 05/10/2011
• Est. Priority Date: 09/28/2007
• Status: Expired due to Fees

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Symantec Corporation (NortonLifeLock Inc.)
• Inventors: Hong, Bo, Kiselev, Oleg, Colgrove, John A., Wang, Feng
• Primary Examiner(s): Maskulinski; Michael C
• Application Number:
  US12/204,486
• Time in Patent Office: 978 Days
• Field of Search: 714/54
• US Class Current: 714/54
• CPC Class Codes: G06F 11/0727 in a storage system, e.g. in a DASD or network based storage system drivers for digital recording or reproducing units G06F3/06; circuits for error detection or correction within digital recording or reproducing units G11B20/18; for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS], H04L67/1097
• CPC Class Codes: G06F 11/0751 Error or fault detection not based on redundancy power supply failures G06F1/30; network fault management H04L41/06
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06

Abstract

A system and method for storing data. In one embodiment, a file system includes a hierarchy of nodes partitioned into a plurality of containers. The file system further includes metadata associated with each node. First metadata describes each node'"'"'s references to other nodes and second metadata identifies each node'"'"'s parent node. The file system further includes a linkage table associated with each container. Each linkage table comprises entries describing links between a node owned by the associated container and other nodes. In response to detecting that a file system error has occurred, the file system identifies a container which corresponds to the detected error, corrects inconsistencies between the first and second metadata associated with each node owned by the container, and corrects inconsistencies between each of the entries of the linkage table associated with the identified container and the first and second metadata.

Claims

1. A computer file system comprising:

a hierarchy of nodes, wherein said hierarchy of nodes is partitioned into a plurality of containers, wherein each of said containers stores one or more of said nodes and wherein a number of said containers is fewer than a number of said nodes;

metadata associated with each node, wherein the metadata includes first metadata (411) that describes each node'"'"'s references to other nodes and second metadata that identifies each node'"'"'s parent node; and

wherein in response to detecting that a file system error has occurred, the file system is configured to;

identify a first container which corresponds to the detected error; and

correct inconsistencies in metadata associated with each node owned by the first container, wherein inconsistencies in metadata associated with nodes exclusively owned by the first container may be corrected independently of correcting inconsistencies in metadata associated with nodes exclusively owned by other containers.

2. The system of claim 1, further comprising

a linkage table associated with each container, wherein each linkage table describes links between nodes owned by an associated container and other nodes which are not owned by the associated container;

wherein in response to detecting that a file system error has occurred, the file system is further configured to correct inconsistencies between data in the linkage table associated with the first container and the metadata.

3. The system of claim 2, wherein the first metadata comprises a plurality of entries with a first field, each entry corresponding to one of said nodes, and wherein the second metadata comprises one or more inodes, each inode comprising a parent reference and a mode field;

wherein to correct inconsistencies between the first and second metadata, the file system is further configured to replace at least one value of the field and the value of the mode field in response to determining that the value of the field does not match the value of the mode field.

4. The system of claim 3, wherein to correct inconsistencies between the first and second metadata, the file system is further configured to:

detect a value of a given inode'"'"'s parent reference;

detect that the first metadata associated with the node to which the parent reference refers does not contain a reference to the node that is associated with the given inode; and

add a reference to the node that is associated with the given inode to the first metadata associated with the node to which the parent reference refers.

5. The system of claim 3;

wherein each of the plurality of entries is associated with a respective one of the plurality of inodes; and

wherein the linkage table includes a link for each reference to a file other than a parent reference; and

wherein the linkage table includes a link for each reference between a directory and a node not owned by the associated container.

6. The system of claim 5;

wherein each inode further comprises a link count;

wherein if a given inode corresponds to a given file in the file system, the link count of the given inode indicates the number of file system directories that refer to the given file; and

wherein if the given inode corresponds to a given file system directory, the link count of the given inode indicates the number of file system subdirectories that are linked to the given file system directory.

7. The system of claim 6, wherein to correct inconsistencies between each of the plurality of entries of the linkage table associated with the identified container and the first and second metadata, the file system is configured to:

for a given inode, increase the link count in response to determining that the number of links in the linkage table associated with the given inode is greater than the link count minus one; and

for the given inode, decrease the link count in response to determining that the number of links in the linkage table associated with the given inode plus the number of additional links associated with the given inode that are present in other container linkage tables or in the first metadata is less than the link count minus one.

8. A method comprising:

partitioning a file system comprising a hierarchy of nodes into a plurality of containers, wherein each of said containers stores one or more of said nodes and wherein a number of said containers is fewer than a number of said nodes;

maintaining first and second metadata associated with each of said nodes, wherein the first metadata describes each node'"'"'s references to other nodes and the second metadata identifies each node'"'"'s parent node;

in response to detecting that a file system error has occurred;

identifying a first container which corresponds to the detected error;

correcting inconsistencies between the first and second metadata associated with each node owned by the first container, wherein inconsistencies in metadata associated with nodes exclusively owned by the first container may be corrected independently of correcting inconsistencies in metadata associated with nodes exclusively owned by other containers.

9. The method of claim 8, further comprising a linkage table associated with each container, wherein each linkage table describes links between nodes owned by an associated container and other nodes which are not owned by the associated container, wherein in response to detecting that a file system error has occurred, the method further comprises correcting inconsistencies between data in the linkage table associated with the first container and the metadata.

10. The method of claim 9, wherein the first metadata comprises a plurality of entries with a first field, each entry corresponding to one of said nodes, and wherein the second metadata comprises one or more inodes, each inode comprising a parent reference and a mode field;

wherein to correct inconsistencies between the first and second metadata, the method further comprises replacing at least one of the value of the field and the value of the mode field in response to determining that the value of the field does not match the value of the mode field.

11. The method of claim 10, wherein correcting inconsistencies between the first and second metadata comprises:

detecting a value of a given inode'"'"'s parent reference;

detecting that the first metadata associated with the node to which the parent reference refers does not contain a reference to the node that is associated with the given inode; and

adding a reference to the node that is associated with the given inode to the first metadata associated with the node to which the parent reference refers.

12. The method of claim 10;

wherein each of the plurality of entries is associated with a respective one of the plurality of inodes; and

wherein the linkage table includes a link for each reference to a file other than a parent reference; and

wherein the linkage table includes a link for each reference between a directory and a node not owned by the associated container.

13. The method of claim 12;

wherein each inode further comprises a link count;

wherein if a given inode corresponds to a given file in the file system, the link count of the given inode indicates the number of file system directories that refer to the given file; and

wherein if the given inode corresponds to a given file system directory, the link count of the given inode indicates the number of file system subdirectories that are linked to the given file system directory.

14. The method of claim 13, wherein correcting inconsistencies between each of the plurality of entries of the linkage table associated with the identified container and the first and second metadata comprises:

for a given inode, increasing the link count in response to determining that the number of links in the linkage table associated with the given inode is greater than the link count minus one; and

for the given inode, decreasing the link count in response to determining that the number of links in the linkage table associated with the given inode plus the number of additional links associated with the given inode that are present in other container linkage tables or in the first metadata is less than the link count minus one.

15. A computer readable storage medium storing computer instructions that are executable by a processor to:

partition a file system into a plurality of containers, wherein the file system comprises a hierarchy of nodes, wherein each of said containers stores one or more of said nodes and wherein a number of said containers is fewer than a number of said nodes;

maintain first and second metadata associated with each node, wherein the first metadata describes each node'"'"'s references to other nodes and the second metadata identifies each node'"'"'s parent node;

in response to detecting that a file system error has occurred;

identify a first container which corresponds to the detected error;

correct inconsistencies in metadata associated with each node owned by the first container, wherein inconsistencies in metadata associated with nodes exclusively owned by the first container may be corrected independently of correcting inconsistencies in metadata associated with nodes exclusively owned by other containers.

16. The computer readable storage media of claim 15, wherein in response to detecting that a file system error has occurred, the instructions are further executable to wherein correct inconsistencies between data in a linkage table associated with the first container and the metadata, wherein the linkage table describes links between nodes owned by the first container and other nodes.

17. The computer readable storage media of claim 16, wherein the first metadata comprises a plurality of entries with a first field, each entry corresponding to one of said nodes, and wherein the second metadata comprises one or more inodes, each inode comprising a parent reference and a mode field;

wherein to correct inconsistencies between the first and second metadata, the instructions are executable to replace at least one of the value of the field and the value of the mode field in response to determining that the value of the field does not match the value of the mode field.

18. The computer readable storage media of claim 17, wherein to correct inconsistencies between the first and second metadata, the instruction are further executable to cause the processor to:

detect a value of a given inode'"'"'s parent reference;

detect that the first metadata associated with the node to which the parent reference refers does not contain a reference to the node that is associated with the given inode; and

add a reference to the node that is associated with the given inode to the first metadata associated with the node to which the parent reference refers.

19. The computer readable storage media of claim 17;

wherein each of the plurality of entries is associated with a respective one of the plurality of inodes; and

wherein the linkage table includes a link for each reference to a file other than a parent reference; and

wherein the linkage table includes a link for each reference between a directory and a node not owned by the associated container.

20. The computer readable storage media of claim 19;

wherein each inode further comprises a link count;

wherein if a given inode corresponds to a given file in the file system, the link count of the given inode indicates the number of file system directories that refer to the given file;

wherein if the given inode corresponds to a given file system directory, the link count of the given inode indicates the number of file system subdirectories that are linked to the given file system directory; and

wherein to correct inconsistencies between each of the plurality of entries of the linkage table associated with the identified container and the first and second metadata, the instruction are further executable to cause the processor to;

for a given inode, increase the link count in response to determining that the number of links in the linkage table associated with the given inode is greater than the link count minus one; and

for the given inode, decrease the link count in response to determining that the number of links in the linkage table associated with the given inode plus the number of additional links associated with the given inode that are present in other container linkage tables or in the first metadata is less than the link count minus one.