TL;DR
Testing complex cloud systems against multiple simultaneous failures is a massive combinatorial challenge. PREFAIL tackles this by introducing a programmable failure injection framework that allows testers to define sophisticated policies to intelligently prune the vast space of potential failure scenarios, significantly speeding up bug detection.
What Problem Does This Paper Address?
Modern cloud software, built on thousands of commodity machines, must be resilient to a wide array of hardware failures (crashes, disk errors, network issues). Testing this resilience against multiple failures is incredibly difficult due to the "combinatorial explosion" – the sheer number of possible failure combinations and sequences becomes computationally intractable for exhaustive testing. Existing tools often focus on single failures, leaving a gap in systematically exploring the complex, multi-failure scenarios that real-world systems face. This makes it hard to uncover critical bugs in failure recovery mechanisms, leading to issues like data loss and system unavailability.
Methods
PREFAIL introduces a novel approach by separating the mechanism of failure injection from the policy that guides it.
- Failure Injection Engine: This component is responsible for actually injecting failures into the system under test at specific execution points. It provides abstractions for failure types and execution contexts.
- Failure Injection Driver: This is where the intelligence lies. Testers write "policies" in this driver, which are essentially programs that define how to prune the failure space. PREFAIL supports two main types of policies:
- Filter Policies: These use predicates to decide whether to include or exclude specific failure sequences based on defined criteria (e.g., only inject crashes before write operations).
- Cluster Policies: These group similar failure sequences together, allowing testers to explore only one representative from each group (e.g., clustering sequences that lead to the same recovery path).
- Abstractions: PREFAIL defines key abstractions like "Failure-Injection Points" (fips) representing contexts where failures can occur, and "Failure-Injection Tasks" (fits) which are a combination of a failure type and a fip. It also captures "per-experiment profiles" of observed fips.
- Programmability: Policies are written in Python, offering flexibility to express complex testing objectives.
Datasets
Not discussed in the paper. The paper focuses on evaluating PREFAIL on existing cloud software systems.
Key Insights and Ideas
- Programmability is Key: The core insight is that a flexible, programmable approach to failure injection is essential. Testers need to express diverse heuristics and strategies to manage the combinatorial explosion, rather than relying on rigid, hard-coded policies.
- Separation of Concerns: Decoupling the failure injection engine from the policy driver is crucial for achieving this programmability and reusability.
- Policy Composition: PREFAIL allows for the composition of multiple policies, enabling testers to build sophisticated testing strategies that combine different pruning objectives (e.g., filtering by failure type and then clustering by recovery path).
- Recovery Path Characterization: The ability to characterize and cluster failure sequences based on the recovery paths they trigger is a powerful technique for ensuring comprehensive testing of fault tolerance mechanisms.
- Optimization Opportunities: The paper highlights that domain-specific knowledge can lead to significant optimizations in failure injection, reducing the number of experiments needed without sacrificing bug-finding potential.
Key Results
- Bug Finding: PREFAIL helped find all previously known bugs in HDFS and discovered 6 new, critical bugs (availability and reliability issues).
- Speedup: PREFAIL achieved significant speedups in testing time, finding all bugs that exhaustive testing could find, but in 10X-200X less time.
- Policy Effectiveness: Coverage-based policies (code and recovery) provided orders of magnitude improvement over brute-force testing. Optimization-based policies reduced experiments by an average of 5X.
- Integration: PREFAIL was successfully integrated with HDFS, ZooKeeper, and Cassandra, demonstrating its applicability to real-world cloud systems.
Limitations and Future Work
- Non-determinism: PREFAIL currently does not control all sources of non-determinism in system execution (e.g., network message ordering). This means that two executions of the same system might behave differently, potentially affecting failure injection.
- Future Work: The authors plan to address non-determinism by exposing message ordering to testers and supporting policies for it. They also aim to add features for automatically triaging failed experiments and parallelizing the PREFAIL architecture for even greater speedups. They envision PREFAIL empowering more program analyses by allowing them to run under failure conditions.
Summary updated