Redundant data storage in multi-die memory systems

• US 8,572,311 B1
• Filed: 01/10/2011
• Issued: 10/29/2013
• 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, Maislos, Ariel, Schwartz, Yair
• Primary Examiner(s): NGUYEN, HIEP T
• Application Number:
  US12/987,174
• Time in Patent Office: 1,023 Days
• Field of Search: None
• US Class Current: 711/103
• 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, in a memory that includes at least N memory units, each memory unit including memory blocks, defining superblocks, each superblock including a respective set of N of the memory blocks that are allocated respectively in N different ones of the memory units, such that compaction of all the memory blocks in a given superblock is performed without any intervening programming operation in the given superblock. Data is stored in the memory by computing redundancy information for a selected portion of the data, and storing the selected portion and the redundancy information in the N memory blocks of a selected superblock.

Claims

1. A method for data storage, comprising:

in a memory that includes at least N memory units, each memory unit comprising memory blocks, defining superblocks, each superblock comprising a respective set of N of the memory blocks that are allocated respectively in N different ones of the memory units, such that compaction of all the memory blocks in a given superblock is performed without any intervening programming operation in the given superblock;

storing data in the memory by computing redundancy information for a selected portion of the data, and storing the selected portion and the redundancy information in the N memory blocks of a selected superblock; and

reading data from a given superblock by issuing read commands to the set of N memory blocks within a given superblock without waiting for data to arrive from a given memory block before issuing a subsequent read command to a next memory block, wherein reading the data from a given superblock further comprises;

receiving data from N−

1 memory blocks; and

using the redundancy information to reconstruct the data unless the redundancy information is in the Nth memory block to arrive.

2. The method according to claim 1, wherein erasure of all the memory blocks in the given superblock is performed without any intervening programming operation in the given superblock.

3. The method according to claim 1, wherein storing the data comprises storing the selected portion in K memory blocks of the selected superblock, 1≦

K<

N, and storing the redundancy information in N−

K remaining memory blocks of the selected superblock.

4. The method according to claim 1, wherein storing the data comprises programming the portions of the data and the redundancy information into N pages belonging respectively to the memory blocks of the selected superblock, without any intervening programming operation.

5. The method according to claim 1, and comprising, upon a failure in a given memory unit from among the N memory units, recovering the data using at least some of the data and the redundancy information that is stored in the memory units other than the given memory unit.

6. The method according to claim 1, and comprising compacting the data stored in a source superblock of the memory by copying valid data from partially-valid memory blocks in the source superblock to a destination superblock and subsequently erasing the source superblock.

7. The method according to claim 6, wherein copying the valid data comprises moving the valid data from first blocks of the source superblock to respective second blocks in the destination superblock, such that each second block belongs to the same memory unit as the respective first block.

8. The method according to claim 7, and comprising running a background process that copies parts of the data between different ones of the memory units.

9. The method according to claim 6, wherein compacting the data comprises, upon detecting that the source superblock no longer contains any valid data but the destination superblock is not full, selecting an additional source superblock and copying additional valid data from the additional source superblock to the destination superblock.

10. The method according to claim 6, wherein compacting the data comprises selecting a given superblock for compaction based on a distribution of invalid data in the superblocks.

11. The method according to claim 10, wherein selecting the given superblock comprises choosing the given superblock having a highest amount of the invalid data among the superblocks to serve as the source superblock.

12. The method according to claim 1, wherein defining the superblock comprises classifying input data to rarely-updated data and frequently-updated data, assigning first superblocks for storing the rarely-updated data and assigning second superblocks, different from the first superblocks, for storing the frequently-updated data.

13. The method according to claim 1, and comprising reserving at least one spare memory unit in addition to the N memory units, and replacing a failed memory unit from among the N memory units with the spare memory unit.

14. The method according to claim 13, and comprising temporarily using the spare memory unit for improving performance of data storage in the N memory units.

15. The method according to claim 1, wherein the memory units are partitioned into multiple groups that are associated with respective multiple processors, and wherein storing the data comprises distributing computing of the redundancy information among the multiple processors.

16. The method according to claim 1, and comprising, in response to a failure in a memory block of a given superblock, redefining the given superblock to include only the blocks other than the memory block having the failure, and storing subsequent data in the redefined superblock.

17. A method for data storage, comprising:

in a memory controller that accepts data items from a host for storage in multiple memory units, defining a mapping between logical addresses assigned by the host and respective physical storage locations in the memory units;

reporting information indicative of the mapping from the memory controller to the host;

in the host, computing redundancy information for the data items, and assigning respective first logical addresses to the data items and second logical addresses to the redundancy information responsively to the reported information indicative of the mapping; and

storing the data items and the redundancy information by the memory controller in the physical storage locations that correspond to the respective first and second logical addresses assigned by the host; and

reserving a subset of the memory units for use as one or more spare memory units to replace one more memory units in response to determining a memory unit has failed and using the one or more spare memory units to improve data storage performance in the memory units until the one or more spare memory units is used as a replacement memory unit.

18. The method according to claim 17, wherein assigning the first and second logical addresses in the host comprises causing the data items and the redundancy information to be stored in different ones of the memory units.

19. The method according to claim 17, wherein reporting the information comprises reporting respective ranges of the logical addresses that are mapped to the memory units according to the mapping.

20. The method according to claim 17, wherein reporting the information comprises, responsively to modifying the mapping in the memory controller, reporting to the host updated information that is indicative of the modified mapping.

21. A data storage apparatus, comprising:

an interface, which is configured to communicate with a memory that includes at least N memory units, each memory unit including memory blocks; and

a processor, which is configured to;

define superblocks, each superblock comprising a respective set of N of the memory blocks that are allocated respectively in N different ones of the memory units, such that compaction of all the memory blocks in a given superblock is performed without any intervening programming operation in the given superblock;

store data in the memory by computing redundancy information for a selected portion of the data, and storing the selected portion and the redundancy information in the N memory blocks of a selected superblock; and

read data from a given superblock by issuing read commands to the set of N memory blocks within a given superblock without waiting for data to arrive from a given memory block before issuing a subsequent read command to a next memory block, wherein reading the data from a given superblock further comprises;

receiving data from N−

1 memory blocks; and

using the redundancy information to reconstruct the data unless the redundancy information is in the Nth memory block to arrive.

22. The apparatus according to claim 21, wherein the processor is configured to erase all the memory blocks in the given superblock without any intervening programming operation in the given superblock.

23. The apparatus according to claim 21, wherein the processor is configured to store the selected portion in K memory blocks of the selected superblock, 1K<

N, and to store the redundancy information in N−

K remaining memory blocks of the selected superblock.

24. The apparatus according to claim 21, wherein the processor is configured to program the portions of the data and the redundancy information into N pages belonging respectively to the memory blocks of the selected superblock, without any intervening programming operation.

25. The apparatus according to claim 21, wherein, upon a failure in a given memory unit from among the N memory units, the processor is configured to recover the data using at least some of the data and the redundancy information that is stored in the memory units other than the given memory unit.

26. The apparatus according to claim 21, wherein the processor is configured to compact the data stored in a source superblock of the memory by copying valid data from partially-valid memory blocks in the source superblock to a destination superblock and subsequently erasing the source superblock.

27. The apparatus according to claim 26, wherein the processor is configured to copy the valid data from first blocks of the source superblock to respective second blocks in the destination superblock, such that each second block belongs to the same memory unit as the respective first block.

28. The apparatus according to claim 27, wherein the processor is configured to run a background process that copies parts of the data between different ones of the memory units.

29. The apparatus according to claim 26, wherein, upon detecting that the source superblock no longer contains any valid data but the destination superblock is not full, the processor is configured to select an additional source superblock and to copy additional valid data from the additional source superblock to the destination superblock.

30. The apparatus according to claim 26, wherein the processor is configured to select a given superblock for compaction based on a distribution of invalid data in the superblocks.

31. The apparatus according to claim 30, wherein the processor is configured to choose the given superblock having a highest amount of the invalid data among the superblocks to serve as the source superblock.

32. The apparatus according to claim 21, wherein the processor is configured to classify input data to rarely-updated data and frequently-updated data, to assign first superblocks for storing the rarely-updated data and to assign second superblocks, different from the first superblocks, for storing the frequently-updated data.

33. The apparatus according to claim 21, wherein the processor is configured to reserve at least one spare memory unit in addition to the N memory units, and to replace a failed memory unit from among the N memory units with the spare memory unit.

34. The apparatus according to claim 33, wherein the processor is configured to temporarily use the spare memory unit for improving performance of data storage in the N memory units.

35. The apparatus according to claim 21, wherein the memory units are partitioned into multiple groups, and wherein the processor comprises multiple processors that compute the redundancy information in the respective groups.

36. The apparatus according to claim 21, wherein the processor is configured, in response to a failure in a memory block of a given superblock, to redefine the given superblock to include only the blocks other than the memory block having the failure, and to store subsequent data in the redefined superblock.

37. A memory controller, comprising:

an interface for communicating with a host; and

a processor, which is configured to;

accept from the host via the interface data items for storage in multiple memory units;

define a mapping between logical addresses assigned by the host and respective physical storage locations in the memory units;

report information indicative of the mapping from the memory controller to the host, so as to cause the host to compute redundancy information for the data items and assign respective first logical addresses to the data items and second logical addresses to the redundancy information responsively to the reported information indicative of the mapping;

store the data items and the redundancy information accepted from the host in the physical storage locations that correspond to the respective first and second logical addresses assigned by the host; and

reserve a subset of the memory units for use as one or more spare memory units to replace one more memory units in response to determining a memory unit has failed and using the one or more spare memory units to improve data storage performance in the memory units until the one or more spare memory units are used as a replacement memory units.

38. The apparatus according to claim 37, wherein the first and second logical addresses assigned by the host cause the data items and the redundancy information to be stored in different ones of the memory units.

39. The apparatus according to claim 37, wherein the processor is configured to report respective ranges of the logical addresses that are mapped to the memory units according to the mapping.

40. The apparatus according to claim 37, wherein the processor is configured to modify the mapping, and to reporting to the host updated information that is indicative of the modified mapping.

41. A method for data storage, comprising:

in a memory that includes at least N memory units that are partitioned into memory blocks, grouping input data into sets of N logical pages, each set containing a respective portion of the data and redundancy information that is computed over the portion;

storing each set in the memory such that the N logical pages in the set are stored in N different memory units;

reading data from a given superblock by issuing read commands to the set of N memory blocks within a given superblock without waiting for data to arrive from a given memory block before issuing a subsequent read command to a next memory block, wherein reading the data from a given superblock further comprises;

receiving data from N−

1 memory blocks; and

using the redundancy information to reconstruct the data unless the redundancy information is in the Nth memory block to arrive; and

compacting a selected memory block by reading at least one invalid page from the selected memory block, reading the redundancy information of the respective set to which the invalid page belongs, updating the read redundancy information based on the read invalid page and on new data, and storing the updated redundancy information and the new data in the memory.

42. A data storage apparatus, comprising:

an interface, which is configured to communicate with a memory that includes at least N memory units that are partitioned into memory blocks; and

a processor, which is configured to;

group input data into sets of N logical pages, each set containing a respective portion of the data and redundancy information that is computed over the portion;

store each set in the memory such that the N logical pages in the set are stored in N different memory units;

read data from a given superblock by issuing read commands to the set of N memory blocks within a given superblock without waiting for data to arrive from a given memory block before issuing a subsequent read command to a next memory block, wherein reading the data from a given superblock further comprises;

receiving data from N−

1 memory blocks; and

using the redundancy information to reconstruct the data unless the redundancy information is in the Nth memory block to arrive; and

compact a selected memory block by reading at least one invalid page from the selected memory block, reading the redundancy information of the respective set to which the invalid page belongs, updating the read redundancy information based on the read invalid page and on new data, and storing the updated redundancy information and the new data in the memory.