Scaleable method for maintaining and making consistent updates to caches

• US 6,216,212 B1
• Filed: 08/18/1999
• Issued: 04/10/2001
• Est. Priority Date: 08/01/1997
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Spivak, Gerald A., Iyengar, Arun K., Challenger, James Robert Harold, Dantzig, Paul Michael
• Primary Examiner(s): Yoo, Do Hyun
• Assistant Examiner(s): Portka, Gary J.
• Application Number:
  US09/376,849
• Time in Patent Office: 601 Days
• Field of Search: 707/8, 707/201, 710/200, 711/141, 711/144, 711/145, 711/163, 711/167
• US Class Current: 711/163
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

Abstract

A determination can be made of bow changes to underlying data affect the value of objects. Examples of applications are: 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 system comprising a set of one or more transaction managers, a method for consistently performing a set S of one or more state-changing transactions which modify state managed by a set T of one or more transaction managers comprising the steps of:

(a) acquiring a plurality of locks on data known as locked data which prevent transactions not in S from one of (i) modifying data accessed by a transaction in S and (ii) reading data modified by a transaction in S;

(b) storing a blocked request set B comprising one or more transaction requests which cannot be completed because of locks acquired in step (a);

(c) determining a timestamp at which a last lock (last_lock_time) was obtained in step (a) from the plurality of locks;

(d) enabling transactions in B, which could not be completed in step (b) and were received before the last_lock_time, to access locked data before transactions in S access the locked data;

(e) enabling transactions in S to access the locked data before enabling transactions in B received after last_lock_time to access the locked data; and

(f) enabling transactions in B received after the last_lock_time to access the locked data after transactions in S have accessed the locked data.

2. The method of claim 1 wherein said T includes a plurality of transaction managers and step (c) further comprises the step of:

for a subset T of said T including a plurality of transaction managers, each member ti of said T′

determining a timestamp for the last lock (last_lock_time_i) it obtained in step (a).

3. The method of claim 2 further comprising the steps of:

(g) a coordinator program receiving values of the last_lock_time_i from the plurality of transaction managers ti in said T′

;

(h) the coordinator program determining the last_lock_time from the values received in step (g); and

(i) the coordinator program sending a value of last_lock_time determined in step (h) to one or more transaction managers in said T′

.

4. The method of claim 2 further comprising the steps of;

(j) a transaction manager ti receiving last_lock_time_j values from one or more other transaction managers tj; and

(k) the transaction manager ti determining the last_lock_time from the values received in step (j).

5. The method as recited in claim 1, wherein at least part of the data which is locked is stored in at least one cache.

6. The method as recited in claim 5, wherein at least one of the transaction managers includes at least one cache manager.

7. A program storage device readable by machine, tangibly embodying a program of instructions executable by machine to perform method steps for consistently performing a set S of one or more state-changing transactions which modify state managed by a set T of one or more transaction managers, according to any of claims 1.

8. In a system comprising a set of at least one transaction manager, a method for consistently performing a set S of at least one state-changing transactions which modify state managed by a set T of at least one transaction manager comprising the steps of:

(a) acquiring a plurality of locks on data known as locked data which prevent transactions outside of S from one of (i) modifying data accessed by a transaction in S and (ii) reading data modified by a transaction in S;

(b) storing a blocked request set B comprising at least one transaction request which cannot be completed because of locks acquired in step (a);

(c) determining a timestamp at which a last lock (last_lock_time) was obtained in step (a) from the plurality of locks; and

(d) enabling transactions in B, which could not be completed in step (b) and were received before the last_lock_time, to access locked data before transactions in S access the locked data.

9. The method as recited in claim 8, further comprising the step of enabling transactions in S to access the locked data before enabling transactions in B received after the last_lock_time to access the locked data.

10. The method as recited in claim 9, further comprising the steps of enabling transactions in B received after the last_lock_time to access the locked data after transactions in S have accessed the locked data.

11. The method as recited in claim 8, further comprising the steps of:

sending the last_lock_time to a program coordinator which evaluates last lock times and determines a latest lock time from the last lock times sent to the program coordinator from each transaction manager;

sending the latest lock time to the transaction managers; and

performing requests received prior to the latest lock time wherein requests for reading and modifying the data which is locked see a same view after all requests prior to the latest lock time are performed.

12. The method as recited in claim 8, wherein the last_lock_time is provided by a timestamp.

13. The method as recited in claim 8, wherein at least a portion of the data which is locked is stored in at least one cache.

14. The method as recited in claim 8, wherein at least one of the transaction managers includes at least one cache manager.

15. The method as recited in claim 8, further comprising the steps of:

exchanging last_lock_times of each of the transaction managers with other transaction managers to evaluate the last_lock_times and determine a latest lock time from the last_lock_times from all the transaction managers;

sending the latest lock time to other transaction managers; and

performing requests received prior to the latest lock time wherein requests for reading and modifying the data which is locked see a same view after all requests prior to the latest lock time are performed.

16. A program storage device readable by machine, tangibly embodying a program of instructions executable by machine to perform method steps for managing locks to maintain consistency in a system performing transactions, according to any of claims 8-15.