Drive replacement techniques for RAID systems

• US 8,386,889 B1
• Filed: 04/24/2012
• Issued: 02/26/2013
• Est. Priority Date: 04/17/2006
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Marvell International Limited (Marvell Technology Group Limited)
• Inventors: Tang, Heng, Wu, Zining, Burd, Gregory, Sutardja, Pantas
• Primary Examiner(s): ABRAHAM, ESAW T
• Application Number:
  US13/454,831
• Time in Patent Office: 308 Days
• Field of Search: 714/770, 714/758, 714/781, 714/801, 714/807
• US Class Current: 714/770
• CPC Class Codes: G06F 11/08 Error detection or correction by redundancy in data representation, e.g. by using checking codes
• 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/1443 Transmit or communication errors
• CPC Class Codes: G11C 29/00 Checking stores for correct operation ; Subsequent repair; Testing stores during standby or offline operation
• CPC Class Codes: H03M 13/09 Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/155 Shortening or extension of codes
• CPC Class Codes: H03M 13/611 Specific encoding aspects, e.g. encoding by means of decoding
• CPC Class Codes: H03M 13/618 Shortening and extension of codes

Abstract

A control module includes an encoder module, which generates a first code word for multiple drives. A detector module, in response to detecting an error in a first drive subsequent to generation of the first code word, initiates replacement of the first drive with a second drive. The encoder module generates a second code word for the second drive. A mapping module maps physical locations of data in the drives to logical locations of the first code word, assigns a predetermined value to one of the logical locations corresponding to the first drive to identify an unused logical location, and assigns the unused logical location to the second drive based on the predetermined value. A difference module generates a third code word based on the first and second code words. The encoder module generates an updated code word for the multiple drives based on the first and third code words.

Claims

1. A control module comprising:

an encoder module configured to (i) receive data, and (ii) based on the data, generate a first code word for a plurality of drives;

a detector module configured to, in response to detecting an error in a first drive of the plurality of drives subsequent to generation of the first code word, initiate replacement of the first drive with a second drive, wherein the encoder module is configured to generate a second code word for the second drive;

a mapping module configured to (i) map physical locations of the data in the plurality of drives to logical locations of the first code word, (ii) assign a predetermined value to one of the logical locations corresponding to the first drive to identify an unused one of the logical locations, and (iii) assign the unused one of the logical locations to the second drive based on the predetermined value; and

a difference module configured to generate a third code word based on each of the first code word and the second code word,

wherein the encoder module is configured to generate an updated code word for the plurality of drives based on the first code word and the third code word.

2. The control module of claim 1, wherein:

the plurality of drives are implemented as a redundant array of independent disks; and

the redundant array of independent disks comprises data drives and at least one parity drive.

3. The control module of claim 2, wherein:

the logical locations are referenced to index positions in a cyclic code word; and

the cyclic code word has a length equal to a sum of (i) a number of the data drives, and (ii) a number of the at least one parity drives.

4. The control module of claim 1, wherein the encoder module is configured to (i) encode the third code word to generate a fourth code word, (ii) add the first code word and the fourth code word to generate the updated code word, and (iii) modify the updated code word to identify the second drive in the previously unused one of the logical locations.

5. The control module of claim 1, wherein the logical locations correspond to index positions in a cyclic code word.

6. The control module of claim 5, wherein the mapping module is configured to map parity drives of the plurality of drives to lowest positions of the index positions.

7. The control module of claim 1, wherein:

the encoder module is configured to generate the first code word for a plurality of drives based on a cyclic code generator polynomial; and

the cyclic code generator polynomial is a Reed-Solomon code generator polynomial.

8. The control module of claim 1, wherein, without reading drives of the plurality of drives other than the first drive,

the mapping module is configured to map the second drive to the unused one of the logical locations, and

the encoder module is configured to generate the updated code word.

9. The control module of claim 1, wherein, without reading the first drive,

the mapping module is configured to map the second drive to the unused one of the logical locations, and

the encoder module is configured to generate the updated code word.

10. The control module of claim 1, wherein, without causing down-time for a drive of the plurality of drives other than the first drive,

the mapping module is configured to map the second drive the unused one of the logical locations, and

the encoder module is configured to generate the updated code word.

11. The control module of claim 1, wherein the unused one of the logical locations is a highest unused one of the logical locations.

12. A system comprising:

the control module of claim 1; and

the plurality of drives, wherein the plurality of drives comprises data drives and at least one parity drive,

wherein each of the data drives and each of the at least one parity drive comprises an error correction module, wherein the error correction modules are configured to (i) perform error correction coding, and (ii) cyclic redundancy checking.

13. A method comprising:

receiving data at a control module;

based on the data, generating a first code word for a plurality of drives; and

in response to detecting an error in a first drive of the plurality of drives subsequent to generation of the first code word,

initiating replacement of the first drive with a second drive,

generating a second code word for the second drive,

mapping physical locations of the data in the plurality of drives to logical locations of the first code word,

assigning a predetermined value to one of the logical locations corresponding to the first drive to identify an unused one of the logical locations,

assigning the unused one of the logical locations to the second drive based on the predetermined value,

generating a third code word based on each of the first code word and the second code word, and

generating an updated code word for the plurality of drives based on each of the first code word and the third code word.

14. The method of claim 13, wherein:

the plurality of drives are implemented as a redundant array of independent disks; and

the redundant array of independent disks comprises data drives and at least one parity drive.

15. The method of claim 14, wherein:

the logical locations are referenced to index positions in a cyclic code word; and

the cyclic code word has a length equal to a sum of (i) a number of the data drives, and (ii) a number of the at least one parity drives.

16. The method of claim 13, further comprising:

encoding the third code word to generate a fourth code word; and

adding the first code word and the fourth code word to generate the updated code word; and

modifying the updated code word to identify the second drive in the previously unused one of the logical locations.

17. The method of claim 13, wherein the logical locations correspond to index positions in a cyclic code word.

18. The method of claim 17, further comprising mapping parity drives of the plurality of drives to lowest positions of the index positions.

19. The method of claim 13, further comprising generating the first code word for a plurality of drives based on a cyclic code generator polynomial, wherein the cyclic code generator polynomial is a Reed-Solomon code generator polynomial.

20. The method of claim 13, wherein, without reading drives of the plurality of drives other than the first drive and without causing down-time for the plurality of drives other than the first drive,

the second drive is mapped to the unused one of the logical locations, and

the updated code word is generated.