MEMORY LOGICAL DEFRAGMENTATION DURING GARBAGE COLLECTION

• US 20130166818A1
• Filed: 12/21/2011
• Published: 06/27/2013
• Est. Priority Date: 12/21/2011
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Sandisk Technologies Incorporated (Western Digital Corporation)
• Inventors: Sela, Rotem
• Granted Patent: US 8,762,627 B2
• Time in Patent Office: Days
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control

Abstract

A method and system defragments data during garbage collection. Garbage collection may be more efficient when the valid data that is aggregated together is related or logically linked. In particular, data from the same file or that is statistically correlated may be combined in the same blocks during garbage collection.

Claims

1. A method for memory storage comprising:

in a memory system having non-volatile storage and a controller in communication with the non-volatile storage, the controller is configured for;

initiating a garbage collection operation, wherein the garbage collection operation includes identifying valid data that is stored with obsolete data in a block;

determining, as part of the garbage collection operation, any correlations between the identified valid data to be copied; and

aggregating, based on the determined correlations, the identified valid data to be copied, wherein the aggregation includes combining correlated data in the block during garbage collection.

2. The method of claim 1 wherein the memory comprises non-volatile storage including a flash memory or a solid state memory.

3. The method of claim 1 wherein each block comprises a plurality of pages whose data is erasable together.

4. The method of claim 3 wherein the garbage collection further comprises:

combining obsolete data into blocks that only include obsolete data; and

erasing the blocks with only obsolete data to generate empty blocks.

5. The method of claim 1 wherein determination of any correlations between the identified valid data further comprises:

determining whether the identified valid data is part of a same file, wherein any of the valid data that is part of the same file is correlated;

utilizing, for valid data that is not determined to be correlated by being in the same file, correlation statistics for the non-correlated valid data to determine which of the identified valid data is correlated; and

determining, for valid data that is not determined to be correlated by being in the same file or from correlation statistics, logical block addresses of the non-correlated valid data and determining that the valid data whose logical block addresses are sequential or contiguous are correlated.

6. The method of claim 1 wherein any of the valid data that is part of the same file is determined to be correlated.

7. The method of claim 1 wherein the correlations are determined based on correlation statistics of when the valid data was accessed.

8. The method of claim 7 wherein the determination of correlations is first based on whether the valid data is part of a same file, and when the valid data is not part of the same file, the correlation determination is based on whether the correlation statistics suggest a correlation.

9. The method of claim 1 wherein the correlation is determined based on logical block addresses of the valid data.

10. The method of claim 9 wherein the correlation is determined when the logical block addresses of the valid data are clustered, or when logical block addresses of the valid data are sequential or contiguous.

11. The method of claim 1 further comprising:

receiving a data write command, wherein the garbage collection operation is initiated upon receiving the data write command.

12. The method of claim 11 wherein the garbage collection comprises:

generating an empty block on which new data from the data write command can be written;

aggregating existing valid data on the empty block with the new data when the existing valid data is determined to be correlated.

13. A memory system comprising:

a non-volatile storage having an array of memory blocks storing data that is associated with logical block address (LBA) addresses; and

a controller in communication with the blocks, the controller configured to;

receive a write instruction for data to be written;

identify blocks that include both valid data and obsolete data; and

aggregate valid data from the identified blocks into a new block, wherein the aggregation further comprises an identification of relationships among the valid data wherein the valid data that is related is aggregated together into the new block.

14. The memory system of claim 13 wherein the valid data that is identified as related is aggregated into the empty block.

15. The memory system of claim 13 wherein the aggregation of valid data is part of a garbage collection operation.

16. The memory system of claim 15 wherein the garbage collection comprises:

generating an empty block on which new data from the data write instruction can be written;

aggregating existing valid data on the empty block with the new data when the existing valid data is identified as related.

17. The memory system of claim 13 wherein the identification of a relationship comprises determining whether the valid data is part of a same file, wherein the valid data that is part of the same file is determined to be related.

18. The memory system of claim 13 wherein the identification of a relationship comprises:

determining whether the valid data is part of a same file, wherein the valid data that is part of the same file is related;

utilizing, for valid data that is not determined to be related by being in the same file, correlation statistics for the non-related valid data to determine which of the valid data is related; and

determining, for valid data that is not determined to be related by being in the same file or from correlation statistics, logical block addresses of the non-related valid data and determining that the valid data whose logical block addresses are sequential or contiguous are related.

19. A method for operating a memory system comprising:

in a non-volatile storage device having a controller and blocks of memory, the controller is configured for;

identifying blocks that include both valid data and obsolete data;

analyzing the blocks that include both valid data and obsolete data to identify the valid data in those blocks that is correlated;

aggregating the valid data, wherein the aggregation includes combining the valid data that is correlated.

20. The method of claim 19 further comprising:

receiving an instruction for writing new data or modifying existing data; and

initiating a garbage collection operation, wherein the garbage collection operation comprises the aggregation of the correlated valid data, and the garbage collection further comprises aggregating obsolete data into a block and erasing blocks with only obsolete data to generate empty blocks.

21. The method of claim 20 further comprising:

writing the new data from the instruction into an empty block; and

identifying valid data that correlates with the new data to be written to the empty block with the new data.