Determining how changes to underlying data affect cached objects

• US 6,026,413 A
• Filed: 08/01/1997
• Issued: 02/15/2000
• Est. Priority Date: 08/01/1997
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Iyengar, Arun K., Challenger, James Robert Harold, Dantzig, Paul Michael, Spivak, Gerald A.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Coby, Frantz
• Application Number:
  US08/905,114
• Time in Patent Office: 928 Days
• Field of Search: 707/202, 707/10, 707/103, 707/104, 707/203
• US Class Current: 717/108
• CPC Class Codes: G06F 12/0815 Cache consistency protocols
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: Y10S 707/922 Communications
• CPC Class Codes: Y10S 707/951 Calendar or scheduling
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A determination can be made of how changes to underlying data affect the value of objects. Examples of applications include: caching dynamic Web pages; client-server applications whereby a server sending objects (which are changing all the time) to multiple clients can track which versions are sent to which clients and how obsolete the versions are; and any situation where it is necessary to maintain and uniquely identify several versions of objects, update obsolete objects, quantitatively assess how different two versions of the same object are, and/or maintain consistency among a set of objects. A directed graph, called an object dependence graph, may be used to represent the data dependencies between objects. Another aspect is constructing and maintaining objects to associate changes in remote data with cached objects. If data in a remote data source changes, database change notifications are used to "trigger" a dynamic rebuild of associated objects. Thus, obsolete objects can be dynamically replaced with fresh objects. The objects can be complex objects, such as dynamic Web pages or compound-complex objects, and the data can be underlying data in a database. The update can include either: storing a new version of the object in the cache; or deleting an object from the cache. Caches on multiple servers can also be synchronized 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 high degree of scaleability.

Claims

1. In a computer system having one or more caches storing one or more complex objects, a method for determining how changes to underlying data can affect values of one or more complex objects, comprising the steps of:

identifying at least part of the underlying data, wherein the underlying data may or may not be cachable;

mapping said at least part of the underlying data to one or more of said complex objects having one or more data dependencies on said at least part of the underlying data; 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.

2. The method of claim 1 further comprising a plurality of computers wherein a first set of computers associated with a first cache is disjoint from a second set of computers associated with said mapping step.

3. The method of claim 1 wherein said mapping step, further comprises the step of a program scheduling operations where different schedules might result in different changes to underlying data.

4. The method of claim 3 wherein said program scheduling operations is a compiler, run-time system, or database.

5. The method of claim 1 in which said mapping step comprises:

using said graph to map said at least part of the underlying data to at least one complex object.

6. The method of claim 1, further comprising the step of assigning weights to the edges wherein the weights are correlated with an importance of data dependencies.

7. The method of claim 6 wherein a weight of at least one edge does not change after it is assigned.

8. The method of claim 6, wherein:

(1) two versions o1_-- v1 and o1_-- v2 of a graph object o1 exist; and

(2) the object dependence graph G contains at least one edge (o2, o1) terminating in o1 and having an assigned weight;

further comprising the steps of;

for one or more edges (o2, o1) terminating in said o1 and comprising a set S, maintaining a version number of said object (s) o2 which is consistent with o1_-- v1 and a second version number of said object (s) o2 which is consistent with o1_-- v2;

determining how similar o1_-- v1 and o1_-- v2 are based on a sum of the weights of edges (o2, o1) in said set S such that a same version of said graph object o2 is consistent with said versions o1_-- v1 and o1_-- v2 and a sum of the weights of all edges terminating in o1 in said set S.

9. The method of claim 8 wherein said step of determining how similar said two versions are, further comprises the step of dividing said sum of the weights of edges (o2, o1) in said set S such that a same version of said graph object o2 is consistent with said versions o1_-- v1 and o1_-- v2 by said sum of the weights of all edges terminating in o1 in said set S.

10. The method of claim 1, wherein said mapping farther comprises the step of:

using information about how one or more complex objects would be affected by changes to said at least part of the underlying data to determine whether or how to make changes to said at least part of the underlying data.

11. The method of claim 1, wherein a program implementing said mapping step generates one or more of:

multiple processes;

multiple threads; and

one or more long-running processes or threads managing storage for said one or more caches.

12. The method of claim 11, wherein a program implementing said mapping step generates at least one long-running process, further comprising the steps of:

an application program identifying a change to at least part of the underlying data; and

the application program communicating an identified change to at least part of the underlying data to said program implementing said mapping step.

13. The method of claim 1 wherein said mapping further comprises the step of:

identifying a change to said at least part of the underlying data; and

identifying how one or more complex objects are affected, in response to said identifying a change to said at least part of the underlying data.

14. The method of claim 13, wherein said at least part of the underlying data is stored in one or more remote data sources, further comprising the steps of:

communicating to a cache, one or more of;

information about 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; and

removing an object from the cache, or updating a new version of an object in the cache, in response to said communicating step.

15. The method of claim 1 further comprising the step of determining that a version of a complex object stored in a cache would become highly obsolete as a result of changes to said at least part of the underlying data.

16. The method of claim 15 further comprising the step of deleting a highly obsolete version of an object from the cache.

17. The method of claim 15 wherein the version of an object is considered to be highly obsolete whenever it is not current.

18. The method of claim 15 wherein said determining that a version of an object (o1_-- v1) would become highly obsolete comprises the steps of:

maintaining an object dependence graph (G) which may change over time and which includes a plurality of graph objects (o1 . . . on) and edges indicating one or more data dependencies between graph objects; and

determining that said o1_-- v1 would become highly obsolete based on a number of edges (o2, o1) such that o1_-- v1 is inconsistent with a current version of o2.

19. The method of claim 15, further comprising the step of replacing a highly obsolete version of the object with a more recent version.

20. The method of claim 19 wherein the more recent version is a current version of the object.

21. The method of claim 15 where in said step of determining that a version o1_-- v1 of an object o1 stored in a cache would become highly obsolete, comprises the steps of:

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;

initializing and maintaining weight_-- act fields for said o1_-- v1 corresponding to one or more edges terminating in said o1;

for one or more changes to a current version of a graph object o2 such that an edge from said object o2 to said object o1 exists such that o1_-- v1 has a weight_-- act field, decrementing the weight_-- act field corresponding to the edge; and

determining if said o1_-- v1 would become highly obsolete based on its weight_-- act fields.

22. The method of claim 21, further comprising the steps of:

maintaining a threshold weight for said o1_-- v1;

wherein said determining if said o1_-- v1 would become highly obsolete based on its weight_-- act fields includes the step of comparing a sum of the weight_-- act fields for said o1_-- v1 to said threshold weight.

23. The method of claim 21, further comprising the steps of:

assigning weights to the edges of the object dependence graph wherein the weights are correlated with an importance of data dependencies; and

initializing one or more weight_-- act fields for said o1_-- v1 to one or more weights of corresponding edges in the object dependence graph.

24. The method of claim 21, further comprising the step of setting the weight_-- act field corresponding to an edge from said o2 to said o1 in the object dependence graph, that is greater than a predetermined minimum possible value, to said predetermined minimum possible value whenever the current version of o2 is updated.

25. The method of claim 15 where the step of determining that a version of a complex object o1 stored in a cache would become highly obsolete comprises the step of determining a number of edges (o2, o1) such that said version of o1 is inconsistent with the current version of said o2.

26. The method of claim 25 wherein said stop of determining that a version of a complex object o1 stored in a cache would become highly obsolete further is based on the total number of edges terminating in said o1.

27. The method of claim 1 wherein said one or more caches includes one or more of:

a multiple version cache;

a single version cache; and

a current version cache.

28. The method of claim 27 wherein said one or more caches includes at least one single version cache c1, further comprising the step of:

for at least one of the objects o1, maintaining a consistency set of other objects o2 such that o1 and o2 must be consistent whenever they are both contained in c1.

29. The method of claim 28 further comprising the step of ensuring that if said o1 and said o2 are both in c1, then said o1 and said o2 are consistent.

30. The method of claim 28, further comprising the step of:

using the consistency set for an object o1 to decide whether or not to add a version of the object o1 to the single version cache, possibly replacing a previous version of the object o1.

31. The method of claim 29 further comprising the steps of:

for multiple objects o1, . . . , on in a single version cache c1;

replacing each object oi with a different version in c1 without ensuring that all constraints imposed by a consistency set for the object oi are satisfied at the time said oi is updated but instead adding objects obj1 from a consistency set for said oi for which an inconsistent version of obj1 might exist in c1 to a consistency stack;

after all objects o1, . . . , on in c1 have been replaced with current versions, traversing all objects on the consistency stack and for each such object obj1 for which an inconsistent version exists in c1, removing it from c1 or replacing it with a consistent version.

32. The method of claim 31 further comprising the step of implementing the consistency stack by storing references to said objects on a linked list.

33. The method of claim 31 further comprising the steps of:

using one or more balanced trees for implementing said consistency stack; and

for at least one object obj1, verifying that a reference to said obj1 is not already included on the consistency stack before adding a reference to said obj1 to the consistency stack.

34. The method of claim 29 further comprising the steps of:

adding a current version of said object o1 to the single version cache, possibly replacing a previous version of the object o1;

identifying one or more objects o2 in the consistency set for o1 such that a noncurrent version o2_-- v of said object (s) o2 is contained in said cache c1 and said o2_-- v was created before the current version of said o1 was created;

removing said o2_-- v from said cache c1 or replacing o2_-- v with a more recent version of said object (s) o2;

recursively applying to objects in the consistency set for said object (s) o2, said step of identifying one or more objects and said step of removing said o2_-- v from said cache c1 or replacing o2_-- v with a more recent version of said object (s) .

35. The method of claim 29 wherein said consistency set (s) are implemented using one or more linked lists.

36. The method of claim 1 wherein said G is one of:

a simple dependence graph; and

a multigraph.

37. The method of claim 36 wherein said G is a simple dependence graph in which proper maximal nodes are complex objects and proper leaf nodes are underlying data which are not objects.

38. The method of claim 37 wherein said maintaining an object dependence graph comprises the steps of:

maintaining an outgoing adjacency list for at least one proper leaf node v; and

maintaining an incoming adjacency list for at least one proper maximal node w.

39. The method of claim 38, further comprising the step of accessing one of outgoing adjacency lists and incoming adjacency lists via a hash table.

40. The method of claim 38 wherein said maintaining an object dependence graph further comprises the steps of:

when initially changed data includes some data d which could be represented by a proper leaf node changes, searching for the outgoing adjacency list corresponding to d.

if the outgoing adjacency list is found, examining the list to determine which complex objects are affected.

41. The method of claim 38, further comprising the step of deleting at least one proper maximal node w from the object dependence graph.

42. The method of claim 41 wherein said step of deleting at least one proper maximal node w from the object dependence graph further comprises the steps of:

deleting said w from the outgoing adjacency list for at least one proper leaf node on the incoming adjacency list for w;

deleting the incoming adjacency list for said w.

43. The method of claim 39, further comprising the step of deleting at least one proper leaf node v from the object dependence graph.

44. The method of claim 43 wherein said step of deleting at least one proper leaf node v from the object dependence graph, further comprises the steps of:

deleting v from the incoming adjacency list for one or more proper maximal nodes on the outgoing adjacency list for v;

deleting the outgoing adjacency list for said v.

45. The method of claim 1 wherein a graph object r is a relational object (RO) which has an associated relational specifier which can represent one of single (SRO) or multiple (MRO) records and wherein said maintaining an object dependence graph further comprises the steps of:

(a) storing the relational specifier for said r;

(b) if one or more graph objects include said r, adding one or more dependencies from said r to one or more graph objects which include said r; and

(c) if said r includes one or more graph objects, adding one or more dependencies to said r from said one or more graph objects included by said r.

46. The method of claim 45, further comprising the steps of:

assigning weights to the edges wherein the weights are correlated with an importance of data dependencies; and

wherein one of said steps (b) and (c) include the step of determining the weight of at least one of the dependencies corresponding to an RO node r1 containing an RO node r2, according to one or both of;

a percentage of records of said r1 contained by said r2; and

a relative importance of said records.

47. The method of claim 45 further comprising one or both of the steps of:

(d) adding one or more dependencies from said r to another RO r2 wherein said another RO r2 does not include said r using a metric based on one or both of;

a percentage of records in said r which are also contained in said r2; and

a relative importance of the records in said r which are also contained in said r2;

(e) adding one or more dependencies from another RO r3 to r wherein said r does not include said r3 using a metric based on one or both of;

a percentage of records in said r3 which are also included in said r; and

a relative importance of the records in said r3 which are also contained in said r.

48. The method of claim 47, further comprising the steps of:

assigning weights to the edges wherein the weights are correlated with an importance of data dependencies; and

calculating the weight of said one or more dependencies added in one or both of steps (d) and (e) using said metric.

49. The method of claim 45 wherein said r is one of:

a newly created node;

an existing node being modified;

an SRO node; and

an MRO node.

50. The method of claim 46 wherein one or more relational specifiers include relation names such that pairs of ROs having a common record have a high probability of possessing a same relation name.

51. The method of claim 50 further comprising the step of segregating ROs using one of:

relation names; and

a balanced tree in conjunction with the relation names.

52. The method of claim 45 wherein said step of identifying at least part of the underlying data comprises the steps of:

identifying a relational specifier; and

locating one or more ROs in the object dependence graph having one or more records in common with the relational specifier.

53. The method of claim 1, wherein said mapping comprises the steps of:

visiting a set of one or more nodes (update_-- set) in the object dependence graph corresponding to said at least part of the underlying data; and

traversing the edges in the object dependence graph in order to visit nodes reachable from said update_-- set.

54. The method of claim 53 wherein said traversing comprises the step of traversing the object dependence graph in one of:

a depth-first manner; and

a breadth-first manner.

55. The method of claim 53 further comprising the steps of:

maintaining a timestamp which uniquely identifies each object dependence graph traversal;

storing the timestamp at a vertex of the object dependence graph whenever the vertex is visited for the first time during a traversal; and

determining whether a vertex has been visited during the current traversal by comparing the timestamp at the vertex to the timestamp for the current traversal.

56. The method of claim 55, further comprising the step of incrementing the time stamp for each new graph traversal.

57. The method of claim 1, wherein two versions o1_-- v1 and o1_-- v2 of a graph object o1 exist, and the object dependence graph G contains at least one edge (o2, o1) terminating in o1, further comprising the steps of:

for one or more edges (o2, o1) terminating in said o1 and comprising a set S, maintaining a version number of said object (s) o2 which is consistent with o1_-- v1 and a second version number of said object (s) o2 which is consistent with o1_-- v2;

determining how similar o1_-- v1 and o1_-- v2 are based on a number of edges (o2, o1) in said set S such that a same version of a graph object o2 is consistent with said versions o1_-- v1 and o1_-- v2 and a number of all edges terminating in o1 in said set S.

58. The method of claim 57 in which said step of determining how similar o1_-- v1 and o1_-- v2 are, comprises the step of dividing a number of edges (o2, o1) in said set S such that a same version of a graph object o2 is consistent with said versions o1_-- v1 and o1_-- v2 by a number of all edges terminating in o1 in said set S.

59. The method of claim 1 in which at least some of the objects are Web documents and at least some of the underlying data are part of one or more databases.

60. The method of claim 1, further comprising the step of using information on how a set s_-- update of one or more graph objects would be affected by changes to the underlying data, in conjunction with the object dependence graph to determine how at least one other graph object having dependencies, specified either directly or transitively by the object dependence graph, on one or more objects in said s_-- update would be affected.

62. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for determining how changes to underlying data can affect values of one or more complex objects, according to any of claims 1-2, 4-11, 13, 18, 21-24, 28-31, 34, 52, 53, or 55.

61. In a computer system including one or more caches storing one or more complex 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 comprising the steps of:

maintaining an object dependence graph which may change over time and which includes a plurality of graph objects and edges indicating one or more data dependencies between said graph objects,

recognizing when at least part of said underlying data has changed;

communicating to a cache, one or more of;

information about 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; and

removing an object from the cache, or updating a new version of an object in the cache, in response to said communicating step.

63. In a computer system having one or more caches storing one or more complex objects, a method for determining how changes to underlying data can affect values of one or more complex objects, comprising the steps of:

identifying at least part of the underlying data, wherein the underlying data may or may not be cachable; and

mapping said at least part of the underlying data to one or more of said complex objects having one or more data dependencies on said at least part of the underlying data, wherein at least some of the objects are Web documents and at least some of the underlying data are part of one or more databases.