Methods and systems for consistently replicating data

Patent metadata

Field	Value
Publication number	US-9317432-B2
Application number	US-97160708-A
Country	US
Kind code	B2
Filing date	Jan 9, 2008
Priority date	Jan 9, 2008
Publication date	Apr 19, 2016
Grant date	Apr 19, 2016

Abstract

Techniques for maintaining consistent replicas of data are disclosed. By way of example, a method for managing copies of objects within caches, in a system including multiple caches, includes the following steps. Consistent copies of objects are maintained within the caches. A home cache for each object is maintained, wherein the home cache maintains information identifying other caches likely containing a copy of the object. In response to a request to update an object, the home cache for the object is contacted to identify other caches which might have copies of the object.

First claim

What is claimed is:

1. A method for managing copies of objects within caches in a system comprised of multiple caches, the method comprising the steps of:
maintaining consistent copies of cached objects within the caches;
selecting a home cache for each cached object, wherein for any two cached objects, the home cache for each of said two cached objects is allowed to be different, wherein the home cache of a cached object maintains information identifying other caches likely containing a copy of the cached object; and
in response to a request to update an object, contacting the home cache for the object to identify other caches which might have copies of the object.

2. The method of claim 1 , further comprising the steps of:
maintaining information on one of accesses and updates to an object; and
using said information to select a home cache for the object.

3. The method of claim 1 , further comprising the step of selecting a cache n as a home cache for the object wherein said maintained information indicates that cache n frequently accesses or updates said object.

4. The method of claim 1 , further comprising the step of, in response to said home cache identifying a cache n as likely containing a copy of said object, contacting cache n to one of invalidate and update its copy of said object.

5. The method of claim 1 , wherein said step of maintaining consistent copies of objects within the caches further comprises using a plurality of methods for maintaining consistent copies of objects wherein different methods incur different trade-offs between a level of consistency and a level of overhead.

6. The method of claim 5 , wherein said plurality of methods comprises at least one of a strong consistency method, an invalidation message without waiting for acknowledgements method, and an expiration times method.

7. An article of manufacture for managing copies of objects within caches in a system comprised of multiple caches, the article comprising a non-transitory computer readable storage medium containing one or more programs, which when executed by a computer implement the steps of claim 1 .

8. A method for managing copies of objects within caches in a system comprised of multiple caches, the method comprising the steps of:
selecting a home cache for each cached object, wherein for any two cached objects, the home cache for each of said two cached objects is allowed to be different, wherein the home cache of a cached object maintains information identifying other caches likely containing a copy of the cached object;
maintaining information on one of accesses and updates to an object;
using said information to select a home cache for the object; and
in response to a request to update an object, contacting the home cache for the object to identify other caches which might have copies of the object.

9. The method of claim 8 , further comprising the step of using a plurality of methods for maintaining consistent copies of objects wherein different methods incur different trade-offs between a level of consistency and a level of overhead.

10. The method of claim 8 , further comprising the step of selecting a cache n as a home cache for the object wherein said maintained information indicates that n frequently accesses or updates said object.

11. The method of claim 8 , further comprising the step of, in response to said home cache identifying a cache n as likely containing a copy of said object, contacting cache n to one of invalidate and update its copy of said object.

12. The method of claim 9 , wherein said plurality of methods for maintaining consistent copies of objects includes at least one of a strong consistency method, an invalidation messages without waiting for acknowledgements method, and an expiration times method.

13. The method of claim 8 , further comprising the step of exchanging heart beat messages between caches to maintain availability information.

14. The method of claim 8 , further comprising the step of modifying a home cache for an object in response to changes in said maintained information on one of accesses and updates.

15. The method of claim 10 , wherein the step of selecting a cache n as a home cache further comprises:
calculating, for the object o 1 and a plurality of caches, Z=a*(accesses to o 1 )+b*(updates to o 1 ), where a and b are constants; and
selecting a home cache with a greatest value of Z.

16. The method of claim 10 , wherein the step of selecting a cache n as a home cache further comprises:
calculating, for the object o 1 and a plurality of caches, Z=a*(accesses to o 1 in last c time units)+b*(updates to o 1 in last c time units), where a, b, and c are constants; and
selecting a home cache with a greatest value of Z.

17. The method of claim 10 , wherein the step of selecting a cache n as a home cache further comprises:
calculating, for the object o 1 and a plurality of caches,

Z
=

∑

i
=
1

M

⁢

f
⁡

(

A
i

)

+

∑

j
=
1

N

⁢

g
⁡

(

U
j

)

where M equals the number of times o was accessed in the last c time units, N equals the number of times o was updated in the last c time units, A i represents times when o was accessed in the last c time units, U i represents times when o was updated in the last c time units, and f and g are functions which assign higher or equal values to more recent times; and
selecting a home cache with a greatest value of Z.

18. An article of manufacture for managing copies of objects within caches in a system comprised of multiple caches, the article comprising a non-transitory computer readable storage medium containing one or more programs, which when executed by a computer implement the steps of claim 8 .

19. A system, comprising:
two or more caches;
wherein the system manages copies of cached objects within the two or more caches by:
maintaining consistent copies of cached objects within the two or more caches;
selecting a home cache for each cached object, wherein for any two cached objects, the home cache for each of said two cached objects is allowed to be different, wherein the home cache of a cached object maintains information identifying other caches of the two or more caches likely containing a copy of the cached object; and
in response to a request to update an object, contacting the home cache for the object to identify ot

Assignees

• Diament Judah M
• Iyengar Arun Kwangil
• Mikalsen Thomas A
• Rouvellou Isabelle Marie
• IBM

Inventors

• Diament Judah M
• Iyengar Arun Kwangil
• Mikalsen Thomas A
• Rouvellou Isabelle Marie

Classifications

• G06F12/0822

  Copy directories (local copy tags for implementing a bus snooping protocol G06F12/0831) · CPC title

• G06F12/0813

  with a network or matrix configuration · CPC title

• G06F12/0815

  Cache consistency protocols · CPC title

• G06F12/082 Primary

  Associative directories (G06F12/0822 takes precedence) · CPC title