Scaleable method for maintaining and making consistent updates to caches

We claim:

1. In a system including a plurality of caches storing objects and one or more remote data sources storing underlying data which may affect a current value of one or more of said objects, a method for updating said plurality of caches, comprising the steps of:

recognizing when at least part of said underlying data stored in at least one of said remote data sources has changed, said underlying data including data which affects values of the one or more objects;

communicating to said plurality of caches, one or more of: information about said at least part of said underlying data which has changed; and information which includes the identity of at least one object whose value has changed as the result of said underlying data which has changed; and information which allows the identity to be determined of at least one object whose value has changed as the result of said underlying data which has changed, the step of communicating being initiated other than by the plurality of caches; and

updating all of the plurality of caches of the system affected by a change, in response to said communicating step;

wherein the communicating and updating to the plurality of caches, objects and underlying data affected by the change is provided by maintaining an object dependence graph (G) which may change over time and which includes a plurality of graph objects and edges indicating one or more data dependencies between graph objects, said graph objects including records indicating underlying data and said edges including dependencies between the underlying data and the one or more objects, the object dependence graph for providing relationships between the objects to enable updates to all objects affected by the change.

2. The method of claim 1 wherein said step of updating a cache comprises storing a new version of an object in the cache or deleting an object from the cache.

3. The method of claim 1, further comprising the steps of:

maintaining correspondences between the underlying data and one or more objects; and

identifying the at least one object whose value has changed due to changes in the underlying data.

4. The method of claim 1, wherein at least part of said underlying data and one or more objects are the same.

5. The method of claim 3 wherein said step of identifying the at least one object whose value has changed due to changes to the underlying data is in response to said communicating step.

6. The method of claim 3 wherein said communicating step is in response to said step of identifying the at least one object whose value has changed due to changes to the underlying data.

7. The method of claim 1, wherein said updating step comprises consistently performing a set of multiple transactions to a single cache.

8. The method of claim 7 wherein said step of consistently performing a set of multiple transactions further comprises preventing access to parts of the cache being modified using a single lock.

9. The method of claim 7 wherein said step of consistently performing a set of multiple transactions further comprises preventing access to parts of the cache being modified using multiple locks.

10. The method of claim 7 wherein said step of consistently performing a set of multiple transactions is based on a last lock time stamp.

11. The method of claim 1, wherein the communicating step further comprises the step of:

communicating to a cache, one or both of: a new value of an object whose value has changed as a result of said underlying data which has changed; and information which allows the new value to be determined; and

said updating step comprises storing said new value of said object in the cache.

12. The method of claim 1, wherein said updating step further comprises consistently performing a set of one or more transactions across multiple caches.

13. The method of claim 12 wherein said step of consistently performing a set of one or more transactions further comprises preventing access to parts of the caches being modified using a single lock.

14. The method of claim 12 wherein said step of consistently performing a set of one or more transactions further comprises preventing access to parts of the caches being modified using multiple locks.

15. The method of claim 12 wherein said step of consistently performing a set of one or more transactions is based on a last lock time stamp.

16. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps according to any of claims 1, 2, 3, 5, 6-15.

17. The method of claim 1, further comprising the step of checking the object dependence graph to determine objects affected by changes in the underlying data.

18. A method for updating a plurality of caches on one or more remote data sources of a system, which stores data, and data for one or more objects, comprising the steps of:

recognizing when underlying data stored in at least one of the remote data sources of the system has changed, the underlying data including data which affects values in the one or more objects;

identifying all caches in the system affected by the changes in the underlying data;

providing updates to the identified caches by directly sending the underlying data to the caches wherein the updates are unsolicited by the plurality of caches; and

maintaining an object dependence graph (G) which may change over time and which includes a plurality of graph objects and edges indicating one or more data dependencies between graph objects, said graph objects including records indicating underlying data and said edges including dependencies between the underlying data and the one or more objects to track updates to all objects in the plurality of caches affected by the changes.

19. The method as recited in claim 18, further comprising the step of storing a new version of an object in the caches.

20. The method as recited in claim 18, wherein the step of providing updates to the identified caches includes the step of deleting an object from the caches.

21. The method as recited in claim 18, wherein the step of recognizing includes the steps of:

monitoring changes in underlying data in the system by employing a trigger monitor.

22. The method as recited in claim 21, wherein the step of monitoring changes in underlying data in the system by employing a trigger monitor includes the step synchronizing underlying data stored in the caches with cache managers at the remote data sources to determine changes in the underlying data.

23. The method as recited in claim 21, wherein the step of monitoring changes in underlying data in the system by employing a trigger monitor includes employing a master trigger monitor at a first location and one or more slave trigger monitors remotely disposed relative to the first location, the slave trigger monitors for locally monitoring activity of the system.

24. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps according to any of claims 18, 19, 20, 21, 22 or 23.

25. The method of claim 18, further comprising the step of checking the object dependence graph to determine objects affected by changes in the underlying data.

Description Submit all comments and votes

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 p1, p2, and p3. Another processor p4 wishes to change the value of x to 255. Before p4 can update x, it must ensure that p1, p2, and p3 have invalidated x from their caches. It is only at this stage that p4 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 (c1, c2, and c3) 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 c1, c2, and c3 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 many systems to simultaneously benefit from the advantages of prefetching and providing a very high degree of scaleability.

BRIEF DESCRIPTION OF THE DRAWINGS

These and other features and advantages will become apparent from the following detailed description and accompanying drawings, wherein:

FIG. 1a depicts an example of a system having features of the present invention;

FIG. 1b depicts an example of an object dependence graph having features of the present invention;

FIG. 1c depicts an example of a system having features of the present invention;

FIG. 2 depicts an example of a cache used in accordance with the present invention;

FIG. 3 depicts an example of an object information block (OIB) used in accordance with the present invention;

FIG. 4 depicts an example of API functions in accordance with the present invention;

FIG. 5 depicts a block diagram of a method for implementing the API functions of FIG. 4;

FIG. 6 depicts a block diagram of an API function which adds an object to a cache;

FIG. 7 depicts a block diagram of an API function which looks for an object in a cache;

FIG. 8 depicts a block diagram of an API function which deletes an object from a cache;

FIG. 9 depicts a block diagram of an API function which adds a dependency from a record to an object;

FIG. 10 depicts a block diagram of an API function which deletes a dependency from a record to an object;

FIG. 11 depicts a block diagram of an API function which is invoked when a record changes;

FIG. 12a depicts another example of a system having features of the present invention;

FIG. 12b depicts another example of an object dependence graph having features of the present invention;

FIG. 12c depicts an example of the object manager of FIG. 12a;

FIG. 12d is another depiction of an object dependence graph having features of the present invention;

FIG. 13 depicts an example of a cache used in accordance with an embodiment of the present invention;

FIG. 14 depicts an example of an object information block (OIB) used in accordance with the present invention;

FIG. 15 depicts an example of a dependency list used in accordance the present invention;

FIG. 16 depicts an example of a dependency information block (DIB) used in accordance with the present invention;

FIG. 17 depicts another example of API functions in accordance with the present invention;

FIG. 18 depicts a block diagram of a method for implementing the API functions in FIG. 17;

FIG. 19 depicts a block diagram of a cache API function which adds the latest version of an object to a cache;

FIG. 20 depicts a block diagram of an API function which attempts to copy a version of an object from one cache to another;

FIG. 21 depicts a block diagram of an API function which may be invoked when underlying data change;

FIG. 22 depicts a block diagram of part of a method for propagating changes through the object dependence graph in response to changes to underlying data;

FIG. 23 depicts a block diagram of part of a method for propagating changes through the object dependence graph in a depth-first manner in response to changes to underlying data;

FIG. 24 depicts a block diagram of part of a method for propagating changes to a specific graph object in response to changes to underlying data;

FIG. 25 depicts a block diagram of part of a method for updating or invalidating a cached version of an object in response to changes to underlying data;

FIG. 26 depicts a block diagram of part of a method for maintaining consistency when one or more objects are added to one or more caches in response to changes to underlying data;

FIG. 27 depicts a block diagram of a cache API function for creating graph nodes corresponding to single record objects (SRO's);

FIG. 28 depicts a block diagram of an API function for creating graph nodes corresponding to multiple record objects (MRO's);

FIG. 29a depicts a block diagram of an API function which may be invoked when records change;

FIG. 29b depicts another example of an object dependence graph and how it can be used for propagating changes to graph objects;

FIG. 30a depicts a block diagram example of a system having features of the present invention for scaleably maintaining and consistently updating caches;

FIG. 30b depicts a more detailed example of the Trigger Monitor of FIG. 30a instantiated as a Master Trigger Monitor;

FIG. 30c depicts an example of the Trigger Monitor instantiated as a Slave Trigger Monitor;

FIG. 30d depicts an example of the send_trigger API of FIG. 30b;

FIG. 30e depicts examples of transaction types in accordance with the present invention;

FIG. 31 depicts an example of the Object Disposition Block (ODB) of FIG. 30b;

FIG. 32 depicts an example of the cache ID of FIG. 31;

FIG. 33 depicts an example of a high-level organization and communication paths of the Trigger Monitor Driver and the Distribution Manager;

FIG. 34 depicts an example of the Receiving Thread logic of FIG. 33;

FIG. 35 depicts an example of the Incoming Work Dispatcher Thread logic of FIG. 33;

FIG. 36 depicts an example of the Cache Manager Communications Thread logic of FIG. 33;

FIG. 37 depicts an example of the Object Generator Thread logic of FIG. 33;

FIG. 38 depicts an example of the Distribution Manager Thread logic of FIG. 33;

FIG. 39 depicts an example of the Outbound Transaction Thread logic of FIG. 33;

FIG. 40 depicts examples of extensions and variations for analysis and translations of Trigger Events;

FIG. 41 depicts an example of logic for making a set of requests consistently to a system consisting of one or more caches; and

FIG. 42 depicts an example of logic for determining a last_lock_time if the set of cache managers receiving a request has multiple members.

DETAILED DESCRIPTION OF A METHOD FOR DETERMINING

HOW CHANGES TO UNDERLYING DATA AFFECT CACHED OBJECTS

Glossary of Terms

While dictionary meanings are also implied by terms used herein, the following glossary of some terms may be useful:

A cache is a storage area. It may be in memory, on disk, or partly in memory and partly on disk. The physical or virtual addresses corresponding to the cache may be fixed. Alternatively, they may vary over time. The definition of caches includes but is not limited to the following:

Caches for Web documents such as the proxy cache in the IBM Internet Connection Server or the browser cache in the Netscape Navigator;

Database caches such as in IBM's DB2 database;

Processor caches such as those in the IBM RS/6000 line of computers; and

Storage repositories for data written in a high-level programming language, wherein for at least some data, the storage repository program does not have explicit control of the virtual or physical addresses of where the data are stored.

A cache union is the combination of all caches in a system.

An object is data which can be stored in one or more caches.

A multiple version cache is a cache which is allowed to include multiple versions of the same object.

A single version cache is a cache which is only allowed to include one version of the same object.

A current version cache is a single version cache in which the version of any cached object must be current.

Underlying data include all data in the system which may affect the value of one or more objects. Underlying data are a superset of all objects in the system.

A complex object is an object with one or more dependencies on underlying data.

The object manager is a program which determines how changes to underlying data affect the values of objects.

A graph G=(V,E) consists of a finite, nonempty set of vertices V also known as nodes and a set of edges E consisting of pairs of vertices. If the edges are ordered pairs of vertices (v, w), then the graph is said to be directed with v being the source and w the target of the edge.

A multigraph is similar to a graph. The key difference is that multiple edges may exist between pairs of vertices. Multigraphs are supersets of graphs.

A weighted graph or weighted multigraph is one in which each edge may optionally have a number known as a weight associated with it.

The object dependence graph is a directed multigraph. Vertices of the object dependence graph are known as graph objects. Graph objects are supersets of objects and may include the following:

(1) objects;

(2) underlying data which are not objects; and

(3) virtual objects.

These graph objects do not correspond to actual data. They are used as a convenience for propagating data dependencies. Virtual objects are not as frequently used as (1) and (2).

An edge from a graph object o1 to o2 indicates a data dependence (also called dependence or dependency) from o1 to o2. This means that a change to o1 might also change o2. Dependencies are transitive. Thus, if a has a data dependence on b and b has a data dependence on c, then a has a dependence on c.

A graph object may also be a relational object (RO). ROs have relational specifiers affiliated with them. 2 examples of RO's are:

1. Single record objects (SRO's); the relational specifier represents a single record.

2. Multiple record objects (MRO's); the relational specifier represents multiple records.

An RO r1 contains (includes) an RO r2 if all records represented by r2 are also represented by r1.

The outgoing adjacency list for a node v is a list containing all nodes w for which the edge (v, w) is contained in E.

The incoming adjacency list for a node v is a list containing all nodes w for which the edge (w, v) is contained in E.

A leaf node is a node which is not the target of any edges.

A proper leaf node is a leaf node which is the source of at least one edge.

A maximal node is a node which is not the source of any edges.

A proper maximal node is a maximal node which is the target of at least one edge.

A simple dependence graph is a directed graph in which each node is a leaf node or a maximal node.

Two objects o1 and o2 are consistent if either:

(1) Both objects are current; or

(2) At some time t in the past, both objects were current.

A version number is data which allows different versions of the same object to be uniquely identified. One implementation would be to use integers for version numbers and to assign a newly created current version, the version number of the previous version plus 1. However, other implementations are also poss