Method for selective defragmentation in a data storage device

• US 8,819,375 B1
• Filed: 11/30/2011
• Issued: 08/26/2014
• Est. Priority Date: 11/30/2011
• Status: Active Grant

• Current Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Original Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Inventors: Pruett, David C., Neppalli, Srinivas
• Primary Examiner(s): DUDEK JR, EDWARD J
• Application Number:
  US13/308,403
• Time in Patent Office: 1,000 Days
• Field of Search: 711/165, 711/E12.002, 707/693
• US Class Current: 711/165
• CPC Class Codes: G06F 13/28 using burst mode transfer, e.g. direct memory access DMA, cycle steal G06F13/32 takes precedence

Abstract

A data storage device is disclosed including a non-volatile media having a plurality of physical locations for storing user data, each physical location associated with a logical block address (LBA), a translation table having a plurality of entries, each entry having a mapping of one or more LBAs to a corresponding number of physical locations on the non-volatile media. The data storage device further includes control circuitry that divides the translation table into a plurality of segments, each segment including a group of entries corresponding to a range of LBAs, determines a first score for each segment using a first metric, and selects a segment for defragmentation by utilizing the first score for each segment.

Claims

1. A data storage device comprising:

a non-volatile media comprising a plurality of physical locations for storing user data, each physical location associated with a logical block address (LBA);

a translation table comprising a plurality of entries, each entry comprising a mapping of one or more LBAs to a corresponding number of physical locations on the non-volatile media; and

control circuitry operable to;

divide the translation table into a plurality of segments based on a first LBA and a last LBA greater than the first LBA per segment, each segment comprising a group of entries corresponding to a range of LBAs extending from a first LBA to a last LBA for the segment;

determine a first score for each segment using a first metric; and

select a segment for defragmentation by utilizing the first score for each segment.

2. The data storage device as recited in claim 1, wherein the control circuitry is further operable to:

read the range of LBAs corresponding to the selected segment on the non-volatile media; and

write the range of LBAs corresponding to the selected segment as a sequential stream on the non-volatile media.

3. The data storage device as recited in claim 1, wherein the first metric is a fragmentation metric, and the control circuitry is further operable to select the segment for defragmentation having a first score indicating the highest number of entries required to describe the range of LBAs corresponding to the segment.

4. The data storage device as recited in claim 1, wherein the first metric is a fragmentation metric, and the control circuitry is further operable to select the segment for defragmentation having a first score indicating the lowest ratio of total number of LBAs per entry.

5. The data storage device as recited in claim 1, wherein the first metric is a dispersion metric, and the control circuitry is further operable to select the segment for defragmentation having a first score indicating the lowest variance in physical locations corresponding to each entry in the segment.

6. The data storage device as recited in claim 1, wherein the first metric is a time metric, and the control circuitry is further operable to select the segment for defragmentation having a first score indicating the least amount of time required to read all of the entries in the segment.

7. The data storage device as recited in claim 1, wherein the control circuitry is further operable to:

select a group of segments from the plurality of segments based on the first scores of the segments;

determine a second score for each segment in the group of segments using a second metric; and

select a segment from the group of segments for defragmentation based on the second score for each segment in the group of segments.

8. The data storage device as recited in claim 7, wherein the first metric is a fragmentation metric and the second metric is a dispersion metric, and the control circuitry is further operable to:

select the group of segments having the highest first scores, wherein each first score indicates the number of entries required to describe the LBA range of the segment; and

select a segment from the group of segments for defragmentation having a second score indicating the lowest variance in physical locations corresponding to each entry in the segment.

9. The data storage device as recited in claim 7, wherein the first metric is a fragmentation metric and the second metric is a dispersion metric, and the control circuitry is further operable to:

select the group of segments having the lowest first scores, wherein each first score indicates a ratio of total number of LBAs per entry; and

select a segment from the group of segments for defragmentation having a second score indicating the lowest variance in physical locations corresponding to each entry in the segment.

10. The data storage device as recited in claim 7, wherein the first metric is a fragmentation metric and the second metric is a time metric, and the control circuitry is further operable to:

select the group of segments having the highest first scores, wherein each first score indicates the number of entries required to describe the LBA range of the segment; and

select a segment from the group of segments for defragmentation having a second score indicating the least amount of time required to read all of the entries in the segment.

11. The data storage device as recited in claim 7, wherein the first metric is a fragmentation metric and the second metric is a time metric, and the control circuitry is further operable to:

select the group of segments having the lowest first scores, wherein each first score indicates a ratio of total number of LBAs per entry; and

select a segment from the group of segments for defragmentation having a second score indicating the least amount of time required to read all entries in the segment.

12. The data storage device as recited in claim 1, wherein the non-volatile media comprises a disk having a plurality of tracks including the plurality of physical locations for storing the user data.

13. The data storage device as recited in claim 12, wherein the plurality of tracks are written on the disk in a shingled manner such that each track is partially overwritten when an immediately contiguous track is written.

14. The data storage device as recited in claim 1, wherein the non-volatile media comprises a non-volatile semiconductor media including the plurality of physical locations for storing the user data.

15. A method of operating a data storage device, the data storage device comprising a non-volatile media comprising a plurality of physical locations for storing user data, each physical location associated with a logical block address (LBA), and a translation table comprising a plurality of entries, each entry comprising a mapping of one or more LBAs to a corresponding number of physical locations on the non-volatile media, the method comprising:

dividing the translation table into a plurality of segments based on a first LBA and a last LBA greater than the first LBA per segment, each segment comprising a group of entries corresponding to a range of LBAs extending from a first LBA to a last LBA for the segment;

determining a first score for each segment using a first metric; and

selecting a segment for defragmentation by using the first score for each segment.

16. The method as recited in claim 15, further comprising:

reading the range of LBAs corresponding to the selected segment on the non-volatile media; and

writing the range of LBAs corresponding to the selected segment as a sequential stream on the non-volatile media.

17. The method as recited in claim 15, wherein:

the first metric is a fragmentation metric; and

further comprising selecting the segment for defragmentation having a first score indicating the highest number of entries required to describe the range of LBAs corresponding to the segment.

18. The method as recited in claim 15, wherein:

the first metric is a fragmentation metric; and

further comprising selecting the segment for defragmentation having a first score indicating the lowest ratio of total number of LBAs per entry.

19. The method as recited in claim 15, wherein:

the first metric is a dispersion metric; and

further comprising selecting the segment for defragmentation having a first score indicating the lowest variance in physical locations corresponding to each entry in the segment.

20. The method as recited in claim 15, wherein:

the first metric is a time metric; and

further comprising selecting the segment for defragmentation having a first score indicating the least amount of time required to read all of the entries in the segment.

21. The method as recited in claim 15, further comprising:

selecting a group of segments from the plurality of segments based on the first scores of the segments;

determining a second score for each segment in the group of segments using a second metric; and

selecting a segment from the group of segments for defragmentation based on the second score for each segment in the group of segments.

22. The method as recited in claim 21, wherein:

the first metric is a fragmentation metric and the second metric is a dispersion metric; and

further comprising;

selecting the group of segments having the highest first scores, wherein each first score indicates the number of entries required to describe the LBA range of the segment; and

selecting a segment from the group of segments for defragmentation having a second score indicating the lowest variance in physical locations corresponding to each entry in the segment.

23. The method as recited in claim 21, wherein:

the first metric is a fragmentation metric and the second metric is a dispersion metric; and

further comprising;

selecting the group of segments having the lowest first scores, wherein each first score indicates a ratio of total number of LBAs per entry; and

selecting a segment from the group of segments for defragmentation having a second score indicating the lowest variance in physical locations corresponding to each entry in the segment.

24. The method as recited in claim 21, wherein:

the first metric is a fragmentation metric and the second metric is a time metric; and

further comprising;

selecting the group of segments having the highest first scores, wherein each first score indicates the number of entries required to describe the LBA range of the segment; and

selecting a segment from the group of segments for defragmentation having a second score indicating the least amount of time required to read all of the entries in the segment.

25. The method as recited in claim 21, wherein:

the first metric is a fragmentation metric and the second metric is a time metric; and

further comprising;

selecting the group of segments having the lowest first scores, wherein each first score indicates a ratio of total number of LBAs per entry; and

selecting a segment from the group of segments for defragmentation having a second score indicating the least amount of time required to read all of the entries in the segment.

26. The method as recited in claim 15, wherein the non-volatile media comprises a disk having a plurality of tracks including the plurality of physical locations for storing the user data.

27. The method as recited in claim 26, wherein the plurality of tracks are written on the disk in a shingled manner such that each track is partially overwritten when an immediately contiguous track is written.

28. The method as recited in claim 15, wherein the non-volatile media comprises a non-volatile semiconductor media including the plurality of physical locations for storing the user data.