Pool-level solid state drive error correction

• US 10,180,875 B2
• Filed: 07/08/2016
• Issued: 01/15/2019
• Est. Priority Date: 07/08/2016
• Status: Active Grant

• Current Assignee: Kioxia Corporation
• Original Assignee: Toshiba Memory Corporation (Kioxia Corporation)
• Inventors: Klein, Yaron
• Primary Examiner(s): Nguyen, Steve N
• Application Number:
  US15/205,248
• Publication Number:
  US 20180011762A1
• Time in Patent Office: 921 Days
• CPC Class Codes: G06F 11/1012 using codes or arrangements adapted for a specific type of error G06F11/1048 takes precedence
• CPC Class Codes: G06F 11/1044 with specific ECC/EDC distribution
• CPC Class Codes: G06F 11/1072 in multilevel memories
• CPC Class Codes: G11C 29/52 Protection of memory contents; Detection of errors in memory contents
• CPC Class Codes: H03M 13/1102 Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/152 Bose-Chaudhuri-Hocquenghem [BCH] codes
• CPC Class Codes: H03M 13/2906 using block codes H03M13/2957 takes precedence

Abstract

A method for performing error correction for a plurality of storage drives and a storage appliance comprising a plurality of storage devices is disclosed. In one embodiment, the method includes generating a first set of parity bits from a first set of data of at least one of the plurality of storage devices, the first set of parity bits capable of correcting a first number of error bits of the first set of data. The method further includes generating a second set of parity bits from a concatenated set of the first data and a second set of data from at least another of the plurality of storage devices, the second set of parity bits capable of correcting a second number of error bits of the first set of data, the second number being greater than the first number. The method further includes reading the first set of data and (i) correcting error bits within the first set of data with the first set of parity bits where a number of error bits is less than the first number of error bits; and (ii) correcting error bits within the first set of data with the second set of parity bits where the number of error bits is greater than the first number.

Claims

1. A method for performing error correction for a plurality of storage devices, the method comprising:

generating a first set of parity bits from a first set of data of at least one of the plurality of storage devices, the first set of parity bits capable of correcting a first maximum number of error bits of the first set of data;

generating a concatenated data set by concatenating the first set of data and a second set of data from at least another of the plurality of storage devices;

generating a second set of parity bits from the concatenated data set, the second set of parity bits capable of correcting a second maximum number of error bits of the first set of data, the second maximum number being greater than the first maximum number;

associating a logical block address of either the first set of data or the second set of data with the second set of parity bits;

correcting error bits within the first set of data with the first set of parity bits where a number of error bits is less than or equal to the first maximum number of error bits; and

correcting error bits within the first set of data with the second set of parity bits where the number of error bits is greater than the first maximum number.

2. The method of claim 1, wherein the first set of data includes a checksum, the checksum indicating whether the first set of parity bits has corrected the first set of data, and if not, correcting error bits within the first set of data with the second set of parity bits.

3. The method of claim 1, further comprising:

generating a mapping table containing locations of the first set of data, the second set of data corresponding to the concatenated data set used to generate the second set of parity bits, and the second set of parity bits within the plurality of storage devices.

4. The method of claim 1, further comprising:

storing the first set of data and the first set of parity bits in a first location within one or more memory devices of the at least one of the plurality of storage devices; and

storing the second set of parity bits in a second location within one or more memory devices of the plurality of storage devices.

5. The method of claim 4, wherein the plurality of storage devices comprise SSDs.

6. The method of claim 5, wherein the first location and the second location correspond to different flash pages within the one or more flash memory devices of the plurality of storage devices.

7. The method of claim 1, wherein the first set of parity bits and second set of parity bits are Bose-Chaudhuri-Hocquenghem parity bits.

8. The method of claim 1, wherein the first set of parity bits and second set of parity bits are Hamming parity bits.

9. The method of claim 1, wherein the first set of parity bits and second set of parity bits are Reed-Soloman parity bits.

10. The method of claim 1, wherein the first set of parity bits and second set of parity bits are low-density parity check (LDPC) parity bits.

11. The method of claim 1, wherein the first and second set of parity bits are independently chosen as Bose-Chaudhuri-Hocquenghem, Hamming, Reed-Soloman, or low-density parity check (LDPC) parity bits.

12. The method of claim 1, further comprising:

storing the second set of parity bits on one of the plurality of storage devices storing either the first set of data or the second set of data.

13. The method of claim 12, wherein the plurality of storage devices comprise SSDs;

and

the method further comprising storing the second set of parity bits in a flash page storing either the first set of data or the second set of data.

14. The method of claim 1, wherein the correcting error bits comprises reading in a single read the second set of parity bits and the second set of data.

15. A storage appliance comprising:

a controller communicatively coupled to a plurality of storage devices, wherein at least one of the plurality of storage devices configured to correct a first maximum number of error bits of a first set of data on the one of the plurality of storage devices with a first set of parity bits when the first set of data is read by the controller, the first set of parity bits generated from the first set of data, and

the controller is configured to;

generate a concatenated data set by concatenating the first set of data and a second set of data of at least one other of the plurality of storage devices;

generate a second set of parity bits from the concatenated data set;

associate a logical block address of either the first set of data or the second set of data with the second set of parity bits; and

correct a second maximum number of error bits greater than the first maximum number of the first set of data with the second set of parity bits when the number of error bits exceeds the first maximum number.

16. The storage appliance of claim 15, wherein the first set of data includes a checksum, the checksum indicating whether the first set of parity bits has corrected the first set of data, and if not, returning an unrecoverable error message to the controller.

17. The storage appliance of claim 15, wherein the controller is configured to store and update a mapping table containing locations of the first set of data and the at least one second set of data corresponding to the concatenated data set used to generate the second set of parity bits, and the second set of parity bits within the plurality of storage devices.

18. The storage appliance of claim 15, wherein the first set of data and the first set of parity bits are stored in a first location within one or more memory devices of the at least one of the plurality of storage devices, and the second set of parity bits are stored in a second location within one or more memory devices of the plurality-of storage devices.

19. The storage appliance of claim 18, wherein the plurality of storage devices comprise SSDs.

20. The storage appliance of claim 19, wherein the first location and the second location correspond to different flash pages within the one or more flash memory devices of the plurality of storage devices.

21. The storage appliance of claim 15, wherein the first set of parity bits and second set of parity bits are Bose-Chaudhuri-Hocquenghem parity bits.

22. The storage appliance of claim 15, wherein the first set of parity bits and second set of parity bits are Hamming parity bits.

23. The storage appliance of claim 15, wherein the first set of parity bits and second set of parity bits are Reed-Soloman parity bits.

24. The storage appliance of claim 15, wherein the first set of parity bits and second set of parity bits are low-density parity check (LDPC) parity bits.

25. The storage appliance of claim 15, wherein the first and second set of parity bits are independently chosen as Bose-Chaudhuri-Hocquenghem, Hamming, Reed-Soloman, or low-density parity check (LDPC) parity bits.

26. The storage appliance of claim 15, wherein the controller is further configured to:

store the second set of parity bits on one of the plurality of storage devices storing either the first set of data or the second set of data.

27. The storage appliance of claim 26, wherein the plurality of storage devices comprise SSDs;

and

wherein the controller is further configured to store the second set of parity bits in a flash page storing either the first set of data or the second set of data.

28. The storage appliance of claim 15, wherein the controller is further configured, when correcting the second maximum number of error bits to read in a single read the second set of parity bits and the second set of data.