System and method for replicating data in a distributed system

• US 7,386,715 B2
• Filed: 02/01/2005
• Issued: 06/10/2008
• Est. Priority Date: 11/01/2001
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Bishop, Christopher Michael, Lawrence, Neil David, Taylor, Michael James, Rowstron, Antony Ian Taylor
• Primary Examiner(s): ELAMIN, ABDELMONIEM I
• Application Number:
  US11/049,018
• Publication Number:
  US 20050144538A1
• Time in Patent Office: 1,225 Days
• Field of Search: 713/1, 713/2, 713/100, 707/10, 707200-204
• US Class Current: 713/100
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

It is common in distributed systems to replicate data. In many cases, this data evolves in a consistent fashion, and this evolution can be modeled. A probabilistic model of the evolution allows us to estimate the divergence of the replicas and can be used by the application to alter its behavior, for example, to control synchronization times, to determine the propagation of writes, and to convey to the user information about how much the data may have evolved. In this paper, we describe how the evolution of the data may be modeled and outline how the probabilistic model may be utilized in various applications, concentrating on a news database example.

Claims

1. A method for synchronizing data, comprising:

receiving information indicative of a rate of change to data in a first data set;

dynamically selecting a time to synchronize at least a portion of data in a second data set with corresponding data in the first data set as a function of the information indicative of the rate of change.

2. The method as recited in claim 1, where the function comprises using a previous rates of change to data in the first data set.

3. The method as recited in claim 2, wherein the function comprises the use of a histogram.

4. The method as recited in claim 2, wherein the previous rates of change comprises a log to record the frequency of changes to data in the first data set.

5. The method as recited in claim 1, wherein the first data set is maintained by a local computer and the second data set is maintained by a remote computer.

6. The method as recited in claim 5, wherein the remote computer communicates with the local computer over a network.

7. The method as recited in claim 1, wherein the second data set is maintained by an application program.

8. The method as recited in claim 7, wherein the application program comprises one of a mobile news database, an e-mail client, and a web cache.

9. A computing apparatus, comprising:

a processor;

a second data set stored in a memory in communication with said processor;

a second memory in communication with said processor and storing computer instructions for receiving information indicative of a rate of change to data in a first data set; and

a third memory communication with said processor and storing computer instructions for dynamically selecting a time to synchronize at least a portion of data in the second data set with corresponding data in the first data set as a function of the information indicative of the rate of change.

10. The apparatus as recited in claim 9, where the function comprises using a previous rates of change to data in the first data set.

11. The apparatus as recited in claim 10, wherein the function comprises the use of a histogram.

12. The apparatus as recited in claim 10, wherein the previous rates of change comprises a log to record the frequency of changes to data in the first data set.

13. The apparatus as recited in claim 9, wherein the first data set is maintained by a local computer and the second data set is maintained by a remote computer.

14. The apparatus as recited in claim 13, wherein the remote computer communicates with the local computer over a network.

15. The apparatus as recited in claim 9, wherein the second data set is maintained by an application program.

16. A computer-readable storage medium bearing computer-readable instructions for synchronizing data, comprising:

computer-readable instructions for receiving information indicative of a rate of change to data in a first data set; and

computer-readable instructions for dynamically selecting a time to synchronize at least a portion of data in a second data set with corresponding data in the first data set as a function of the information indicative of the rate of change.

17. The computer-readable medium as recited in claim 16, where the function comprises using a previous rates of change to data in the first data set.

18. The computer-readable medium as recited in claim 17, wherein the function comprises the use of a histogram.

19. The computer-readable medium as recited in claim 17, wherein the using previous rates of change comprises recording in a log the frequency of changes to data in the first data set.

20. The computer-readable medium as recited in claim 16, comprising maintaining the first data set on a local computer and maintaining the second data set on a remote computer.