Method and apparatus for providing improved caching for a virtual tape server

• US 6,269,423 B1
• Filed: 05/13/1998
• Issued: 07/31/2001
• Est. Priority Date: 05/13/1998
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kishi, Gregory Tad
• Primary Examiner(s): Nguyen, Hiep T.
• Assistant Examiner(s): GOODARZI, NASSER MOAZZAMI
• Application Number:
  US09/078,181
• Time in Patent Office: 1,175 Days
• Field of Search: 711/113, 711/111, 711/112, 711/114, 711/118, 707/204, 360/45
• US Class Current: 711/113
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 12/121 using replacement algorithms
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99955 Archiving or backup

Abstract

A method and apparatus for improving caching for a virtual tape server is disclosed. The method and apparatus improve caching by making assumptions to increase cache hits, but which do not cause the virtual tape server to under-perform when these assumptions prove to be incorrect. The method includes the steps of correlating logical volume usage to externally determined file characteristics to derive usage histories for cached logical volumes, maintaining a record of the histories for the files that share the same predefined characteristics, and managing the migration of the logical volumes according to the usage history and the externally determined file characteristics of the logical volume. The correlation is accomplished by associating the first logical volume with a logical volume type based on predefined characteristics, assigning a time bin for the type of the first logical volume based on the time of last access of the first logical volume therein and based on the type assigned to the first logical volume at the time the first logical volume was last accessed and updating a usage count in the time bin for the type. Scores for each logical volume in the cache are updated by determining the age and type of each logical volume, selecting appropriate time buckets for the logical volume, calculating a usage score for the time buckets, computing time-weighted usage scores for the time buckets and identifying a final score for the logical volume. The logical volume with the lowest score is the next volume to be discarded from the cache.

Claims

1. A method for improving caching in a virtual tape system, comprising the steps of:

correlating logical volume usage to externally determined file characteristics to derive a usage history for cached logical volumes;

wherein the step of correlating further comprises the steps of;

associating the first logical volume with a logical volume type based on predefined characteristics;

assigning a time bin for the type of the first logical volume based on the time of last access of the first logical volume therein, the time of current access of the first logical volume and based on the type assigned to the first logical volume at the time the first logical volume was last accessed; and

updating a usage count in the time bin for the type;

maintaining a record of the usage history in time bins; and

managing the migration of the logical volumes according to the usage history and the externally determined file characteristics of the logical volume.

2. The method of claim 1 further comprising the step of calculating a score for a logical volume based upon the size of the first logical volume, the age of the first logical volume, and the historic performance of the other volumes.

3. The method of claim 2 wherein the time bin has data associated therewith, the data in the time bin for the first logical volume being divided by a predetermined number to prevent overrun and to maintain weighted historic data when a total for all time bins reaches a predetermined threshold.

4. The method of claim 2 wherein the score is updated periodically for any cached volume as the cached volume ages.

5. The method of claim 2 wherein the score is updated periodically for all cached volumes.

6. The method of claim 2 wherein the step of updating the score further comprises the steps of:

determining the age and type of each logical volume;

selecting a time bucket for the logical volume;

calculating a usage score for the time bucket;

computing a time-weighted usage score for the time bucket; and

identifying a final score for the time bucket.

7. The method of claim 5 wherein the usage score comprises calculating a usage score for all nth time buckets, n>

m, wherein the mth time bucket is a current time bucket, and wherein the usage score comprises a scaling constant times the sum of the time buckets for the logical volume between n and m divided by the sum of all time buckets greater than or equal to m plus a number of misses.

8. The method of claim 6 wherein the usage score is proportional to the percentage of cache hits when the cartridge is kept for n−

m+1 time intervals.

9. The method of claim 6 wherein the time-weighted usage score for the nth time bucket is equal to the usage score for the nth bucket divided by n−

m+l.

10. The method of claim 6 wherein the final score for the logical volume is equal to the maximum of the time-weighted usage score for the nth time buckets.

11. The method of claim 6 wherein the final score for the logical volume is equal to the time-weighted usage score for the logical volume divided by the size of the logical volume.

12. The method of claim 2 further comprising the step of processing logical volumes having an age in excess of a predetermined maximum period according to a size-weighted least recently used basis.

13. The method of claim 2 further comprising the steps of assigning logical volumes having no historic data a 50% hit rate in the first time bucket, and setting the score equal to minus the age of the cartridge times its size.

14. The method of claim 2 further comprising the step of assigning logical volumes having no historic data an average score for all logical volumes.

15. The method of claim 2 wherein the step of managing the migration of the logical volumes according to the usage history and the externally determined file characteristics of the logical volume further comprises the step of migrating a logical volume having the lowest score first.

17. The article of manufacture of claim 15 further comprising the step of calculating a score for a logical volume based upon the size of the first logical volume, the age of the first logical volume, and the historic performance of the other volumes.

16. An article of manufacture for a computer-based user-interface, the article of manufacture comprising a computer readable medium having instructions for causing a computer to perform a method comprising the steps of:

correlating logical volume usage to externally determined file characteristics to derive a usage history for cached logical volumes;

wherein the step of correlating further comprises the steps of;

associating the first logical volume with a logical volume type based on predefined characteristics;

assigning a time bin for the type of the first logical volume based on the time of last access of the first logical volume therein, the time of current access of the first logical volume and based on the type assigned to the first logical volume at the time the first logical volume was last accessed; and

updating a usage count in the time bin for the type;

maintaining a record of the usage history in time bins; and

managing the migration of the logical volumes according to the usage history and the externally determined file characteristics of the logical volume.

18. The article of manufacture of claim 16 wherein the time bin has data associated therewith, the data in the time bin for the first logical volume being divided by a predetermined number to prevent overrun and to maintain weighted historic data when a total for all time bins reaches a predetermined threshold.

19. The article of manufacture of claim 16 wherein the score is updated periodically for any cached volume as the cached volume ages.

20. The article of manufacture of claim 16 wherein the score is updated periodically for all cached volumes.

21. The article of manufacture of claim 16 wherein the step of updating the score further comprises the steps of:

determining the age and type of each logical volume;

selecting a time bucket for the logical volume;

calculating a usage score for the time bucket;

computing a time-weighted usage score for the time bucket; and

identifying a final score for the time bucket.

22. The article of manufacture of claim 19 wherein the usage score comprises calculating a usage score for all nth time buckets, n>

m, wherein the mth time bucket is a current time bucket, and wherein the usage score comprises a scaling constant times the sum of the time buckets for the logical volume between n and m divided by the sum of all time buckets greater than or equal to m plus a number of misses.

23. The article of manufacture of claim 20 wherein the usage score is proportional to the percentage of cache hits when the cartridge is kept for n−

m+1 time intervals.

24. The article of manufacture of claim 20 wherein the time-weighted usage score for the nth time bucket is equal to the usage score for the nth bucket divided by n−

m+1.

25. The article of manufacture of claim 20 wherein the final score for the logical volume is equal to the maximum of the time-weighted usage score for the nth time buckets.

26. The article of manufacture of claim 20 wherein the final score for the logical volume is equal to the time-weighted usage score for the logical volume divided by the size of the logical volume.

27. The article of manufacture of claim 16 further comprising the step of processing logical volumes having an age in excess of a predetermined maximum period according to a size-weighted least recently used basis.

28. The article of manufacture of claim 16 further comprising the steps of assigning logical volumes having no historic data a 50% hit rate in the first time bucket, and setting the score equal to minus the age of the cartridge times its size.

29. The article of manufacture of claim 16 further comprising the step of assigning logical volumes having no historic data an average score for all logical volumes.

30. The article of manufacture of claim 16 wherein the step of managing the migration of the logical volumes according to the usage history and the externally determined file characteristics of the logical volume further comprises the step of migrating a logical volume having the lowest score first.

32. The virtual tape server of claim 29 wherein the automatic storage manager calculates a score for a logical volume based upon the size of the first logical volume, the age of the first logical volume, and the historic performance of the other volumes.

33. The virtual tape server of claim 30 wherein the time bin has data associated therewith, the data in the time bin for the first logical volume is divided by a predetermined number to prevent overrun and to maintain weighted historic data when a total for all time bins reaches a predetermined threshold.

34. The virtual tape server of claim 30 wherein the score is updated periodically for any cached volume as the cache volume ages.

35. The virtual tape server of claim 30 wherein the score is updated periodically for all cached volumes.

36. The virtual tape server of claim 30 wherein the automatic storage manager administrator further comprises:

means for determining the age and type of each logical volume;

means for selecting a time bucket for the logical volume;

means for calculating a usage score for the time bucket;

means for computing a time-weighted usage score for the time bucket; and

means for identifying a final score for the time bucket.

37. The virtual tape server of claim 33 wherein the calculating means calculates a usage score for all nth time buckets, n>

m, wherein the mth time bucket is a current time bucket, and wherein the usage score comprises a scaling constant times the sum of the time buckets for the logical volume between n and m divided by the sum of all time buckets greater than or equal to m plus a number of misses.

38. The virtual tape server of claim 34 wherein the usage score is proportional to the percentage of cache hits when the cartridge is kept for n−

m+1 time intervals.

39. The virtual tape server of claim 34 wherein the time-weighted usage score for the nth time bucket is equal to the usage score for the nth bucket divided by n−

m+1.

40. The virtual tape server of claim 34 wherein the final score for the logical volume is equal to the maximum of the time-weighted usage score for the nth time buckets.

41. The virtual tape server of claim 34 wherein the final score for the logical volume is equal to the time-weighted usage score for the logical volume divided by the size of the logical volume.

42. The virtual tape server of claim 30 wherein the automatic storage manager administrator processes logical volumes having an age in excess of a predetermined maximum period according to a size-weighted least recently used basis.

43. The virtual tape server of claim 30 wherein the automatic storage manager administrator assigns logical volumes having no historic data a 50% hit rate in the first time bucket, and sets the score equal to minus the age of the cartridge times its size.

44. The virtual tape server of claim 30 wherein the automatic storage manager administrator assigns logical volumes having no historic data an average score for all logical volumes.

45. The virtual tape server of claim 30 wherein the automatic storage manager administrator migrates logical volumes having the lowest score first.

31. A virtual tape server, comprising:

primary storage media for storing intensively used and frequently accesses data, the data being transferred to the primary storage media as logical volumes;

secondary storage media, coupled to the primary storage media, for storing less frequently accesses logical volumes and forming a library;

a library manager, coupled to the secondary storage media, for controlling access to the logical volumes stored on the secondary storage media;

a distributed storage manager, operatively coupled to the primary and secondary storage media, for moving logical volumes between the primary and secondary storage media, the distributed storage manager further comprising a distributed storage manager server and a hierarchical storage manager client; and

an automatic storage manager administrator, coupled to the distributed storage manager, for controlling the distributed storage manager, the automatic storage manager administrator managing the caching of logical volumes in the virtual tape system by correlating logical volume usage to externally determined file characteristics to derive a usage history for cached logical volumes, maintaining a record of the usage history in time bins and managing the migration of the logical volumes according to the usage history and the externally determined file characteristics of the logical volume;

wherein the automatic storage manager administrator further correlates logical volume usage to externally determined file characteristics by associating the first logical volume with a logical volume type based on predefined characteristics, assigning a time bin for the type of the first logical volume based on the time of last access of the first logical volume therein, the time of current access of the first logical volume and based on the type assigned to the first logical volume at the time the first logical volume was last accesses and updating a usage count in the time bin for the type.