Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2001-11-06
2003-07-22
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S134000, C711S138000, C711S156000
Reexamination Certificate
active
06598121
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the field of system caching. Specifically, the present invention provides a system and method for coordinated hierarchical caching in a client/server environment, particularly on the World Wide Web. Furthermore, the present invention provides a cache replacement method which adapts to changing system resource bottlenecks.
Glossary of Terms
While dictionary meanings are also implied by terms used here, the following glossary of some terms may be useful.
Client
A client is a computer which typically issues commands to one or more servers which perform the task associated with the command.
Server
Any computer that performs a task at the command of one or more computers is a server. A Web server typically supports one or more clients.
World Wide Web (Web)
The Internet's application that lets people seeking information on the Internet switch from server to server and database to database. Users can click on highlighted words or phrases of interest (hyperlinks), click on graphics such as applets or image maps, fill in forms, and enter URLs. An Internet Web server supports clients and provides information. The Web can be considered as the Internet with all of the resources addressed as URLs and which uses HTTP protocols to transfer information between computers and which uses HTML (among other formats) to display the information corresponding to URLs and provide a point-and-click interface to other URLs.
Universal Resource Locator (URL)
A way to identify or address information on the Internet.
HyperText Markup Language (HTML)
HTML is a standard device-independent representation of content on Web servers. Web servers may deliver content (including hyperlinks) to clients in HTML with confidence that the client will choose an appropriate presentation.
Hypertext Transfer Protocol (HTTP)
HTTP is an example of a stateless protocol, which means that every request from a client to a server is treated independently. Clients send request to servers and servers respond using this protocol.
Internet Browser or Web Browser
A graphical interface tool that runs Internet protocols such as HITP, and displays results on the customer's screen. The browser can act as an Internet tour guide, complete with pictorial desktops, directories and search tools used when a user “surfs” the Internet. In this application, the Web browser is a client service which communicates with the Web servers.
Object
An object is data which can be stored in a cache.
Cache Replacement Policy
A cache replacement policy is an algorithm for determining which objects should be placed in a cache when the cache contains insufficient space to contain all objects.
BACKGROUND OF THE INVENTION
Caching is commonly used for improving performance on computer systems. By caching an object, the cost for fetching or creating the object is only incurred once. Subsequent requests for a cached object can be satisfied from the cache, a process which incurs significantly less overhead than regenerating the object or fetching it from a remote location.
Systems on the World Wide Web (“Web”) today often contain browser and proxy caching (see “Caching Proxies: Limitations and Potentials” by M. Abrams et. al., “Fourth International World Wide Web Conference Proceedings,” December 1996, pp. 119-133 and “World Wide Web Proxies” by A. Luotonen and K. Altis in “Computer Networks and ISDN Systems,” vol. 27 (1994), pp. 147-154) to improve performance. While these caching systems are sometimes hierarchical in nature, normally caching at one level is not coordinated with caching at the next level. In other words, each cache makes decisions independently of what another cache is doing.
In U.S. patent application Ser. No. 08/831,237 entitled “Collaborative Caching” by Yu et al., filed Apr. 2, 1997, a method for collaborative caching in a hierarchy of proxy caches is disclosed. The disclosed system bases a client's or proxy's caching decision on whether the object is cached at another proxy location in the hierarchy closer to the Web server which stores or generates the object. No cache is disclosed to be local to the Web server and the client or proxy must rely on header information contained in the object and caching status information provided by the other proxy location for its caching decision. While this system addresses general network access (browsing) speed, it does not address the problem of slow service of Web pages (such as dynamic pages) to clients from a particularly hot Web server site. The Yu system would have to be implemented across the internet's multitude of proxy servers to provide improved service from a particular Web site. Finally, it would be practically impossible to update, with the Yu system, dynamic pages (those generated “on the fly”) in view of network bottlenecks and the decoupled nature of the proxies to the Web server. Thus, there is a need for a client/server system that implements a true hierarchy of caches from a Web server level to the client browser level, supports dynamic pages and coordinates the actions of the caches so that superior performance can be attained.
Level
1
, level
2
, etc. caches in uniprocessors are well known to those skilled in the art. However, while level
1
and level
2
processor caches are often coordinated to some extent (for example, the decision to place an object in one processor cache might be made depending on whether the object is contained in another processor cache), the client/server environment has characteristics which pose different problems to a caching system. First, in the client/server environment, there can be multiple level
2
(server) caches located behind a level
1
(e.g., router) cache, all with different contents. In contrast, a uniprocessor contains, at most, one level
2
cache. Second, compared with processor caches, there are more constraints over what can be stored in these router and server caches. For example, in a Web-based client/server environment, it may be necessary to keep some URLs out of a router cache in order to force a particular request to be directed to a server. It is also undesirable to cache objects (e.g., static pages) in server caches which are inexpensive for the Web server to generate. This would not be the case for processor caches because level
2
caches are generally faster than main memory. Third, the parameters affecting admittance to the cache and cache replacement are significantly different for the two environments. In processor caching, least recently used (LRU) information generally suffices. In Web-based client/server systems, considerations such as the expected number of accesses per unit time, expected lifetime, object size and time to create or fetch the object are important to consider.
Another prior art system is the Parallel-Sysplex in the System 390 (Special Issue on S/390 Parallel Sysplex Cluster, IBM Systems Journal, Vol. 36, No. 2, 1997). The Parallel Sysplex has level
1
database caches in each of the processing nodes and a level
2
cache in the coupling facility, which is shared among the nodes. While the level
1
and level
2
caches in the Sysplex are coordinated, there are several differences between the Sysplex and a client/server system.
In the Sysplex, the database system runs at the same node as the level
1
cache, the level
2
cache is on a shared coupling facility and the permanent data is located on shared disks accessed from the node at which the level
1
caches reside. In a client/server system, however, remote clients may have to make requests which initially go to the level
1
cache, while the permanent locations of the data are at the nodes at which the level
2
caches reside. Furthermore, the criteria for placing objects in the level
1
or level
2
caches are very different for the two systems. In the Sysplex, hot shared records/objects, especially those frequently updated, are placed in the level
2
coupling facility cache. In the client/server case, there is no concept of sharing (i.e. programs at different Sysplex
Challenger James R. H.
Dantzig Paul Michael
Dias Daniel Manuel
Iyengar Arun Kwangil
Levy-Abegnoli Eric M.
Anderson Matthew D.
F. Chau & Associates LLP
International Business Machines Corp.
Kim Matthew
LandOfFree
System and method for coordinated hierarchical caching and... 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 coordinated hierarchical caching and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for coordinated hierarchical caching and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3006414