Injecting a fault into a stream operator in a data stream processing application

• US 8,458,650 B2
• Filed: 03/29/2010
• Issued: 06/04/2013
• Est. Priority Date: 03/29/2010
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Andrade, Henrique, Gedik, Bugra, Jacques da Silva, Gabriela, Wu, Kun-Lung
• Primary Examiner(s): Tecklu, Isaac
• Assistant Examiner(s): MORSHED, HOSSAIN M
• Application Number:
  US12/748,633
• Publication Number:
  US 20110239048A1
• Time in Patent Office: 1,163 Days
• Field of Search: None
• US Class Current: 717/106
• CPC Class Codes: G06F 11/28 by checking the correct order of processing G06F11/08 - G06F11/26 take precedence; monitoring patterns of pulse trains H03K5/19
• CPC Class Codes: G06F 11/3612 by runtime analysis performance monitoring G06F11/3466
• CPC Class Codes: G06F 11/3616 using software metrics
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity

Abstract

In one embodiment, the invention comprises partial fault tolerant stream processing applications. One embodiment of a method for implementing partial fault tolerance in a stream processing application comprising a plurality of stream operators includes: defining a quality score function that expresses how well the application is performing quantitatively, injecting a fault into at least one of the plurality of operators, assessing an impact of the fault on the quality score function, and selecting at least one partial fault-tolerant technique for implementation in the application based on the quantitative metric-driven assessment.

Claims

1. A method for injecting a fault into a stream operator in a data stream processing application, the method comprising:

developing a fault injection operator having specialized logic to emulate an effect of a failure, the fault injection operator corresponding to a fault model, wherein the fault injection operator is a bursty tuple loss fault injection operator;

embedding the fault injection operator into a data flow graph for the data stream processing application, so as to emulate at least one possible effect of the fault model on the data stream processing application, wherein the embedding comprises;

embedding the fault injection operator immediately after each source operator in the data flow graph;

embedding the fault injection operator immediately before each operator in the data flow graph that contains an upstream operator that produces more than one output stream;

embedding the fault injection operator immediately before each operator in the data flow graph that consumes more than one input stream; and

embedding the fault injection operator immediately before each operator in the data flow graph that has a stateful upstream operator;

wherein the fault injection operator is embedded only in one or more positions of the data flow graph at which the fault model manifests, and

wherein the fault injection operator emulates a different failure when embedded at each of the one or more positions in the data flow graph.

2. The method of claim 1, wherein the bursty tuple loss fault injection operator emulates a crash-and-restore of an operator in which the bursty tuple loss fault injection operator is embedded.

3. The method of claim 2, wherein the bursty tuple loss fault injection operator emulates the crash-and-restore from a checkpoint.

4. The method of claim 1, further comprising:

compiling the data stream processing application, including the fault injection operator, into executable application code; and

evaluating a result of the fault injection operator on the executable application code.

5. The method of claim 4, wherein the evaluating comprises:

indicating an adequacy of a fault tolerance policy for the data stream processing application, wherein the adequacy is quantified in a quality score function that expresses how well the application is performing quantitatively.

6. The method of claim 5, wherein the evaluating comprises:

calculating the quality score function using an output of the data stream processing application in a fault-free condition to generate a target quality score function;

calculating the quality score function using an output of executable application code including the data stream processing application and the fault injection operator to generate a faulty quality score function; and

determining whether a difference between the faulty quality score function and the target quality score function is within a tolerance threshold.

7. The method of claim 6, wherein the faulty quality score function is calculated over local sections of the output of the executable application code including the data stream processing application and the fault injection operator.

8. The method of claim 5, wherein the quality score function accounts for at least one a metric specific to the at least one operator of the data stream processing application, and wherein the at least one metric characterizes the data stream processing application in terms of effect on predictability and availability under a failure.

9. The method of claim 8, wherein the at least one a metric comprises an outage duration metric that correlates a duration of an outage of the at least one operator with a degradation in quality of an output of the data stream processing application.

10. The method of claim 8, wherein the at least one metric comprises a data dependency level metric that defines how a fault emulated by the fault injection operator affects a quality of an output of the data stream processing application when injected at different stream offsets.

11. The method of claim 8, wherein the at least one a metric comprises a quality impact metric that defines a deviation of a quality of an output of the data stream processing application over local sections of the output.

12. The method of claim 8, wherein the at least one a metric comprises a recovery time metric that estimates how long it takes the data stream processing application to recover after occurrence of a fault emulated by the fault injection operator.

13. The method of claim 1, wherein the fault model emulates an effect of a partial fault tolerance policy on the data stream processing application.

14. An article of manufacture, comprising:

a non-transitory computer readable storage medium containing an executable program for injecting a fault into a stream operator in a data stream processing application, where the program performs steps comprising;

developing a fault injection operator having specialized logic to emulate an effect of a failure, the fault injection operator corresponding to a fault model, wherein the fault injection operator is a bursty tuple loss fault injection operator;

embedding the fault injection operator into a data flow graph for the data stream processing application, so as to emulate at least one possible effect of the fault model on the data stream processing application, wherein the embedding comprises;

embedding the fault injection operator immediately after each source operator in the data flow graph;

embedding the fault injection operator immediately before each operator in the data flow graph that contains an upstream operator that produces more than one output stream;

embedding the fault injection operator immediately before each operator in the data flow graph that consumes more than one input stream; and

embedding the fault injection operator immediately before each operator in the data flow graph that has a stateful upstream operator;

wherein the fault injection operator is embedded only in one or more positions of the data flow graph at which the fault model manifests, and wherein the fault injection operator emulates a different failure when embedded at each of the one or more positions in the data flow graph.

15. The article of manufacture of claim 14, wherein the bursty tuple loss fault injection operator emulates a crash-and-restore of an operator in which the bursty tuple loss fault injection operator is embedded.

16. The article of manufacture of claim 15, wherein the bursty tuple loss fault injection operator emulates the crash-and-restore from a checkpoint.

17. The article of manufacture of claim 14, wherein the steps further comprise:

compiling the data stream processing application, including the fault injection operator, into executable application code; and

evaluating a result of the fault injection operator on the executable application code.

18. The article of manufacture of claim 17, wherein the evaluating comprises:

calculating a first instance of a quality score function using an output of the data stream processing application in a fault-free condition to generate a target quality score function;

calculating a second instance of a quality score function using an output of executable application code including the data stream processing application and the fault injection operator to generate a faulty quality score function; and

determining whether a difference between the faulty quality score function and the target quality score function is within a tolerance threshold.

19. The article of manufacture of claim 18, wherein the faulty quality score function is calculated over local sections of the output of the executable application code including the data stream processing application and the fault injection operator.

20. The article of manufacture of claim 18, wherein the quality score function accounts for at least one a metric specific to the at least one operator of the data stream processing application, and wherein the at least one metric characterizes the data stream processing application in terms of effect on predictability and availability under a failure.

21. The article of manufacture of claim 20, wherein the at least one a metric comprises an outage duration metric that correlates a duration of an outage of the at least one operator with a degradation in quality of an output of the data stream processing application.

22. The article of manufacture of claim 20, wherein the at least one metric comprises a data dependency level metric that defines how a fault emulated by the fault injection operator affects a quality of an output of the data stream processing application when injected at different stream offsets.

23. The article of manufacture of claim 20, wherein the at least one a metric comprises a quality impact metric that defines a deviation of a quality of an output of the data stream processing application over local sections of the output.

24. The article of manufacture of claim 20, wherein the at least one a metric comprises a recovery time metric that estimates how long it takes the data stream processing application to recover after occurrence of a fault emulated by the fault injection operator.

25. A system, comprising:

a pre-processor for injecting a fault into a stream operator in a data stream processing application, where the pre-processor performs steps comprising;

at least one processor and memory;

developing a fault injection operator having specialized logic to emulate an effect of a failure, the fault injection operator corresponding to a fault model, wherein the fault injection operator is a bursty tuple loss fault injection operator;

embedding the fault injection operator into a data flow graph for the data stream processing application, so as to emulate at least one possible effect of the fault model on the data stream processing application, wherein the embedding comprises;

embedding the fault injection operator immediately after each source operator in the data flow graph;

embedding the fault injection operator immediately before each operator in the data flow graph that contains an upstream operator that produces more than one output stream;

embedding the fault injection operator immediately before each operator in the data flow graph that consumes more than one input stream;

and embedding the fault injection operator immediately before each operator in the data flow graph that has a stateful upstream operator; and

a compiler for compiling the data stream processing application, including the fault injection operator, into executable application code, wherein the fault injection operator is embedded only in one or more positions of the data flow graph at which the fault model manifests, and wherein the fault injection operator emulates a different failure when embedded at each of the one or more positions in the data flow graph.