Dynamic reduction of stream backpressure

• US 10,324,756 B2
• Filed: 01/12/2017
• Issued: 06/18/2019
• Est. Priority Date: 07/26/2011
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Branson, Michael J., Cradick, Ryan K., Santosuosso, John M.
• Primary Examiner(s): Bullock, Jr., Lewis A
• Assistant Examiner(s): Headly, Melissa A
• Application Number:
  US15/404,366
• Publication Number:
  US 20170123851A1
• Time in Patent Office: 887 Days
• Field of Search: None
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system

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.

Claims

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 a first processing element to the execution path of the operator graph;

before adding the first processing element, identifying a predicted relative change of data throughput in a second processing element in the execution path, wherein the predicted relative change of data is based on predicting a utilization rate of one of the computer processors resulting from adding the first processing element to the operator graph;

upon determining that the relative change of data throughput satisfies a predetermined threshold, determining not to add the at first processing element to the operator graph; and

upon determining that a relative change of data throughput corresponding to a third processing element does not satisfy a predetermined threshold, adding the third processing element to the operator graph.

2. The method of claim 1, wherein the utilization rate is associated with the second processing element.

3. The method of claim 1, wherein the request to add the first processing element to the operator graph is predicted to increase the amount of data flowing to the second processing element.

4. The method of claim 1, wherein predicting the effect that adding the the first processing element will have on the utilization rate is performed by evaluating historical information containing the conditions of the operator graph that caused backpressure previously.

5. The method of claim 1, wherein the first processing element is upstream in the execution path relative to a location where the the first processing element is to be inserted into the execution path.

6. The method of claim 1, wherein the second processing element is downstream in the execution path relative to a location where the the first processing element is to be inserted into the execution path.

7. 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 a first processing element to the execution path of the operator graph;

before adding the first processing element, identifying a predicted relative change of data throughput in second processing element in the execution path, wherein the predicted relative change of data is based on predicting a utilization rate of the computer processor resulting from adding the first processing element;

upon determining that the relative change of data throughput satisfies a predetermined threshold, determining not to add the first processing element to the operator graph; and

upon determining that a relative change of data throughput corresponding to a third processing element does not satisfy a predetermined threshold, adding the third processing element to the operator graph.

8. The system of claim 7, wherein the utilization rate is associated with the second processing element.

9. The system of claim 7, wherein the request to add the first processing element to the operator graph is predicted to increase the amount of data flowing to the second processing element.

10. The system of claim 7, wherein predicting the effect that adding the first processing element will have on the utilization rate is performed by evaluating historical information containing the conditions of the operator graph that caused backpressure previously.

11. The system of claim 7, wherein the second processing element is upstream in the execution path relative to a location where the first processing element is to be inserted into the execution path.

12. The system of claim 7, wherein the second processing element is downstream in the execution path relative to a location where the first processing element is to be inserted into the execution path.

13. The system of claim 7, wherein each of the plurality of processing elements comprises at least one operator, wherein the operator comprises the executable portion of code.

14. 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, when executed on one or more computer processors, is 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 the 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 a first processing element to the execution path of the operator graph;

before adding the first processing element, identify a predicted relative change of data throughput in a second processing element in the execution path, wherein the predicted relative change of data is based on predicting a utilization rate of the computer processor resulting from adding the first processing element;

upon determining that the relative change of data throughput satisfies a predetermined threshold, determine not to add the first processing element to the operator graph; and

upon determining that a relative change of data throughput corresponding to a third processing element does not satisfy a predetermined threshold, add the third processing element to the operator graph.

16. The computer program product of claim 14, wherein the request to add the first processing element to the operator graph is predicted to increase the amount of data flowing to the second processing element.

17. The computer program product of claim 14, wherein predicting the effect that adding the first processing element will have on the utilization rate is performed by evaluating historical information containing the conditions of the operator graph that caused backpressure previously.

18. The computer program product of claim 14, wherein the second processing element is upstream in the execution path relative to a location where the at least one processing element is to be inserted into the execution path.

19. The computer program product of claim 14, wherein the second processing element is downstream in the execution path relative to a location where the first processing element is to be inserted into the execution path.

20. The computer program product of claim 14, wherein each of the plurality of processing elements comprises at least one operator, wherein the operator comprises the executable portion of code.

15. The computer program product of 14, wherein the utilization rate is associated with the second processing element.