System and method for achieving deferred invalidation consistency

• US 7,318,074 B2
• Filed: 11/17/2003
• Issued: 01/08/2008
• Est. Priority Date: 11/17/2003
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Iyengar, Arun Kwangil, King, Richard P., Rosu, Daniela, Witting, Karen
• Primary Examiner(s): PARDO, THUY N
• Application Number:
  US10/715,260
• Publication Number:
  US 20050108191A1
• Time in Patent Office: 1,513 Days
• Field of Search: 707/1, 707/3, 707/10, 707/203, 707/204, 707/205, 716/6, 710/1, 713/178, 714/13, 709/246, 709/200, 711/144, 717/46, 717/171
• US Class Current: 707/690
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: Y10S 707/955 Object-oriented
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99954 Version management

Abstract

In a system having a plurality of caches, a method for maintaining cached objects includes storing an object in a plurality of caches. In response to a request to update the object, a future invalidation time is determined when the object should be invalidated in caches currently storing the object. Updating of the object is delayed until the invalidation time has passed.

Claims

1. In a system having a plurality of storage elements, a method for maintaining stored objects in the plurality of storage elements, comprising the steps of:

storing an object in a plurality of storage elements;

in response to a request to update the object determining a future invalidation time when the object will be invalidated in storage elements currently storing the object, the invalidation time including a time selected such that each of the plurality of storage elements has either received notification of an update pursuant to the request or has declared itself failed;

delaying updating the object until the invalidation time has passed; and

updating the object after the invalidation time has passed to maintain consistency for the object across the plurality of storage elements by allowing the storage elements to serve an old version of the object until all active storage elements are ready to serve a new updated version of the object.

2. The method as recited in claim 1, further comprising a step of serving an object by a storage element only if the invalidation time for the object has not passed.

3. The method as recited in claim 1, wherein the system includes a consistency coordinator and the method further comprises steps of:

determining the invalidation time using the consistency coordinator; and

communicating the invalidation time to the storage elements storing the object.

4. The method as recited in claim 1, further comprising a step of sending, from the consistency coordinator to a storage element and/or from a storage element to the consistency coordinator, heart beat messages to obtain availability information.

5. The method as recited in claim 4, further comprising declaring an entity expecting a heartbeat down in response to the entity failing to receive a heart beat.

6. The method as recited in claim 1, further comprising a step of sending an acknowledge message, by the storage elements, that The invalidation time has been received.

7. The method as recited in claim 1, further comprising a step of invalidating all objects that have a current time later than the invalidation time.

8. The method as recited in claim 1, further comprising a step of discarding and replacing a current version of an object with a pending-update version if the object has a current time later than the invalidation time.

9. The method as recited in claim 1, wherein the storage elements include at least one cache.

10. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for a method for maintaining stored objects in a plurality of storage elements, the method steps comprising:

storing an object in a plurality of storage elements;

in response to a request to update the object, determining a future invalidation time when the object will be invalidated in storage elements currently storing the object, the invalidation time including a time selected such that each of the plurality of storage elements has either received notification of an update pursuant to the request or has declared itself failed;

delaying updating the object until the invalidation time has passed; and

updating the object after the invalidation time has passed to maintain consistency for the object across the plurality of storage elements by allowing the storage elements to serve an old version of the object until all active storage elements are ready to serve a new updated version of the object.

11. A method for maintaining stored objects comprising the steps of:

providing a plurality of storage elements;

storing an object in a plurality of storage elements;

requesting an update for the object;

determining a future invalidation time when the object will be invalidated in storage elements currently storing the object, the invalidation time including a time selected such that each of the plurality of storage elements has either received notification of an update pursuant to the request or has declared itself failed;

delaying updating the object until the invalidation time has passed;

updating the object after the invalidation time has passed to maintain consistency for the object across the plurality of storage elements by allowing the storage elements to serve an old version of the object until all active storage elements are ready to serve a new updated version of the object.

12. The method as recited in claim 11, further comprising a step of serving an object by a storage element only if the invalidation time for the object has not passed.

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

determining the invalidation time using a consistency coordinator; and

communicating the invalidation time to the storage elements storing the object.

14. The method as recited in claim 13, further comprising a step of sending heart beat messages to obtain availability information from the consistency coordinator to a storage element and/or from a storage element to the consistency coordinator.

15. The method as recited in claim 14, further comprising declaring an entity expecting a heartbeat down in response to the entity failing to receive a heart beat.

16. The method as recited in claim 11, further comprising a step of sending an acknowledge message, by the storage elements that the invalidation time has been received.

17. The method as recited in claim 11, further comprising a step of invalidating all objects that have a current time later than the invalidation time.

18. The method as recited in claim 11, further comprising a step of discarding and replacing a current version of an object with a pending-update version if the object has a current time later than the invalidation time.

19. The method as recited in claim 11, wherein the storage elements include at least one cache.

20. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for maintaining stored objects, the method steps comprising:

providing a plurality of storage elements;

storing an object in a plurality of storage elements;

requesting an update for the object;

determining a future invalidation time when the object will be invalidated in storage elements currently storing the object, the invalidation time including a time selected such that each of the plurality of storage elements has either received notification of an update pursuant to the request or has declared itself failed;

delaying updating the object until the invalidation time has passed

updating the object after the invalidation time has passed to maintain consistency for the object across the plurality of storage elements by allowing the storage elements to serve an old version of the object until all active storage elements are ready to serve a new updated version of the object.

21. A system for maintaining stored objects consistently, comprising:

at least one object;

a plurality of storage elements for storing the object; and

a consistency coordinator which receives a request to update the object from at least one the storage elements and in response determines a future invalidation time when the object will be invalidated in storage elements currently storing the object, the invalidation time including a time selected such that each of the plurality of storage elements has either received notification of an update pursuant to the request or has declared itself failed;

the storage elements delaying updating the object until the invalidation time has passed, such that the object is updated after the invalidation time has passed to maintain consistency for the object across the plurality of storage elements by allowing the storage elements to serve an old version of the object until all active storage elements are ready to serve a new updated version of the object.

22. The system as recited in claim 21, wherein the storage elements serve an object only if the invalidation time for the object has not passed.

23. The system as recited in claim 21, wherein the consistency coordinator communicates the invalidation time only to the storage elements storing the object.

24. The system as recited in claim 21, further comprising heart beat messages sent to obtain availability information from the consistency coordinator to a storage element and/or from a storage element to the consistency coordinator.

25. The system as recited in claim 24, further comprising a down mode for which an entity expecting a heartbeat declares in response to the entity failing to receive a heart beat.

26. The system as recited in claim 21, further comprising an acknowledge message sent by the storage elements when the invalidation time has been received.

27. The system as recited in claim 21, further comprising a pending-update version list to which an object is added pending an update if the object has a current time later than the invalidation time.

28. The method as recited in claim 21, wherein the storage elements include at least one cache.