# US 8,572,311 B1 · Redundant data storage in multi-die memory systems

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,572,311 B1
- Document ID: US8572311B1
- Status: Granted
- Kind: B1
- Application number: 12/987,174
- Filed: 2011-01-10
- Granted: 2013-10-29
- Earliest claimed: 2010-01-11
- Assignees: Apple Inc.
- Applicants: Ofir Shalvi; Naftali Sommer; Uri Perlmutter; Julian Vlaiko; Moshe Neerman; Yair Schwartz; Ariel Maislos
- Inventors: Ofir Shalvi; Naftali Sommer; Uri Perlmutter; Julian Vlaiko; Moshe Neerman; Yair Schwartz; Ariel Maislos
- Web page: https://patentgrep.com/patent/US8572311B1

## CPC

- G06F 11/1068: {in sector programmable memories, e.g. flash disk (G06F11/1072 takes precedence)}
- G06F 3/0619: {in relation to data integrity, e.g. data losses, bit errors}
- G06F 3/064: {Management of blocks}
- G06F 3/065: {Replication mechanisms}
- G06F 3/0655: {Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices}
- G06F 3/0688: {Non-volatile semiconductor memory arrays}
- G06F 11/1016: {Error in accessing a memory location, i.e. addressing error}
- G06F 11/108: {Parity data distribution in semiconductor storages, e.g. in SSD}
- G06F 11/14: Error detection or correction of the data by redundancy in operations (error detection or correction of the data by redundancy in hardware G06F11/16)
- G06F 11/1666: {where the redundant component is memory or memory area}
- G06F 12/023: {Free address space management}
- G06F 12/0246: {in block erasable memory, e.g. flash memory}
- G11C 29/52: Protection of memory contents; Detection of errors in memory contents
- G06F 2212/7205: Cleaning, compaction, garbage collection, erase control
- G06F 2212/7208: Multiple device management, e.g. distributing data over multiple flash devices
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G11C: STATIC STORES (semiconductor memory devices H10B)

## 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

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 1)

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.

### Claim 4 (depends on 1)

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.

### Claim 5 (depends on 1)

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.

### Claim 6 (depends on 1)

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.

### Claim 7 (depends on 6)

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.

### Claim 8 (depends on 7)

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.

### Claim 9 (depends on 6)

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.

### Claim 10 (depends on 6)

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.

### Claim 11 (depends on 10)

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.

### Claim 12 (depends on 1)

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.

### Claim 13 (depends on 1)

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.

### Claim 14 (depends on 13)

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.

### Claim 15 (depends on 1)

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.

### Claim 16 (depends on 1)

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.

### Claim 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.

### Claim 18 (depends on 17)

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.

### Claim 19 (depends on 17)

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.

### Claim 20 (depends on 17)

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.

### Claim 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.

### Claim 22 (depends on 21)

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.

### Claim 23 (depends on 21)

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.

### Claim 24 (depends on 21)

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.

### Claim 25 (depends on 21)

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.

### Claim 26 (depends on 21)

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.

### Claim 27 (depends on 26)

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.

### Claim 28 (depends on 27)

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.

### Claim 29 (depends on 26)

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.

### Claim 30 (depends on 26)

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.

### Claim 31 (depends on 30)

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.

### Claim 32 (depends on 21)

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.

### Claim 33 (depends on 21)

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.

### Claim 34 (depends on 33)

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.

### Claim 35 (depends on 21)

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.

### Claim 36 (depends on 21)

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.

### Claim 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.

### Claim 38 (depends on 37)

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.

### Claim 39 (depends on 37)

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.

### Claim 40 (depends on 37)

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.

### Claim 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.

### Claim 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.