Systems, methods, and devices for multi-dimensional flash RAID data protection

• US 9,003,264 B1
• Filed: 03/15/2013
• Issued: 04/07/2015
• Est. Priority Date: 12/31/2012
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Enterprise IP LLC (Western Digital Corporation)
• Inventors: Prins, Douglas A.
• Primary Examiner(s): DeCady, Albert
• Assistant Examiner(s): Ahmed, Enam
• Application Number:
  US13/831,707
• Time in Patent Office: 753 Days
• Field of Search: 714/773
• US Class Current: 714/773
• CPC Class Codes: G06F 11/10 Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
• 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/108 Parity data distribution in semiconductor storages, e.g. in SSD

Abstract

A method for recovering corrupted data stored in persistent memory provides protection against, at least, loss of a single block, loss of a single page, as well as a high number of random retention errors. In some implementations, each data element in a quadrant of the persistent memory is protected by a row check word and a diagonal check word. Each row check word includes a value resulting from a mathematical operation performed on a respective row set comprising a set of data elements and each diagonal check word in the quadrant includes a value resulting from a mathematical operation performed on a respective diagonal set comprising a set of data elements distributed over the banks, blocks and pages in the quadrant so that failure of any one page, block or die in the quadrant does not result in the loss of any data in the quadrant.

Claims

1. A persistent memory device, comprising:

memory comprising a plurality of banks of nonvolatile memory cells, each bank comprising one or more die, each die comprising a memory array having a plurality of memory blocks including even blocks and odd blocks, each memory block having a plurality of pages, including even pages and odd pages, and storing a plurality of data elements;

wherein the one or more die of each bank are distinct from the one or more die of every other bank of the plurality of banks;

wherein;

the memory is logically divided into a set of quadrants, each quadrant including, for every bank in the plurality of banks, one or more even blocks and one or more odd blocks, and for each block in the quadrant, one or more even pages and one or more odd pages;

each quadrant stores a set of row check words and a set of diagonal check words;

each data element in the quadrant corresponds to a single row check word of the set of row check words and a single diagonal check word of the set of diagonal check words;

each row check word in the quadrant comprising a value encoded with a result of a mathematical operation performed on a respective row set comprising a set of data elements corresponding to the row check word, wherein;

no more than two data elements in the row set are stored in the same bank of the plurality of banks;

a first portion of the data elements in the row set are stored in a first set of blocks, the first set of blocks comprising entirely even or entirely odd blocks;

a first complementary portion of the data elements in the row set are stored in a second set of blocks, the second set of blocks comprising a set of blocks complementary to the first set of blocks and comprising entirely odd blocks or entirely even blocks;

a second portion of the data elements in the row set are stored in a first set of pages, the first set of pages comprising entirely even pages or entirely odd pages; and

a second complementary portion of the data elements in the row set are stored in a second set of pages, the second set of pages comprising a set of pages complementary to the first set of pages and comprising entirely odd pages or entirely even pages;

each diagonal check word in the quadrant comprising a value encoded with a result of a mathematical operation performed on a respective diagonal set comprising a set of data elements corresponding to the diagonal check word;

no more than two data elements in the diagonal set are stored in the same bank of the plurality of banks;

a first portion of the data elements in the diagonal set are stored in the first set of blocks;

a first complementary portion of the data elements in the diagonal set are stored in the second set of blocks; and

all the data elements in the diagonal set are stored in a single set of pages, the single set of pages comprising only pages in the first set of pages or only pages in the second set of pages.

2. The persistent memory device of claim 1, wherein the even blocks in the quadrant comprise blocks in the quadrant satisfying predefined block designation criteria, and the odd blocks in the quadrant comprise blocks in the quadrant not satisfying the predefined block designation criteria.

3. The persistent memory device of claim 2, wherein the predefined block designation criteria are met for a respective block when a predefined respective bit in a block address for the respective block is equal to a predetermined value.

4. The persistent memory device of claim 3, wherein the predefined respective bit is one of the group consisting of:

a most significant bit and a least significant bit.

5. The persistent memory device of claim 2, wherein each block has an assigned block number and the predefined block designation criteria comprises blocks whose block number modulo two has a first predefined value.

6. The persistent memory device of claim 1, wherein the even pages in the quadrant comprise pages in the quadrant satisfying predefined page designation criteria, and the odd pages in the quadrant comprise pages in the quadrant not satisfying the predefined page designation criteria.

7. The persistent memory device of claim 6, wherein the predefined page designation criteria are met for a respective page when a predefined respective bit in a page address for the respective page is equal to a predetermined value.

8. The persistent memory device of claim 7, wherein the predefined respective bit is one of the group consisting of:

a most significant bit and a least significant bit.

9. The persistent memory device of claim 6, wherein each page has an assigned page number and the predefined page designation criteria comprises pages whose page number modulo two has a first predefined value.

10. The persistent memory device of claim 1, wherein each of the data elements comprises a codeword that includes both data and parity elements.

11. The persistent memory device of claim 1, wherein:

each row set corresponding to a respective row check word includes one or more diagonal check words from the set of diagonal check words.

12. The persistent memory device of claim 1, wherein:

each diagonal set corresponding to a respective diagonal check word includes one or more row check words from the set of row check words.

13. The persistent memory device of claim 1, wherein the mathematical operation comprises an XOR operation.

14. The persistent memory device of claim 1, wherein the plurality of memory banks includes first level parity information for each data element stored in the plurality of memory banks, the first level parity information for correcting errors, if any, in respective data elements using a first level data correction methodology, and wherein the row check words and diagonal check words are for correcting errors in respective data elements using a second level data correction methodology.

15. The persistent memory device of claim 14, wherein:

wherein every data element stored in the memory is recoverable using the first level data correction methodology, the second level data correction methodology or a combination thereof, unless;

the memory stores at least four data elements, comprising first, second, third and fourth data elements, that are not correctable using the first level data correction methodology,

the first data element and second data element are members of the set of data elements corresponding to a first diagonal check word;

the first data element and third data element are members of the set of data elements corresponding to a first row check word;

the third data element and fourth data element are members of the set of data elements corresponding to a second diagonal check word distinct from the first diagonal check word; and

the second data element and fourth data elements are members of the set of data elements corresponding to a second row check word distinct from the first row check word.

16. The persistent memory device of claim 15, wherein

the first data element and second data element are both stored in the even blocks, and the third data element and fourth data element are both stored in the odd blocks;

and

the first data element and second data element are both stored in a third set of pages comprising entirely even pages or entirely odd pages, and the third data element and the fourth data element are stored in a fourth set of pages comprising a set of pages complementary to the third set of pages and comprising entirely odd pages or entirely even pages.

17. The persistent memory device of claim 1, wherein no more than one data element in the row set is stored in the same bank of the plurality of banks.

18. The persistent memory device of claim 17, wherein no more than one data element in the diagonal set is stored in the same bank of the plurality of banks.

19. The persistent memory device of claim 1, wherein each die has an equal numbers of even blocks and odd blocks, and each memory block has equal numbers of even pages and odd pages.

20. A method of storing data in and recovering data from a persistent memory device, comprising:

storing data elements in memory comprising a plurality of banks of nonvolatile memory cells, each bank comprising one or more die, each die comprising a memory array having a plurality of memory blocks including even blocks and odd blocks, each memory block having a plurality of pages, including even pages and odd pages;

wherein the one or more die of each bank are distinct from the one or more die of every other bank of the plurality of banks;

wherein, the memory is logically divided into a set of quadrants, each quadrant including, for every bank in the plurality of banks, one or more even blocks and one or more odd blocks, and for each block in the quadrant, one or more even pages and one or more odd pages;

storing in each quadrant a set of row check words and a set of diagonal check words;

each row check word in the quadrant comprising a value encoded with a result of a mathematical operation performed on a respective row set comprising a set of data elements corresponding to the row check word;

each diagonal check word in the quadrant comprising a value encoded with a result of a mathematical operation performed on a respective diagonal set comprising a set of data elements corresponding to the diagonal check word;

reading a respective data element from a respective quadrant of the memory, and

in accordance with a determination that the respective data element is not recoverable using a first level data correction methodology, recovering the respective data element using a respective check word, comprising a row check word of the set of row check words stored in the respective quadrant of the memory or a diagonal check word of the set of diagonal check words stored in the respective quadrant of the memory, by performing a complementary mathematical operation on the respective check word with all data elements, excluding the respective data element, of a set of data elements corresponding to the respective check word;

wherein;

no more than two data elements in the row set for a respective row check word are stored in the same bank of the plurality of banks;

a first portion of the data elements in the row set are stored in a first set of blocks, the first set of blocks comprising entirely even or entirely odd blocks;

a first complementary portion of the data elements in the row set are stored in a second set of blocks, the second set of blocks comprising a set of blocks complementary to the first set of blocks and comprising entirely odd blocks or entirely even blocks, wherein;

a second portion of the data elements in the row set are stored in a first set of pages, the first set of pages comprising entirely even pages or entirely odd pages;

a second complementary portion of the data elements in the row set are stored in a second set of pages, the second set of pages comprising a set of pages complementary to the first set of pages and comprising entirely odd pages or entirely even pages;

no more than two data elements in the diagonal set for a respective diagonal check word are stored in the same bank of the plurality of banks;

a first portion of the data elements in the diagonal set are stored in the first set of blocks;

a first complementary portion of the data elements in the diagonal set are stored in the second set of blocks; and

all the data elements in the diagonal set are stored in a single set of pages, the single set of pages comprising only pages in the first set of pages or only pages in the second set of pages.

21. The method of claim 20, wherein the even blocks in the quadrant comprise blocks in the quadrant satisfying predefined block designation criteria, and the odd blocks in the quadrant comprise blocks in the quadrant not satisfying the predefined block designation criteria.

22. A persistent memory device, comprising:

memory comprising a plurality of banks of nonvolatile memory cells, each bank comprising one or more die, each die comprising a memory array having a plurality of memory blocks including even blocks and odd blocks, each memory block having a plurality of pages, including even pages and odd pages, and storing a plurality of data elements;

wherein the one or more die of each bank are distinct from the one or more die of every other bank of the plurality of banks;

wherein;

the memory is logically divided into a set of quadrants, each quadrant including, for every bank in the plurality of banks, one or more even blocks and one or more odd blocks, and for each block in the quadrant, one or more even pages and one or more odd pages;

each quadrant stores a set of row check words and a set of diagonal check words;

each data element in the quadrant corresponds to a single row check word of the set of row check words and a single diagonal check word of the set of diagonal check words;

each row check word in the quadrant comprising a value encoded with a result of a mathematical operation performed on a respective row set comprising a set of data elements corresponding to the row check word, wherein;

no more than two data elements in the row set are stored in the same bank of the plurality of banks;

a first portion of the data elements in the row set are stored in a first set of blocks, the first set of blocks comprising entirely even or entirely odd blocks; and

a first complementary portion of the data elements in the row set are stored in a second set of blocks, the second set of blocks comprising a set of blocks complementary to the first set of blocks and comprising entirely odd blocks or entirely even blocks;

each diagonal check word in the quadrant comprising a value encoded with a result of a mathematical operation performed on a respective diagonal set comprising a set of data elements corresponding to the diagonal check word;

no more than two data elements in the diagonal set are stored in the same bank of the plurality of banks;

a first portion of the data elements in the diagonal set are stored in the first set of blocks;

a first complementary portion of the data elements in the diagonal set are stored in the second set of blocks;

a second portion of the data elements in the diagonal set are stored in a first set of pages, the first set of pages comprising entirely even pages or entirely odd pages; and

a second complementary portion of the data elements in the diagonal set are stored in a second set of pages, the second set of pages comprising a set of pages complementary to the first set of pages and comprising entirely odd pages or entirely even pages;

wherein all the data elements in the row set are stored in a single set of pages, the single set of pages comprising only pages in the first set of pages or only pages in the second set of pages.

23. The persistent memory device of claim 22, wherein the even blocks in the quadrant comprise blocks in the quadrant satisfying predefined block designation criteria, and the odd blocks in the quadrant comprise blocks in the quadrant not satisfying the predefined block designation criteria.

24. The persistent memory device of claim 23, wherein the predefined block designation criteria are met for a respective block when a predefined respective bit in a block address for the respective block is equal to a predetermined value.