Architecture for partition computation and propagation of changes in data replication

• US 7,406,499 B2
• Filed: 05/09/2003
• Issued: 07/29/2008
• Est. Priority Date: 05/09/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Narayanan, Charumathy, Singh, Ram P.
• Primary Examiner(s): Burgess; Glenton B.
• Assistant Examiner(s): Higa; Brendan Y
• Application Number:
  US10/434,647
• Publication Number:
  US 20050015436A1
• Time in Patent Office: 1,908 Days
• Field of Search: 709/248, 709203-207, 709213-214, 707/201, 707/8
• US Class Current: 709/205
• 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
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

Abstract

The present invention provides for facilitating synchronization in a data source/data destination environment using data replicas. When a plurality of destinations request synchronization with a source, a first destination selected for synchronization is processed such that differences between the first destination data and source data is determined and persisted in a partition update. After updating the first destination, the synchronization process continues only for those remaining destinations that will be affected by the partition change, as determined by the persisted data, and then as updated by the persisted data.

Claims

1. A system embodied on a computer readable storage medium that facilitates synchronization in a client/server environment using a plurality of destination replicas at a plurality of clients, comprising:

a receiver component that receives information relating to a partition update in data from a first destination replica at a first client to a source replica, wherein the partition update represents all rows of a partition of the first replica that have been modified since the last synchronization of the first destination replica, the receiver component assigns a generation identifier to all of the rows of the partition update, wherein the value of the generation identifier is the same for all rows of the partition update, wherein a partition is a subset of rows of replica data;

a determination component that propagates the partition update and determines a priori to synchronization by other clients which of the other clients'"'"' destination replicas will be affected by the partition update, wherein the determination component employs a set based query on server tables to make the determination, wherein the server tables comprise a partition metadata table, a current changes metadata table, and a past changes metadata table, wherein the partition metadata table identifies each partition that is relevant to each destination replica, the current changes metadata table identifies each row that is currently part of each partition, the past changes metadata table identifies each row that was previously part of each partition; and

an update component that where upon synchronization by the clients, each client determined to be affected by the partition change is updated with all generations of changes that have not propagated to the client to facilitate partition consistency across the plurality of clients, the update component employs a generation partition mapping table that identifies each generation identifier that is relevant to each partition and a generation metadata table the identifies each generation that has been propagated to each client to identify the changes that have not propagated to each client.

2. The system of claim 1, the information relating to the partition update received in the form of replication metadata.

3. The system of claim 1, the server tables further comprising a row metadata table that identifies the time of each change to each row.

4. The system of claim 1, the partitions of the client and the first destination replica aligned such that a row undergoing updating is updated.

5. The system of claim 1, a partition of a client aligned with the first destination replica such that a row undergoing updating is updated, and expanded utilizing a filter to get related rows from joined tables.

6. The system of claim 5, the row expanded utilizing the filter, which is a join filter, the expansion computation in accordance with a set-based query.

7. The system of claim 5, the filter is a dynamic row filter.

8. The system of claim 1, the partition updates comprise a destination replica of metadata that is membership information persisted for synchronization with the other clients that are affected by the partition change.

9. The system of claim 8, the persisted membership information including a mapping between a row identifier of a changed row and a partition identity of a respective replica of the other clients.

10. The system of claim 8, the persisted membership information that includes at least one of a row deletion and a row update requires row information about past memberships.

11. The system of claim 1, the partition updates propagated in accordance with a synchronization anchor value such that only the other clients that were not updated during the last synchronization get updated.

12. The system of claim 1, the partition updates tracked with a change tracking logic that processes changes in the partition when a row of the first destination replica is at least one of updated, inserted, and deleted.

13. The system of claim 1, further comprising a change enumeration mechanism that enumerates changes in the partition update in the other clients during synchronization therewith that processes changes in the other clients that occurred since the last synchronization.

14. The system of claim 13, a delete and a partition update enumerated by selecting a row whose synchronization anchor is newer than the negotiated synchronization anchor of the session.

15. The system of claim 14, the row selected from metadata that reflects past changes of the row.

16. The system of claim 13, an insert and a partition update enumerated by selecting a row whose synchronization anchor is more new than the negotiated synchronization anchor of the session.

17. The system of claim 16, the row selected from metadata that reflects current changes of the row.

18. The system of claim 1, further comprising a synchronization anchor assigned to changes propagated from the first destination replica, the synchronization anchor in the form of generation identification information.

19. The system of claim 18, the generation identification information of a first partition overwritten with generation identification information of a second partition when the respective client synchronizes.

20. A server based system comprising the system of claim 1.

21. A network comprising the system of claim 1.

22. A method of facilitating synchronization in a client/server environment using a plurality of destination replicas at a plurality of clients, comprising:

receiving information relating to a partition update in data from a first destination replica, wherein the partition update represents all rows of a partition of the first replica that have been modified since the last synchronization of the first destination replica, wherein a partition is a subset of rows of replica data;

assigning a generation identifier to all of the rows of the partition update, wherein the value of the generation identifier is the same for all rows of the partition update;

determining a priori to synchronization by other clients'"'"' destination replicas, which other clients will be affected by the partition update, wherein the determining employs a set based query on server tables to make a determination, wherein the server tables comprise a partition metadata table, a current changes metadata table, and a past changes metadata table, wherein the partition metadata table identifies each partition that is relevant to each destination replica, the current changes metadata table identifies each row that is currently part of each partition, the past changes metadata table identifies each row that was previously part of each partition;

upon synchronization by the clients, employing a generation partition mapping table that identifies each generation identifier that is relevant to each partition and a generation metadata table the identifies each generation that has been propagated to each client to identify generation of changes that have not propagated to each client; and

updating the clients determined to be affected by the partition change with all generations of changes that have not propagated to each client to facilitate partition consistency across the plurality of clients.

23. The method of claim 22, receiving the information relating to the partition update in the form of replication metadata.

24. The method of claim 22, the server tables further comprising a row metadata table that identifies the time of each change to each row.

25. The method of claim 22, further comprising the step of aligning partitions of the client and the first destination replica such that a row undergoing updating is updated.

26. The method of claim 22, further comprising the step of aligning partitions of the client and the first destination replica such that a row undergoing updating is updated, and expanded utilizing a filter to get related rows from joined tables.

27. The method of claim 26, the row expanded utilizing the filter, which is a join filter, the expansion computation in accordance with a set-based query.

28. The method of claim 26, the filter is a dynamic row filter.

29. The method of claim 22, the partition updates comprise a partial replica of metadata that is membership information persisted for synchronization with the other clients that are affected by the partition change.

30. The method of claim 29, the persisted membership information including a mapping between a row identifier of a changed row and a partition identity of a respective replica of the other clients.

31. The method of claim 29, the persisted membership information that includes at least one of a row deletion and a row update requires row information about past memberships.

32. The method of claim 22, the partition updates propagated in accordance with a synchronization anchor value such that only the other clients that were not updated during the last synchronization get updated.

33. The method of claim 22, the partition updates tracked with a change tracking logic that processes changes in the partition when a row of the first destination replica is at least one of updated, inserted, and deleted.

34. The method of claim 22, further comprising the step of enumerating changes in the other clients during synchronization therewith utilizing a change enumeration mechanism that processes changes in the other clients that occurred since the last synchronization.

35. The method of claim 34, a delete and a partition update enumerated by selecting a row whose synchronization anchor is newer than the negotiated synchronization anchor of the session.

36. The method of claim 35, the row selected from metadata that reflects past changes of the row.

37. The method of claim 34, an insert and a partition update enumerated by selecting a row whose synchronization anchor is newer than the negotiated synchronization anchor of the session.

38. The method of claim 37, the row selected from metadata that reflects current changes of the row.

39. The method of claim 22, further comprising the step of assigning a synchronization anchor to changes propagated from the first destination replica, the synchronization anchor in the form of generation identification information.

40. The method of claim 39, the generation identification information of a first partition overwritten with generation identification information of a second partition when the respective client synchronizes.

41. A computer-readable medium having stored thereon computer executable instructions for performing the method of claim 22.

42. A system embodied on a computer readable storage medium that facilitates synchronization in a client/server environment using replicas, comprising:

means for receiving information relating to a partition update in data from a first replica at a first client, wherein the partition update represents all rows of the first replica that have been modified since the last synchronization of the first replica;

means for assigning a generation identifier to all of the rows of the partition update, wherein the value of the generation identifier is the same for all rows of the partition update, wherein a partition is a subset of rows of replica data;

means for determining a priori to synchronization by other clients, which other clients'"'"' replicas will be affected by the partition update, wherein the determining employs a set based query on server tables to make the determination, wherein the server tables comprise a partition metadata table, a current changes metadata table, and a past changes metadata table, wherein the partition metadata table identifies each partition that is relevant to each destination replica, the current changes metadata table identifies each row that is currently part of each partition, the past changes metadata table identifies each row that was previously part of each partition;

upon synchronization by the clients, means employing a generation partition mapping table that identifies each generation identifier that is relevant to each partition and a generation metadata table the identifies each generation that has been propagated to each client to identify generations of changes that have not propagated to each client; and

means for updating the clients determined to be affected by the partition change with all generations of changes that have not propagated to each client to facilitate partition consistency across the plurality of clients.

43. A method of facilitating synchronization in a client/server environment using replicas, comprising:

receiving information relating to a partition update in data from a first replica, the received information in the form of replication metadata that is membership information of all changed rows of the first replica since the last synchronization of the first replica persisted for synchronization with the other clients, the replication metadata including a generation identifier to all of the changes rows of the partition update, wherein the value of the generation identifier is the same for all rows of the partition update, wherein a partition identifies a subset of replica data;

determining a priori to synchronization by other clients, which other clients will be affected by the partition update, wherein the determining employs a set based query on server tables to make the determination, wherein the server tables comprise a partition metadata table, a current changes metadata table, and a past changes metadata table, wherein the partition metadata table identifies each partition that is relevant to each destination replica, the current changes metadata table identifies each row that is currently part of each partition, the past changes metadata table identifies each row that was previously part of each partition;

upon synchronization by the clients, employing a generation partition mapping table that identifies each generation identifier that is relevant to each partition and a generation metadata table the identifies each generation that has been propagated to each client to identify generation of changes that have not propagated to each client; and

updating the clients determined to be affected by the partition change with all generations of changes that have not propagated to each client to facilitate partition consistency across the plurality of clients.

44. A system embodied on a computer readable storage medium that facilitates synchronization of data collections using replicas, comprising:

a receiver component for receiving information relating to a partition update in data from a first replica, wherein the partition represents all rows of the first replica that have been modified since the last synchronization of the first replica, the receiver component assigns a generation identifier to all of the rows of the partition update, wherein the value of the generation identifier is the same for all rows of the partition update, wherein a partition identifies a subset of replica data;

a determination component determining a priori the synchronization by other destination data collections, which other destination data collections will be affected by the partition change, wherein the determination component employs a set based query on server tables to make the determination, wherein the server tables comprise a partition metadata table, a current changes metadata table, and a past changes metadata table, wherein the partition metadata table identifies each partition that is relevant to each destination replica, the current changes metadata table identifies each row that is currently part of each partition, the past changes metadata table identifies each row that was previously part of each partition; and

an update component where upon synchronization by the destination data collections, each destination data collection determined to be affected by the partition change is updated with all generations of changes that have not propagated to the destination data collection to facilitate partition consistency across the plurality of destination data collections, the update component employs generation identifiers and a generation partition mapping table that identifies each generation identifier that is relevant to each partition and a generation metadata table the identifies each generation that has not propagated to each destination data collection.

45. The system of claim 44, the information relating to the partition update received in the form of replication metadata.