Fractional redundant array of silicon independent elements

Patent metadata

Field	Value
Publication number	US-9727414-B2
Application number	US-201213675874-A
Country	US
Kind code	B2
Filing date	Nov 13, 2012
Priority date	Dec 1, 2010
Publication date	Aug 8, 2017
Grant date	Aug 8, 2017

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).

First claim

What is claimed is:

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.

Assignees

• Seagate Technology Llc

Inventors

• Cohen Earl T

Classifications

• G06F11/1096

  Parity calculation or recalculation after configuration or reconfiguration of the system · CPC title

• G06F11/1068 Primary

  in sector programmable memories, e.g. flash disk (G06F11/1072 takes precedence) · CPC title

• G06F11/1076

  Parity data used in redundant arrays of independent storages, e.g. in RAID systems · CPC title