Selecting computing nodes in cloud service using replication topologies

• US 9,110,724 B2
• Filed: 02/08/2011
• Issued: 08/18/2015
• Est. Priority Date: 02/08/2011
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Balakrishnan, Mahesh, Aguilera, Marcos K., Tiwana, Birjodh, Ballani, Hitesh
• Primary Examiner(s): SALL, EL HADJI MALICK
• Application Number:
  US13/022,635
• Publication Number:
  US 20120203888A1
• Time in Patent Office: 1,652 Days
• Field of Search: 709201-226, 709/200, 711114-163
• US Class Current: 1/1
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 9/505 considering the load

Abstract

A cloud statistics server generates statistics for a cloud service based on an identified data item and an identified operation. The cloud service may include various computing nodes and storage nodes. The cloud statistics may include expected completion times for the identified operation and the identified data item with respect to each of the computing nodes. A computing node may be selected to execute the identified operation based on the expected completion times. The generated statistics may be generated by the cloud statistics server using a network topology associated with the data item that is based on the latencies or expected transfer times between the various storage nodes and computing nodes, and a replication strategy used by the cloud service. The topology may be implemented as a directed graph with edge weights corresponding to expected transfer times between each node.

Claims

1. A method comprising:

receiving an identifier of a data item and an identifier of an operation at a computing device, wherein the data item is stored by a cloud service comprising a plurality of storage nodes and a plurality of computing nodes;

requesting a topology from the cloud service using the identifier of a data item by the computing device;

receiving the topology from the cloud service by the computing device, the topology identifying one or more storage nodes from the plurality of storage nodes used to store the identified data item and a replication strategy used by the identified one or more storage nodes;

determining by the computing device, for each computing node of the plurality of computing nodes, an expected completion time for the computing node to complete the identified operation on the identified data item given the replication strategy used by the identified one or more of storage nodes; and

determining a minimum expected completion time of the determined expected completion times by the computing device.

2. The method of claim 1, further comprising:

providing the determined minimum expected completion time.

3. The method of claim 2, further comprising providing an identifier of the computing node associated with the determined minimum expected completion time.

4. The method of claim 3, further comprising causing the identified operation to be performed using the identified data item at the computing node associated with the determined minimum expected completion time.

5. The method of claim 1, wherein the replication strategy includes one or more expected transfer times associated with each of the one or more identified storage nodes and the plurality of computing nodes, and determining the expected completion time for the computing node to complete the identified operation on the identified data item given the replication strategy used by the identified one or more storage nodes comprises determining a combination of the expected transfer times between the computing node and one or more of the storage nodes identified by the replication strategy.

6. The method of claim 5, further comprising determining the combination using one or more of a summation operation, a minimum operation, and a maximum operation.

7. The method of claim 1, wherein the identified operation is one of a read operation or an update operation.

8. The method of claim 1, wherein the replication strategy comprises an erasure coding replication strategy.

9. The method of claim 1, wherein the replication strategy comprises a synchronous mirroring replication strategy.

10. The method of claim 1, wherein the topology comprises a directed graph.

11. The method of claim 1, further comprising determining, for each computing node of a subset of the plurality of computing nodes, an expected cost for the identified operation and the identified data item using the replication strategy.

12. A method comprising:

receiving an identifier of an operation, an identifier of a data item, and a time constraint by a computing device, wherein the data item is stored in a cloud service comprising a plurality of storage nodes and a plurality of computing nodes;

requesting a topology from the cloud service by the computing device using the identifier of a data item;

receiving the topology from the cloud service by the computing device, the topology identifying one or more storage nodes from the plurality of storage nodes used to store the identified data item, and a replication strategy used by the identified one or more storage nodes, wherein the replication strategy includes one or more expected transfer times associated with each of the one or more identified storage nodes and the plurality of computing nodes;

for each computing node, combining the expected transfer times associated with the computing node and one or more of the identified storage nodes according to the replication strategy to generate an expected completion time of the operation for the computing node;

determining one or more computing nodes with an expected completion time that is less than the time constraint; and

providing identifiers of the determined one or more computing nodes.

13. The method of claim 12, wherein the identified operation comprises a sequence of operations, and the identified data item comprises a plurality of identified data items.

14. The method of claim 12, wherein the topology comprises a directed graph.

15. The method of claim 12, wherein the identified operations are one of a read operation or an update operation.

16. The method of claim 12, wherein the replication strategy comprises an erasure coding replication strategy.

17. The method of claim 12, wherein the replication strategy comprises a synchronous mirroring replication strategy.

18. A system comprising:

a cloud service comprising a plurality of storage nodes and a plurality of computing nodes; and

a cloud statistics server adapted to;

receive an identifier of a data item and an identifier of an operation, wherein the data item is stored by the cloud service;

request a topology from the cloud service using the identifier of a data item;

receive the topology from the cloud service, wherein the topology identifies one or more storage nodes from the plurality of storage nodes used to store the identified data item and a replication strategy used by the identified one or more storage nodes;

determine, for each computing node of the plurality of computing nodes, an expected completion time for the computing node to complete the identified operation on the identified data item given the replication strategy used by the identified one or more of storage nodes; and

determine a minimum expected completion time of the determined expected completion times.

19. The system of claim 18, wherein the cloud statistics server is further adapted to:

provide the determined minimum expected completion time.

20. The system of claim 19, wherein the cloud statistics server is further adapted to provide an identifier of the computing node associated with the determined minimum expected completion time.