Dynamic reduction of stream backpressure

Patent metadata

Field	Value
Publication number	US-9389911-B2
Application number	US-201213682008-A
Country	US
Kind code	B2
Filing date	Nov 20, 2012
Priority date	Jul 26, 2011
Publication date	Jul 12, 2016
Grant date	Jul 12, 2016

Abstract

Techniques are described for eliminating backpressure in a distributed system by changing the rate data flows through a processing element. Backpressure occurs when data throughput in a processing element begins to decrease, for example, if new processing elements are added to the operating chart or if the distributed system is required to process more data. Indicators of backpressure (current or future) may be monitored. Once current backpressure or potential backpressure is identified, the operator graph or data rates may be altered to alleviate the backpressure. For example, a processing element may reduce the data rates it sends to processing elements that are downstream in the operator graph, or processing elements and/or data paths may be eliminated. In one embodiment, processing elements and associate data paths may be prioritized so that more important execution paths are maintained.

First claim

What is claimed is:

1. A method of processing data in a stream application, comprising:
receiving streaming data to be processed by a plurality of processing elements, the processing elements processing at least a portion of the received data by operation of one or more computer processors, wherein each of the processing elements comprises an executable portion of code;
establishing an operator graph of the plurality of processing elements, the operator graph defining at least one execution path through which the streaming data flows through the plurality of processing elements, and wherein each processing element in the execution path is configured to at least one of receive data from at least one upstream processing element and transmit data to at least one downstream processing element;
receiving a request to add at least one processing element to the execution path of the operator graph;
before adding the at least one processing element, identifying a predicted relative change of data throughput in a first processing element in the execution path, wherein the predicted relative change of data is based on (i) predicting utilization rates of computer processors in two or more downstream processing elements resulting from adding the at least one processing element to the operator graph, (ii) determining whether at least one downstream processing element is at or near a maximum utilization rate and (iii) determining whether, based on historical information containing conditions in the operator graph that caused backpressure previously, adding the at least one processing element will cause backpressure in the future; and
upon determining that the relative change of data throughput satisfies a predetermined threshold, determining not to add the at least one processing element to the operator graph.

2. The method of claim 1 , wherein the request to add at least one processing element to the operator graph is predicted to increase the amount of data flowing to the first processing element.

3. A system for processing data, comprising:
a computer processor; and
a memory containing a program that, when executed on the computer processor, performs an operation for processing data, comprising:
receiving streaming data to be processed by a plurality of processing elements, wherein each of the processing elements comprises an executable portion of code;
establishing an operator graph of the plurality of processing elements, the operator graph defining at least one execution path through which the streaming data flows through the plurality of processing elements, and wherein each processing element in the execution path is configured to at least one of receive data from at least one upstream processing element and transmit data to at least one downstream processing element;
receiving a request to add at least one processing element to the execution path of the operator graph;
before adding the at least one processing element, identifying a predicted relative change of data throughput in a first processing element in the execution path, wherein the predicted relative change of data is based on (i) predicting utilization rates of computer processors in two or more downstream processing elements resulting from adding the at least one processing element, (ii) determining whether at least one downstream processing element is at or near a maximum utilization rate and (iii) determining whether, based on historical information containing conditions in the operator graph that caused backpressure previously, adding the at least one processing element will cause backpressure in the future; and
upon determining that the relative change of data throughput satisfies a predetermined threshold, determining not to add the at least one processing element to the operator graph.

4. The system of claim 3 , wherein the request to add at least one processing element to the operator graph is predicted to increase the amount of data flowing to the first processing element.

5. A computer program product for processing data, the computer program product comprising:
a non-transitory computer-readable storage medium having computer-readable program code embodied therewith, the computer-readable program code comprising
computer-readable program code configured to:
receive streaming data to be processed by a plurality of processing elements, the processing elements processing at least a portion of the received data by operation of one or more computer processors, wherein each of the processing elements comprises an executable portion of code;
establish an operator graph of the plurality of processing elements, the operator graph defining at least one execution path through which the streaming data flows through the plurality of processing elements, and wherein each processing element in the execution path is configured to at least one of receive data from at least one upstream processing element and transmit data to at least one downstream processing element;
receive a request to add at least one processing element to the execution path of the operator graph;
before adding the at least one processing element, identify a predicted relative change of data throughput in a first processing element in the execution path, wherein the predicted relative change of data is based on (i) predicting utilization rates of computer processors in two or more downstream processing elements resulting from adding the at least one processing element, (ii) determining whether at least one downstream processing element is at or near a maximum utilization rate and (iii) determining whether, based on historical information containing conditions in the operator graph that caused backpressure previously, adding the at least one processing element will cause backpressure in the future; and
upon determining that the relative change of data throughput satisfies a predetermined threshold, determining not to add the at least one processing element to the operator graph.

6. The computer program product of claim 5 , wherein the request to add at least one processing element to the operator graph is predicted to increase the amount of data flowing to the first processing element.

Assignees

• IBM

Inventors

• Branson Michael J
• Cradick Ryan K
• Santosuosso John M

Classifications

• G06F9/5083 Primary

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

• G06F16/9024

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

• G06F16/24568

  Data stream processing; Continuous queries · CPC title

• G06F9/4843

  by program, e.g. task dispatcher, supervisor, operating system · CPC title

• G06F9/4887 Primary

  involving deadlines, e.g. rate based, periodic · CPC title