System and method for limiting fragmentation

• US 8,990,477 B2
• Filed: 04/19/2012
• Issued: 03/24/2015
• Est. Priority Date: 04/19/2012
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Sandisk Technologies Incorporated (Western Digital Corporation)
• Inventors: Parker, Liam M., Gorobets, Sergey A.
• Primary Examiner(s): Bertram, Ryan
• Application Number:
  US13/451,182
• Publication Number:
  US 20130282955A1
• Time in Patent Office: 1,069 Days
• Field of Search: 711/103, 711/154, 711/171
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2206/1004 Defragmentation
• CPC Class Codes: G06F 2212/7202 Allocation control and policies
• CPC Class Codes: G06F 2212/7204 Capacity control, e.g. partitioning, end-of-life degradation
• 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

Abstract

A method and system are disclosed for controlling the storage of data in a storage device to reduce fragmentation. The method may include a controller of a storage device receiving data for storage in non-volatile memory, proactively preventing fragmentation by only writing an amount of sequentially addressed logical groups of data into a main storage area of the storage device, such as multi-level cell (MLC) flash memory, and reactively defragmenting data previously written into the MLC memory when a trigger event is reached. The system may include a storage device with a controller configured to perform the method noted above, where the thresholds for minimum sequential writes into MLC, and for scanning the memory for fragmented data and removing fragmentation by re-writing the fragmented data already in MLC into new MLC blocks, may be fixed or variable.

Claims

1. A method of controlling storage of content on a storage device, the method comprising:

in a storage device having a controller in communication with non-volatile memory, wherein the non-volatile memory comprises a first type of non-volatile memory and a second type of non-volatile memory, the controller;

receiving data for storage in the non-volatile memory;

upon determining that a fullness of the storage device has reached a proactive defragmentation threshold, only writing sequentially addressed logical groups of received data to the second type of non-volatile memory, wherein only writing sequentially addressed logical groups of received data to the second type of non-volatile memory comprises the controller;

determining if the received data contains at least a threshold number of sequentially addressed logical groups and, when the received data is determined to contain at least the threshold number of sequentially addressed logical groups, bypassing the first type of non-volatile memory and writing the sequentially addressed logical groups of received data directly into the second type of non-volatile memory; and

when the received data is determined to contain less than the threshold number of sequentially addressed logical groups, writing the received data into the first type of non-volatile memory;

and

upon determining that the fullness of the storage device has reached a reactive defragmentation threshold automatically defragmenting data already written into the second type of non-volatile memory in response to a triggering event.

6. The method of claim 1, wherein automatically defragmenting data already written into the second type of non-volatile memory comprises the controller:

scanning the second type of non-volatile memory for sequentially numbered logical groups of data previously written in noncontiguous locations in the non-volatile memory; and

if a threshold amount of sequentially numbered logical groups previously written in noncontiguous locations are present, re-writing at least the threshold amount of sequentially numbered logical groups of data contiguously into a new block in the second type of non-volatile memory.

7. The method of claim 6, wherein scanning the second type of non-volatile memory for sequentially numbered logical groups of data previously written in noncontiguous locations in the non-volatile memory comprises the controller:

determining a number of valid logical groups stored in the second type of non-volatile memory that are associated with a particular cluster; and

determining a number of blocks in the second type of non-volatile memory containing the valid logical groups associated with the particular cluster.

8. The method of claim 7, further comprising the controller re-writing the valid logical groups of data associated with the particular cluster contiguously into a new block in the second type of non-volatile memory when both the number of valid logical groups is greater than a logical group threshold and the number of blocks in the second type of non-volatile memory containing the valid logical groups is greater than a fragmentation threshold.

9. The method of claim 1, wherein the first type of non-volatile memory comprises single level cell (SLC) flash memory and the second type of non-volatile memory comprises multi-level cell (MLC) flash memory.

10. The method of claim 6, wherein the trigger event comprises a number of fragmenting write operations exceeding a fragmenting write operation threshold.

11. The method of claim 6, wherein automatically defragmenting data already written into the second type of non-volatile memory further comprises exclusively re-writing data into the new block, wherein the new block is dedicated to only defragmented data.

12. The method of claim 6, further comprising separately writing compacted data into the new block in addition to automatically defragmenting data already written into the second type of non-volatile by re-writing data into the new block, wherein the new block is dedicated to both defragmented data and data received from a compaction process.

2. A method of controlling storage of content on a storage device, the method comprising:

in a storage device having a controller in communication with non-volatile memory, wherein the non-volatile memory comprises a first type of non-volatile memory and a second type of non-volatile memory, the controller;

receiving data for storage in the non-volatile memory;

upon determining that a fullness of the storage device has reached a proactive defragmentation threshold, only writing sequentially addressed logical groups of received data to the second type of non-volatile memory;

wherein only writing sequentially addressed logical groups of received data to the second type of non-volatile memory comprises the controller;

monitoring the first type of non-volatile memory for previously received data having the threshold number of sequentially addressed logical groups; and

writing an amount of sequentially addressed logical groups of data from the first type of non-volatile memory to the second type of non-volatile memory data when at least the threshold number of sequentially addressed logical groups is found in the first non-volatile memory type;

and

upon determining that the fullness of the storage device has reached a reactive defragmentation threshold automatically defragmenting data already written into the second type of non-volatile memory in response to a triggering event.

4. The method of claim 2, wherein the controller determines if the received data contains at least the threshold number of sequentially addressed logical groups based on host information received prior to a host write command, the host information comprising an indicator of a number of sequential logical groups of data to be written next.

5. The method of claim 2, wherein the controller determines if the received data contains at least the threshold number of sequentially addressed logical groups based on monitoring a host write pattern and determining that a last sequence of host writes has provided sequentially addressed logical groups of data in an amount equal to or greater than the threshold number of sequentially addressed logical groups.

3. A method of controlling storage of content on a storage device, the method comprising:

in a storage device having a controller in communication with non-volatile memory, wherein the non-volatile memory comprises a first type of non-volatile memory and a second type of non-volatile memory, the controller;

receiving data for storage in the non-volatile memory;

upon determining that a fullness of the storage device has reached a proactive defragmentation threshold, only writing sequentially addressed logical groups of received data to the second type of non-volatile memory;

wherein only writing sequentially addressed logical groups of received data to the second type of non-volatile memory comprises the controller;

determining if the received data contains at least a threshold number of sequentially addressed logical groups and, when the received data is determined to contain at least the threshold number of sequentially addressed logical groups, bypassing the first type of non-volatile memory and writing the sequentially addressed logical groups of received data directly into the second type of non-volatile memory;

when the received data is determined to contain less than the threshold number of sequentially addressed logical groups, writing the received data into the first type of non-volatile memory;

monitoring the first type of non-volatile memory for data having the threshold number of sequentially addressed logical groups; and

writing at least the threshold amount of sequentially addressed logical groups of data from the first type of non-volatile memory to the second type of non-volatile memory data when at least the threshold number of sequentially addressed logical groups is found in the first non-volatile memory type;

and

upon determining that the fullness of the storage device has reached a reactive defragmentation threshold automatically defragmenting data already written into the second type of non-volatile memory in response to a triggering event.

13. A storage device comprising:

a non-volatile memory having a first type of non-volatile memory and a second type of non-volatile memory; and

a controller in communication with the non-volatile memory, the controller configured to;

receive data for storage in the non-volatile memory;

upon a determination that a fullness of the storage device has reached a proactive defragmentation threshold, only write sequentially addressed logical groups of received data to the second type of non-volatile memory;

wherein to only write sequentially addressed logical groups of received data to the second type of non-volatile memory, the controller is further configured to;

determine if the received data contains at least a threshold number of sequentially addressed logical groups and, when the received data is determined to contain at least the threshold number of sequentially addressed logical groups, bypass the first type of non-volatile memory and write the sequentially addressed logical groups of received data directly into the second type of non-volatile memory; and

when the received data is determined to contain less than the threshold number of sequentially addressed logical groups, write the received data into the first type of non-volatile memory;

and

upon a determination that the fullness of the storage device has reached a reactive defragmentation threshold, automatically defragment data already written into the second type of non-volatile memory in response to a trigger event.

14. A storage device comprising:

a non-volatile memory having a first type of non-volatile memory and a second type of non-volatile memory; and

a controller in communication with the non-volatile memory, the controller configured to;

receive data for storage in the non-volatile memory;

upon a determination that a fullness of the storage device has reached a proactive defragmentation threshold, only write sequentially addressed logical groups of received data to the second type of non-volatile memory;

wherein to only write sequentially addressed logical groups of received data to the second type of non-volatile memory the controller is further configured to;

monitor the first type of non-volatile memory for previously received data having the threshold number of sequentially addressed logical groups; and

write an amount of sequentially addressed logical groups of data from the first type of non-volatile memory to the second type of non-volatile memory data when at least the threshold number of sequentially addressed logical groups is found in the first non-volatile memory type;

and

upon a determination that the fullness of the storage device has reached a reactive defragmentation threshold, automatically defragment data already written into the second type of non-volatile memory in response to a trigger event.

16. The storage device of claim 14, wherein the controller is configured to determine if the received data contains at least the threshold number of sequentially addressed logical groups based on host information received prior to a host write command, the host information comprising an indicator of a number of sequential logical groups of data to be written next.

17. The storage device of claim 14, wherein the controller is further configured to:

determine if the received data contains at least the threshold number of sequentially addressed logical groups based on monitoring a host write pattern; and

determine that a last sequence of host writes has provided sequentially addressed logical groups of data in an amount equal to or greater than the threshold number of sequentially addressed logical groups.

15. A storage device comprising:

a non-volatile memory having a first type of non-volatile memory and a second type of non-volatile memory; and

a controller in communication with the non-volatile memory, the controller configured to;

receive data for storage in the non-volatile memory;

upon a determination that a fullness of the storage device has reached a proactive defragmentation threshold, only write sequentially addressed logical groups of received data to the second type of non-volatile memory;

wherein to only write sequentially addressed logical groups of received data to the second type of non-volatile memory the controller is further configured to;

determine if the received data contains at least a threshold number of sequentially addressed logical groups and, when the received data is determined to contain at least the threshold number of sequentially addressed logical groups, bypass the first type of non-volatile memory and write the sequentially addressed logical groups of received data directly into the second type of non-volatile memory;

when the received data is determined to contain less than the threshold number of sequentially addressed logical groups, write the received data into the first type of non-volatile memory;

monitor the first type of non-volatile memory for data having the threshold number of sequentially addressed logical groups; and

write at least the threshold amount of sequentially addressed logical groups of data from the first type of non-volatile memory to the second type of non-volatile memory data when at least the threshold number of sequentially addressed logical groups is found in the first non-volatile memory type; and

upon a determination that the fullness of the storage device has reached a reactive defragmentation threshold, automatically defragment data already written into the second type of non-volatile memory in response to a trigger event.

18. A storage device comprising:

a non-volatile memory having a first type of non-volatile memory and a second type of non-volatile memory; and

a controller in communication with the non-volatile memory, the controller configured to;

receive data for storage in the non-volatile memory;

upon a determination that a fullness of the storage device has reached a proactive defragmentation threshold, only write sequentially addressed logical groups of received data to the second type of non-volatile memory; and

upon a determination that the fullness of the storage device has reached a reactive defragmentation threshold, automatically defragment data already written into the second type of non-volatile memory in response to a trigger event, wherein to automatically defragment data already written into the second type of non-volatile memory in response to a trigger event the controller is configured to;

scan the second type of non-volatile memory for sequentially numbered logical groups of data previously written in noncontiguous locations in the non-volatile memory; and

if a threshold amount of sequentially numbered logical groups previously written in noncontiguous locations are present, re-write at least the threshold amount of sequentially numbered logical groups of data contiguously into a new block in the second type of non-volatile memory.

19. The storage device of claim 18, wherein to scan the second type of non-volatile memory for sequentially numbered logical groups of data previously written in noncontiguous locations in the non-volatile memory the controller is further configured to:

determine a number of valid logical groups stored in the second type of non-volatile memory that are associated with a particular cluster; and

determine a number of blocks in the second type of non-volatile memory containing the valid logical groups associated with the particular cluster.

20. The storage device of claim 19, wherein the controller is further configured to re-write the valid logical groups of data associated with the particular cluster contiguously into a new block in the second type of non-volatile memory when both the number of valid logical groups is greater than a logical group threshold and the number of blocks in the second type of non-volatile memory containing the valid logical groups is greater than a fragmentation threshold.

21. The storage device of claim 20, wherein the first type of non-volatile memory comprises single level cell (SLC) flash memory and the second type of non-volatile memory comprises multi-level cell (MLC) flash memory.

22. The storage device of claim 18, wherein the trigger event comprises a number of fragmenting write operations exceeding a fragmenting write operation threshold.

23. The storage device of claim 18, wherein the controller is configured to automatically defragment data already written into the second type of non-volatile memory further by exclusively re-writing data into the new block, wherein the new block is dedicated to only defragmented data.

24. The storage device of claim 18, wherein the controller is configured to separately write compacted data into the new block in addition to automatically defragmenting data already written into the second type of non-volatile by re-writing data into the new block, wherein the new block is dedicated to both defragmented data and data received from a compaction process.

25. A method of controlling storage of content on a storage device, the method comprising:

in a storage device having a controller in communication with non-volatile memory, wherein the non-volatile memory comprises a first type of non-volatile memory and a second type of non-volatile memory, the controller;

receiving data for storage in the non-volatile memory;

upon determining that the fullness of the storage device has reached a reactive defragmentation threshold, automatically defragmenting data already written into the second type of non-volatile memory in response to a triggering event; and

wherein automatically defragmenting data already written into the second type of non-volatile memory comprises the controller;

scanning the second type of non-volatile memory for sequentially numbered logical groups of data previously written in noncontiguous locations in the non-volatile memory by;

determining a number of valid logical groups stored in the second type of non-volatile memory that are associated with a particular cluster; and

determining a number of blocks in the second type of non-volatile memory containing the valid logical groups associated with the particular cluster;

and

if a threshold amount of sequentially numbered logical groups previously written in noncontiguous locations are present, re-writing at least the threshold amount of sequentially numbered logical groups of data contiguously into a new block in the second type of non-volatile memory.