Method, system, and program for maintaining data in distributed caches

• US 20040064650A1
• Filed: 09/27/2002
• Published: 04/01/2004
• Est. Priority Date: 09/27/2002
• Status: Active Grant

• Current Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Johnson, Sandra K.
• Granted Patent: US 6,973,546 B2
• Time in Patent Office: Days
• US Class Current: 711/141
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching

Abstract

Provided are a method, system, and program for maintaining data in distributed caches. A copy of an object is maintained in at least one cache, wherein multiple caches may have different versions of the object, and wherein the objects are capable of having modifiable data units. Update information is maintained for each object maintained in each cache, wherein the update information for each object in each cache indicates the object, the cache including the object, and indicates whether each data unit in the object was modified. After receiving a modification to a target data unit in one target object in one target cache, the update information for the target object and target cache is updated to indicate that the target data unit is modified, wherein the update information for the target object in any other cache indicates that the target data unit is not modified.

Claims

1. A method for maintaining data in distributed caches, comprising:

maintaining a copy of an object in at least one cache, wherein multiple caches may have different versions of the object, and wherein the objects are capable of having modifiable data units;

maintaining update information for each object maintained in each cache, wherein the update information for each object in each cache indicates the object, the cache including the object, and indicates whether each data unit in the object was modified; and

after receiving a modification to a target data unit in one target object in one target cache, updating the update information for the target object and target cache to indicate that the target data unit is modified, wherein the update information for the target object in any other cache indicates that the target data unit is not modified.

2. The method of claim 1, further performing after receiving the request to modify the data unit:

if the update information for the target object and target cache indicate that the target data unit is modified, then applying the received modification to the data unit in the target object in the target cache.

3. The method of claim 1, further performing after receiving the modification:

if the update information for the target object and target cache indicate that the target data unit is not modified, then determining whether another cache includes the target object and a most recent target data unit value;

if another cache does not include the most recent target data unit value, then applying the modification to the data unit in the target object in the target cache; and

updating the update information for the target object and target cache to indicate that the target data unit is modified, wherein the update information for the target object in any other cache indicates that the data unit is not modified.

4. The method of claim 1, further performing after receiving the modification:

if the update information for the target object and target cache indicate that the target data unit is not modified, then determining whether another cache includes the target object and a most recent target data unit value; and

if another cache includes the most recent target data unit value, then retrieving the most recent target data unit value from the determined cache and updating the target object in the target cache with the retrieved most recent target data unit value.

5. The method of claim 4, further comprising:

after updating the target object in the target cache with the most recent target data unit value, applying the received modification to the data unit in the target object in the target cache; and

updating the update information for the target object and target cache to indicate that the target data unit is modified, wherein the update information for the target object in any other cache indicates that the data unit is not modified.

6. The method of claim 4, wherein a central server performs the steps of determining whether another cache includes the target object and the most recent target data unit value and retrieving the most recent target data unit value from the other cache, further comprising:

returning, with the central server, the most recent target data unit value, wherein the modification to the target data unit is applied to the target cache after the most recent target data unit value is applied to the target cache.

7. The method of claim 6, wherein one cache server is coupled to each cache, and wherein each cache server maintains update information for each object in the at least one cache to which the cache server is coupled, and wherein the central server maintains update information for each object in each cache.

8. The method of claim 1, further comprising:

maintaining invalidation information for each object in each cache, wherein the invalidation information for one object in one cache indicates whether each data unit in the object is valid or invalid.

9. The method of claim 8, further comprising:

if the invalidation information for the target object and target cache indicate that the target data unit is invalid, then determining from the update information the cache that includes a most recent target data unit value for the target object; and

retrieving the most recent target data unit value from the determined cache and updating the target object in the target cache with the most recent target data unit value.

10. The method of claim 9, further comprising:

after updating the target object in the target cache with the most recent target data unit value, applying the received modification to the target data unit in the target object in the target cache;

updating the update information for the target object and target cache to indicate that the target data unit is modified; and

updating the invalidation information for each cache that includes the target object to indicate that the target data unit is invalid.

11. The method of claim 10, further comprising:

updating the update information for the target object in the determined cache to indicate that the data unit is not modified.

12. The method of claim 9, wherein a central server performs the steps of determining whether the invalidation information for the target object and target cache indicates that the target data unit is invalid, determining the cache that includes the target object and the most recent target data unit value, and retrieving the most recent target data unit value from the determined cache, further comprising:

returning, by the central server, the most recent target data unit value, wherein the modification to the target data unit is applied to the target cache after the most recent target data unit value is applied to the target object in the target cache.

13. The method of claim 12, wherein one cache server is coupled to each cache, and wherein each cache server maintains update information for each object in the at least one cache to which the cache server is coupled, and wherein the central server maintains update information and invalidation information for each object in each cache, further comprising:

determining, by a target cache server that received the modification to the target data unit, whether the update information for the target object and target cache indicate that the target data unit is modified; and

updating, by the target cache server, the data unit in the target object in the target cache after determining that the update information for the target object and target cache indicate that the target data unit is modified.

14. The method of claim 13, further comprising:

sending, by the target cache server, a request to the central server to modify the target data unit; and

returning, by the central server, a message to the target cache server to proceed with the modification that (i) does not include the most recent target data unit value if no other cache had the most recent target data unit value or (2) includes the most recent target data unit value if another cache had the most recent target data unit value; and

applying, by the target cache server, the received most recent target data unit value to the target page in the target cache before applying the received modification to the target data unit value.

15. A system for maintaining data, comprising:

a plurality of caches;

means for maintaining a copy of an object in at least one cache, wherein the caches may have different versions of the object, and wherein the objects are capable of having modifiable data units;

means for maintaining update information for each object maintained in each cache, wherein the update information for each object in each cache indicates the object, the cache including the object, and indicates whether each data unit in the object was modified; and

means for updating the update information for the target object and target cache to indicate that the target data unit is modified after receiving a modification to a target data unit in one target object in one target cache, wherein the update information for the target object in any other cache indicates that the target data unit is not modified.

16. The system of claim 15, further comprising:

means for applying the received modification to the data unit in the target object in the target cache after receiving the request to modify the data unit and if the update information for the target object and target cache indicate that the target data unit is modified.

17. The system of claim 15, further comprising means for performing after receiving the modification:

determining whether another cache includes the target object and a most recent target data unit value if the update information for the target object and target cache indicate that the target data unit is not modified;

applying the modification to the data unit in the target object in the target cache if another cache does not include the most recent target data unit value; and

updating the update information for the target object and target cache to indicate that the target data unit is modified, wherein the update information for the target object in any other cache indicates that the data unit is not modified.

18. The system of claim 18, further comprising means for performing after receiving the modification:

determining whether another cache includes the target object and a most recent target data unit value if the update information for the target object and target cache indicate that the target data unit is not modified; and

retrieving the most recent target data unit value from the determined cache and updating the target object in the target cache with the retrieved most recent target data unit value if another cache includes the most recent target data unit value.

19. The system of claim 18, further comprising:

means for maintaining invalidation information for each object in each cache, wherein the invalidation information for one object in one cache indicates whether each data unit in the object is valid or invalid.

20. The system of claim 19, further comprising:

means for determining from the update information the cache that includes a most recent target data unit value for the target object if the invalidation information for the target object and target cache indicate that the target data unit is invalid; and

means for retrieving the most recent target data unit value from the determined cache and updating the target object in the target cache with the most recent target data unit value.

21. The system of claim 20, wherein a central server implements the means for determining whether the invalidation information for the target object and target cache indicates that the target data unit is invalid, determining the cache that includes the target object and the most recent target data unit value, and retrieving the most recent target data unit value from the determined cache, further comprising:

means for returning, performed by the central server, the most recent target data unit value, wherein the modification to the target data unit is applied to the target cache after the most recent target data unit value is applied to the target object in the target cache.

22. An article of manufacture for maintaining data in distributed caches, wherein the article of manufacture causes operations to be performed, the operations comprising:

maintaining a copy of an object in at least one cache, wherein multiple caches may have different versions of the object, and wherein the objects are capable of having modifiable data units;

maintaining update information for each object maintained in each cache, wherein the update information for each object in each cache indicates the object, the cache including the object, and indicates whether each data unit in the object was modified; and

after receiving a modification to a target data unit in one target object in one target cache, updating the update information for the target object and target cache to indicate that the target data unit is modified, wherein the update information for the target object in any other cache indicates that the target data unit is not modified.

23. The article of manufacture of claim 22, further performing after receiving the request to modify the data unit:

if the update information for the target object and target cache indicate that the target data unit is modified, then applying the received modification to the data unit in the target object in the target cache.

24. The article of manufacture of claim 22, further performing after receiving the modification:

if the update information for the target object and target cache indicate that the target data unit is not modified, then determining whether another cache includes the target object and a most recent target data unit value;

if another cache does not include the most recent target data unit value, then applying the modification to the data unit in the target object in the target cache; and

updating the update information for the target object and target cache to indicate that the target data unit is modified, wherein the update information for the target object in any other cache indicates that the data unit is not modified.

25. The article of manufacture of claim 22, further performing after receiving the modification:

if the update information for the target object and target cache indicate that the target data unit is not modified, then determining whether another cache includes the target object and a most recent target data unit value; and

if another cache includes the most recent target data unit value, then retrieving the most recent target data unit value from the determined cache and updating the target object in the target cache with the retrieved most recent target data unit value.

26. The article of manufacture of claim 25, further comprising:

after updating the target object in the target cache with the most recent target data unit value, applying the received modification to the data unit in the target object in the target cache; and

updating the update information for the target object and target cache to indicate that the target data unit is modified, wherein the update information for the target object in any other cache indicates that the data unit is not modified.

27. The article of manufacture of claim 26, wherein a central server performs the steps of determining whether another cache includes the target object and the most recent target data unit value and retrieving the most recent target data unit value from the other cache, further comprising:

returning, with the central server, the most recent target data unit value, wherein the modification to the target data unit is applied to the target cache after the most recent target data unit value is applied to the target cache.

29. The article of manufacture of claim 22, further comprising:

maintaining invalidation information for each object in each cache, wherein the invalidation information for one object in one cache indicates whether each data unit in the object is valid or invalid.

30. The article of manufacture of claim 29, further comprising:

if the invalidation information for the target object and target cache indicate that the target data unit is invalid, then determining from the update information the cache that includes a most recent target data unit value for the target object; and

retrieving the most recent target data unit value from the determined cache and updating the target object in the target cache with the most recent target data unit value.

31. The article of manufacture of claim 30, further comprising:

after updating the target object in the target cache with the most recent target data unit value, applying the received modification to the target data unit in the target object in the target cache;

updating the update information for the target object and target cache to indicate that the target data unit is modified; and

updating the invalidation information for each cache that includes the target object to indicate that the target data unit is invalid.

32. The article of manufacture of claim 31, further comprising:

updating the update information for the target object in the determined cache to indicate that the data unit is not modified.

33. The article of manufacture of claim 30, wherein a central server performs the steps of determining whether the invalidation information for the target object and target cache indicates that the target data unit is invalid, determining the cache that includes the target object and the most recent target data unit value, and retrieving the most recent target data unit value from the determined cache, further comprising:

returning, by the central server, the most recent target data unit value, wherein the modification to the target data unit is applied to the target cache after the most recent target data unit value is applied to the target object in the target cache.

34. The article of manufacture of claim 33, wherein one cache server is coupled to each cache, and wherein each cache server maintains update information for each object in the at least one cache to which the cache server is coupled, and wherein the central server maintains update information and invalidation information for each object in each cache, further comprising:

determining, by a target cache server that received the modification to the target data unit, whether the update information for the target object and target cache indicate that the target data unit is modified; and

updating, by the target cache server, the data unit in the target object in the target cache after determining that the update information for the target object and target cache indicate that the target data unit is modified.

35. The article of manufacture of claim 34, further comprising:

sending, by the target cache server, a request to the central server to modify the target data unit; and

returning, by the central server, a message to the target cache server to proceed with the modification that (i) does not include the most recent target data unit value if no other cache had the most recent target data unit value or (2) includes the most recent target data unit value if another cache had the most recent target data unit value; and

applying, by the target cache server, the received most recent target data unit value to the target page in the target cache before applying the received modification to the target data unit value.

28. The article of manufacture of claim 28, wherein one cache server is coupled to each cache, and wherein each cache server maintains update information for each object in the at least one cache to which the cache server is coupled, and wherein the central server maintains update information for each object in each cache.