US 6,606,629 B1 · Data structures containing sequence and revision number metadata used in mass storage data integrity-assuring technique

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.

Claims23

Dependent claims

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.

1 more element

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.

8 more elements

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.

8 more elements

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.

6 more elements

Dependencies are inferred from the claim text.

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

Life of this patent

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

Life of this patent

Abstract

Claims23