Service Scheduling Method, Apparatus, and System

Patent metadata

Field	Value
Publication number	US-2016110228-A1
Application number	US-201514982375-A
Country	US
Kind code	A1
Filing date	Dec 29, 2015
Priority date	Jun 17, 2014
Publication date	Apr 21, 2016
Grant date	—

Abstract

A service scheduling method, applied to a stream computing system, is presented. The stream computing system includes a master control node and multiple working nodes, and the master control node is configured to schedule sub-services included in the service to the multiple working nodes for processing. The method includes acquiring a stream computing application graph of the service; dividing the stream computing application graph according to operator degrees and operator potentials of operators in the stream computing application graph and according to a division quantity for dividing the stream computing application graph, to obtain divided sub-graphs with the division quantity; and scheduling a sub-service corresponding to an operator included in each divided sub-graph to a working node corresponding to the divided sub-graph for processing. The method provided in embodiments of the present disclosure can enable services to use physical resources and network resources in a balanced manner.

First claim

What is claimed is:

1 . A service scheduling method, applied to a stream computing system, wherein the stream computing system is configured to schedule and process a service, wherein the stream computing system comprises a master control node and multiple working nodes, and wherein the master control node is configured to schedule sub-services comprised in the service to the multiple working nodes for processing; the method comprising:
acquiring a stream computing application graph of the service, wherein the stream computing application graph is a logical relationship graph that is created in advance for the service and that comprises operators and moving directions of data streams between the operators, and wherein the operator in the stream computing application graph carries computational logic used for processing a sub-service that is in the service and corresponds to the operator; dividing the stream computing application graph according to operator degrees and operator potentials of the operators in the stream computing application graph and according to a division quantity for dividing the stream computing application graph, to obtain divided sub-graphs with the division quantity, wherein the operator degree is a cumulative sum of traffic weights of input-and-output traffic of the operator, and wherein the operator potential is a load degree of the operator in the stream computing application graph; and scheduling a sub-service corresponding to an operator comprised in each divided sub-graph to a working node corresponding to the divided sub-graph for processing.

2 . The method according to claim 1 , wherein before the dividing the stream computing application graph according to operator degrees and operator potentials of operators in the stream computing application graph and according to a division quantity for dividing the stream computing application graph, the method further comprising:
determining a quantity of working nodes that are needed for processing the service corresponding to the stream computing application graph; and determining the division quantity according to the quantity of working nodes that are needed for processing the service.

3 . The method according to claim 1 , wherein dividing the stream computing application graph according to operator degrees and operator potentials of operators in the stream computing application graph and according to the division quantity for dividing the stream computing application graph comprises:
performing first-time division on the stream computing application graph according to the operator degrees of the operators and the division quantity, to obtain first-time divided graphs; and performing second-time division on the first-time divided graphs according to the operator potentials, to obtain the divided sub-graphs.

4 . The method according to claim 3 , wherein performing the first-time division on the stream computing application graph according to the operator degrees of the operators and the division quantity, to obtain first-time divided graphs comprises:
determining center operators with a same quantity as the division quantity according to the operator degrees of the operators and the division quantity, wherein an operator degree of the center operator is at least greater than an operator degree of an operator connected to the center operator; traversing other operators except the center operators layer by layer using each center operator as a traversal starting point, until another center operator except the center operator or a swing operator is traversed, wherein the swing operator is an operator that is traversed simultaneously during traversal using two adjacent center operators as starting points; and allocating, to the first-time divided graphs, operators that are traversed starting from the center operator and before the another center operator or the swing operator is traversed.

5 . The method according to claim 4 , wherein determining the center operators with the same quantity as the division quantity according to the operator degrees of the operators and the division quantity comprises:
determining core operators and ordinary operators in the stream computing application graph according to the operator degrees of the operators, wherein an operator degree of the core operator is higher than an operator degree of an operator connected to the core operator, and wherein the ordinary operators are operators in the stream computing application graph except the core operators; and determining the center operators with the same quantity as the division quantity from either the core operators and according to the division quantity, or a combination of the core operators and the ordinary operators and according to the division quantity.

6 . The method according to claim 5 , wherein determining, from the core operators, the center operators with the same quantity as the division quantity comprises selecting core operators, with the division quantity, having largest operator degrees as the center operators when a quantity of the core operators is not less than the quantity of the center operators.

7 . The method according to claim 5 , wherein determining, from the combination of the core operators and the ordinary operators, the center operators with the same quantity as the division quantity comprises selecting ordinary operators having largest operator degrees as remaining center operators that cannot be provided by the core operators adequately when a quantity of the core operators is less than the quantity of the center operators.

8 . The method according to claim 4 , wherein performing the second-time division on the first-time divided graphs according to the operator potentials, to obtain the divided sub-graphs comprises:
determining a graph partition potential of each first-time divided graph, wherein the graph partition potential is a cumulative sum of operator potentials of operators in the first-time divided graph; and determining, according to an operator potential of a swing operator between adjacent first-time divided graphs and graph partition potentials of the adjacent first-time divided graphs, a first-time divided graph to which the swing operator should be allocated, to obtain the divided sub-graphs.

9 . The method according to claim 1 , further comprising:
calculating graph partition load, wherein the graph partition load is a sum of load of operators in the divided sub-graph; calculating a load error value according to the graph partition load; and adjusting, when the load error value is greater than a preset first check threshold, a swing operator from the divided sub-graph to a divided sub-graph having a smallest load error value, to obtain adjusted divided sub-graphs, wherein scheduling the sub-service corresponding to an operator comprised in each divided sub-graph to the working node corresponding to the divided sub-graph for processing comprises scheduling a sub-service corresponding to an operator comprised in each adjusted divided sub-graph to a working node corresponding to the adjusted divided sub-graph for processing.

10 . The method according to claim 1 , further comprising:
calculating graph partition network input traffic, output traffic, indegree, and outdegree, wherein the graph partition network input traffic is input traffic of operators that are in the divided sub-graph and that receive data streams across a physical node, wherein the graph partition network output traffic is output traffic of operators that are in the divided sub-graph and that send data streams across a physical node, wherein the graph partition network indegree is a quantity of data streams received by oper

Assignees

• Huawei Tech Co Ltd

Inventors

• Zhang Songshan

Classifications

• H04L67/1008

  based on parameters of servers, e.g. available memory or workload (monitoring of computer activity G06F11/30) · CPC title

• H04L67/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) · CPC title

• G06F16/9024 Primary

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F9/5083 Primary

  Techniques for rebalancing the load in a distributed system · CPC title

• G06F17/30958

  Physics · mapped topic