REPLICATING DATA ACROSS DATA CENTERS

• US 20180121466A1
• Filed: 12/28/2017
• Published: 05/03/2018
• Est. Priority Date: 08/31/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: AGUILERA, Marcos Kawazoe, CHO, Brian
• Granted Patent: US 10,204,114 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 11/2097 maintaining the standby controller/processing unit updated initialisation or re-synchronisation thereof G06F11/1658 and subgroups
• CPC Class Codes: G06F 16/184 implemented as replicated file system
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 67/60 Scheduling or organising the servicing of application requests, e.g. requests for application data transmissions using the analysis and optimisation of the required network resources admission control or resource allocation H04L47/70

Abstract

The present techniques prioritize transmission of feature information associated with data copies in data transmission, and selectively transmit the data copies when necessary. As the size of the feature information is small compared with the data copies, and as feature information is transmitted using prioritized messages, delays caused by congestion in the network are reduced. Based on the use of prioritized messages, the present techniques provide solutions for replicating data across data centers when conducting various data operations including reading, writing, and modifying data. The present techniques also replicate data across data centers while providing consistency, access locality, and disaster tolerance.

Claims

1. A method comprising:

identifying a data item stored at a first computing device of a network that includes a plurality of computing devices, the network including a plurality of copies of the data item distributed across the plurality of computing devices of the network;

sending, from the first computing device to the plurality of computing devices, a request for a prioritized message from each of the plurality of computing devices, each given prioritized message comprising at least an update indicator associated with a most recent time a copy of the data item was updated at each given computing device of the plurality of computing devices;

receiving, at the first computing device, a plurality of prioritized messages from at least one of the plurality of computing devices, wherein at least one of the plurality of prioritized messages was received via a first path that met one or more first criteria when the message was sent on the first path;

determining that a reply threshold has been met based at least partially on a total number of received prioritized messages;

based on determining that the reply threshold has been met, analyzing the plurality of received prioritized messages to identify a particular prioritized message having a first update indicator that is associated with a copy of the data item that is most recent as compared to all of the plurality of received prioritized messages;

based on identifying the particular prioritized message, identifying a particular computing device of the plurality of computing devices of the network at which the most recent copy of the data item is stored;

sending, from the first computing device to the particular computing device, a request for the most recent copy of the data item to be distributed to the plurality of computing devices of the network; and

receiving, at the first computing device, the most recent copy of the data item via a second path that met one or more second criteria when the most recent copy of the data item was sent on the second path.

2. The method as recited in claim 1, wherein a size of each given prioritized message is smaller than a size of a copy of the data item associated with the given prioritized message.

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

identifying a prioritized message having a second update indicator that is at least as up-to-date as the first update indicator and a different computing device at which a copy of the data item associated with the second update indicator is stored; and

sending, from the first computing device to the different computing device, a request for a copy of the data item stored at the different computing device.

4. The method as recited in claim 3, wherein sending a request for a copy of the data item stored at the different computing device comprises:

sending the first update indicator to a plurality of computing devices; and

requesting each of the plurality of computing devices to send a stored data copy if the stored data copy has an associated update indicator that includes update time information at least as up-to-date as that of the first update indicator.

5. The method as recited in claim 1, further comprising

requesting, by the first computing device, at least one computing device to send a data copy stored at the at least one computing device if the copy of the data item is associated with a second update indicator indicating update time information that is at least as up-to-date as that of the first update indicator;

applying one or more modification commands to the copy of the data item to obtain a modified data copy;

associating a new update indicator with the modified copy of the data item; and

storing the modified copy of the data item and the new update indicator at a local computing device.

6. The method as recited in claim 5, further comprising propagating the modified copy of the data item and the new update indicator from the local computing device to one or more remote computing devices.

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

determining one or more remote computing devices that store one or more copies of the data item associated with the first update indicator from the plurality of computing devices;

sending one or more modification commands and a new update indicator to at least one of the one or more remote computing devices; and

requesting the at least one of the one or more remote computing devices to apply the one or more modification commands to the stored one or more copies of the data item to obtain a modified copy of the data item and associate the new update indicator with the modified copy of the data item.

8. The method of claim 1, wherein a particular path meets the one or more first criteria at a first time, and meets the one or more second criteria at a second time, such that the particular path comprises both the first path and the second path.

9. The method of claim 1, wherein the first path is also the second path.

10. The method of claim 1, wherein the one or more first criteria include one or more of:

a time for data transmission on the first path, a cost for data transmission on the first path, a number of routers on the first path, data volume on the first path, congestion on the first path, or latency on the first path.

11. The method of claim 1, wherein the one or more second criteria include one or more of:

a time for data transmission on the second path, a cost for data transmission on the second path, a number of routers on the second path, data volume on the second path, congestion on the second path, or latency on the second path.

12. A computing device, comprising:

one or more processors; and

one or more computer readable storage media having stored thereon computer-executable instructions that are executable by the one or more processors to cause the computing device to update redundant data within a plurality of computing devices in a network while conserving network bandwidth, the computer-executable instructions including instructions that are executable to cause the computer system to perform at least the following;

identify a data item stored at the computing device, the network including a plurality of copies of the data item distributed across the plurality of computing devices of the network;

send, from the computing device to the plurality of computing devices, a request for a prioritized message from each of the plurality of computing devices, each given prioritized message comprising at least an update indicator associated with a most recent time a copy of the data item was updated at each given computing device of the plurality of computing devices;

receive, at the computing device, a plurality of prioritized messages from at least one of the plurality of computing devices, wherein at least one of the plurality of prioritized messages was received via a first path that met one or more first criteria when the message was sent on the first path;

determine that a reply threshold has been met based at least partially on a total number of received prioritized messages;

based on determining that the reply threshold has been met, analyze the plurality of received prioritized messages to identify a particular prioritized message having a first update indicator that is associated with a copy of the data item that is most recent as compared to all of the plurality of received prioritized messages;

based on identifying the particular prioritized message, identify a particular computing device of the plurality of computing devices of the network at which the most recent copy of the data item is stored;

send, from the computing device to the particular computing device, a request for the most recent copy of the data item to be distributed to the plurality of computing devices of the network; and

receive, at the computing device, the most recent copy of the data item via a second path that met one or more second criteria when the most recent copy of the data item was sent on the second path.

13. The computing device as recited in claim 12, wherein a size of each given prioritized message is smaller than a size of a copy of the data item associated with the given prioritized message.

14. The computing device as recited in claim 12, wherein the computer-executable instructions further include instructions that are executable to cause the computing device to:

identify a prioritized message having a second update indicator that is at least as up-to-date as the first update indicator and a different computing device at which a copy of the data item associated with the second update indicator is stored; and

send, from the computing device to the different computing device, a request for a copy of the data item stored at the different computing device.

15. The computing device as recited in claim 12, wherein the computer-executable instructions further include instructions that are executable to cause the computing device to propagate the most recent copy of the data item from one or more local computing devices to one or more remote computing devices.

16. The computing device of claim 12, wherein a particular path meets the one or more first criteria at a first time, and meets the one or more second criteria at a second time, such that the particular path comprises both the first path and the second path.

17. The computing device of claim 12, wherein the first path is also the second path.

18. The computing device of claim 12, wherein the one or more first criteria include one or more of:

a time for data transmission on the first path, a cost for data transmission on the first path, a number of routers on the first path, data volume on the first path, congestion on the first path, or latency on the first path.

19. The computing device of claim 12, wherein the one or more second criteria include one or more of:

a time for data transmission on the second path, a cost for data transmission on the second path, a number of routers on the second path, data volume on the second path, congestion on the second path, or latency on the second path.

20. A computer program product comprising one or more hardware storage devices having stored thereon computer-executable instructions that are executable by one or more processors of a computer system to cause the computer system to update redundant data within a plurality of computing devices in a network while conserving network bandwidth, the computer-executable instructions including instructions that are executable to cause the computer system to perform at least the following:

identify a data item stored at a first computing device of a network that includes a plurality of computing devices, the network including a plurality of copies of the data item distributed across the plurality of computing devices of the network;

send, from the first computing device to the plurality of computing devices, a request for a prioritized message from each of the plurality of computing devices, each given prioritized message comprising at least an update indicator associated with a most recent time a copy of the data item was updated at each given computing device of the plurality of computing devices;

receive, at the first computing device, a plurality of prioritized messages from at least one of the plurality of computing devices, wherein at least one of the plurality of prioritized messages was received via a first path that met one or more first criteria when the message was sent on the first path;

determine that a reply threshold has been met based at least partially on a total number of received prioritized messages;

based on determining that the reply threshold has been met, analyze the plurality of received prioritized messages to identify a particular prioritized message having a first update indicator that is associated with a copy of the data item that is most recent as compared to all of the plurality of received prioritized messages;

based on identifying the particular prioritized message, identify a particular computing device of the plurality of computing devices of the network at which the most recent copy of the data item is stored;

send, from the first computing device to the particular computing device, a request for the most recent copy of the data item to be distributed to the plurality of computing devices of the network; and

receive, at the first computing device, the most recent copy of the data item via a second path that met one or more second criteria when the most recent copy of the data item was sent on the second path.