Dynamic reduction of stream backpressure

• US 8,990,452 B2
• Filed: 07/26/2011
• Issued: 03/24/2015
• 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): ALFRED, MELISSA A
• Application Number:
  US13/190,694
• Publication Number:
  US 20130031556A1
• Time in Patent Office: 1,337 Days
• Field of Search: None
• US Class Current: 710/29
• 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. In another embodiment, if a request to add one or more processing elements may cause future backpressure, the request may be refused.

Claims

1. 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, wherein each of the processing elements is 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, 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;

monitor an indicator of backpressure associated with a first processing element in the execution path, wherein the indicator of backpressure represents the data throughput of the first processing element;

prioritize at least two of the plurality of processing elements that are one of upstream and downstream of the first processing element in the execution path, wherein priority is based on at least one of (i) an importance of a job associated with each of the at least two of the processing elements, (ii) an importance of data transmitted by each of the at least two of the processing elements, and (iii) a transient time required by each of the processing elements in the at least two of the processing elements to process the streaming data ; and

upon determining that the indicator of backpressure satisfies a predetermined threshold indicating that the first processing element is processing data at an output rate that is less than an input rate at which the first processing element receives data, perform a corrective action to change the rate of data flowing through the first processing element to enable the first processing element to process data such that the output rate is greater than or equal to the input rate, wherein the corrective action is performed on a lowest priority processing element of the prioritized processing elements.

2. The computer program product of claim 1, wherein the corrective action is at least one of (i) eliminating a data connection between the lowest priority processing element and the first processing element and (ii) reducing the amount of data received by the lowest priority processing element from the first processing element such that the lowest priority processing element receives a least amount of data among the prioritized processing elements.

3. The computer program product of claim 1, wherein the at least two of the processing elements are prioritized based on an amount of data transmitted by each of the at least two of the processing elements.

8. The computer program product of claim 1, wherein the indicator of backpressure is a performance metric of a hardware element used when executing the processing element.

9. The computer program product of claim 1, wherein the corrective action is eliminating a data connection between the first processing element and an upstream processing element in the execution path.

4. 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 is 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, 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;

monitoring an indicator of backpressure associated with a first processing element in the execution path, wherein the indicator of backpressure represents the data throughput of the first processing element;

prioritizing at least two of the plurality of processing elements that are one of upstream and downstream of the first processing element in the execution path, wherein priority is based on at least one of (i) an importance of a job associated with each of the at least two of the processing elements, (ii) an importance of data transmitted by each of the at least two of the processing elements, and (iii) a transient time required by each of the processing elements in the at least two of the processing elements to process the streaming data ; and

upon determining that the indicator of backpressure satisfies a predetermined threshold indicating that the first processing element is processing data at an output rate that is less than an input rate at which the first processing element receives data, performing a corrective action to change the rate of data flowing through the first processing element to enable the first processing element to process data such that the output rate is greater than or equal to the input rate, wherein the corrective action is performed on a lowest priority processing element of the prioritized processing elements.

5. The system of claim 4, wherein the corrective action is at least one of (i) eliminating the lowest priority processing element and (ii) reducing the amount of data received by the lowest priority processing element from the first processing element such that the lowest priority processing element receives a least amount of data among the prioritized processing elements.

6. The system of claim 4, wherein the at least two of the processing elements are prioritized based on an amount of data transmitted by each of the at least two of the processing elements.

7. The system of claim 4, wherein the first processing element transmits data to at least two downstream processing elements, the operation for processing data further comprising:

assigning a priority to each of the downstream processing elements; and

changing the amount of data transmitted by the first processing element to the downstream processing elements based on the assigned priority.

10. The system of claim 4, wherein the indicator of backpressure is a performance metric of a hardware element used when executing the processing element.

11. The system of claim 4, wherein the corrective action is eliminating a data connection between the first processing element and an upstream processing element in the execution path.

12. A method of processing data, 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 is 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, 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;

monitoring an indicator of backpressure associated with a first processing element in the execution path, wherein the indicator of backpressure represents the data throughput of the first processing element;

prioritizing at least two of the plurality of processing elements that are one of upstream and downstream of the first processing element in the execution path, wherein priority is based on at least one of (i) an importance of a job associated with each of the at least two of the processing elements, (ii) an importance of data transmitted by each of the at least two of the processing elements, and (iii) a transient time required by each of the processing elements in the at least two of the processing elements to process the streaming data ; and

upon determining that the indicator of backpressure satisfies a predetermined threshold indicating that the first processing element is processing data at an output rate that is less than an input rate at which the first processing element receives data, perform a corrective action to change the rate of data flowing through the first processing element to enable the first processing element to process data such that the output rate is greater than or equal to the input rate, wherein the corrective action is performed on a lowest priority processing element of the prioritized processing elements.

13. The method of claim 12, the corrective action is at least one of (i) eliminating a data connection between the lowest priority processing element and the first processing element and (ii) reducing the amount of data received by the lowest priority processing element from the first processing element such that the lowest priority processing element receives a least amount of data among the prioritized processing elements.

14. The method of claim 12, wherein the at least two of the processing elements are prioritized based on an amount of data transmitted by each of the at least two of the processing elements.

15. The method of claim 12, wherein the indicator of backpressure is at least one of usage of a computer processing unit (CPU) and usage of a buffer, wherein the CPU and buffer are associated with the first processing element.

16. The method of claim 12, wherein the indicator of backpressure is a predictive measurement of data throughput based on at least one of current usage of a computer processing unit (CPU) and historical data, wherein the CPU and historical data are associated with the first processing element.

17. The method of claim 12, wherein the corrective action comprises changing the amount of data transmitted by the first processing element.

18. The method of claim 12, wherein the first processing element transmits data to the at least two of the processing elements that are downstream in the execution path,

wherein the corrective action comprises:

changing the amount of data transmitted by the first processing element to the at least two of the processing elements based on the priority assigned to each of the at least two processing elements.