Granted Patent B1

US 8,819,375 · App. 13/308,403 · Granted Aug 26, 2014

Abstract

Claims (79)

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.

Assignments (7)