Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1998-04-10
2002-05-07
Yoo, Do Hyun (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S134000, C711S136000, C711S159000, C709S217000
Reexamination Certificate
active
06385699
ABSTRACT:
BACKGROUND
A paging system is a computer system in which the appearance of a large virtual memory is provided through a combination of high speed main memory and slower speed auxiliary memory. The first computer system to use paging was the Atlas machine (Sumner, T. K.,
One Level Storage System,
IEEE Transactions on Computers, April 1962, pp. 223-235).
The original idea of a CPU managed memory hierarchy was introduced by Wilkes (Wilkes, M. V.,
Slave Memories and Dynamic Storage Allocation,
IEEE Transactions on Electronic Computers, pp. 270-271, 1965). The key concept is that a small buffer of frequently referenced data can more quickly respond to fetch requests. Requests that are not in the buffer are fetched from main memory. A small amount of expensive high speed buffer can have a disproportionally good improvement on average access time. The first production computer with cache memory was the IBM 360
Model
85 (Liptay, J. S.,
Structural aspects of the System/
360 Model 85 II—
The Cache,
IBM Systems Journal, 7, 1968, pp. 15-21 and Conti, C. J.,
Concepts for buffer storage,
Computer Group News, 2, 1969, pp. 9-13).
Paging systems provide a memory cache of recently used pages and therefore can be considered a specific instance of a caching system. Both caching systems and paging systems require a dynamic mechanism for deciding which data to keep in the buffer. The decision hinges on which page to remove when a new candidate is to be inserted. It is frequently called the replacement algorithm.
The most often used replacement algorithm in computing systems is the Least Recently Used (LRU) algorithm (see Baylis, M. H., Fletcher, D. G., and Howarth, D. J.,
Paging Studies on the I.C.T. Atlas Computer,
Proceedings of the IFIP Congress, pp. 831-837, 1968; Belady, L. A.,
A Study of Replacement Algorithms for a Virtual-memory Computer,
IBM Systems Journal, 5, 1966, pp. 78-100; and U.S. Pat. No. 3,964,028, issued Jun. 15, 1976 to Belady et al.). In many cases the algorithm used is an LRU approximation that will operate with lower overhead. Belady showed that the optimal algorithm would replace the page with the longest time until next reference. However, this is not implementable. In general, replacement algorithms (LRU included) are trying to predict the next reference.
Effelsberg (Effelsberg, W., and Haerder, T.,
Principles of Database Buffer Management,
ACM Transactions on Data Base Systems, 9, 1984, pp. 560-595) analyzed frequency based approaches. The frequency approach was later refined in U.S. Pat. No. 5,043,885, issued Aug. 27, 1991, entitled
Data Cache Using Dynamic Frequency Based Replacement and Boundary Criteria,
by Robinson). Frequency based algorithms place a higher value on frequently referenced blocks. This is another attempt at ranking blocks by the time of estimated next reference.
These paging and caching techniques have been incorporated into database buffer caches, file system buffer caches, and caches in disk control units. In all cases, LRU variants or frequency based replacement algorithms are used. The systems all share two important characteristics: first, all objects are the same size (or one of a small number of predetermined sizes); second, all blocks take approximately the same time to retrieve from the backing store. In these systems improvements to the replacement algorithm will result in higher hit ratios, lower miss ratios and reduced average latency.
Web page caching introduces two new deviations from previous automatic storage hierarchy systems. First, objects are of a wide range of different sizes. Second, the fetch time in the event of a miss is different (often very different due to network latency, server load and object size). The relaxation that allows variable fetch times and variable size decouples the relationship between hit ratio and average fetch time.
Average user fetch time is a reasonable objective function for the optimization problem for which the replacement algorithm is used. If objects are variable in size, then the fast buffer may be more effectively used for multiple small objects instead of one large object that is referenced more often than any one of the small objects. Long network latency to a particular object may make it a better candidate to retain in memory than other objects that are referenced more frequently but have lower miss penalties.
One proposed solution is a server centric system in which the server gives hints to clients about what to cache (see
Using the Overhead Costs of Network Messages to Choose Between Cache Coherency Strategies in a Distributed File System,
IBM Technical Disclosure Bulletin (TDB), pp. 266-268, (August 1991)). Here, the server decides whether to cache an item. The concern is the tradeoff, in network traffic, of invalidate messages versus more data movement when caching is not done. The TDB article does not make any proposal about which cacheable items should actually be cached. The TDB article makes use of a cost function (which are pervasive in optimizations) for making decisions.
The Hybrid algorithm uses a cost function that includes: time to connect to a server; bandwidth to the server; the number of times requested; and the size (see Wooster, R., and Abrams, M.
Proxy Caching That Estimates Page Load Delays,
6th International World Wide Web Conference, Apr. 7-11, 1997, Santa Clara, Calif.). It also includes a number of tuning parameters that must be experimentally determined. The cost function should really be viewed as a heuristic because it is not dimensionally meaningfull (time is added to time divided by size). It does not use reference probabilities for evaluating a cost function.
The current state of the art is recognizing that size, retrieval time, and frequency of reference may play a role in replacement algorithms. However, at this time, it is only entering in empirically created decision functions. Thus, the need remains for an improved method and system for evaluating the relative value of cacheable objects. The need also remains for a method and system that makes use of reference probabilities in evaluating replacement costs. The present invention addresses these needs.
SUMMARY
In accordance with the aforementioned needs, the present invention is directed to a computerized method, system and program storage device for managing an object store, such as a cache, based on a replacement penalty.
An example of a method having features of the present invention includes the the steps of: collecting one or more performance statistics about one or more storage repositories from which one or more objects can be retrieved; retrieving an object from a storage repository, in response to an object reference; determining a reference probability for an object; determining and associating a replacement penalty with the object wherein the replacement penalty is based on the one or more performance statistics and the reference probability; and storing the object and an associated replacement penalty for the object. The storage repositories include but are not limited to locally attached devices, network sites, and/or remotely attached devices.
The replacement penalty of the present invention can be used to free storage, for example, by reducing the storage used by stored objects or replacing stored objects. An example of a method for reducing the storage used by stored objects includes the additional steps of: receiving a new object reference to a new object, not in the object store; retrieving an object from a storage repository, in response to an object reference; determining there is insufficient free space in the object store for the new object; and reducing the resolution of one or more objects in the object store until sufficient space is available to store the new object; and storing the new object and an associated replacement penalty for the new object.
An example of a method for cache replacement according to the present invention includes the steps of: collecting one or more performance statistics about one or more storage repositories from which one or more ob
Bozman Gerald Parks
Robinson John Timothy
Tetzlaff William Harold
Dougherty Anne Vachon
International Business Machines - Corporation
Portka Gary J.
Yoo Do Hyun
Zarick Gail H.
LandOfFree
Managing an object store based on object replacement... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Managing an object store based on object replacement..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Managing an object store based on object replacement... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2905330