Efficient data storage in storage device arrays

• US 8,239,734 B1
• Filed: 10/15/2009
• Issued: 08/07/2012
• Est. Priority Date: 10/15/2008
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Shalvi, Ofir
• Primary Examiner(s): Duncan, Marc
• Application Number:
  US12/579,432
• Time in Patent Office: 1,027 Days
• Field of Search: 714/764, 714/768, 714/769, 714/770, 714/773
• US Class Current: 714/770
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 2211/109 Sector level checksum or ECC, i.e. sector or stripe level checksum or ECC in addition to the RAID parity calculation

Abstract

A method for data storage includes encoding data with an inter-device Error Correction Code (ECC), and sending the encoded data for storage on two or more storage devices. The data to be stored on each of the storage devices, and which has been encoded with the inter-device ECC, is encoded with an intra-device ECC, and the data encoded with the inter-device and intra-device ECCs is stored on the storage device. After storing the data, at least part of the stored data is retrieved and output by decoding the intra-device and inter-device ECCs, while using information related to one of the intra-device and inter-device ECCs in decoding the other of the intra-device and inter-device ECCs.

Claims

1. A method for data storage, comprising:

encoding data with an inter-device Error Correction Code (ECC), and sending the encoded data for storage on two or more storage devices;

encoding the data to be stored on each of the storage devices, and which has been encoded with the inter-device ECC, with an intra-device ECC, and storing the data encoded with the inter-device and intra-device ECCs on the storage device; and

after storing the data, retrieving and outputting at least part of the stored data by decoding the intra-device and inter-device ECCs, while using information related to one of the intra-device and inter-device ECCs in decoding the other of the intra-device and inter-device ECCs,

wherein encoding the data with the inter-device ECC comprises dividing the data into pages comprising data bits, computing a respective parity bit for the data bits in each bit position within the pages, sending the pages for storage on respective ones of the storage devices, and sending the parity bits for storage on another of the storage devices.

2. The method according to claim 1, wherein the storage devices comprise at least one device type selected from a group of types consisting of a magnetic disk, a Solid State Disk (SSD), a Direct Access Storage Device (DASD), a solid state memory device, a memory chip, a Multi-Chip Package (MCP) memory device and a disk sub-array.

3. The method according to claim 1, wherein the information is related to the inter-device ECC, and wherein retrieving the at least part of the data comprises making an attempt to decode the intra-device ECC independently of the information, and decoding the intra-device ECC using the information responsively to a failure of the attempt.

4. The method according to claim 1, wherein encoding the data with the intra-device ECC comprises generating intra-device redundancy bits, and wherein the information comprises the intra-device redundancy bits.

5. The method according to claim 4, wherein decoding the intra-device and inter-device ECCs comprises exporting the intra-device redundancy bits from one or more of the storage devices.

6. The method according to claim 1, wherein decoding the intra-device and inter-device ECCs comprises identifying at least one bit position for which the data bits read from the storage devices are inconsistent with the respective parity bit, and decoding the intra-device ECC based on the identified at least one bit position.

7. The method according to claim 6, wherein decoding the intra-device ECC comprises modifying soft metrics of one or more of the data bits located in the identified bit positions in the pages, and decoding the intra-device ECC based on the modified soft metrics.

8. The method according to claim 6, wherein decoding the intra-device ECC comprises modifying bit values of one or more of the data bits located in the identified bit positions in the pages, and decoding the intra-device ECC based on the modified bit values.

9. The method according to claim 1, wherein encoding the data with the inter-device and intra-device ECCs comprises encoding the data with a systematic ECC to produce redundancy bits, and dividing the redundancy bits for storage among the two or more storage devices, wherein decoding the intra-device ECC comprises decoding a portion of the data stored on a given storage device using only a subset of the redundancy bits that are stored on the given storage device, and wherein decoding the inter-device ECC comprises decoding the entire data using the redundancy bits stored on the two or more storage devices.

10. The method according to claim 9, wherein the systematic ECC comprises a Low Density Parity Check (LDPC) code.

11. The method according to claim 1, wherein decoding the intra-device and inter-device ECCs comprises performing alternating decoding iterations of the intra-device and inter-device ECCs, and transferring soft metrics between the decoding iterations of the intra-device and inter-device ECCs.

12. The method according to claim 1, wherein encoding the data with the inter-device ECC comprises mirroring the data in the two or more storage devices, and wherein decoding the intra-device and inter-device ECCs comprises computing soft metrics of respective bits in each of the storage devices, combining the soft metrics of corresponding bits stored on the two or more storage devices, and decoding the intra-device ECC using the combined soft metrics.

13. A method for data storage, comprising:

encoding data with an inter-device Error Correction Code (ECC), and sending the encoded data for storage on two or more storage devices;

encoding the data to be stored on each of the storage devices, and which has been encoded with the inter-device ECC, with an intra-device ECC, and storing the data encoded with the inter-device and intra-device ECCs on the storage device; and

after storing the data, retrieving and outputting at least part of the stored data by decoding the intra-device and inter-device ECCs, while using information related to one of the intra-device and inter-device ECCs in decoding the other of the intra-device and inter-device ECCs,

wherein decoding the intra-device ECC comprises computing soft metrics of respective bits of the at least part of the data, and wherein the information comprises the soft metrics.

14. A method for data storage, comprising:

encoding data with an inter-device Error Correction Code (ECC), and sending the encoded data for storage on two or more storage devices;

encoding the data to be stored on each of the storage devices, and which has been encoded with the inter-device ECC, with an intra-device ECC, and storing the data encoded with the inter-device and intra-device ECCs on the storage device; and

after storing the data, retrieving and outputting at least part of the stored data by decoding the intra-device and inter-device ECCs, while using information related to one of the intra-device and inter-device ECCs in decoding the other of the intra-device and inter-device ECCs,

wherein the information is related to the inter-device ECC, and wherein decoding the intra-device and inter-device ECCs comprises sending the information to a given storage device, and decoding the intra-device ECC in the given storage device responsively to the information.

15. Apparatus for data storage, comprising:

two or more storage devices, each of which is configured to encode data with an intra-device Error Correction Code (ECC) and to store the encoded data on the storage device;

a controller, which is configured to encode input data with an inter-device ECC, to send the input data encoded with the inter-device ECC to the two or more storage devices, for subsequent encoding with the intra-device ECC and storage; and

a joint decoder, which is configured to retrieve and output at least part of the stored input data by decoding the intra-device and inter-device ECCs, while using information related to one of the intra-device and inter-device ECCs in decoding the other of the intra-device and inter-device ECCs,

wherein the controller is configured to encode the input data with the inter-device ECC by dividing the input data into pages comprising data bits, computing a respective parity bit for the data bits in each bit position within the pages, sending the pages for storage on respective ones of the storage devices, and sending the parity bits for storage on another of the storage devices.

16. The apparatus according to claim 15, wherein the storage devices comprise at least one device type selected from a group of types consisting of a magnetic disk, a Solid State Disk (SSD), a Direct Access Storage Device (DASD), a solid state memory device, a memory chip, a Multi-Chip Package (MCP) memory device and a disk sub-array.

17. The apparatus according to claim 15, wherein the information is related to the inter-device ECC, wherein each storage device is configured to make an attempt to decode the intra-device ECC independently of the information, and wherein the joint decoder is configured to decode the intra-device ECC using the information responsively to a failure of the attempt.

18. The apparatus according to claim 15, wherein each storage device is configured to generate intra-device redundancy bits when encoding the data with the intra-device ECC, and wherein the information comprises the intra-device redundancy bits.

19. The apparatus according to claim 18, wherein each storage device is configured to export the intra-device redundancy bits to the controller.

20. The apparatus according to claim 15, wherein the joint decoder is configured to identify at least one bit position for which the data bits read from the storage devices are inconsistent with the respective parity bit, and to decode the intra-device ECC based on the identified at least one bit position.

21. The apparatus according to claim 20, wherein the joint decoder is configured to modify soft metrics of one or more of the data bits located in the identified bit positions in the pages, and to decode the intra-device ECC based on the modified soft metrics.

22. The apparatus according to claim 20, wherein the joint decoder is configured to modify bit values of one or more of the data bits located in the identified bit positions in the pages, and to decode the intra-device ECC based on the modified bit values.

23. The apparatus according to claim 15, wherein the controller is configured to encode the input data with a systematic ECC to produce redundancy bits, and to divide the redundancy bits for storage among the two or more storage devices, wherein a given storage device is configured to decode the intra-device ECC by decoding a portion of the input data stored on the given storage device using only a subset of the redundancy bits that are stored on the given storage device, and wherein the joint decoder is configured to decode the entire input data using the redundancy bits stored on the two or more storage devices.

24. The apparatus according to claim 23, wherein the systematic ECC comprises a Low Density Parity Check (LDPC) code.

25. The apparatus according to claim 15, wherein the joint decoder is configured to perform alternating decoding iterations of the intra-device and inter-device ECCs, and to transfer soft metrics between the decoding iterations of the intra-device and inter-device ECCs.

26. The apparatus according to claim 15, wherein the controller is configured to mirror the input data in the two or more storage devices, wherein each storage device is configured to compute soft metrics of respective bits of the input data stored on the storage device, and wherein the joint decoder is configured to combine the soft metrics of corresponding bits stored on the two or more storage devices, and to decode the intra-device ECC using the combined soft metrics.

27. Apparatus for data storage, comprising:

two or more storage devices, each of which is configured to encode data with an intra-device Error Correction Code (ECC) and to store the encoded data on the storage device;

a controller, which is configured to encode input data with an inter-device ECC, to send the input data encoded with the inter-device ECC to the two or more storage devices, for subsequent encoding with the intra-device ECC and storage; and

a joint decoder, which is configured to retrieve and output at least part of the stored input data by decoding the intra-device and inter-device ECCs, while using information related to one of the intra-device and inter-device ECCs in decoding the other of the intra-device and inter-device ECCs,

wherein the storage devices are configured to compute soft metrics of respective bits of the at least part of the input data, and wherein the information comprises the soft metrics.

28. Apparatus for data storage, comprising:

two or more storage devices, each of which is configured to encode data with an intra-device Error Correction Code (ECC) and to store the encoded data on the storage device;

a controller, which is configured to encode input data with an inter-device ECC, to send the input data encoded with the inter-device ECC to the two or more storage devices, for subsequent encoding with the intra-device ECC and storage; and

a joint decoder, which is configured to retrieve and output at least part of the stored input data by decoding the intra-device and inter-device ECCs, while using information related to one of the intra-device and inter-device ECCs in decoding the other of the intra-device and inter-device ECCs,

wherein the information is related to the inter-device ECC, and wherein the joint decoder is configured to send the information to a given storage device, and to cause the given storage device to decode the intra-device ECC responsively to the information.