Latency reduction with pre-moving of distributed data and adaptive allocating of compute operations

• US 10,320,708 B2
• Filed: 11/20/2015
• Issued: 06/11/2019
• Est. Priority Date: 11/20/2015
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Bahl, Paramvir, Ananthanarayanan, Ganesh, Kandula, Srikanth, Bodik, Peter, Pu, Qifan, Akella, Srinivasa Aditya
• Primary Examiner(s): Lazaro, David R
• Assistant Examiner(s): Ye, Zi
• Application Number:
  US14/948,217
• Publication Number:
  US 20170149691A1
• Time in Patent Office: 1,299 Days
• Field of Search: 709226, 709228, 707640
• CPC Class Codes: H04L 41/147 for predicting network behaviour
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 47/83 based on usage prediction

Abstract

Latency in responding to queries directed to geographically distributed data can be reduced by allocating individual steps, of a multi-step compute operation requested by the query, among the geographically distributed computing devices so as to reduce the duration of shuffling of intermediate data among such devices, and, additionally, by pre-moving, prior to the receipt of the query, portions of the distributed data that are input to a first step of the multistep compute operation, to, again, reduce the duration of the exchange of intermediate data. The pre-moving of input data occurring, and the adaptive allocation of intermediate steps, are prioritized for high-value data sets. Additionally, a threshold increase in a quantity of data exchanged across network communications can be established to avoid incurring network communication usage without an attendant gain in latency reduction.

Claims

1. A method of reducing latency of a multi-step compute operation that is performed by geographically distributed computing devices on a set of geographically distributed data, the method comprising the steps of:

predicting a duration of a first data exchange between a first computing device at a first geographical location and a second computing device at a second geographical location, the first data exchange comprising;

the first computing device transmitting a first portion of a first subset of intermediate data to the second computing device; and

the second computing device transmitting a first portion of a second subset of the intermediate data to the first computing device;

wherein the first portions of the first and second subsets of the intermediate data are based on a first allocation, of processing of a subsequent step of a multi-step compute operation, among the first and second computing devices;

predicting a duration of a second data exchange between the first and second computing devices, the second data exchange comprising;

the first computing device transmitting a second portion of the first subset of the intermediate data to the second computing device; and

the second computing device transmitting a second portion of the second subset of the intermediate data to the first computing device;

wherein the second portions of the first and second subsets of the intermediate data are based on a second allocation, of the processing of the subsequent step of the multi-step compute operation, among the first and second computing devices, the second allocation differing from the first allocation; and

allocating, among the first and second computing devices, the processing of the subsequent step of the multi-step compute operation in accordance with the second duration is less than the first duration;

wherein the allocating causes the first computing device to transmit the second portion of the first subset of the intermediate data to the second computing device and further causes the second computing device to transmit the second portion of the second subset of the intermediate data to the first computing device; and

wherein processing of a prior step of the multi-step compute operation by the first and second computing devices resulted in the first computing device locally generating the first subset of the intermediate data and second computing device locally generating the second subset of the intermediate data.

2. The method of claim 1, further comprising:

moving a portion of initial data, distributed between the first and second computing devices, from the second computing device to the first computing device if the second duration is less than the first duration and the second allocation allocated more of the processing of the subsequent step of the multi-step compute operation to the second computing device;

wherein the moving is initiated prior to a receipt of a query triggering the multi-step compute operation.

3. The method of claim 2, wherein the initiating the moving of the portion of the initial data is not performed if an aggregate amount of data previously moved is greater than a predetermined threshold.

4. The method of claim 2, wherein the moving terminates upon the receipt of the query.

5. The method of claim 2, further comprising:

predicting when the query will be received based on prior queries.

6. The method of claim 5, further comprising:

assigning a first value to the initial data inversely proportionally to a first lag between a current time and a predicted time when the query will be received;

assigning a second value to a second set of geographically distributed data inversely proportionally to a second lag between a current time and a predicted time when a second query, directed to the second set of geographically distributed data, will be received; and

performing the steps of claim 1 if the first value is greater than the second value.

7. The method of claim 2, wherein the processing of the prior step by the first and second computing devices is performed on the initial data after the moving the portion of the initial data from the second computing device to the first computing device.

8. The method of claim 1, wherein the moving is performed even after the receipt of the query if a quantity of the intermediate data generated by the prior step of multi-step compute operation is greater than a quantity of the initial data.

9. A system comprising:

a first computing device in a first geographic location having locally accessible to it a first subset of intermediate data, the first subset of the intermediate data having been locally generated by the first computing device processing a prior step of a multi-step compute operation;

a second computing device in a second, different geographic location having locally accessible to it a second subset of the intermediate data, the second subset of the intermediate data having been locally generated by the second computing device processing the prior step of the multi-step compute operation;

a communicational connection between the first and second computing devices allowing data to be provided from the first computing device to the second computing device faster than data can be provided from the second computing device to the first computing device; and

one or more computer-readable media comprising computer-executable instructions, which, when executed, cause a computing device to;

predict a duration of a first data exchange between the first and second computing devices, the first data exchange comprising;

the first computing device transmitting a first portion of the first subset of the intermediate data to the second computing device; and

the second computing device transmitting a first portion of the second subset of the intermediate data to the first computing device;

wherein the first portions of the first and second subsets of the intermediate data are based on a first allocation, of processing of a subsequent step of the multistep compute operation, among the first and second computing devices;

predict a duration of a second data exchange between the first and second computing devices, the second data exchange comprising;

the first computing device transmitting a second portion of the first subset of the intermediate data to the second computing device; and

the second computing device transmitting a second portion of the second subset of the intermediate data to the first computing device;

wherein the second portions of the first and second subsets of the intermediate data are based on a second allocation, of the processing of the subsequent step of the multi-step compute operation, among the first and second computing devices, the second allocation differing from the first allocation; and

allocate processing of the subsequent step of the multi-step compute operation among the first and second computing devices in accordance with the second allocation if the second duration is less than the first duration;

wherein the allocating causes the first computing device to transmit the second portion of the first subset of the intermediate data to the second computing device and further causes the second computing device to transmit the second portion of the second subset of the intermediate data to the first computing device.

10. The system of claim 9, wherein the computer-executable instructions causing the computing device to allocate the processing of the subsequent step in accordance with the second allocation comprise computer-executable instructions, which, when executed, cause the computing device to:

instruct the first computing device to transmit the second portion of the first subset of the intermediate data to the second computing device; and

instruct the second computing device to transmit the second portion of the second subset of the intermediate data to the first computing device.

11. The system of claim 9, wherein the one or more computer-readable media comprise further computer-executable instructions, which, when executed, cause the computing device to:

instruct the second computing device to move a portion of initial data, distributed between the first and second computing devices, from the second computing device to the first computing device if the second duration is less than the first duration and the second allocation allocated more of the processing of the subsequent step of the multi-step compute operation to the second computing device;

wherein the moving is initiated prior to a receipt of a query triggering the multi-step compute operation.

12. The system of claim 11, wherein the computer-executable instructions causing the computing device to instruct the second computing devices to move the portion of the initial data are not executed if an aggregate amount of data previously moved, is greater than a predetermined threshold.

13. The system of claim 11, wherein the computer-executable instructions causing the computing device to instruct the second computing devices to move the portion of the initial data are executed even after the receipt of the query if a quantity of intermediate data generated by the prior step of the multi-step compute operation is greater than a quantity of the initial data.

14. The system of claim 11, wherein the one or more computer-readable media comprise further computer-executable instructions, which, when executed, cause the computing device to:

predict when the query will be received based on prior queries.

15. The system of claim 14, wherein

the one or more computer-readable media comprise further computer-executable instructions, which, when executed, cause the computing device to:

assign a first value to the initial data inversely proportionally to a first lag between a current time and a predicted time when the query will be received;

assign a second value to a second set of geographically distributed data inversely proportionally to a second lag between a current time and a predicted time when a second query, directed to the second set of geographically distributed data, will be received; and

execute the computer-executable instructions if the first value is greater than the second value.

16. The system of claim 11, wherein the processing of the prior step by the first and second computing devices is performed on the initial data after the moving the portion of the initial data from the second computing device to the first computing device.

17. The system of claim 11, wherein the one or more computer-readable media comprise further computer-executable instructions, which, when executed, cause the computing device to instruct the second computing device to terminate the moving of the portion of the initial data upon receipt of the query.

18. A computing device comprising:

one or more processing units; and

one or more computer-readable storage media comprising computer-executable instructions, which, when executed by at least some of the one or more processing units, cause the computing device to;

predict a duration of a first data exchange between a first computing device in a first geographic location and a second computing device in a second, different geographic location, the first data exchange comprising;

the first computing device transmitting a first portion of a first subset of intermediate data to the second computing device; and

the second computing device transmitting a first portion of a second subset of the intermediate data to the first computing device;

wherein the first portions of the first and second subsets of the intermediate data are based on a first allocation, of processing of a subsequent step of a multi- step compute operation, among the first and second computing devices;

predict a duration of a second data exchange between the first and second computing devices, the second data exchange comprising;

the first computing device transmitting a second portion of the first subset of the intermediate data to the second computing device; and

the second computing device transmitting a second portion of the second subset of the intermediate data to the first computing device;

wherein the second portions of the first and second subsets of the intermediate data are based on a second allocation, of the processing of the subsequent step of the multi-step compute operation, among the first and second computing devices, the second allocation differing from the first allocation; and

allocate, among the first and second computing devices, the processing of the subsequent step of the multi-step compute operation in accordance with the second allocation if the second duration is less than the first duration;

wherein the allocating causes the first computing device to transmit the second portion of the first subset of the intermediate data to the second computing device and further causes the second computing device to transmit the second portion of the second subset of the intermediate data to the first computing device; and

wherein processing of a prior step of the multi-step compute operation by the first and second computing devices resulted in the first computing device locally generating the first subset of the intermediate data and second computing device locally generating the second subset of the intermediate data.

19. The computing device of claim 18, wherein the computer-executable instructions causing the computing device to allocate the processing of the subsequent step in accordance with the second allocation comprise computer-executable instructions, which, when executed, cause the computing device to:

instruct the first computing device to transmit the second portion of the first subset of the intermediate data to the second computing device; and

instruct the second computing device to transmit the second portion of the second subset of the intermediate data to the first computing device.

20. The computing device of claim 18, wherein the one or more computer-readable media comprise further computer-executable instructions, which, when executed, cause the computing device to:

instruct the second computing device to move a portion of initial data, distributed between the first and second computing devices, from the second computing device to the first computing device if the second duration is less than the first duration and the second allocation allocated more of the processing of the subsequent step of the multi-step compute operation to the second computing device;

wherein the moving is initiated prior to a receipt of a query triggering the multi-step compute operation.