STREAMING QUERY RESOURCE CONTROL

• US 20150249583A1
• Filed: 03/03/2014
• Published: 09/03/2015
• Est. Priority Date: 03/03/2014
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Vojnovic, Milan, Gkantsidis, Christos, Zong, Bo
• Granted Patent: US 9,819,558 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/957 Browsing optimisation, e.g. caching or content distillation
• CPC Class Codes: H04L 43/062 related to network traffic
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/101 based on network conditions
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs
• CPC Class Codes: H04L 67/1031 Controlling of the operation of servers by a load balancer, e.g. adding or removing servers that serve requests

Abstract

Streaming query resource control is described, for example, to allocate streaming queries to servers in a data center providing a streaming query platform. In various embodiments streaming queries are allocated to servers in a manner seeking to balance load between the servers and also to reduce network traffic costs between data stream sources and the servers. In various examples, query types are taken into account, where a query type is the identity of one or more data stream sources used by the query, and optionally also traffic rates of the data stream sources. In some examples, processes for allocating incoming queries in an online fashion are described and in some examples, processes for allocating queries in an offline fashion are described. In examples, a network traffic cost metric is used which takes into account an incremental network traffic cost of adding a given query at a server.

Claims

1. A computer-implemented method comprising:

receiving, at a processor, a query comprising instructions to be executed, the instructions comprising instructions to read from at least one data stream;

sending control instructions in a data center to install the received query at a selected one of a plurality of computing entities at the data center; and

calculating the selected one of the plurality of computing entities on the basis of both a measure of load balancing between the plurality of computing entities and a measure of communications traffic cost between the at least one data stream and the selected computing entity.

2. The method of claim 1 carried out as part of an online greedy process whereby the query is an individual query of a plurality of queries and the steps of calculating and sending are repeated in order to install the plurality of queries at computing entities of the data center.

3. The method of claim 2 where the measure of load balancing comprises an absolute load balancing metric during installation of a first subset of the plurality of queries.

4. The method of claim 2 where the measure of load balancing comprises a relative load balancing metric during installation of a second subset of the plurality of queries.

5. The method of claim 2 where the measure of load balancing is switched between an absolute and a relative load balancing metric according to data about the state of the data center.

6. The method of claim 1 where the measure of communications traffic cost measures the change in traffic cost at one of the computing entities as a result of a proposed addition of the received query to that computing entity.

7. The method of claim 1 where the measure of communications traffic cost measures a new total traffic cost at one of the computing entities in the case that the received query is installed at the computing entity.

8. The method of claim 1 where the measure of communications traffic cost measures the similarity of query types at one of the computing entities in the case that the received query is installed at the computing entity.

9. The method of claim 1 where the received query is one of a pool comprising a plurality of queries, and the method comprises taking into account data about the queries in the pool when calculating the selected one of the plurality of computing entities.

10. The method of claim 9 comprising selecting a query type on the basis of traffic rates of the queries in the pool and sending control instructions to install queries of the selected query type from the pool at the selected one of the plurality of computing entities.

11. The method of claim 9 comprising selecting a query type and sending control instructions to install a specified number of queries of the selected query type from the pool at the selected one of the plurality of computing entities.

12. The method of claim 9 comprising grouping the plurality of queries by query type, a query type being an identity of one or more data streams used by a query, selecting the selected one of the plurality of computing entities in conjunction with selecting one of the query types;

and sending control instructions to install queries of the selected query type at the selected computing entity.

13. The method of claim 9 wherein the plurality of queries in the pool are queries predicted to be received over a specified time interval.

14. The method of claim 13 comprising sending control instructions in the data center to reserve resources for queries at one or more of the computing entities.

15. The method of claim 2 comprising switching the method to an offline method and rebalancing queries installed at the computing entities.

16. A computer-implemented method comprising:

receiving, at a processor, a query comprising instructions to be executed, the instructions comprising instructions to read from at least one data stream;

sending control instructions in a data center to install the received query at a selected one of a plurality of computing entities at the data center; and

calculating the selected one of the plurality of computing entities on the basis of both a measure of load balancing between the plurality of computing entities and a measure of communications traffic cost between the at least one data stream and the selected computing entity;

where the measure of communications traffic cost measures the change in traffic cost at one of the computing entities as a result of a proposed addition of the received query to that computing entity.

17. A data center management component comprising:

a processor arranged to receive a query comprising instructions to be executed, the instructions comprising instructions to read from at least one data stream;

an interface arranged to send control instructions in a data center to install the received query at a selected one of a plurality of computing entities at the data center; and

a query allocator arranged to calculate the selected one of the plurality of computing entities on the basis of both a measure of load balancing between the plurality of computing entities and a measure of communications traffic cost between the at least one data stream and the selected computing entity.

18. A data center management component as claimed in claim 17 the interface arranged to receive data about the state of the data center.

19. A data center management component as claimed in claim 17 where the measure of communications traffic cost measures the change in traffic cost at one of the computing entities as a result of a proposed addition of the received query to that computing entity.

20. A data center management component as claimed in claim 17 the query allocator being at least partially implemented using hardware logic selected from any one or more of:

a field-programmable gate array, a program-specific integrated circuit, a program-specific standard product, a system-on-a-chip, a complex programmable logic device, a graphics processing unit.