Method and apparatus for enabling partial replication of object stores

• US 6,757,896 B1
• Filed: 01/29/1999
• Issued: 06/29/2004
• Est. Priority Date: 01/29/1999
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Cohen, Norman H., Purakayastha, Apratim, Mohindra, Ajay
• Primary Examiner(s): An, Meng-Al T.
• Assistant Examiner(s): Zhen, Li B.
• Application Number:
  US09/239,645
• Time in Patent Office: 1,978 Days
• Field of Search: 707/201, 707/203, 709/248, 711/141, 718/100
• US Class Current: 718/100
• CPC Class Codes: G06F 16/275 Synchronous replication
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

Abstract

Method and apparatus are provided for enabling partial replication of object stores, wherein two or more computers can partially replicate object stores by allowing synchronization of only such objects contained in the stores that are intended to be shared among the stores.

Claims

1. A method for synchronizing a plurality of replica object stores to enable partial sharing of objects therebetween, wherein the stores respectively have store controllers associated therewith, the method comprising the steps of:

(a) maintaining a plurality of data structures, wherein one of the data structures is associated with one of the stores and each data structure comprises a filter F and a list L, the filter F embodying an operation that can be applied to the objects in the stores, the list L comprising object identifiers of the objects that are shared between the stores as of a last synchronization;

(b) applying the filter F of a first store to the objects in the first store to generate a subset S comprising the objects in the first store to be shared with remaining stores of the plurality of stores, by a first store controller;

(c) incrementing version information of the objects of the first store that were not shared between the stores as of the last synchronization but should now be shared, and of the objects of the first store that were shared between the stores as of the last synchronization but should no longer be shared, by the first store controller;

(d) transferring version information of objects in the remaining plurality of stores corresponding to the objects in subset S, to the first store controller, from the remaining plurality of store controllers;

(e) determining one of which objects in subset S and identified by object identifiers in list L of the first store have the version information that is one of newer than and conflicting with version information of the remaining stores, by the first store controller;

(f) applying updates associated with the determined objects, by remaining store controllers;

(g) updating the lists L of each of the plurality of stores, by the plurality of store controllers; and

(h) repeating steps (b) through (g) for a next store of the remaining stores, with roles of the first store now performed by the next store, and the remaining stores now being all stores of the plurality of stores except the next store.

2. The method according to claim 1, wherein said determining step further comprises the step of obtaining the version information of the remaining stores, by the first store controller.

3. The method according to claim 2, wherein said obtaining step comprises the steps of:

requesting the version information of the remaining stores, by the first store controller; and

sending the version information of the remaining stores to the first store, by the remaining controllers.

4. The method according to claim 3, wherein said requesting step comprises the step of sending a Summary Version Message Request.

5. The method according to claim 3, wherein said sending step comprises the step of sending a Summary Version Message Reply.

6. The method according to claim 1, wherein said method further comprises the step of sending the determined objects to the remaining controllers, by the first store controller.

7. The method according to claim 6, wherein said sending step comprises the step of sending a List of Updates Message.

8. The method according to claim 1, wherein the updates comprise a content, the identifier and the version information of the object.

9. The method according to claim 1, wherein said step of applying the updates comprises, for each update, one of the steps of:

copying a content of a determined object to a corresponding local object in the remaining stores;

merging the content of the determined object with a content of the corresponding local object in the remaining stores; and

keeping an original content of the corresponding local object in the remaining stores.

10. The method according to claim 1, wherein said updating step comprises the steps of:

adding object identifiers to the list L of the remaining stores for all the updates that were not already present in the list L of the remaining stores;

removing object identifiers from the list L of the remaining stores for all the updates whose objects no longer satisfy the filter F; and

updating the list L of the first store with a list L′

.

11. The method according to claim 1, wherein the version information of the objects comprises a clock value associated with a last time the respective objects were modified.

12. A method for synchronizing replica object stores store1 and store2 to enable partial sharing of objects therebetween, wherein the store1 and store2 respectively have store1 and store2 controllers associated therewith, the method comprising the steps of:

(a) maintaining a first list L for store1 and a second list L for store2, the first list L and the second list L comprising object identifiers of the objects that are shared between store1 and store2 as of a last synchronization;

(b) applying a filter F to the objects in the store1 to generate a subset S comprising the objects in the store1 to be shared with the store2, wherein the filter F embodies an operation that can be applied to the objects in the store1 and store2, said applying by the store1 controller;

(c) incrementing version information of the objects that were not shared between the store1 and store2 as of a last synchronization but should now be shared, and of the objects that were shared between the store1 and store2 as of the last synchronization but should no longer be shared, by the store1 controller;

(d) transferring version information of objects in the store2 corresponding to objects in the subset S, to the store1 controller from the store2 controller;

(e) determining one of which objects in the subset S and identified by object identifiers in the first list L have the version information that is one of newer than and conflicting with version information of the store2, said determining by the store1 controller;

(f) applying updates associated with the determined objects, by the store2 controller;

(g) updating the lists L of the store2 and the store1, by the store2 and store1 controllers, respectively; and

(h) repeating steps (b) through (g), with roles of the store1 with respect to the store2 reversed, and roles of the store1 controller with respect to the store2 controller reversed.

13. The method according to claim 12, further comprising the step of:

maintaining respective data structures for the store1 and store2 comprising the filter F and the list L, by the store1 and store2 controller, respectively.

14. The method according to claim 12, wherein said determining step further comprises the step of obtaining the version information of the store2, by the store1 controller.

15. The method according to claim 14, wherein said obtaining step comprises the steps of:

requesting the version information of the store2, by the store1 controller; and

sending the version information of the store2 to the store1, by the store2 controller.

16. The method according to claim 15, wherein said requesting step comprises the step of sending a Summary Version Message Request.

17. The method according to claim 15, wherein said sending step comprises the step of sending a Summary Version Message Reply.

18. The method according to claim 12, wherein said method further comprises the step of sending the determined objects to the store2 controller, by the store1 controller.

19. The method according to claim 18, wherein said sending step comprises the step of sending a List of Updates Message.

20. The method according to claim 12, wherein the updates comprise a content, the identifier and the version information of the object.

21. The method according to claim 12, wherein said step of applying the updates comprises, for each update, one of the steps of:

copying a content of a determined object to a corresponding local object in the store2;

merging the content of the determined object with a content of the corresponding local object in the store2; and

keeping an original content of the corresponding local object in the store2.

22. The method according to claim 12, wherein said updating step comprises the steps of:

adding object identifiers to the list L of the store2 for all the updates that were not already present in the list L of the store2;

removing object identifiers from the list L of the store2 for all the updates whose objects no longer satisfy the filter F; and

updating the list L of the store1 with a list L′

.

23. The method according to claim 12, wherein the version information of the objects comprises a clock value associated with a last time the respective objects were modified.

24. A method for synchronizing two replica object stores store1 and store2 to enable partial sharing therebetween, the store1 and store2 respectively having store1 and store2 controllers associated therewith, the method comprising the steps of:

(a) maintaining a first list L for store1 and a second list L for store2, the first list L and the second list L comprising object identifiers of the objects that are shared between store1 and store2 as of a last synchronization;

(b) applying a filter F to the objects in the store1 to generate a subset S comprising the objects in the store1 to be shared with the store2, wherein the filter F embodies an operation that can be applied to the objects in the store1 and store2, said applying by the store1 controller;

(c) computing a list L′

that comprises object identifiers of the objects in the subset S, by the store1 controller;

(d) computing a list L⁺ that comprises entries that are in the list L′

but not in the first list L, by the store1 controller;

(e) computing a list L−

that contains entries that are in the first list L but are not in the list L′

, by the store1 controller;

(f) incrementing version information of the objects in L⁺ and L⁻

, by the store1 controller;

(g) constructing a set S′

comprising objects whose identifiers are in one of the list L or the list L′

, by the store1 controller;

(h) transferring version information of objects in the store2 corresponding to objects in the subset S′

, to the store1 controller from the store2 controller;

(i) determining which objects in the set S′

have the version information that are one of newer than and conflicting with the version information of the store2, by the store1 controller;

(j) applying updates associated with the determined objects, by the store2 controller;

(k) updating the lists L of the store2 and store1, by the store2 and store1 controller; and

(l) repeating steps (b) through (k), with roles of the store1 with respect to the store2 reversed, and roles of the store1 controller with respect to the store2 controller reversed.

25. The method according to claim 24, further comprising the step of maintaining respective data structures for the store1 and store2 comprising the filter F and the list L, by the store1 and store2 controller, respectively.

26. The method according to claim 24, wherein the version information of each object comprises a node identifier and a clock value.

27. The method according to claim 24, wherein the list L⁺ comprises the object identifiers for the objects that were not previously shared between the store1 and store2 but should now be shared.

28. The method according to claim 24, wherein the list L−

comprises the object identifiers for the objects that were previously shared between the store1 and store2 but should no longer be shared.

29. The method according to claim 24, wherein said determining step further comprises the step of obtaining the version information of the store2 controller, by the store1 controller.

30. The method according to claim 29, wherein said obtaining step comprises the steps of:

requesting the version information of the store2, by the store1 controller; and

sending the version information of the store2 to the store1, by the store2 controller.

31. The method according to claim 30, wherein said requesting step comprises the step of sending a Summary Version Message Request.

32. The method according to claim 30, wherein said sending step comprises the step of sending a Summary Version Message Reply.

33. The method according to claim 24, wherein said method further comprises the step of sending the determined objects to the store2 controller, by the store1 controller.

34. The method according to claim 33, wherein said sending step comprises the step of sending a List of Updates Message.

35. The method according to claim 24, wherein the updates comprise a content, the identifier and the version information of the object.

36. The method according to claim 24, wherein said step of applying the updates comprises, for each update, one of the steps of:

copying a content of a determined object to a corresponding local object in the store2;

merging the content of the determined object with a content of the corresponding local object in the store2; and

keeping an original content of the corresponding local object in the store2.

37. The method according to claim 24, wherein said step of updating the list L of the store2 comprises the steps of:

adding object identifiers to the list L of the store2 for all the updates that were not already present in the list L of the store2;

removing object identifiers from the list L of store2 for all the updates whose objects no longer satisfy the filter F; and

updating the list L of the store1 with the list L′

.

38. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for synchronizing replica object stores store1 and store2 to enable partial sharing of objects therebetween, the method comprising the steps of:

(a) maintaining a first list L for store1 and a second list L for store2, the first list L and the second list L comprising object identifiers of the objects that are shared between store1 and store2 as of a last synchronization;

(b) applying a filter F to the objects in the store1 to generate a subset S comprising the objects in the store1 to be shared with the store2, wherein the filter F embodies an operation that can be applied to the objects in the store1 and store2, said applying by the store1 controller;

(c) incrementing version information of the objects that were not shared between the store1 and store2 as of a last synchronization but should now be shared, and of the objects that were shared between the store1 and store2 as of the last synchronization but should no longer be shared, by the store1 controller;

(d) transferring version information of objects in the store2 corresponding to objects in the subset S, to the store1 controller from the store2 controller;

(e) determining one of which objects in the subset S and identified by object identifiers in the first list L have the version information that is one of newer than and conflicting with version information of the store2, said determining by the store1 controller;

(f) applying updates associated with the determined objects, by the store2 controller;

(g) updating the lists L of the store2 and the store1 , by the store2 and store1 controllers, respectively; and

(h) repeating steps (b) through (g), with roles of the store1 with respect to the store2 reversed, and roles of the store1 controller with respect to the store2 controller reversed.