Filtered Replication of Data Stores

• US 20060190572A1
• Filed: 04/27/2006
• Published: 08/24/2006
• Est. Priority Date: 07/31/2003
• Status: Active Grant

• 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
• Granted Patent: US 7,440,985 B2
• Time in Patent Office: Days
• US Class Current: 709/220
• 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 multi-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 can make 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 of which a first replica is aware, and a filter that identifies a particular set of data in the stored data;

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 of which the first replica is not aware, wherein the at least one change is associated with the particular set of data identified by the filter; and

sending the at least one change to the first replica.

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 particular set of data identified by the 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 filter is a retractable filter; and

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

5. The method of claim 1 further comprising:

a list associated with the 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 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 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 filter when the filter criteria identifies stored data that is in the filter; and

adding a version associated with exit of the piece of data from the filter when the filter criteria identifies stored data that is not in the 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 method for replicating at least one change to stored data between replicas in a sync community wherein each replica can make changes independently of other replicas in the sync community, comprising:

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

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

incorporating the at least one received change into the stored data maintained by the first replica.

11. The method of claim 10, further comprising:

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

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

12. The method of claim 10, further comprising:

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 particular set of data identified by the filter according to the second replica;

updating the stored data maintained by the first replica using the information that identifies the at least one non-filtered change.

13. The method of claim 12 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 of which the first replica was aware before receiving the at least one change.

14. The method of claim 12 wherein updating the stored data maintained by the first replica further comprises deleting at least one part of the stored data corresponding to the information that identifies the at least one non-filtered change.

15. The method of claim 10, wherein incorporating the at least one received change further comprises:

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

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

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

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

and a second change ID associated with the second change is not in the first replica knowledge value.

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

an item data store module configured to manage the stored data;

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

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

a change enumeration module configured to;

receive a first replica knowledge value that represents knowledge of changes to the stored data of which a first replica is aware, and a first filter that identifies a first particular set of data in the stored data;

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 of which the first replica is not aware, wherein the at least one enumerated change is associated with the first particular set of data identified by the first filter; and

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

a change incorporation module configured to;

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

receive at least one received change that exists in the second replica of which 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; and

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

17. The system of claim 16 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.

18. The system of claim 16 wherein the change incorporation module is further configured to:

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

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

19. The system of claim 16 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 of 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; and

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

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

20. The system of claim 16 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 compare operation and data identified by the filter criteria applied as of the time represented by the first replica knowledge value.