Data structures containing sequence and revision number metadata used in mass storage data integrity-assuring technique

• US 6,606,629 B1
• Filed: 05/17/2000
• Issued: 08/12/2003
• Est. Priority Date: 05/17/2000
• Status: Expired due to Term

• Current Assignee: NetApp, Inc.
• Original Assignee: LSI Logic Corporation (Broadcom, Inc.)
• Inventors: DeKoning, Rodney A., Langford, Thomas L. II, Greenfield, Scott E.
• Primary Examiner(s): Breene, John
• Assistant Examiner(s): LEWIS, CHERYL RENEA
• Application Number:
  US09/573,135
• Time in Patent Office: 1,182 Days
• Field of Search: 707/100, 711/114, 714/100, 360/47, 360/48
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/2058 using more than 2 mirrored copies
• CPC Class Codes: G06F 11/2069 Management of state, configuration or failover
• CPC Class Codes: G06F 11/2082 Data synchronisation
• CPC Class Codes: G06F 2201/83 the solution involving signatures
• CPC Class Codes: G06F 2211/104 Metadata, i.e. metadata associated with RAID systems with parity

Abstract

A data structure contains sequence number metadata which identifies an input/output (I/O) operation such as a full stripe write on a redundant array of independent disks (RAID) mass storage system, and also contains revision number metadata which identifies a subsequent I/O operation such as a read modify write on only a fractional component of the entire user data. The sequence number and revision number metadata are used in an error detection and correction technique, along with parity metadata, to detect and correct silent errors arising from inadvertent data path and drive data corruption. An error to a portion of the stripe is detected by a difference in sequence numbers for all of the components of data. An error arising after an I/O operation is detected by a revision number which is different from the correct revision number. The errors in both cases are corrected by using the parity metadata for the entire collection of user data and the correct information from the other components of the user data and metadata, and applying this information to an error correcting algorithm. The technique may be executed in conjunction with a read I/O operation without incurring a substantial processing overhead penalty.

Claims

1. A group of data structures defining an input/output (I/O) operation performed on storage media and used to contain user data and to contain metadata which is used to detect errors arising from other I/O operations performed on one or more of the data structures of the group, comprising in combination:

a plurality of user data structures, each user data structure having a plurality of fields including the user data field for containing user data, a sequence number field for containing sequence number information identifying the I/O operation which originated the group of data structures, and a revision number field for containing revision number information identifying a subsequent I/O operation after the original I/O operation in which user data was written in the user data field of at least one user data structure of the plurality of user data structures;

a parity data structure associated with the plurality of user data structures of the group, the parity data structure having a plurality of fields including a parity field for containing parity information describing the user data in each of the user data fields of each of the associated user data structures of the group, a sequence number field for containing sequence number information identifying the I/O operation which originated the group of data structures, and a revision number field for each associated user data structure which contains revision number information identifying the subsequent I/O operation in which user data was written in the user data field of the associated user data structure; and

the parity data structure and the associated plurality of user data structures collectively and logically constituting a separate unit of I/O information recorded on the storage media.

2. A group of data structures as defined in claim 1 wherein:

the group of data structures is recorded on a plurality of disk drives of a redundant array of independent disk (RAID) mass storage system; and

each user data structure and the parity data structure is recorded on a separate disk drive of the RAID mass storage system.

3. A group of data structures as defined in claim 2 wherein:

the plurality of disk drives of the RAID mass storage system constitute a single redundancy group;

the separate unit of I/O information constitutes a full stripe written on the plurality of disk drives of the single redundancy group.

4. A group of data structures as defined in claim 1 wherein:

each user data structure includes a plurality of separate user data fields, each separate user data field is for containing a component of user data in the user data structure; and

the parity data structure data includes a plurality of separate parity fields, each separate parity field correlates to one separate user data field of each user data structure, and each separate parity field is for containing parity information describing the component of user data contained in the separate user data field of the correlated user data structure.

5. A group of data structures as defined in claim 4 wherein:

the separate revision number field of the parity data structure is for containing revision number information describing the user data of the associated user data structure which was written during the subsequent I/O operation.

6. A group of data structures as defined in claim 5 wherein:

the fields of each user data structure further include a code field correlated with each separate user data field for containing error detecting code information describing the user data contained in the separate user data field of that user data structure.

7. A group of data structures as defined in claim 4 wherein:

each separate user data field of each user data structure further includes a plurality of divisions into separate user data field subdivisions; and

each separate parity field of the parity data structure further includes a plurality of divisions into separate parity field subdivisions each of which correlates to corresponding separate user data field subdivision of the associated user data structures, each separate parity field subdivision is for containing parity information describing the user data contained in the corresponding correlated separate user data field subdivision.

8. A group of data structures as defined in claim 7 wherein:

the fields of the parity data structure further include a code field correlated with each separate parity field subdivision for containing error detecting code information describing the parity information contained in the correlated separate parity field subdivision.

9. A group of data structures as defined in claim 8 wherein:

the fields of each user data structure further include a code field correlated with each separate user data field subdivision of that user data structure for containing error detecting code information describing the user data contained in the correlated separate user data field subdivision.

10. A group of data structures as defined in claim 7 wherein:

the fields of each user data structure further include a code field correlated with each separate user data field subdivision of that user data structure for containing error detecting code information describing the user data contained in the correlated separate user data field subdivision.

11. A group of data structures as defined in claim 4 wherein:

the storage media is divided into sectors each of which is a uniform length;

each user data structure includes a user data region which includes each separate user data field;

the user data region consumes a plurality of logically contiguous sectors on the storage media;

each user data structure further includes a control block metadata region in which each sequence number field and each revision number field is located; and

the control block metadata region of each user data structure consumes one sector on the storage media logically preceding the contiguous sectors occupied by the user data region.

12. A group of data structures defining an input/output (I/O) operation performed on storage media and used to contain user data and to contain metadata which is used to detect errors arising from other I/O operations performed on one or more of the data structures of the group, comprising in combination:

a plurality of user data structures, each user data structure having a plurality of fields including the user data field for containing user data, a sequence number field for containing sequence number information identifying the I/O operation which originated the group of data structures, and a revision number field for containing revision number information identifying a subsequent I/O operation after the original I/O operation in which user data was written in the user data field of at least one user data structure of the plurality of user data structures;

a parity data structure associated with the plurality of user data structures of the group, the parity data structure having a plurality of fields including a parity field for containing parity information describing the user data in each of the user data fields of each of the associated user data structures of the group, a sequence number field for containing sequence number information identifying the I/O operation which originated the group of data structures, and a revision number field for each associated user data structure which contains revision number information identifying the subsequent I/O operation in which user data was written in the user data field of the associated user data structure;

the parity data structure and the associated plurality of user data structures collectively and logically constituting a separate unit of I/O information recorded on the storage media;

wherein each user data structure includes a plurality of separate user data fields, each separate user data field is for containing a component of user data in the user data structure;

the parity data structure data includes a plurality of separate parity fields, each separate parity field correlates to one separate user data field of each user data structure, and each separate parity field is for containing parity information describing the component of user data contained in the separate user data field of the correlated user data structure;

wherein each separate user data field of each user data structure further includes a plurality of divisions into separate user data field subdivisions;

each separate parity field of the parity data structure further includes a plurality of divisions into separate parity field subdivision of the associated user data structures, each separate parity field subdivision is for containing parity information describing the user data contained in the corresponding correlated separate user data field subdivision;

wherein the fields of each user data structure further include a code field correlated with each separate user data field subdivision of that user data structure for containing error detecting code information describing the user data contained in the correlated separate user data field subdivision; and

wherein each user data structure has four separate parity fields; and

the parity data structure has four separate parity fields.

13. A group of data structures as defined in claim 12 wherein:

each separate user data field is 4 KB in size; and

each separate parity segment is 4 KB in size.

14. A group of data structures as defined in claim 12 wherein:

each separate user data field is divided into eight separate user data field subdivisions; and

each separate parity field is divided into eight separate parity field subdivisions.

15. A group of data structures as defined in claim 14 wherein:

each separate user data field subdivision is 512 bytes in size; and

each separate parity segment is 512 bytes in size.

16. A group of data structures as defined in claim 15 wherein:

the storage media is divided into 512 byte sectors;

each user data structure includes a user data region in which each separate user data field subdivision is located;

the user data region consumes 32 logically contiguous 512 byte sectors on the storage media in which the eight separate user data field subdivisions of the four separate user data fields of the user data structure are located;

each user data structure further includes a control block metadata region in which each separate sequence number field and each separate revision number field is located; and

the control block metadata region of each user data structure consumes one 512 byte sector in which the separate sequence number field and the separate revision number field are located, the metadata region located on the storage media is logically adjacent to the 32 logically contiguous 512 byte sectors.

17. A group of data structures as defined in claim 15 wherein:

the storage media is divided into 512 byte sectors;

each user data structure includes a user data region in which each separate user data field subdivision is located;

each of the four separate user data fields of the user data structure consume eight logically contiguous 512 byte sectors;

each user data structure further includes a control block metadata region in which each separate sequence number field and each separate revision number field is located;

the control block metadata region of each user data structure is divided into separate metadata regions which correlate to each separate user data region, each separate control block metadata region having a size equal to a fractional portion of one 512 byte sector; and

each separate metadata region is located logically contiguous with the eight contiguous 512 byte sectors occupied by the separate user data field subdivisions of the separate user data fields with which the separate metadata region is correlated.

18. A group of data structures as defined in claim 17 wherein:

each separate metadata region is located in one 512 byte sector which is logically contiguous with the eight contiguous 512 byte sectors occupied by the separate user data field subdivisions of the one separate user data field with which the separate metadata region is correlated; and

another eight contiguous 512 byte sectors occupied by the separate user field subdivisions of another separate user data field are located logically contiguous with the separate metadata region correlated with the one separate user data field.

19. A group of data structures as defined in claim 17 wherein:

each separate metadata region is located in one 512 byte sector which is logically contiguous with the eight contiguous 512 byte sectors occupied by the separate user data field subdivisions of the one separate user data field with which the separate metadata region is correlated;

a remaining portion of the one 512 byte sector not occupied by the separate metadata region is unused; and

another eight contiguous 512 byte sectors occupied by the separate user data field subdivisions of another separate user data field are located logically contiguous with the separate metadata region correlated with the one separate user data field.

20. A group of data structures defining an input/output (I/O) operation performed on storage media and used to contain user data and to contain metadata which is used to detect errors arising from other I/O operations performed on one or more of the data structures of the group, comprising in combination:

a plurality of user data structures, each user data structure having a plurality of fields including the user data field for containing user data, a sequence number field for containing sequence number information identifying the I/O operation which originated the group of data structures, and a revision number field for containing revision number information identifying a subsequent I/O operation after the original I/O operation in which user data was written in the user data field of at least one user data structure of the plurality of user data structures;

a parity data structure associated with the plurality of user data structures of the group, the parity data structure having a plurality of fields including a parity field for containing parity information describing the user data in each of the user data fields of each of the associated user data structures of the group, a sequence number field for containing sequence number information identifying the I/O operation which originated the group of data structures, and a revision number field for each associated user data structure which contains revision number information identifying the subsequent I/O operation in which user data was written in the user data field of the associated user data structure;

the parity data structure and the associated plurality of user data structures collectively and logically constituting a separate unit of I/O information recorded on the storage media;

wherein each user data structure includes a plurality of separate user data fields, each separate user data field is for containing a component of user data in the user data structure;

the parity data structure data includes a plurality of separate parity fields, each separate parity field correlates to one separate user data field of each user data structure, and each separate parity field is for containing parity information describing the component of user data contained in the separate user data field of the correlated user data structure;

wherein the storage media is divided into sectors of uniform length;

each user data structure includes a user data region which includes each separate user data field;

each separate user data field consumes a plurality of logically contiguous sectors on the storage media;

each user data structure further includes a control block metadata region in which the sequence number field and the revision number field is located;

the control block metadata region of each user data structure is divided into separate metadata regions which correlate to each separate user data region, each separate metadata region has a size equal to a fractional portion of a sector;

each separate metadata region is located logically contiguous with the plurality of sectors occupied by the separate user data field with which the separate metadata region is correlated.

21. A group of data structures as defined in claim 20 wherein:

each separate metadata region is located in one sector which is logically contiguous with the plurality of sectors of the one separate user data field with which the separate metadata region is correlated; and

another plurality of sectors occupied by another separate user data field is located logically contiguous with the separate metadata region correlated with the one separate user data field.

22. A group of data structures as defined in claim 20 wherein:

each separate metadata region is located in one sector logically contiguous with the plurality of sectors occupied by the one separate user data field with which the separate metadata region is correlated;

a remaining portion of the sector not occupied by the separate metadata region is unused; and

another plurality of sectors occupied by another separate user data field is located logically contiguous with the separate metadata region correlated with the one separate user data field.

23. A method of containing user data a metadata to detect and correct errors arising from input/output (I/O) operations performed on storage media, comprising the steps of:

forming a group of data structures defining an input/output (I/O) operation performed on storage media and used to contain user data and to contain metadata which is used to detect errors arising from other I/O operations performed on one or more of the data structures of the group, including;

a plurality of user data structures, each user data structure having a plurality of fields including the user data field for containing user data, a sequence number field for containing sequence number information identifying the I/O operation which originated the group of data structures, and a revision number field for containing revision number information identifying a subsequent I/O operation after the original I/O operation in which user data was written in the user data field of at least one user data structure of the plurality of user data structures;

a parity data structure associated with the plurality of user data structures of the group, the parity data structure having a plurality of fields including a parity field for containing parity information describing the user data in each of the user data fields of each of the associated user data structures of the group, a sequence number field for containing sequence number information identifying the I/O operation which originated the group of data structures, and a revision number field for each associated user data structure which contains revision number information identifying the subsequent I/O operation in which user data was written in the user data field of the associated user data structure;

the parity data structure and the associated plurality of user data structures collectively and logically constituting a separate unit of I/O information recorded on the storage media;

writing user data in the user data fields of the user data structure;

writing sequence number information in the sequence number fields of the user data structures and the parity data structure;

writing revision number information in the revision number fields of the user data structures and the parity data structure; and

writing parity information in the parity fields of the parity data structure.