Cache management techniques

Details Cache management techniques Cache management techniques

1999-04-23

2001-05-22

Yoo, Do Hyun (Department: 2185)

Electrical computers and digital processing systems: memory

Storage accessing and control

C711S117000, C711S118000, C711S133000, C711S135000, C711S136000, C711S159000, C711S160000, C707S793000, C707S793000, C709S213000, C709S216000, C709S227000, C709S203000

Reexamination Certificate

active

06237060

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of Invention
The invention relates generally to memory systems. More particularly, methods and apparatus for managing the available memory space in a cache memory is disclosed.
2. Description of Relevant Art
The explosive growth in Internet traffic has made it critical to look for ways of accommodating the increasing number of users while preventing excessive delays, congestion and widespread blackouts. For the past several years a large proportion of Internet traffic has been generated by web-browsing and most of the web browsing traffic is in turn comprised of images. This trend will continue with more sites becoming media rich as the users' access bandwidths increase and media-enabled PCs become more common. This has led to a great deal of effort being devoted to studying web caching techniques.
One such web caching technique is referred to as proxy based caching. With proxy based caching, clients can designate a host to serve as a proxy for all or some of their requests (e.g., http, ftp, etc). The proxy acts as a cache by temporarily storing on local disks, or memory, objects that were requested by the clients. It should be noted that in the context of the Internet, an object is a file, text, image, audio, executable program, and the like which is available to be downloaded by a client. When one of the clients sharing the proxy generates a request, the proxy searches its local storage for the requested object. If the object is available locally (hit) it is sent to the client, otherwise (miss) the request is passed on to the remote server or to another proxy server, if the proxy cache belongs to a hierarchy of caches. Unfortunately, if the ratio of number of misses to hits is even relatively small, then the performance of the browser can be substantially degraded as the requested documents must be retrieved from other proxies or the remote servers.
Another well known web caching technique used to improve performance is referred to as client side caching. Client side caching is the temporary storage of web objects (such as HTML documents) in local cache memory for later retrieval. Advantages to client side caching include: reduced bandwidth consumption since fewer requests and responses that need to go over the network are created, reduced server load since fewer requests for a server to handle are made, and reduced latency since responses for cached requests are available immediately and closer to the client being served. In most cases, client side caching can be performed by the client application and is built into, for example, Netscape's Communicator, Microsoft's Internet Explorer, various Java browsers, as well as most other web browsers.
Since web browsers (and the computers that support them) have only finite disk space, they must eventually discard old copies of stored documents to make room for new requests. Most systems use a policy based on discarding the least recently requested document as being the least likely to be requested again in future. Given sufficient disk space, documents are discarded around the time when they would, in any case, have been replaced by a more up-to-date version. However, if disk space is insufficient then the cache may be forced to discard a current document and make an unnecessary connection to the source host when the document is next requested. The amount of disk space required depends on the number of users served and the number of documents requested. Ideally a cache should have room to store every document which the users of the cache request more than once during the lifetime of the document. Such a cache would never retrieve a second copy of an unchanged document and thereby generate the minimum possible network traffic. To achieve this in practice would, of course, involve storing every requested document locally since there is no way to predict which documents will be re-read in the future.
Since storing every requested document for at least its lifetime is impractical, the number of documents which must be reclaimed (or garbage collected) from the cache memory is directly related to the available cache memory space. As is well known in the art, garbage collection is a process whereby inactive, or otherwise unneccessary objects, are identified, collected, and deactivated. If too many documents, or if those documents which are frequently requested are garbage collected, system performance is degraded since the document must be retrieved from the network if it is not stored in the local cache memory. Conversely, if documents that are not frequently requested are not periodically garbage collected, then the limited memory space available in the local cache memory can be quickly saturated. When this occurs, no new documents can be stored and, again, system performance is degraded since requested documents not stored in the local cache memory must again be retrieved from the network.
Therefore, what is desired is an efficient method and apparatus for intelligently purging documents from a local cache memory in a browser environment based upon the available cache memory and browser traffic.
SUMMARY OF THE INVENTION
Broadly speaking, the invention relates to an improved method, apparatus and computer system for efficiently managing available memory space in a cache memory. The invention can be implemented in numerous ways, including as a method, a computer system, and an apparatus. Several embodiments of the invention are discussed below.
According to one aspect of the present invention, a computer-implemented cache memory manager is disclosed. The cache memory manager includes a document key stack having a depth of stack locations each being arranged to store a document key associated with a document stored in the cache memory indicating the associated document has a strong reference associated with it. The manager also includes a master document file having a plurality of file locations each being arranged to store a document identifier used to uniquely identify an associated document stored in the cache memory indicating the associated document has only a weak reference associated with it. A garbage collector is also included that reclaims those documents stored in the cache memory that are only weakly referenced and not those documents that are strongly referenced. In this way, cache memory space commensurate with the reclaimed documents is periodically made available to store more recently requested documents.
In another embodiment, the number of stack locations are adjusted to provide sufficient cache memory space to accommodate the most recently requested files in the cache memory.
In another aspect of the invention, a method for managing available cache memory space in a cache memory is disclosed. If a document key associated with a requested document is present in the document key stack, then the document key associated with the requested document is moved to a first stack location. Those documents stored in the cache memory that do not have corresponding document keys present in the document key stack are reclaimed by the garbage collector, such that cache memory space commensurate with the reclaimed documents is periodically made available to store more recently requested documents.
These and other advantages of the present invention will become apparent upon reading the following detailed descriptions and studying the various figures of the drawings.


REFERENCES:
patent: 99/10811 (1999-03-01), None
Wilson, P. Uniprocessor garbage collection techniques. In International Workshop on Memory Management. France, Sep. 1992. [Online] http://citeseer.nj.nec.com/wilson92uniprocessor.html.*
Jones R. The Garbage Collection Bibliography. [Online] http://www.cs.ukc.ac.uk/people/staff/rej/gcbib/gcbib.html.

Affiliated with

Also associated with

Rating

Cache management techniques does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Cache management techniques, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cache management techniques will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2490640