Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2001-05-15
2003-11-25
McLean-Mayo, Kimberly (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S118000, C711S134000
Reexamination Certificate
active
06654856
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
This invention relates generally to computer data storage and retrieval, and more particularly to the management of a cache to provide effective usage of the cache space.
BACKGROUND OF THE INVENTION
A cache is an amount of data storage space that is used to hold recently accessed data for quick access in subsequent references. The retrieval of data from the cache is typically significantly faster than accessing a data source from which the data in the cache are originally obtained. By storing recently accessed data in the cache, the data can be retrieved and made available quickly the next time they are requested. Data caching is one of the most fundamental concepts in the computer science and has been widely applied in various applications where it is desired to minimize the data access time. The effective use of a cache space is, however, not a simple matter, especially when the cache space and the number of cached data objects become very large.
For instance, in the context of accessing information available from the World-Wide Web (“WWW”) on the Internet, it is common for a proxy server of a private network to cache data objects downloaded from various Websites in response to requests by computers on the private network. When the proxy server receives a request from a computer on the private network for a particular data object, it checks the cache (often referred to as the “cache unit”) to see whether the requested object is already in the cache. If the requested object is not in the cache, the proxy server forwards the request on to the Internet so the requested data object can be downloaded from a Website. On the other hand, if the requested data object is found in the cache unit (which is called a “cache hit”), it is retrieved from the cache and sent to the requesting computer. In this way, the need to keep the user waiting while the requested data object is being downloaded through the Internet is avoided. Since the speed of downloading data objects from Websites can be very slow, a properly implemented cache unit can significantly reduce the average amount of time for a user to receive a requested data object, thereby providing a significantly improved user experience.
The performance requirements on the cache unit, however, can be very high. For instance, a typical implementation of a cache unit may be expected to hold up to 50 millions data objects. With such a large number of data objects, it can become very difficult to effectively manage the cache space to provide an adequate performance of the caching operation.
Tradition approaches to cache space management treat the cache space as disjointed pieces that can be separately allocated and recycled in a generally random manner. As new data objects are continuously being added to the cache, the cache space has to be reclaimed by removing existing cached objects and allocating the reclaimed space to the new objects. Efficient reclaiming of the cache space typically relies upon sophisticated scavenging and garbage collection schemes. The complexity of managing the cache space usage increases as the cache size becomes larger. With the increased overhead for each object caching transaction, the caching operation slows down significantly, and the number of cache hits per unit time is reduced. Moreover, the scavenging and garbage collection operations tend to add spikes to the demand for the computer processing power. Such spikes can interrupt and delay the write and read operations and cause further degradation of the cache performance. Another issue with common cache design paradigms is the fragmentation of the cache space, which becomes increasingly difficult to manage as the cache size grows.
SUMMARY OF THE INVENTION
In view of the foregoing, the present invention provides a system and method for managing a cache space according to a unique space allocation and recycling scheme that has very low complexity for each data caching transaction regardless of the size of the data set. In addition, this invention is virtually fragmentation free, and does not require garbage collection or scavenging techniques. The space allocation and recycling scheme is based on a novel approach that treats the cache space as a linear space with its two ends connected in the manner of a cyclic queue. Each new write operation may involve reclaiming the space used by an existing object or objects for writing the new object. The reclaiming of cache space can be viewed as an “allocation wave” that sweeps in a pre-selected direction over the “circular” cache space. As the allocation wave moves along the circular space, the space used by existing objects are reclaimed for writing new objects except for those existing objects that for some reason are not to be written over. Those existing objects to be passed over by the reclaiming wave are viewed as “interruptions” to the generally first-in-first-out (FIFO) allocation scheme for writing new objects into the circular cache space. Such interruption objects may include, for instance, hot objects that are frequently requested.
By virtue of this linear progression of the allocation wave along a circular space to reclaim cache space for storing new objects, there is no need for any sophisticated and complex garbage collection or scavenging techniques. Moreover, the complexity of each allocation operation does not depend on the size of the data object to be written to the allocated space. Also, as long as the portion of interruption objects is low, the allocation complexity is O(1) in average. In other words, the allocation complexity does not increase with the number of objects in the cache.
In accordance with another aspect of the invention, a cache system architecture is provided that is based on the new approach to cache space management described above. This cache system architecture effectively couples a cache space residing in the main memory of the computer, such as the random-access memory (RAM), with a cache space on a mass storage device, such as a hard disk. The cache space in the main memory is used as a buffer for storing objects that are to be written into or retrieved from the cache space on the disk. The cache space in the main memory and the storage device are each managed as a circular space with “interruptions”. Moreover, the operation of copying objects from the main memory space into the storage device space also progresses as a wave along the circular memory cache space. Objects that should not be written into the disk cache space, such as those that are still being downloaded from the Internet, are viewed as “interruptions” and skipped over by the copy wave.
Additional features and advantages of the invention will be made apparent from the following detailed description of illustrative embodiments, which proceeds with reference to the accompanying figures.
REFERENCES:
patent: 4802086 (1989-01-01), Gay et al.
patent: 5913224 (1999-06-01), MacDonald
patent: 5974508 (1999-10-01), Maheshwari
patent: 6012126 (2000-01-01), Aggarwal et al.
patent: 6061764 (2000-05-01), Chittor et al.
patent: 6349364 (2002-02-01), Kai et al.
patent: 6353874 (2002-03-01), Morein
patent: 6389510 (2002-05-01), Chen et al.
patent: 6438655 (2002-08-01), Nicol et al.
patent: 6446188 (2002-09-01), Henderson et al.
Leydig , Voit & Mayer, Ltd.
McLean-Mayo Kimberly
Microsoft Corporation
LandOfFree
System and method for managing storage space of a cache does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for managing storage space of a cache, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for managing storage space of a cache will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3116179