Data Consolidation and Garbage Collection in Direct Data File Storage Memories

• US 20070033376A1
• Filed: 08/02/2006
• Published: 02/08/2007
• Est. Priority Date: 08/03/2005
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Corporation (Western Digital Corporation)
• Inventors: Wright, Barry, Sinclair, Alan
• Granted Patent: US 7,610,437 B2
• Time in Patent Office: Days
• US Class Current: 711/203
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 16/1847 specifically adapted to static storage, e.g. adapted to flash memory or SSD
• CPC Class Codes: G06F 2212/7202 Allocation control and policies
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 3/0605 by facilitating the interaction with a user or administrator
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0643 Management of files
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G11C 16/0483 comprising cells having several storage transistors connected in series
• CPC Class Codes: G11C 16/102 External programming circuits, e.g. EPROM programmers; In-circuit programming or reprogramming; EPROM emulators

Abstract

Host system data files are written directly to a large erase block flash memory system with a unique identification of each file and offsets of data within the file but without the use of any intermediate logical addresses or a virtual address space for the memory. Directory information of where the files are stored in the memory is maintained within the memory system by its controller, rather than by the host.

Claims

1. For a re-programmable non-volatile memory system having a plurality of blocks of memory cells that are individually erased prior to data being written therein and that operates with an inventory of a minimum number of erased blocks ready to have data stored therein, a method of operation, comprising:

receiving data logically addressed by unique file identifiers and offsets within the files,

storing the received data of a first file as pages within one or more of the erased blocks that only partially fill one of the erased blocks, thereby leaving erased data storage capacity within the partially filled block, and

postponing consolidating valid data from the partially filled block with valid data of a second file into another one of the erased blocks until at least the inventory of the number of erased blocks is deemed insufficient to maintain the minimum number.

2. The method of claim 1, additionally comprising, in response to a need to provide another erased block, consolidating valid data from the first file and second file into another one of the erased blocks and thereafter erasing at least the partially filled block, thereby to add another erased block to the inventory.

3. The method of claim 1, additionally comprising, in response to receiving a command to delete the first file, mark all the data of the first file in at least the partially filled block as obsolete, thereby eliminating any valid data from the first file in at least the partially filled block, whereby no consolidation of data of the first file in the partially filled block is necessary.

4. The method of claim 1, additionally comprising maintaining a plurality of records that identify groups of variable amounts of data making up the first file, wherein the individual groups have both contiguous logical offset addresses and contiguous physical addresses of data within the group.

5. A method of operation of a re-programmable non-volatile memory system having a plurality of blocks of memory cells that are individually erased prior to data being written therein and which receives data having logical addresses of unique file identifiers and offsets within the individual files, wherein:

valid data from a first group of two or more blocks partially programmed with data of two or more files are occasionally consolidated into another block,

blocks containing valid data from a second group of one or more blocks that also contain obsolete data are occasionally garbage collected,

only one of the data consolidation or garbage collection is carried out at one time, and

priority is given to garbage collection over data consolidation.

6. A method of operation of a re-programmable non-volatile memory system having a plurality of blocks of memory cells that are individually erased prior to data being written therein and which receives data having logical addresses of unique file identifiers and offsets within the individual files, wherein:

received data of individual files are programmed into one or more erased blocks in a manner that data of at least a first file may only partially fill a first block and thereby leave erased storage capacity in the first block,

subsequent operations on data within the memory system cause at least some of the data of a second file stored in a second block to become obsolete,

in response to at least some of the data of the second file in the second block becoming obsolete, any remaining valid data in the second block are copied into a third block,

in response to the first block having erased storage capacity, valid data are copied from the first block into a fourth block, and

priority is given to the above-recited copying of valid data from the second block into the third block over the above-recited copying of valid data from the first block into the fourth block.

7. The method of claim 6, wherein at least one of the third or fourth blocks is an erased block into which the copied data are written.

8. The method of claim 6, wherein at least one of the third or fourth blocks contains data of a third file at the time the copied data are written therein.

9. The method of claim 6, additionally wherein a plurality of records that identify groups of variable amounts of data making up the individual files are maintained, wherein the groups individually have both contiguous logical offset addresses and contiguous physical addresses of data within the group.