Error rate reduction for memory arrays

• US 7,930,586 B1
• Filed: 02/07/2008
• Issued: 04/19/2011
• Est. Priority Date: 02/07/2008
• Status: Expired due to Fees

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property II LP (AT&T, Inc.)
• Inventors: Asher, Michael
• Primary Examiner(s): McCarthy; Christopher S
• Application Number:
  US12/069,143
• Time in Patent Office: 1,167 Days
• Field of Search: None
• US Class Current: N/A
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 2211/1057 Parity-multiple bits-RAID6, i.e. RAID 6 implementations
• CPC Class Codes: G06F 2211/1059 Parity-single bit-RAID5, i.e. RAID 5 implementations

Abstract

A RAID 6 system, which has two strips to hold redundant data, employs a memory array controller that at each “read” operation considers not just the data but also the redundant information, even in the absence of any indication from the collection of memory controllers associated with the hard drives that any error condition exists. Thus, with each “read” operation the array controller checks the data for an unreported error, and takes corrective action when an error condition is discovered.

Claims

1. A controller that interacts with a plurality of N memories, where (a) data to be stored is divided and stored in blocks, (b) the data of a block comprises N-i data strips, i being either 1 or 2, and i redundant-data strips that are associated with said N-i data strips and which, together with the N-i data strips, form a stripe of N strips, (c) the N strips of a stripe are stored in said N memories, respectively, (d) the i redundant-data strips of a stripe being adapted to be used in handling up to i errors that are discovered when an error arises upon reading at least said N-i data strips of a stripe, and (e) the controller includes a module, in response to a request from a user to provide a block of data, for reading N-i data strips from said N memories, the improvement comprising:

the module adapted to read, in response to every request for data, said N-i data strips and at least one of said i redundant data strips when reading a block data, even when there is no indication of any error in any of the N-i data strips that are read from said N memories;

when processing said N-i read data strips and the at least one of said i redundant data strips indicates an error condition in information contained in one of said N-i read data strips, taking corrective action.

2. The controller of claim 1 where, when i=1, the corrective action comprises informing said user of the indicated error condition.

3. The controller of claim 1 where, when i=2, one of the i redundant data strips is a parity strip, and said controller:

reads N-2 data strips responsive to said user request and the associated parity strip;

determines whether an error condition exists in the read strips based on the N-2 read data strips and the associated read parity strip;

when a conclusion is reached that said error condition exists, reads remaining strip associated with the read N-2 data strips.

4. The controller of claim 3 where said corrective action identifies the error that gave rise to the error condition, and corrects the identified error, by using both of the two redundant data strips.

5. The controller of claim 1 where, when i=2, said controller:

reads N-2 data strips responsive to said user request and said 2 associated redundant data strips; and

determines whether an error condition exists in the read strips based on said N-2 read data strips and one of the read redundant data strips.

6. The controller of claim 5 where said corrective action identifies the error that gave rise to the error condition, and corrects the identified error, by using both of the two redundant data strips.

7. The controller of claim 1 where i=2, the first redundant data strip associated with a block of data is a parity strip, P, and the second redundant data strip associated with said block of data is a syndrome, Q, computed from said N-2 data strips, where the computing is over a field, and said controller

reads N-i data strips responsive to said user request and the associated parity strip, P;

and

determines whether an error condition exists in the read strips by computing a parity strip P′

based on read N-i data strips, and concluding that an error exists when P′

≠

P.

8. The controller of claim 7 where said corrective action employs the Q syndrome to identify the strip of said N-2 strips that contains the error, and employs the P strip to correct the error.

9. The controller of claim 7 where Q is a Reed-Solomon code, RS(N,N-2).

10. The controller of claim 7 where P=D₀+D₁+ . . . +D_N-1, and Q=g⁰·

D₀+g¹·

D₁+ . . . +g^N-1·

D_N-1, where D_i is data of strip i, the “

+”

designates Exclusive OR operation, the “

·

”

designates multiplication of a Galois field, and gⁱ i^th coefficient of a polynomial in said Galois field.

11. The controller of claim 10 where said strips P and Q are computed using a Read Only Memory (ROM).

12. The controller of claim 7 where said strips P and Q are obtained from a Read Only Memory (ROM).

13. A method comprising the steps of:

receiving a request for data at a given address of an array of N memories;

retrieving a data stripe from said given address of said array, the data stripe comprising strips D₀, D₁, . . . , D_N-1, where D_i is the strip of memory of index i, N-i of said strips holding data (data strips) and i of said strips holding redundant information (redundant information strips), and i=2;

identifying the read strip, P, that corresponds to a first of said redundant information strips;

computing a parity strip (P′

) based on said N-i data strips; and

executing remedial action when P is not equal to P′

, where the remedial action fixes said error and submits valid results to process that submitted said request for data, and said remedial action comprises the steps of;

computing information of data strip D_j′

, where j is a chosen value between 0 and N-2, from strips D₀ through D_N-2 other than D_j, and from strip P;

compute a second redundant strip, Q′

, using said strip D_j′

;

if Q′

equals a second redundant information strip that was retrieved by said step of retrieving, return D_j′

to process that submitted said request for data in lieu of D_j′

together with strips D₀ through D_N-2 other than D_j, and otherwise, choose another value of j and return to said step of computing.