System and method for replicating data in a distributed system

• US 20030084361A1
• Filed: 11/01/2001
• Published: 05/01/2003
• Est. Priority Date: 11/01/2001
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Taylor Rowstron, Antony Ian, Taylor, Michael James, Bishop, Christopher Michael, Lawrence, Neil David
• Granted Patent: US 6,889,333 B2
• Time in Patent Office: Days
• US Class Current: 713/400
• 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 in first and second databases, comprising:

receiving information indicative of changes over a predetermined period of time to data in the first database;

selecting a time to synchronize data in the second database with data in the first database where the time selection is based on the information indicative of the changes over the predetermined period of time.

2. The method as recited in claim 1, further comprising:

preparing a probabilistic model of the rate of change of the information indicative of changes.

3. The method as recited in claim 2, wherein the probabilistic model comprises a histogram having bins comprising a predetermined time interval.

4. The method as recited in claim 1, wherein the information indicative of changes comprises a log indicative of changes to data in the first database.

5. The method as recited in claim 1, wherein the first database is maintained by a local computer and the second database 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 database 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. The method as recited in claim 1, wherein at least two times are selected to synchronize the first and second databases that are asynchronous with respect to one another.

10. The method as recited in claim 9, wherein the times selected to synchronize the first and second databases are selected to minimize staleness of data in the second database.

11. The method as recited in claim 3, wherein the synchronization time is adaptively selected based on the histogram.

12. The method as recited in claim 1, wherein the second database comprises a subset of the first database.

13. A computing apparatus, comprising:

an application data store;

means for receiving information indicative of changes over a predetermined period of time to data in a first data store;

program code that synchronizes data in the application data store with data in the first data store where the time selection is based on the information indicative of the changes over the predetermined period of time.

14. The apparatus as recited in claim 13, further comprising:

preparing a probabilistic model of the rate of change of the information indicative of changes.

15. The apparatus as recited in claim 14, wherein the probabilistic model comprises a histogram having bins comprising a predetermined time interval.

16. The apparatus as recited in claim 13, wherein the information indicative of change comprises a log indicative of changes to data in the first data store.

17. The apparatus as recited in claim 13, wherein the first data store is maintained by a computer that is remote from the computing apparatus.

18. The apparatus as recited in claim 17, wherein the means for receiving communicates with the remote computer over a network.

19. The apparatus as recited in claim 13, wherein the application data store is maintained by an application program.

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

21. The apparatus as recited in claim 13, wherein at least two times are selected to synchronize the application data store and the first data store that are asynchronous with respect to one another.

22. The apparatus as recited in claim 21, wherein the times selected to synchronize the application data store and first data store are selected to minimize staleness of data in the second data store.

23. The apparatus as recited in claim 15, wherein the synchronization time is adaptively selected based on the histogram.

24. The apparatus as recited in claim 13, wherein the application data store comprises a subset of the data in the first data store.

25. A computer-readable medium bearing computer-readable instructions for synchronizing data in first and second databases, carrying out the steps of:

receiving information indicative of changes over a predetermined period of time to data in the first database;

selecting a time to synchronize data in the second database with data in the first database where the time selection is based on the information indicative of the changes over the predetermined period of time.

26. The computer-readable medium as recited in claim 25, further comprising:

preparing a probabilistic model of the rate of change of the information indicative of changes.

27. The computer-readable medium as recited in claim 26, wherein the probabilistic model comprises a histogram having bins comprising a predetermined time interval.

28. The computer-readable medium as recited in claim 25, wherein the information indicative of changes comprises a log indicative of changes to data in the first database.

29. The computer-readable medium as recited in claim 25, wherein the first database is maintained by a local computer and the second database is maintained by a remote computer.

30. The computer-readable medium as recited in claim 29, wherein the remote computer communicates with the local computer over a network.

31. The computer-readable medium as recited in claim 25, wherein the second database is maintained by an application program.

32. The computer-readable medium as recited in claim 31, wherein the application program comprises one of a mobile news database, an e-mail client, and a web cache.

33. The computer-readable medium as recited in claim 25, wherein at least two times are selected to synchronize the first and second databases that are asynchronous with respect to one another.

34. The computer-readable medium as recited in claim 33, wherein the times selected to synchronize the first and second databases are selected to minimize staleness of data in the second database.

35. The computer-readable medium as recited in claim 27, wherein the synchronization time is adaptively selected based on the histogram.

36. The computer-readable medium as recited in claim 25, wherein the second database comprises a subset of the first database.