Method and apparatus for generating an optimized streaming graph using an adjacency operator combination on at least one streaming subgraph

Patent metadata

Field	Value
Publication number	US-10613909-B2
Application number	US-201715640685-A
Country	US
Kind code	B2
Filing date	Jul 3, 2017
Priority date	Jan 4, 2015
Publication date	Apr 7, 2020
Grant date	Apr 7, 2020

Abstract

A streaming graph optimization method and apparatus are disclosed, relating to the stream processing field. A stream application streaming graph provided by a user is received and the streaming graph is parsed and a streaming graph described by an operator node and a data stream side is constructed. Additionally the streaming graph is disassembled according to a maximum atom division principle, so as to obtain at least one streaming subgraph and adjacency operator combination is performed on the at least one streaming subgraph according to a combination algorithm, so as to obtain an optimized streaming graph.

First claim

What is claimed is:

1. A method comprising:
receiving, by a master node of a stream computing system, a user streaming graph, wherein the streaming computing system comprises multiple worker nodes;
parsing, by the master node, the user streaming graph and constructing a streaming graph described by an operator node and a data stream side;
disassembling, by the master node the streaming graph according to a maximum atom division principle of streaming graph types, to obtain at least one streaming subgraph, wherein the at least one streaming subgraph comprises many operators, and wherein the at least one streaming subgraph belongs to only one of the streaming graph types; and
performing, by the master node, adjacency operator combination on the at least one streaming subgraph according to processing logic complexity of the at least one streaming subgraph, to obtain an optimized streaming graph, so processing logic complexity of the at least one streaming subgraph is balanced after the adjacency operator combination;
wherein the streaming graph types comprise a pulse streaming graph, a split streaming graph, and an iterative streaming graph;
wherein the pulse streaming graph comprises sequential flowing-through of a data stream in an arrangement order operators of the streaming graph, wherein the pulse streaming graph comprises a pulse operator, wherein the pulse operator comprises window cache, and wherein data output has a batch processing characteristic;
wherein the split streaming graph comprises splitting of a data stream at an inlet operator, and aggregation at an outlet operator, wherein the split streaming graph comprises a split operator, and wherein the split operator is an inlet operator or an outlet operator of the split streaming graph; and
wherein the iterative streaming graph comprises returning of an output data stream at a successor operator to a predecessor operator as an input stream for iterative processing, wherein the iterative streaming graph comprises an iterative operator, and wherein the iterative operator is an inlet operator or an outlet operator of the iterative streaming graph.

2. The method according to claim 1 , wherein disassembling the streaming graph according to the maximum atom division principle of streaming graph types comprises:
traversing the operators in the streaming graph to find operators of multiple types, wherein the operators of multiple types comprise the iterative operator, the split operator, and the pulse operator;
selecting, in descending order of priorities, from the operators of multiple types, an operator for a boundary operator, wherein the descending order of the priorities is successively an iterative operator, a split operator, and a pulse operator; and
dividing, using the maximum atom division principle of streaming graph types and according to the selected boundary operator, the operators in the streaming graph, to obtain at least one streaming subgraph, wherein the maximum atom division principle comprises a streaming subgraph obtained through splitting comprises many operators, and wherein the at least one streaming subgraph belongs to one of an iterative streaming graph, a split streaming graph, or a pulse streaming graph.

3. The method according to claim 1 , wherein performing adjacency operator combination on the at least one streaming subgraph further comprises:
determining a combination range according to a cluster system resource and operator logic complexity; and
performing, in the determined combination range, adjacency operator combination on the at least one streaming subgraph according to a combination algorithm, to obtain the optimized streaming graph, so the processing logic complexity of the at least one streaming subgraph is balanced after the adjacency operator combination.

4. The method according to claim 3 , wherein performing the adjacency operator combination on the at least one streaming subgraph according to a combination algorithm comprises:
performing adjacency operator combination on the at least one streaming subgraph according to a combination priority list, to obtain the optimized streaming graph, wherein a to-be-combined adjacency operator is a system operator.

5. The method according to claim 3 , wherein performing the adjacency operator combination on the at least one streaming subgraph according to a combination algorithm comprises:
performing adjacency operator combination on the at least one streaming subgraph, to obtain the optimized streaming graph, so operator relative complexity after combination is less than or equal to N times operator relative complexity before combination, wherein N is greater than or equal to 1, wherein a to-be-combined adjacency operator is a user-defined operator.

6. The method according to claim 1 , wherein the method further comprises:
deploying the optimized streaming graph to a worker node of the multiple worker nodes for execution.

7. A master node of a streaming computing system, wherein the streaming computing system comprises multiple worker nodes, and wherein the master node comprises:
a processor; and
a non-transitory computer readable storage medium storing a program for execution by the processor, the program including instructions to:
receive a streaming graph;
parse the streaming graph, and construct a streaming graph operator and a data stream side description structure;
disassemble the streaming graph according to a maximum atom division principle of streaming graph types to obtain at least one streaming subgraph; and
perform adjacency operator combination on the at least one streaming subgraph according to processing logic complexity of the at least one streaming subgraph, to obtain an optimized streaming graph, so the processing logic complexity of the at least one streaming subgraph is balanced after the adjacency operator combination;

wherein the streaming graph types comprise a pulse streaming graph, a split streaming graph, and an iterative streaming graph;
wherein the pulse streaming graph comprises sequential flowing-through of a data stream in an arrangement order of operators of the streaming graph, wherein the pulse streaming graph comprises a pulse operator, wherein the pulse operator comprises window cache, and wherein data output has a batch processing characteristic;
wherein the split streaming graph comprises splitting of a data stream at an inlet operator, and aggregation at an outlet operator, wherein the split streaming graph comprises a split operator, and wherein the split operator is an inlet operator or an outlet operator of the split streaming graph; and
wherein the iterative streaming graph comprises returning of an output data stream at a successor operator to a predecessor operator as an input stream for iterative processing, wherein the iterative streaming graph comprises an iterative operator, and wherein the iterative operator is an inlet operator or an outlet operator of the iterative streaming graph.

8. The master node according to claim 7 , wherein the instructions to disassemble the streaming graph comprise instructions to:
traverse the operators of the streaming graph to find operators of multiple types, wherein the operators of multiple types comprise the iterative operator, the split operator, and the pulse operator;
select, in descending order of priorities, from the operators of multiple types, an operator for a boundary operator, wherein the descending order of the priorities is successively an iterative operator, a split operator, and a pulse operator; and
divide, using the maximum atom division principle of streaming graph types and according to the selected boundary operator, the operators in the streaming graph, to obtain at least one streaming sub

Assignees

• Huawei Tech Co Ltd

Inventors

• Zhang Songshan
• Xia Mingzhen

Classifications

• G06F16/24568

  Data stream processing; Continuous queries · CPC title

• G06F9/5083 Primary

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

• G06F16/9024 Primary

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

• G06F9/3005

  to perform operations for flow control · CPC title