US 9,448,877 B2Granted

Methods and apparatus for error detection and correction in data storage systems using hash value comparisons

AssigneeCisco Technology, Inc.

InventorJames Candelaria

Life of this patent

Estimating the term…

Loading patent…

Abstract

Data processing methods and apparatus for processing stored data with error correcting bits to detect and in some instances correct errors. The data processing including, e.g., techniques such as the detection of errors by comparing hash values of data retrieved from storage with hash values of the data generated during storage. For example, one embodiment of a method in accordance with the present invention includes reading data stored with error correcting bits from a storage device, performing a hash operation on the data read from the storage device to generate a first hash value, comparing said first hash value to a previously generated hash value corresponding to said data, and determining that a read error has occurred when said first hash value does not match said previously generated hash value. In some embodiments, the method further includes performing an error recovery operation upon detection of an error.

Claims15

Dependent claims

A method of processing stored data, the method comprising:

reading data stored with error correcting bits from a storage device;
performing a hash operation on a data portion of the data read from the storage device separate from an error correcting bit portion to generate a first hash value;
comparing said first hash value to a previously generated hash value corresponding to said data portion, wherein the previously generated hash value and the error correcting bits are different;
determining that a read error has occurred when said first hash value does not match said previously generated hash value;
and
when it is determined that a read error has occurred, performing an error recovery operation to determine a source of the read error, the error recovery operation comprising:
(a) determining a current Redundant Array of Independent Drives (RAID) storage element;
(b) recovering information from other RAID storage elements excluding the current RAID storage element;
(c) generating a second hash value from the recovered information;
(d) comparing the generated second hash value to the previously generated hash value corresponding to said data portion;
(e) determining that an error remains when there is not a match between the generated second hash value and the previously generated hash value;
(f) determining that no error remains when there is a match between the generated second hash value and the previously generated hash value;
(g) identifying a particular RAID storage element as the source of the read error when the particular RAID storage element has been excluded from the generated second hash value and there is a match between the generated second hash value and the previously generated hash value;
and
(h) advancing the current RAID storage element to a next RAID storage element and repeating (a), (b), (c), (d), (e), (f) and (g) until the source of the read error is identified.

12 more elements

A data processing apparatus comprising:

a data retrieval module configured to read data stored with error correcting bits from a storage device;
a hash generation module configured to perform a hash operation on a data portion of the data read from the storage device separate from an error correcting bit portion to generate a first hash value;
a comparison module configured to compare said first hash value to a previously generated hash value corresponding to said data, wherein the previously generated hash value and the error correcting bits are different;
a read error determination module configured to determine that a read error has occurred when said first hash value does not match said previously generated hash value;
and
an error recovery module configured to perform an error recovery operation to determine a source of the read error when it is determined that a read error has occurred, the error recovery operation comprising:
(a) determining a current Redundant Array of Independent Drives (RAID) storage element;
(b) recovering information from other RAID storage elements excluding the current RAID storage element;
(c) generating a second hash value from the recovered information;
(d) comparing the generated second hash value to the previously generated hash value corresponding to said data portion;
(e) determining that an error remains when there is not a match between the generated second hash value and the previously generated hash value;
(f) determining that no error remains when there is a match between the generated second hash value and the previously generated hash value;
(g) identifying a particular RAID storage element as the source of the read error when the particular RAID storage element has been excluded from the generated second hash value and there is a match between the generated second hash value and the previously generated hash value;
and
(h) advancing the current RAID storage element to a next RAID storage element and repeating (a), (b), (c), (d), (e), (f) and (g) until the source of the read error is identified.

12 more elements

A computer program product for use in a data processing apparatus, the computer program product comprising:

a non-transitory computer readable medium comprising:
code for causing at least one computer to read data stored with error correcting bits from a storage device;
code for causing said at least one computer to perform a hash operation on a data portion of the data read from the storage device separate from an error correcting bit portion to generate a first hash value;
code for causing said at least one computer to compare said first hash value to a previously generated hash value corresponding to said data, wherein the previously generated hash value and the error correcting bits are different;
code for causing said least one computer to determine that a read error has occurred when said first hash value does not match said previously generated hash value;
and
code for causing said at least one computer to perform an error recovery operation to determine a source of the read error when it is determined that a read error has occurred, the error recovery operation comprising:
(a) determining a current Redundant Array of Independent Drives (RAID) storage element;
(b) code for recovering information from other RAID storage elements excluding the current RAID storage element;
(c) code for generating a second hash value from the recovered information;
(d) code for comparing the generated second hash value to the previously generated hash value corresponding to said data portion;
(e) code for determining that an error remains when there is not a match between the generated second hash value and the previously generated hash value;
(f) code for determining that no error remains when there is a match between the generated second hash value and the previously generated hash value;
(g) code for identifying a particular RAID storage element as the source of the read error when the particular RAID storage element has been excluded from the generated second hash value and there is a match between the generated second hash value and the previously generated hash value;
and
(h) code for advancing the current RAID storage element to a next RAID storage element and repeating (a), (b), (c), (d), (e), (f) and (g) until the source of the read error is identified.

13 more elements

Dependencies are inferred from the claim text.

Facts

Application: 13/844,272Filed 15 Mar 2013
Published: US 2014/0317479 A123 Oct 2014
Granted: 20 Sep 2016
Term ends: Not estimatedThe source records don’t support an estimate.

Classification7 codes

G06F 11/1004
Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's: to protect a block of data words, e.g. CRC or…
G06F 11/0727
The processing taking place on a specific hardware platform or in a specific software environment: in a storage system, e.g. in a DASD or network…
G06F 11/0763
Error or fault detection not based on redundancy: by bit configuration check, e.g. of formats or tags
G06F 11/108
Parity data used in redundant arrays of independent storages, e.g. in RAID systems: parity data distribution in semiconductor storages, e.g. in SSD