File usage history log for improved placement of files in differential rate memory according to frequency of utilizations and volatility of allocation space

• US 7,124,272 B1
• Filed: 04/18/2003
• Issued: 10/17/2006
• Est. Priority Date: 04/18/2003
• Status: Active Grant

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Symantec Corporation (NortonLifeLock Inc.)
• Inventors: Sobel, William, Kennedy, Mark K.
• Primary Examiner(s): Padmanabhan, Mano
• Assistant Examiner(s): Doan, Duc T
• Application Number:
  US10/418,476
• Time in Patent Office: 1,278 Days
• Field of Search: None
• US Class Current: 711/173
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/0643 Management of files
• CPC Class Codes: G06F 3/0676 Magnetic disk device

Abstract

Improved file tracking methods and file re-positioning or file defragmenting mechanisms are disclosed for use with a differential rate memory device which has allocatable storage units disposed in regions of comparatively faster data access and of comparatively slower data access for storing retrievable data file contents in such regions.

Claims

1. A differential rate memory device having regions of comparatively faster data access and of comparatively slower data access for storing data files in such regions, where said differential rate memory device comprises:

a first set of relatively frequently utilized files situated in a corresponding, relatively fastest and first access region of the memory device;

a second set of relatively infrequently utilized files situated in a corresponding, relatively slowest and second access region of the memory device;

one or more free spaces positioned between said first and second access regions of the memory device, each of the one or more free spaces being essentially free of data belonging to undeleted files; and

a file-utilization tracking log which tracks at least recent history of content utilizing and/or re-sizing references made to files stored in the comparatively faster data access regions and the comparatively slower data access regions of the differential rate memory device.

2. The differential rate memory device of claim 1 wherein:

the file-utilization tracking log further tracks at least recent history of size volatility of the files stored in the comparatively faster and slower data access regions of the differential rate memory device.

3. The differential rate memory device of claim 1 and further comprising:

a third set of relatively frequently re-sized files situated adjacent to at least a first of the one or more free spaces.

4. The differential rate memory device of claim 3 and further comprising:

a fourth set of relatively infrequently re-sized files situated between the comparatively, more frequently re-sized files of the third set and the comparatively, more frequently utilized files of the first set.

5. The differential rate memory device of claim 4 and further comprising:

a fifth set of relatively middlingly utilized and relatively size-wise nonvolatile files situated between the comparatively, more frequently re-sized files of the fourth set and the comparatively, more frequently utilized files of the first set.

6. The differential rate memory device of claim 4 wherein:

the file-utilization tracking log further tracks at least recent history of size volatility of the files stored in the comparatively faster and slower data access regions of the differential rate memory device.

7. A file placement method for use with a differential rate memory device having regions of comparatively faster data access and of comparatively slower data access for storing retrievable data file contents in such regions, where said file placement method comprises:

placing a first set of relatively frequently utilized files in a corresponding, relatively fastest and first access region of the memory device;

placing a second set of relatively infrequently utilized files in a corresponding, relatively slowest and second access region of the memory device;

providing one or more free spaces positioned between said first and second access regions of the memory device, each of the one or more free spaces being essentially free of data belonging to undeleted files; and

basing the placings on file-utilization data provided by a file-utilization tracking log which tracks at least recent history of content utilizing and/or re-sizing references made to files stored in the comparatively faster and comparatively slower data access regions of the differential rate memory device.

8. The file placement method claim 7 wherein:

the file-utilization tracking log further tracks at least recent history of size volatility of the files stored in the comparatively faster and slower data access regions of the differential rate memory device; and

said basing further bases the placement of the first and second set of files on file-volatility data provided by the file-utilization tracking log.

9. The file placement method of claim 7 and further comprising:

placing a third set of relatively frequently re-sized files in a beachhead region adjacent to a volatile boundary of at least a first of the one or more free spaces.

10. The file placement method of claim 9 and further comprising:

placing a forth set of relatively infrequently re-sized files in a moderate volatility region between the comparatively, more frequently resized files of the beachhead region and the comparatively, more frequently utilized files of the first region.

11. The file placement method of claim 10 and further comprising:

placing a fifth set of relatively middlingly utilized and relatively size-wise nonvolatile files in a middling region between the comparatively, more frequently re-sized files of the moderate volatility region and the comparatively, more frequently utilized files of the first region.

12. The file placement method of claim 10 wherein:

the file-utilization tracking log further tracks at least recent history of size volatility of the files stored in the comparatively faster and slower data access regions of the differential rate memory device; and

said basing further bases the placement of the first and second set of files on file-volatility data provided by the file-utilization tracking log.

13. A differential rate memory device having respective data storage and retrieval regions which are comparatively characterized by respective faster and slower data access speeds;

where said comparatively faster and slower regions store contents of data files, said differential rate memory device comprising;

a file-utilization tracking log which tracks at least recent history of content utilizing and/or re-sizing references made to files stored in the comparatively faster and slower data access regions of the differential rate memory device.

14. The differential rate memory device of claim 13 wherein:

the file-utilization tracking log further tracks at least recent history of size volatility of the files stored in the comparatively faster and slower data access regions of the differential rate memory device.

15. The differential rate memory device of claim 14 wherein:

the file-utilization tracking log is logically divided to track different time frames, one of said time frames defining said recent history of size volatility and content utilization of the files stored in the comparatively faster and slower data access regions and a second of said time frames defining an older time frame for which such size volatility and content utilization is tracked, where tracking data in said at least one older time frame has lower resolution of time versus size volatility and content utilization than does tracking data in said recent history.

16. A file-utilization tracking method which may be used in combination with a differential rate memory device having regions of comparatively faster data access and of comparatively slower data access for storing retrievable data file contents in such regions, where said file-utilization tracking method comprises:

intercepting file-access requests;

for each intercepted request, first determining whether the requested access will utilize/re-size or has utilized/re-sized file data contents or not of a correspondingly referenced file or a correspondingly-referenced group of files; and

in response to an indication by said first determining that the requested access will, or has utilized file data contents, updating a file-utilization history log record of the referenced file or referenced group of files to indicate an increased amount of utilization and/or size volatility for the referenced file or group of files.

17. The file-utilization tracing method of claim 16 and further comprising:

prior to invoking said history log record updating step, second determining whether the requested access is referencing a file or group of files which is pre-identified by name and/or type as a respective file or group that is to be excluded from having its utilization history being logged by said history log record updating step, and if said second determining indicates that the referenced file or group of files is to be excluded, bypassing said history log record updating step.

18. The file-utilization tracking method of claim 16 and further comprising:

prior to invoking said history log record updating step, second determining whether a history log record exists for the referenced file or group of files, and if not, creating a respective history log record for the respectively referenced file or group of files.

19. The file-utilization tracking method of claim 18 and further comprising:

when creating said respective history log record, filling the created history log record with mock history data.

20. The file-utilization tracking method of claim 16 and further comprising:

second determining either before or after the requested access is carried out whether the referenced file respectively will, or has had its storage allocation size changed; and

if not, bypassing an updating of volatility information recorded in the respective history log record for the respectively referenced file or group of files.

21. The file-utilization tracking method of claim 20 and further comprising:

if said second determining indicates that the storage allocation size of the referenced file respectively will, or has changed, updating the volatility information recorded in the respective history log record for the respectively referenced file or group of files.

22. The file-utilization tracking method of claim 21 and further comprising:

using said history log records to automatically classify the correspondingly tracked files or group of files as being comparatively frequently or infrequently utilized.

23. The file-utilization tracking method of claim 22 and further comprising:

using said history log records to automatically classify the correspondingly tracked files or group of files as being comparatively volatile or not volatile with respect to their storage allocation sizes changing over time.

24. The file-utilization tracking method of claim 16 and further comprising:

detecting a period of dormancy such as system power-off during which file utilization and utilization tracking are dormant; and

updating historical information recorded in the respective history log records of files or group of files whose utilization was dormant during the period of dormancy to reflect the period of dormancy.

25. A file-volatility tracking method which may be used in combination with a differential rate memory device having allocatable storage units disposed in regions of comparatively faster data access and of comparatively slower data access for storing retrievable data file contents in such regions, where said file-volatility tracking method comprises:

intercepting file-access requests;

for each intercepted request, first determining whether the requested access will cause or has caused a change in the number of allocatable storage units consumed by file data contents of a correspondingly referenced file or a correspondingly-referenced group of files, and if so, further determining at least approximately, the magnitude of such a positive or negative change in number of consumed storage units; and

in response to an indication by said first determining that the requested access will, or has changed the number of allocatable storage units, updating a file-tracking history log record of the referenced file or referenced group of files to indicate an amount of size volatility versus time for the referenced file or group of files.

26. The file-volatility tracking method of claim 25 and further comprising:

prior to invoking said history log record updating step, second determining whether the requested access is referencing a file or group of files which is pre-identified by name and/or type as a respective file or group that is to be excluded from having its volatility history being logged by said history log record updating step, and if said determining indicates that the referenced file or group of files is to be excluded, bypassing said history log record updating step.

27. The file-volatility tracking method of claim 25 and further comprising:

prior to invoking said history log record updating step, second determining whether a history log record exists for the referenced file or group of files, and if not, creating a respective history log record for the respectively referenced file or group of files.

28. The file-volatility tracking method of claim 27 and further comprising:

when creating said respective history log record, filling the created history log record with mock volatility history data.

29. A manufactured storage media having a files-utilization tracking log recorded therein, where said tracking log may be cooperatively used in combination with a differential rate memory device having allocatable storage units disposed in regions of comparatively faster data access and of comparatively slower data access for storing retrievable data file contents in such regions, where said files-utilization tracking log of the storage media comprises:

a plurality of tracking records each for tracking utilization and/or size volatility of a corresponding file or a corresponding group of files;

where utilization involves at least actual reading of data from contents of at least one of said corresponding files or actual writing of new data contents to at least one of said corresponding files; and

where size volatility involves a change in the number of allocatable storage units consumed by file data contents of at least one of said corresponding files; and

where each tracking record comprises;

at least a first record section adapted for keeping track of recent utilization and/or recent size volatility of a corresponding file or a corresponding group of files in a predefined recent time frame; and

at least a second record section adapted for keeping track of older utilization and/or older size volatilities of the corresponding file or the corresponding group of files which took place in a predefined older time frame occurring at least partially before the predefined recent time frame.

30. The storage media of claim 29 and further where each tracking record comprises:

at least a third record section adapted for keeping track of yet older utilization and/or yet older size volatilities of the corresponding file or the corresponding group of files which took place in a predefined, yet older time frame occurring at least partially before the predefined older time fame.

31. The storage media of claim 30 and further wherein:

said predefined older time frame covers a time period at least as long as that covered by the predefined recent time frame; and

said predefined, yet older time frame covers a longer time period than that covered by the older time frame.

32. The storage media of claim 30 and further wherein:

said third record section is adapted to provide an age-decaying representation of the yet older utilization and/or yet older size volatilities of the corresponding file or the corresponding group of files, where the age-decaying representation emphasizes representation of more recent historical information over more aged historical information.

33. The storage media of claim 29 and further wherein:

the plurality of tracking records of the files-utilization tracking log are logically organized according to recent and/or older utilization histories such that a least-utilized fall-off algorithm can be employed for automatically deleting from the log, excessive numbers of rows whose statistics indicate they are least often utilized within the recent time frame and/or the middling time frame as compared to others of the files or groups of files tracked by other records, where excessive records are those beyond a predefined records limit of the files-utilization tracking log.

34. The storage media of claim 29 wherein:

the plurality of tracking records of the files-utilization tracking log are logically organized as linked lists which are automatically sort-able to identify which files or groups of files are recently more utilized or utilized to a lesser extent based on the historical statistics gathered for said corresponding files or corresponding groups of files within the recent time frame and/or the middling time frame.

35. A machine-implemented, files re-positioning method for repositioning files within a differential rate memory device, where the memory device has allocatable storage units disposed in regions of comparatively faster data access and of comparatively slower data access for storing retrievable data file contents in such regions, where said files re-positioning method comprises:

accessing a files-utilization tracking log whose tracking records are logically organized according to which files or groups of files are recently more utilized/re-sized or utilized/resized to a lesser extent based on the historical statistics gathered for said corresponding files or corresponding groups of files within one or more time frames covered by the files-utilization tracking log; and

prioritizing file re-positioning activities to work first on re-positioning and/or defragmenting identified files or groups of files whose tracking records are logically organized to indicate that those identified files or groups of files are recently more utilized relative to other files which may also benefit from re-positioning and/or defragmenting.

36. A machine-implemented, files utilization tracking method comprising:

providing a files-utilization tracking log, where said tracking log may be cooperatively used in combination with a differential rate memory device having allocatable storage units disposed in regions of comparatively faster data access and of comparatively slower data access for storing retrievable data file contents in such regions, where said files-utilization tracking log comprises;

a plurality of tracking records each for tracking utilization and/or size volatility of a corresponding file or a corresponding group of files,

where utilization involves at least actual reading of data from contents of at least one of said corresponding files or actual writing of new data contents to at least one of said corresponding files;

where size volatility involves a change in the number of allocatable storage units consumed by file data contents of at least one of said corresponding files; and

where each tracking record has;

at least a first record section structured for keeping track of recent utilization and/or recent size volatility of a corresponding file or a corresponding group of files in a predefined recent time frame; and

at least a second record section structured for compressively keeping track of older utilization and/or older size volatilities of the corresponding file or the corresponding group of files which took place in a predefined older time frame occurring before the predefined recent time frame; and

when a first record section fills up with tracking data fully covering said predefined recent time frame, compressing tracking data of an older part of the first record section and shifting the compressed tracking data to the second record section to thereby create free storage area in the first record section for maintaining more current tallies.

37. A machine-implemented, file utilization classifying method comprising:

defining a first time frame as constituting a recent time frame;

defining an older second time frame as constituting a middling time frame;

providing a files-utilization tracking log, where said tracking log may be cooperatively used in combination with a differential rate memory device having allocatable storage units disposed in regions of comparatively faster data access and of comparatively slower data access for storing retrievable data file contents in such regions, where said files-utilization tracking log comprises;

a plurality of tracking records each for tracking utilization and/or size volatility of a corresponding file or a corresponding group of files,

where utilization involves at least actual reading of data from contents of at least one of said corresponding files or actual writing of new data contents to at least one of said corresponding files;

where size volatility involves a change in the number of allocatable storage units consumed by file data contents of at least one of said corresponding files; and

where each tracking record has;

at least a first record section structured for keeping track of recent utilization and/or recent size volatility of a corresponding file or a corresponding group of files in the recent time frame; and

at least a second record section structured for keeping track of older utilization and/or older size volatilities of the corresponding file or the corresponding group of files which took place in the middling time frame; and

first determining from the files-utilization tracking log if an identified file or group of files has experienced a non-negligible amount of size-volatility in the recent time frame, and if so, classifying the identified file or group of files as being frequently modified.

38. The file utilization classifying method of claim 37 and further comprising:

second determining from the files-utilization tracking log if an identified file or group of files has experienced a non-negligible amount of utilization in the recent time frame, and if so, classifying the identified file or group of files as being frequently utilized.

39. The file utilization classifying method of claim 38 and further comprising:

third determining from the files-utilization tracking log if an identified file or group of files has experienced a non-negligible amount of size-volatility in the middling time frame but not in the recent time frame, and if so, classing the identified file or group of files as being infrequently modified.

40. A machine readable medium having instructions stored thereon that when executed by a processor cause a system to:

place relatively frequently utilized but size-unmodified files in a corresponding, relatively fastest and first access region of the memory device;

place relatively infrequently utilized and size-unmodified files in a corresponding, relatively slowest and second access region of the memory device;

create one or more free spaces positioned between said first and second access regions of the memory device, each of the one or more free spaces being essentially free of data belonging to undeleted files; and

wherein said first and second placings an file-utilization data provided by a file-utilization tracking log which tracks at least recent history of content utilizing and/or re-sizing references made to files stored in the comparatively faster and comparatively slower data access regions of the differential rate memory device.