Synchronization of subsets of data including support for varying set membership

• US 8,805,783 B2
• Filed: 10/29/2010
• Issued: 08/12/2014
• Est. Priority Date: 05/27/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Muhunthan, Siva, Novik, Lev, Clark, Michael, Maksimenka, Andrei
• Primary Examiner(s): FILIPCZYK, MARCIN R
• Application Number:
  US12/915,795
• Publication Number:
  US 20110295796A1
• Time in Patent Office: 1,383 Days
• Field of Search: 707/612, 707/614, 707/626, 707/638, 711/117
• US Class Current: 707/626
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor

Abstract

An efficient way and general mechanism is provided to represent and exchange knowledge and/or partial knowledge across nodes when synchronizing between any two nodes including custom or move filters where set membership can change over time at a device as data items come in and out of filter scope. A first node sends a second node its knowledge and/or partial knowledge, including objects and versions of those objects. The second node compares its knowledge and/or partial knowledge with the knowledge and/or partial knowledge of the first node, and then sends the first node any latest versions of objects of which the first node is unaware. In addition, the second node sends its knowledge and/or partial knowledge to the first node. The first node then performs a similar object-by-object version comparison to determine any conflicts due to independent evolution of objects and any changes that can be sent to the second node in order to bring the objects of the second node up to date with the knowledge and/or partial knowledge of the first node. Replicas can track filters to efficiently support synchronizing with filtered replicas. Filter forgotten knowledge is also used to represent how recently a replica can guarantee to know which items have been in the filter. Ghosts can be used to represent items that have been in the filter recently but have currently moved out. Filter forgotten knowledge concept allows both new filters to be tracked when they are introduced into the community, as well as periodically cleaning up of tombstones and ghosts.

Claims

1. A computing device, comprising:

at least one processor;

memory that stores modules for execution by the at least one processor, the modules including;

a sync module configured to support variable membership in a filter set in connection with multi-master synchronization, configured to maintain filter forgotten knowledge, where forgotten knowledge supports synchronization of knowledge by the sync module with one or more other sync modules and the filter forgotten knowledge supports synchronization of filtered knowledge by the sync module with one or more other sync modules, and configured to communicatively couple to a local replica that stores a local version of a set of data objects and associated metadata, the sync module comprising;

a communications module configured to communicate with at least one other sync module included in a multi-master community of sync modules; and

an analysis module configured to manage information associated with the set of data objects, wherein the information includes (1) knowledge that pertains to at least one version of the set of data objects received from the at least one other sync module, and (2) filter forgotten knowledge that pertains to deleted data objects, or versions thereof, that belong to filtered knowledge, which is a filtered subset of the set of data objects in which membership is dynamic;

the sync module being further configured to synchronize the local replica based upon information received from the at least one other sync module.

2. The computing device of claim 1, wherein the information further includes forgotten knowledge that pertains to deleted data objects or versions thereof.

3. The computing device of claim 1, wherein the information is metadata associated with changes to the set of data objects or versions thereof.

4. The computing device of claim 1, wherein the sync module is configured to initiate a synchronization procedure with the at least one other sync module by way of a change request and transmits the information to the at least one other sync module.

5. The computing device of claim 1, wherein the sync module is configured to at least one of (1) respond to a synchronization procedure requested by the at least one other sync module based upon receipt of a change request that includes at least one of knowledge, forgotten knowledge, or filter forgotten knowledge associated with the at least one other sync module, (2) perform a comparison between data included in the change request and data included in the local replica;

or (3) transmit data determined to be unknown to the at least one other sync module based upon the comparison by way of a change conveyance.

6. The computing device of claim 5, wherein the sync module is configured to compare received knowledge from the at least one other sync module to either forgotten knowledge or filter forgotten knowledge included in the local replica in order to perform the comparison, and to (1) perform a normal sync when the received knowledge is contained in the forgotten knowledge or filter forgotten knowledge;

(2) perform a synch with line item exceptions when the received knowledge is not contained in the forgotten knowledge or not contained in the filter forgotten knowledge;

or (3) perform a full enumeration sync when the received knowledge is not contained in the forgotten knowledge or not contained in the filter forgotten knowledge.

7. The computing device of claim 1, wherein the sync module further comprising a tracking module configured to monitor at least one filter applied to the set of data objects.

8. The computing device of claim 7, wherein the tracking module is further configured to maintain a data table related to filtered data objects, wherein the table includes at least one of (1) an item ID that uniquely describes a filtered data object;

(2) a creation version that denotes a sync module ID and an indication of time associated with creation of the filtered data object;

(3) a last update version that relates to a sync module ID, and an indication of time associated with an update to or versioning of the filtered data object;

(4) an indication of presence or recent presence of the filtered data object in the at least one filter;

or (5) a move out version that relates to either a sync module ID and an indication of time associated with a change to the filtered data object that removes the filtered data object from the at least one filter or a null value or another value that indicates the filtered data object has not ever, or not recently, been in the at least one filter.

9. The computing device of claim 8, wherein the tracking module is further configured to bootstrap the at least one filter in order to track preexisting filters, wherein the tracking module sets filter forgotten knowledge associated with data objects included in the filter to knowledge associated with the data objects included in the filter.

10. The computing device of claim 8, wherein the tracking module is further configured to set filter forgotten knowledge of a moved data object to the move out version of the moved data object in order to treat the moved data object as though the moved data object never existed in the at least one filter.

11. The computing device of claim 1, wherein the local replica is a full replica configured to maintain all data managed by the multi-master community and a remote replica associated with the at least one other sync module is a filtered replica configured to maintain a subset of the data managed by the multi-master community based upon at least one filter applied to the set of data objects.

12. The computing device of claim 1, wherein the local replica is a filtered replica configured to maintain a subset of data managed by the multi-master community based upon at least one filter applied to the set of data objects and a remote replica associated with the at least one other sync module is a full replica configured to maintain all data managed by the multi-master community.

13. A method, comprising:

maintaining a first replica for storing a first version of data objects and associated metadata in a computer readable storage medium;

configuring the first replica for supporting variable membership in a filter set in connection with multi-master synchronization;

communicating by a first sync module associated with the first replica with a second sync module associated with a second replica of a multi-master community of replicas, the second replica storing a second version of data objects and associated metadata;

including in the first replica knowledge relating to known versions of data objects maintained by the multi-master community and filter forgotten knowledge relating to purged data objects belonging to a filtered subset of the first version of data objects in which membership is dynamic, where forgotten knowledge supports synchronization of knowledge between the first and second replicas and the filter forgotten knowledge supports synchronization of filtered knowledge between the first and second replicas; and

synchronizing by the first sync module the first replica with the second replica based upon information received from the second sync module;

at least one of the maintaining, configuring, communicating, including and synchronizing steps being executed by a processor.

14. The method of claim 13, further comprising at least one of the following:

including in the first replica forgotten knowledge relating to purged data objects or version thereof;

transmitting at least one of the knowledge, forgotten knowledge, or the filter forgotten knowledge to initiate a synchronization process with the second replica;

receiving at least one of the knowledge, forgotten knowledge, or the filter forgotten knowledge from the second replica during a synchronization process, and responding with information determined to be unknown by the second replica;

performing a partial synchronization with line item exceptions when knowledge received from the second replica is not contained in either forgotten knowledge or filter forgotten knowledge of the first replica;

or

performing a full enumeration synchronization when knowledge received from the second replica is not contained in either forgotten knowledge or filter forgotten knowledge of the first replica.

15. The method of claim 13, further comprising at least one of the following:

employing filter forgotten knowledge for tracking one or more filter applied to the first version of the data objects;

maintaining a first indication of whether a tracked data object has been in the one or more filter since a last cleanup operation for tracking the one or more filter;

maintaining a second indication of whether the tracked data object has moved out of the one or more filter for tracking the one or more filter;

bootstrapping the one or more filter by tracking an existing filter and setting knowledge relating to data objects included in the existing filter to filter forgotten knowledge relating to data object included in the existing filter;

vacating stale moved objects from the one or more filter when a moved out version of the moved object that has left the one or more filter predates a last cleanup process by setting filter forgotten knowledge for the moved object to forgotten knowledge for the moved object;

or

performing the vacating concurrently with a cleanup process.

16. A method, comprising:

maintaining a local replica for storing a current version of data objects and associated metadata;

communicatively coupling by a first sync module associated with the local replica to a second sync module associated with an other replica of a multi-master community of replicas, the other replica storing an other version of data objects and associated metadata;

maintaining in the local replica knowledge relating to known versions of data objects maintained by the multi-master community, forgotten knowledge relating to purged data object or versions thereof, and filter forgotten knowledge relating to purged data objects, or versions thereof, that are included in a filtered subset, with dynamic membership, of the local version of data objects, where forgotten knowledge supports synchronization of knowledge between the local replica and an other replica and the filter forgotten knowledge supports synchronization of filtered knowledge between the local replica and an other replica; and

synchronizing by the first sync module the local replica and the other replica based upon information received from the second sync module;

at least one of the maintaining, coupling and synchronizing steps being executed by a processor.

17. The method of claim 16, wherein synchronizing the local replica and the other replica comprises at least one of the following:

synchronizing the local replica and the other replica according to a normal sync operation;

synchronizing the local replica and the other replica according to a partial sync operation with line item exceptions;

or

synchronizing the local replica and the other replica according to a full enumeration operation.

18. The method of claim 16, further comprising at least one of the following:

tracking at least one filter applied to the data objects;

maintaining a first indication of whether a tracked data object has been in the one or more filter since a last cleanup operation;

or

maintaining a second indication of whether the tracked data object has moved out of the one or more filter for tracking the one or more filter.

19. The method of claim 16, further comprising at least one of the following:

bootstrapping a preexisting filter included in the at least one filter;

vacating stale moved objects from the at least one filter;

or

performing the vacating contemporaneously with a cleanup operation.