DYNAMIC REDUCTION OF STREAM BACKPRESSURE

• US 20130081042A1
• Filed: 11/20/2012
• Published: 03/28/2013
• 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., Santosuosso, John M., Cradick, Ryan A.
• Granted Patent: US 9,389,911 B2
• Time in Patent Office: Days
• US Class Current: 718/103
• 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, 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;

establishing an operator graph of the plurality of processing elements, the operator graph defining at least one execution path, wherein each processing element of the operator graph is configured to receive data from at least one upstream processing element and transmit data to at least one downstream processing element;

identifying a relative change of data throughput in a first processing element of the plurality of processing elements, wherein the data throughput measures whether the first processing element is processing data as fast as the first processing element is receiving data from the at least one upstream processing element; and

upon identifying the relative change of data throughput, changing the rate of data flowing in at least one of the first processing element and a second processing element of the plurality of processing elements to increase the data throughput of the first processing element.

2. The method of claim 1, wherein changing the rate of data flowing in the second processing element further comprises at least one of (i) eliminating a connection of the second processing element to a different processing element, (ii) changing the amount of data transmitted by the second processing element (iii) discarding a portion of the data received by the second processing element, and (iv) changing the amount of data received by the second processing element.

3. The method of claim 1, further comprising, before changing the rate of data flowing in the second processing element, prioritizing at least two of the processing elements, wherein the second processing element is one of the at least two of the processing elements and is assigned a lowest priority.

4. The method of claim 3, wherein changing the rate of data flowing in the second processing element further comprises, based on the lowest priority, at least one of (i) eliminating the second processing element and (ii) reducing the amount of data received by the second processing element such that the second processing element receives a least amount of data among the prioritized processing elements.

5. The method of claim 3, wherein the at least two of the processing elements are prioritized 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, (iii) amount of data transmitted by each of the at least two of the processing elements, and (iv) a transient time required for data to flow through each of the processing elements in the at least two of the processing elements.

6. The method of claim 1, wherein the relative change is identified based on 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.

7. The method of claim 1, wherein the relative change is identified by 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.

8. The method of claim 1, wherein changing the rate of data flowing in the first processing element further comprises changing the amount of data transmitted by the first processing element.

9. The method of claim 1, wherein the first processing element transmits data to at least two processing elements, further comprising:

assigning a priority to each of the at least two processing elements; and

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

10. 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;

establishing an operator graph of the plurality of processing elements, the operator graph defining at least one execution path and wherein each processing element of the operator graph is configured to 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 operator graph;

identifying a relative change of data throughput in a first processing element of the plurality of processing elements, wherein the relative decrease is based on a predictive measurement of future data throughput in the first processing element; and

upon identifying the relative change of data throughput, refusing the request to add the at least one processing element to the operator graph.