Fractional redundant array of silicon independent elements
View Patent ↗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).
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 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 as an erasure-correcting code protecting all of the pages of the group, and the redundancy includes a first portion computed based on a parity coding and a second portion computed based on a weighted-sum coding.
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 configured to generate redundancy information protecting data corresponding to a plurality of pages, the redundancy information including a first portion computed based on a parity coding and a second portion computed based on a weighted-sum coding;
a storage controller configured to store the redundancy information into at least one page; and
wherein a failure of at least one of the blocks is correctable based on the redundancy information.
20. The system of claim 19 , wherein the controller is further configured to store the redundancy information to a number of pages equal to a number of blocks.
21. The system of claim 19 , wherein the parity coding is computed based on a logical XOR of all corresponding bytes of selected pages to be protected by the redundancy information.
22. The system of claim 19 , wherein the weighted-sum coding is computed based on each page in a group of pages to be protected by the redundancy information being assigned a unique non-zero index value as a weight, where each index value corresponds to a non-zero element in a finite field.