Redundant data storage schemes for multi-die memory systems

• US 8,677,203 B1
• Filed: 01/10/2011
• Issued: 03/18/2014
• Est. Priority Date: 01/11/2010
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Shalvi, Ofir, Sommer, Naftali, Perlmutter, Uri, Vlaiko, Julian, Neerman, Moshe
• Primary Examiner(s): MCMAHON, DANIEL F
• Application Number:
  US12/987,175
• Time in Patent Office: 1,163 Days
• Field of Search: None
• US Class Current: 714/747
• CPC Class Codes: G06F 11/1016 Error in accessing a memory location, i.e. addressing error
• CPC Class Codes: G06F 11/1068 in sector programmable memories, e.g. flash disk G06F11/1072 takes precedence
• CPC Class Codes: G06F 11/108 Parity data distribution in semiconductor storages, e.g. in SSD
• CPC Class Codes: G06F 11/14 Error detection or correction of the data by redundancy in operation G06F11/16 takes precedence
• CPC Class Codes: G06F 11/1666 where the redundant component is memory or memory area
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 2212/7208 Multiple device management, e.g. distributing data over multiple flash devices
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0655 Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays
• CPC Class Codes: G11C 29/52 Protection of memory contents; Detection of errors in memory contents

Abstract

A method for data storage includes storing data in a memory that includes one or more memory units, each memory unit including memory blocks. The stored data is compacted by copying at least a portion of the data from a first memory block to a second memory block, and subsequently erasing the first memory block. Upon detecting a failure in the second memory block after copying the portion of the data and before erasure of the first memory block, the portion of the data is recovered by reading the portion from the first memory block.

Claims

1. A method for data storage, comprising:

storing data in a memory that includes one or more memory units, wherein each memory unit includes a plurality of memory blocks;

compacting the stored data by reading at least a portion of the stored data from a first memory block and storing the read data in a second memory block, and subsequently erasing the first memory block; and

upon detecting a failure in the second memory block after storing the read data in the second memory block and before erasure of the first memory block, recovering the portion of the stored data by re-reading the portion of the stored data from the first memory block.

2. The method according to claim 1, wherein compacting the stored data comprises delaying erasure of the first memory block.

3. The method according to claim 1, wherein the memory includes at least first and second memory units, and wherein the first memory block is located in the first memory unit and the second memory block is located in the second memory unit.

4. A method for data storage, comprising:

accepting data for storage in a memory that includes multiple memory units;

encoding the data with an Error Correction Code (ECC), to produce an ECC code word, wherein the ECC code word includes multiple bits;

storing subsets of the multiple bits of the ECC code word in respective memory units of the multiple memory units; and

upon a failure in a given memory unit, decoding the ECC code word using the multiple bits of the ECC code word excluding bits of the ECC code word stored in the given memory unit.

5. The method according to claim 4, wherein decoding the code word comprises associating the multiple bits with respective soft metrics, and decoding the ECC code word responsively to the soft metrics.

6. The method according to claim 4, wherein decoding the ECC code word comprises marking a subset of the multiple bits that is stored in the given memory unit as erasures, and decoding the code word responsively to the erasures.

7. The method according to claim 4, wherein storing the subsets comprises assigning the subsets of the multiple bits respective logical addresses that are mapped to physical storage locations in the respective memory units.

8. The method according to claim 7, wherein the ECC code word comprises data and redundancy information, and comprising selecting an additional set of the respective logical addresses for storing additional data and additional redundancy information, such that the respective logical addresses that are assigned for storing the additional redundancy information in the additional set are mapped to a different subset of the memory units, in comparison with the respective logical addresses that are assigned for storing the redundancy information in the ECC code word.

9. The method according to claim 7, wherein the respective memory units are assigned respective, non-overlapping ranges of the respective logical addresses.

10. The method according to claim 7, wherein accepting the data comprises receiving the data from a host, and wherein assigning the respective logical addresses comprises allocating the respective logical addresses from a range of the respective logical addresses that is not accessible to the host.

11. The method according to claim 4, and comprising reserving at least one spare memory unit in addition to the multiple memory units, and replacing the given memory unit with the at least one spare memory unit.

12. The method according to claim 11, and comprising temporarily using the at least one spare memory unit for improving performance of data storage in the multiple memory units.

13. The method according to claim 4, wherein the multiple memory units are partitioned into two or more groups, wherein each group of the two or more groups is associated with a respective processor of two or more processors, and wherein storing the subsets comprises distributing storage of the subsets among the multiple processors.

14. A data storage apparatus, comprising:

an interface, which is configured to communicate with a memory that includes one or more memory units, wherein each memory unit includes a plurality of memory blocks; and

a processor, which is configured to store data in the memory, to compact the stored data by reading at least a portion of the data from a first memory block and storing the read data to a second memory block and subsequently erasing the first memory block, and, upon detecting a failure in the second memory block after storing the read data in the second memory block and before erasure of the first memory block, to recover the portion of the data by re-reading the portion of the stored data from the first memory block.

15. The apparatus according to claim 14, wherein the processor is configured to delay erasure of the first memory block.

16. The apparatus according to claim 14, wherein the memory includes at least first and second memory units, and wherein the first memory block is located in the first memory unit and the second memory block is located in the second memory unit.

17. A data storage apparatus, comprising:

an interface, which is configured to communicate with a memory that includes multiple memory units; and

a processor, which is configured to accept data for storage in the memory, to encode the data with an Error Correction Code (ECC) so as to produce an ECC code word comprising multiple bits, to store respective subsets of the multiple bits of the code word in the multiple memory units, and, upon a failure in a given memory unit, to decode the ECC code word using the multiple bits that are stored in the memory units other than the given memory unit.

18. The apparatus according to claim 17, wherein the processor is configured to associate the multiple bits with respective soft metrics, and to decode the ECC code word responsively to the soft metrics.

19. The apparatus according to claim 17, wherein the processor is configured to mark a subset of the multiple bits that is stored in the given memory unit as erasures, and to decode the ECC code word responsively to the erasures.

20. The apparatus according to claim 17, wherein the processor is configured to assign the subsets respective logical addresses that are mapped to physical storage locations in the respective memory units.

21. The apparatus according to claim 20, wherein the ECC code word comprises data and redundancy information, and wherein the processor is configured to select an additional set of the respective logical addresses for storing additional data and additional redundancy information, such that the respective logical addresses that are assigned for storing the additional redundancy information in the additional set are mapped to a different subset of the memory units, in comparison with the respective logical addresses that are assigned for storing the redundancy information in the ECC code word.

22. The apparatus according to claim 20, wherein the respective memory units are assigned respective, non-overlapping ranges of the respective logical addresses.

23. The apparatus according to claim 20, wherein the interface is configured to receive the data from a host, and wherein the processor is configured to assign the respective logical addresses from a range of the respective logical addresses that is not accessible to the host.

24. The apparatus according to claim 17, wherein the processor is configured to reserve at least one spare memory unit in addition to the multiple memory units, and to replace the given memory unit with the at least one spare memory unit.

25. The apparatus according to claim 24, wherein the processor is configured to temporarily use the at least one spare memory unit for improving performance of data storage in the multiple memory units.

26. The apparatus according to claim 17, wherein the multiple memory units are partitioned into two or more groups, wherein each group of the two or more groups is associated with a respective processor unit of two or more processing units, and wherein the processor is configured to distribute storage of the subsets among the multiple processors.