Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1997-08-01
2001-07-03
Yoo, Do Hyun (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S119000, C707S793000, C707S793000
Reexamination Certificate
active
06256712
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention is related to an improved data processing system. Particular aspects relate to the World Wide Web, databases, and transaction processing systems. A more particular aspect is related to the caching of dynamic documents on the World Wide Web.
2. Related Art
Complex objects can be expensive and time-consuming to create. Caching complex objects reduces the cost of creation by minimizing the frequency of regeneration of identical objects. The cost of generating objects in the absence of caching is reflected to end-users in terms of: (a) increased response time; and (b) inconsistent response time.
Consider a Web-based server with a very high frequency of access, whose content contains a high ratio of dynamic to static pages. Assume further that the content of the dynamic pages change frequently. When a page becomes obsolete and is flushed from cache: the first user who requests that page will experience a cache-miss, causing regeneration of that page. Because the cost (and therefore, the physical wall-clock time) of creating that page is great, there may be a significant probability of several other requests for that same page arriving before it is replaced in cache. This can result in many simultaneous regenerations of the same page, and resultant wasted resources. A specific instance of this scenario is a sports server, for example, serving the Olympics. Results for the currently active sports are arriving at a high rate, causing the pages that reflect scores to change frequently; at the same time users are requesting those pages at a high rate to see the status of the event. Because the pages are being invalidated frequently, a significant number of requests cause the page to be regenerated. Thus there is a need for a system which maintains the validity of the page in one or more caches at all times, and automatically replaces it when the underlying data changes, thereby reducing system loading and significantly improving response time. The present invention addresses such a need.
Another problem is manifested on web servers where consistency of response time is critical. Once users have accessed a site, or a location within a site, keeping their attention may be of prime importance. For example, a Web-based mail-order catalog may want to encourage browsing; if the user gets bored waiting for pages he or she may well leave for other entertainment.
The present invention is of particular importance to proxy caches (see “Caching Proxies: Limitations and Potentials” by M. Abrams et. al., Fourth International World Wide Web Conference Proceedings, Dec. 1996, pp. 119-133; and “World-Wide Web Proxies”, A. Luotonen and K. Altis, in Computer Networks and ISDN Systems, vol. 27 (1994) pp. 147-154). One of the problems with most proxy caches on the Web today is that there is no way to determine if pages in the caches are obsolete. For this reason, most proxy caches do not store dynamic pages. The present invention solves this problem and provides a powerful method for maintaining current copies of both dynamic and static data in multiple caches distributed across a network.
Thus, there is a need for a method and system for automatically detecting changes in the underlying data and efficiently replacing objects dependent on that data in one or more caches as the primary mechanism for cache maintenance. The present invention addresses such a need. Existing cache invalidation schemes typically involve some variant of (a) aging, in which items which have not been referenced within some period of time are removed from cache, and (b) forceful deletion of items known to be obsolete.
A considerable amount of work has been done in the area of cache coherence for shared-memory multiprocessors (see “Computer Architecture: A Quantitative Approach” by J. Hennessy and D. Patterson, Morgan Kaufmann Publishers, Inc., 1996). In shared-memory multiprocessors, no caches are allowed to contain obsolete values. For example, suppose the variable x=99 is stored in caches belonging to processors p
1
, p
2
, and p
3
. Another processor p
4
wishes to change the value of x to 255. Before p
4
can update x, it must ensure that p
1
, p
2
, and p
3
have invalidated x from their caches. It is only at this stage that p
4
can update x.
However, Web caches operate in a different environment from the environment that processor caches operate in. In processor caches, incorrect behavior can result if a cache contains a value which is even a fraction of a second out of date. For Web caches, it is often acceptable for a cached Web document to be slightly out of date. For example, suppose that a Web document w is contained in three caches (c
1
, c
2
, and c
3
) and that the Web document w is managed and updated by a data source d. Using the multiprocessor cache coherence approach, the data source d must first invalidate the Web document w from c
1
, c
2
, and c
3
before updating the Web document. Thus, the multiprocessor cache coherence approach would cause the Web document w to be absent from the cache for a certain period of time whenever the Web document was updated. Requiring the data source d to invalidate the Web document w in caches before performing the update, results in slower updates and cache misses during the extra time that the Web document w is not present in the cache. Thus, there is also a need for a method and system which provides faster updates and higher cache hit rates. The present invention addresses such a need.
SUMMARY OF THE INVENTION
In accordance with the aforementioned needs, the present invention is directed to a method and system for maintaining updated caches and making consistent updates.
The present invention has features for constructing and maintaining objects to associate changes in remote data with cached objects. In one embodiment, if data in a remote data source changes, database change notifications are used to “trigger” a dynamic rebuild of associated objects. The information communicated from the data source to the cache can be either an identifier of an object whose value has changed, or information about the initially changed data. In the latter case, the cache(s) receiving the information about the initially changed data would compute the identity of the objects affected. In either event, rather than deleting stale items from the cache when they become obsolete, they can be immediately replaced with fresh objects. According to another aspect of the present invention, the objects can be compound-complex objects, that is an object composed of multiple complex objects; and the data can be underlying data.
In a system including one or more caches storing objects and one or more remote data sources storing data which may affect the value of a cached object, a method having features of the present invention for coordinating updates to a cache includes the steps of: recognizing when at least part of the data stored in a remote data source has changed; communicating to a cache, one or more of: information about at least part of the data which has changed; and information which includes the identity of at least one object whose value has changed as the result of the changes to the data; and information which allows the identity to be determined of at least one object whose value has changed as the result of the changes to the data; and updating a cache, in response to the communicating step.
According to another aspect of the present invention, the update can include either: storing a new version of the object in the cache; or deleting an object from the cache.
The present invention has features which ensure that end-users never observe that an item is not in the cache, and that each item can be regenerated exactly once, regardless of the current rate of requests.
The present invention has still other features for synchronizing caches on multiple servers with the data in a single common database. Updated information, whether new pages or delete orders, can be broadcast to a set of server nodes, permitting ma
Challenger James Robert Harold
Dantzig Paul Michael
Iyengar Arun K.
Spivak Gerald A.
F. Chau & Associates LL
International Business Machines - Corporation
Portka Gary J.
Yoo Do Hyun
LandOfFree
Scaleable method for maintaining and making consistent... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Scaleable method for maintaining and making consistent..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scaleable method for maintaining and making consistent... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2468883