Filtered replication of data stores

• US 7,440,985 B2
• Filed: 04/27/2006
• Issued: 10/21/2008
• Est. Priority Date: 07/31/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Novik, Lev, Terry, Douglas B., Clark, Michael R., Talius, Tomas, Wu, Yunxin, Hudis, Irena
• Primary Examiner(s): Truong; Cam Y
• Assistant Examiner(s): XUE, BIN
• Application Number:
  US11/380,579
• Publication Number:
  US 20060190572A1
• Time in Patent Office: 908 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/1787 Details of non-transparently synchronising file systems
• CPC Class Codes: G06F 16/184 implemented as replicated file system
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99955 Archiving or backup

Abstract

Methods for enabling mult-master synchronization of particular sets of data using filters. In a synchronization request, data including knowledge and filters may be supplied. A response may comprise data including changes that are identified by the filter and that have versions that are not known by the requestor.

Claims

1. A method for replicating at least one change to stored data between replicas in a sync community wherein each replica makes changes independently of other replicas in the sync community, comprising:

receiving, at a second replica, a first replica knowledge value that represents knowledge of changes to the stored data that a first replica is aware, and a first filter that identifies a first particular set of data in the stored data, wherein the first replica knowledge value includes a first change identifier and a second change identifier, the first change identifier indicating the first replica is aware of all changes made by the first replica up to the first change identifier, the second change identifier indicating the first replica is aware of all changes made by a third replica up to the second change identifier;

comparing the first replica knowledge value with versions associated with changes to the stored data in the second replica to identify the at least one change known by the second replica that the first replica is not aware, wherein the at least one change is associated with a first particular set of data identified by the first filter;

sending the at least one change to the first replica;

sending, to the second replica, a system knowledge value provided by a knowledge store that represents knowledge of changes to the stored data that a system is aware, and a second filter provided by a filter store that identifies a second particular set of data in the stored data;

receiving at least one received change that exists in the second replica that the system was not aware, wherein the at least one received change is associated with the second particular set of data identified by the second filter;

incorporating the at least one received change into the stored data associated with item data store module;

receiving information that identifies at least one non-filtered change to the stored data that is not represented by the first replica knowledge value and is also not associated with the second particular set of data identified by the second filter according to the second replica; and

updating the stored data maintained by the first replica using the information that identifies the at least one non-filtered change, wherein said updating the stored data maintained by the first replica further comprises creating at least one exception in the first replica knowledge value according to the information that identifies the at least one non-filtered change, the at least one exception referencing knowledge of changes to the stored data that the first replica was aware before receiving the at least one change.

2. The method of claim 1, further comprising:

sending a second replica knowledge value that represents knowledge of changes to the stored data of which the second replica is aware to the first replica.

3. The method of claim 1, further comprising:

identifying at least one non-filtered change to the stored data that is not represented by the first replica knowledge value and is also not associated with the first particular set of data identified by the first filter according to the second replica; and

sending information that identifies the at least one non-filtered change to the first replica.

4. The method of claim 1 wherein:

the first filter is a retractable filter; and

the first particular set of data identified by the first filter comprises data identified by a filter criteria applied during the comparing and data identified by the first filter criteria applied as a time represented by the first replica knowledge value.

5. The method of claim 1 further comprising:

a list associated with the first filter that comprises one or more stored data identifiers each identifying a separate piece of data and having at least one version associated with an entry of the piece of data into the first filter.

6. The method of claim 5 wherein at least one of the one or more stored data identifiers also has at least one version associated with an exit of the piece of data from the first filter.

7. The method of claim 5, wherein the list is maintained by:

evaluating a filter criteria;

adding a version associated with entry of the piece of data into the first filter when the first filter criteria identifies stored data that is in the first filter; and

adding a version associated with exit of the piece of data from the first filter when the filter criteria identifies stored data that is not in the first filter.

8. The method of claim 7 wherein the list is maintained immediately before or during a sync operation.

9. The method of claim 7 wherein the list is maintained at a time separate from a sync operation.

10. A system for managing and replicating changes to stored data between replicas in a sync community, wherein each replica makes changes independently of other replicas in the sync community, comprising:

a processor;

a memory operatively coupled to the processor;

an item data store module to manage the stored data;

a knowledge store module to manage knowledge of changes to the stored data;

a filter store module to maintain one or more filters that each identify a particular set of data in the stored data;

a change enumeration module to;

receive a first replica knowledge value that represents knowledge of changes to the stored data that a first replica is aware, and a first filter that identifies a first particular set of data in the stored data, wherein the first replica knowledge value includes a first change identifier and a second change identifier, the first change identifier indicating the first replica is aware of all changes made by the first replica up to the first change identifier, the second change identifier indicating the first replica is aware of all changes made by a third replica up to the second change identifier, the changes made by the third replica up to the second change identifier including a first change to a first item and a second change to a second item, the first change and second change corresponding to different change identifiers;

compare the first replica knowledge value with versions associated with changes provided by the item data store module to identify at least one enumerated change known by the system that the first replica is not aware, wherein the at least one enumerated change is associated with a first particular set of data identified by a first filter; and

send the at least one enumerated change to the first replica; and

a change incorporation module to;

send, to a second replica, a system knowledge value provided by the knowledge store that represents knowledge of changes to the stored data that the system is aware of, and a second filter provided by the filter store module that identifies a second particular set of data in the stored data;

receive at least one received change that exists in the second replica that the system was not aware, wherein the at least one received change is associated with the second particular set of data identified by the second filter;

incorporate the at least one received change into the stored data associated with item data store module;

receive information that identifies at least one non-filtered change to the stored data that is not represented by the first replica knowledge value and is also not associated with the first particular set of data identified by the first filter according to the second replica; and

update the stored data maintained by the first replica using the information that identifies the at least one non-filtered change, wherein updating the stored data maintained by the first replica further comprises creating at least one exception in the first replica knowledge value according to the information that identifies the at least one non-filtered change, the at least one exception referencing the knowledge of changes to the stored data that the first replica was aware before receiving the at least one enumerated change.

11. The system of claim 10 wherein the change enumeration module is further configured to send, to the first replica, the system knowledge value provided by the knowledge store that represents knowledge of changes to the stored data of which the system is aware.

12. The system of claim 10 wherein the change incorporation module is further configured to:

receive a second replica knowledge value that represents knowledge of changes to the stored data which the second replica is aware; and

update the system knowledge value so that the system knowledge value represents knowledge of changes to the stored data which the second replica is aware, for only the second particular set of data identified by the second filter.

13. The system of claim 10 wherein the change incorporation module is further configure to:

receive a made-with-knowledge value from the second replica that represents knowledge of changes to the stored data which the second replica was aware when the at least one received change was made on the second replica;

determine that a conflict exists when, for a single piece of the stored data;

a first change has been made on the system;

a second change has been made on the second replica; and

a first change ID associated with the first change is not in the made-with-knowledge value; and

a second change ID associated with the second change is not in the system knowledge value.

14. The system of claim 10 wherein:

the first filter is a retractable filter; and

the first particular set of data identified by the first filter comprises data identified by a filter criteria applied during the comparing and data identified by the filter criteria applied as time represented by the first replica knowledge value.