FRACTIONAL REDUNDANT ARRAY OF SILICON INDEPENDENT ELEMENTS

• US 20130073895A1
• Filed: 11/13/2012
• Published: 03/21/2013
• Est. Priority Date: 12/01/2010
• Status: Active Grant

• Current Assignee: Seagate Technology LLC (Seagate Technology Holdings Plc)
• Original Assignee: LSI Corporation (Broadcom, Inc.)
• Inventors: COHEN, Earl T.
• Granted Patent: US 9,727,414 B2
• Time in Patent Office: Days
• US Class Current: 714/6.2
• CPC Class Codes: G06F 11/1068 in sector programmable memories, e.g. flash disk G06F11/1072 takes precedence
• 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/1096 Parity calculation or recalculation after configuration or reconfiguration of the system

Abstract

Higher-level redundancy information computation enables a Solid-State Disk (SSD) controller to provide higher-level redundancy capabilities to maintain reliable operation in a context of failures of non-volatile (e.g. flash) memory elements during operation of an SSD implemented in part by the controller. For example, a first computation is an XOR, and a second computation is a weighted-sum. Various amounts of storage are dedicated to storing the higher-level redundancy information, such as amounts equivalent to an integer multiple of flash die (e.g. one, two, or three entire flash die), and such as amounts equivalent to a fraction of a single flash die (e.g. one-half or one-fourth of a single flash die).

Claims

1. A method comprising:

computing one or more portions of higher-level redundancy information based at least in part on a plurality of portions of data storage information;

storing the portions of higher-level redundancy information and the portions of data storage information in portions of one or more non-volatile memory devices; and

wherein the computing comprises accumulating a weighted sum of a respective non-zero unique constant value for each of the portions of data storage information multiplied by contents of the portions of data storage information as at least a portion of the portions of higher-level redundancy information.

2. The method of claim 1, wherein the portions of higher-level redundancy information are not computable as a remainder of a polynomial division by a generator polynomial of corresponding bytes of the portions of data storage information.

3. The method of claim 1, wherein the accumulating comprises accumulating incrementally.

4. The method of claim 3, wherein the accumulating further comprises processing at least partially in parallel more than one of the portions of data storage information.

5. The method of claim 1, further comprising reading at least some portions stored in the non-volatile memory devices;

and determining if any of the portions read are uncorrectable via lower-level redundancy information.

6. The method of claim 1, further comprising computing a correction version of the higher-level redundancy information, wherein the computing a correction version of the higher-level redundancy information selectively excludes up to two portions of the portions of data storage information.

7. The method of claim 6, further comprising processing results of the computing a correction version of the higher-level redundancy information to restore the excluded portions of the data storage information.

8. The method of claim 6, wherein the accumulating comprises accumulating incrementally at least partially in an order determined at least in part by an order that read operations are completed by the non-volatile memory devices.

9. The method of claim 1, wherein each of the portions is a page, the non-volatile memory devices are comprised of a plurality of flash die, and only one of the pages of the higher-level redundancy information or the data storage information is stored in any one of the flash die.

10. The method of claim 9, wherein the pages of the higher-level redundancy information are excluded from at least one of the flash die.

11. The method of claim 9, wherein the pages of the data storage information are excluded from at least one of the flash die.

12. The method of claim 1, wherein:

the storing comprises writing a respective first page to each of a first block of each of the plurality of non-volatile memory devices;

the storing further comprises writing a respective second page to each of a second block of each of the plurality of non-volatile memory devices;

the first blocks are distinct from the second blocks;

the respective first pages and the respective second pages taken together are a group of pages, and one or more of the pages of the group contains redundancy of an erasure-correcting code protecting all of the pages of the group; and

the portions of higher-level redundancy information comprise the redundancy of an erasure-correcting code protecting all of the pages of the group.

13. A method comprising:

writing a respective first page to each of a first block of each of a plurality of non-volatile memory devices;

writing a respective second page to each of a second block of each of the plurality of non-volatile memory devices;

wherein the first blocks are distinct from the second blocks; and

wherein the respective first pages and the respective second pages taken together are a group of pages, and one or more of the pages of the group contains redundancy of an erasure-correcting code protecting all of the pages of the group.

14. The method of claim 13, wherein a fraction of the pages of the group containing the redundancy of the erasure-correcting code is less than one in a number of the plurality of non-volatile memory devices.

15. The method of claim 14, wherein the fraction is one in an integer multiple of the number of the plurality of non-volatile memory devices.

16. The method of claim 15, wherein the integer multiple is a power of two.

17. The method of claim 13, wherein the erasure-correcting code is an error-correcting code.

18. The method of claim 13, wherein the respective first blocks are dual-plane blocks.

19. A system comprising:

a plurality of non-volatile memory devices, each of the non-volatile memory devices comprising a plurality of blocks, each of the blocks comprising a plurality of pages;

an erasure-correcting code generator operable to generate one or more pages of redundant data protecting a respective plurality of pages of user data, the one or more pages of redundant data and the respective plurality of pages of user data forming a codeword of an erasure-correcting code;

wherein the one or more pages of redundant data and the respective plurality of pages of user data are each compatible with being stored into a separate respective one of the pages of at least some of the blocks such that more than one of the non-volatile memory devices contains more than one of the one or more pages of redundant data and the respective plurality of pages of user data, and such that none of the at least some of the blocks contains more than one of the one or more pages of redundant data and the respective plurality of pages of user data; and

wherein a failure of at least one of the at least some of the blocks is correctable by the erasure-correcting code.

20. The system of claim 19, wherein a number of the one or more pages of redundant data is equal to a number of the at least one of the at least some of the blocks that is correctable.

21. The system of claim 19, further comprising an erasure-correcting code corrector enabled to process information read from at least some of the separate respective ones of the pages of the at least some of the blocks to correct others of the separate respective ones of the pages of the at least some of the blocks.

22. The system of claim 19, further comprising an error-correcting code generator enabled to encode each of the one or more pages of redundant data and the respective plurality of pages of user data to produce respective error-correcting information, the respective error-correcting information compatible with being stored into the separate respective ones of the pages of the at least some of the blocks along with the corresponding one or more pages of redundant data and the respective plurality of pages of user data.