Chaos Engineering Ch 12 · The Experiment Selection Problem

Chaos Engineering: System Resiliency in Practice · Ch 12 · The Experiment Selection Problem (and a Solution) · 2020

What is this chapter about?

When you stream a video, a hundred small programs pass the work along behind the scenes: one checks who you are, one picks recommendations, one finds the video file. Chaos engineering means breaking some of them on purpose to see whether the whole still holds up.

Here is the catch: which ones do you break? There are a hundred ways to break one, nearly five thousand ways to break two at once, and over a hundred thousand ways to break three. You can only try one at a time, and a bad pick is a wasted try. This chapter is about deciding what to try first.

A strange idea first

To find a bridge's weakest point, instinct says watch it fail. This chapter says the opposite: first look closely at how it stands up on an ordinary day.

Once you know which pillars actually carried the load this time, you know that kicking an idle pillar teaches you nothing. Kick the ones that are carrying weight and have no stand-in.

Why the old ways struggle

Kick at random. Like letting a monkey loose in the server room to pull plugs. Simple and unbiased, but there are so many combinations that the deadly "two things break together" case may never come up.
Ask the veteran. An experienced engineer can point and say "those two together are the scary ones". Often right, but there are only a few veterans, you cannot copy them, and their picture of the system may itself be wrong.

How it works: follow the credit list

Every time a request succeeds, have the system keep a "credit list": who helped this time, and who was standing by as whose backup.

Reading the list tells you the smallest groups you would have to break together to make that request fail, such as a main helper and its backup at the same time.
Try only those groups and skip the thousands of others.
After each try, either it really fails and you have found a weakness, or it still succeeds, which means there is a backup you did not know about. Add it to the list and work out the next round.

It is like a detective checking alibis: first understand how each suspect could have pulled it off, then take those stories apart one by one.

What it buys you

The number of tries drops from astronomical to a short list, every try has a reason, and the veteran's instinct becomes something a machine can compute.

One honest cost: the system has to record clearly who helped, and wherever that record is incomplete, this method misses things too.

Remember it in one line

Don't kick at random and don't rely only on veterans: see how the system succeeds, then try only the smallest groups that could make it fail. Every try either catches a bug or reveals a backup you never knew about.

Want the combinatorics, the lineage graph, the solver loop and how Netflix ran it? → Switch to the deep read

In one sentence

You'd think finding weaknesses means studying failures, but the answer to "which faults should I inject" is hidden in successful requests: record why a request succeeded as a lineage graph, compute the fewest supports you must knock out to make it fail, and test only those. An unbounded fault space shrinks to a short list.

Glossary

Fault injection: deliberately causing failures (killing processes, dropping messages, timing out dependencies) to watch how the system reacts.
Fault space: the set of every fault you could inject, and every combination of them.
Microservice: one of many small, independently deployed services that make up an application and call each other over the network.
Fallback: the backup path taken when a dependency fails, such as serving a cached or default value.
Redundancy: having more than one path to the same result, so losing one still leaves another.
Distributed tracing: tagging each request with an ID and recording every service call it makes, assembled into a call tree.
Observability: the ability to infer what is happening inside a system from what it emits (logs, metrics, traces).
SAT solver: a program that, given a logical formula of ANDs, ORs and NOTs, finds variable values that make it true; industrial solvers handle millions of variables.

Where it sits

Chapter 12 closes Part III, "Human Factors". It is written by Peter Alvaro, a professor at UC Santa Cruz who introduced LDFI. Chapter 11 has just argued that choosing experiments is a human judgment; this chapter asks whether that judgment can be reproduced and scaled by a machine. Chapter 16's continuous verification is where that path becomes engineering practice.

The problem this chapter tackles

Picture a system with 100 services. Single faults give you 100 candidates. Any two failing together gives C(100,2) = 4,950. Any three gives 161,700, before you even count fault types like latency, packet loss or partial failure. Each experiment costs production traffic and watching time; a few dozen a day is already a busy team.

Worse, in a mature system the fatal bugs tend to live in exactly those combinations. A single service going down has long been covered by a fallback (otherwise someone would have noticed), and only "the main path and its backup fail together" breaks through. So experiment selection is not a nice optimisation; it decides whether chaos engineering can still find anything new. Leave it unsolved and a team either burns resources on uninteresting faults or bets everything on a few experts' intuition.

The core ideas, explained

1. The two old approaches: random search and expert guidance

Random search is the Chaos Monkey approach: kill instances at random. It needs no prior knowledge, carries no bias, is trivial to build, and is very effective against shallow problems such as "this single point of failure had no fallback". But its hit rate falls exponentially with combination depth. If the fatal case is two particular services failing together, random pairwise injection needs on the order of thousands of tries to hit it once.

Expert guidance is the game-day model: senior engineers use their understanding of the system to say "this looks suspicious". It works well in practice, and many of the most valuable experiments come from experts. It has three problems. It scales only with expert time. It is hard to teach, because intuition rarely explains itself. And most fundamentally, chaos engineering exists to test people's mental models; using the same model to choose experiments carries its blind spots straight through.

Violet rings = fault combinations that actually cause failure; blue dots = experiments actually run.

2. Flip the question: from "how does it fail" to "how does it succeed"

Alvaro's key move is to study success first. A successful request rests on a set of supports: which services were called and answered correctly, which messages arrived. Recording those causal dependencies gives you the success's lineage, a concept borrowed from data provenance in databases.

Lineage matters because it exposes redundancy as well. An example: a homepage request succeeds if auth service A is up, and either recommendation service B or its fallback trending list C is up, and either primary database D or replica E is up. As a formula, A ∧ (B ∨ C) ∧ (D ∨ E). In plain words: A must be there, at least one of B and C, and at least one of D and E.

Experiments like "kill only B" or "kill only D" are guaranteed to show nothing; the lineage graph rules them out before you touch production.

Five components have 32 subsets, and most random picks are wasted; the minimal sets that can fail this request number just 3. The expert's hunch, "it's dangerous only when the main path and its backup go together", has become something you can compute.

3. LDFI: a conjecture-and-refutation loop

Lineage-Driven Fault Injection (LDFI) automates that reasoning. Think of it as a tireless expert who reasons only from evidence. The loop:

Observe success: run a normal request and extract its lineage from trace data.
Turn it into a formula: "for the outcome to fail, at least one thing on every supporting path must break". That is a satisfiability problem; a SAT solver returns every minimal fault set (a minimal hitting set: the smallest set that intersects every path).
Inject and watch: inject one set. If the request fails, you have found a real bug (or a known risk to confirm). If it still succeeds, the system has a backup path missing from the graph; add the new lineage and solve again.
Converge: stop when no set can break the outcome any more, or the budget runs out.

Neither outcome is wasted: a failure is a bug, and a surprising success is redundancy you did not know you had.

LDFI was first built in the research prototype Molly (SIGMOD 2015), which worked on protocol models written in a logic language. This chapter covers the version that left the lab for Netflix production. There was no ready-made "program lineage" there, so the call trees from distributed tracing stood in for lineage, Netflix's existing fault-injection platform did the injecting, and real-world noise had to be handled: requests of the same kind don't always take the same path, and services are constantly being redeployed.

4. Observability is both prerequisite and lever

The chapter's larger frame: observability infrastructure was built for debugging, but what it records about how requests succeed is exactly the knowledge you need to choose experiments. Experts are accurate because they carry a rough dependency-and-redundancy map in their heads. Tracing moves that map out of heads and into data, where a machine can read and reason about it. In essence this is engineering intuition: not replacing experts, but letting their way of reasoning run where no expert is available.

Key trade-offs and choices

The approaches are not substitutes; they trade prerequisites, cost and the depth of bug they can reach.

Approach	Prerequisites	Good at finding	Scales with	Cost / blind spot
Random search	Almost none; ability to kill instances	Shallow gaps: a single point with no fallback	Machines, but collapses with combination depth	Tiny hit rate on deep combos; lots of "nothing happened"
Expert guidance	Senior engineers who know the system	High-value, domain-specific combos	Capped at expert time	Inherits the experts' blind spots; hard to teach
Exhaustive	A small enough space	Everything	Triples of 100 services: 161,700	Infeasible in production; small models or test setups only
LDFI	Request tracing + a definition of success + programmable injection	Main path and backup failing together	Compute; narrows each round	Can't reason about dependencies tracing doesn't see; costly to build

Rule of thumb: without tracing, start with random plus experts; LDFI pays off once tracing covers the critical paths.

Teams just starting: random instance kills clear out the first wave of "no fallback" problems at the best cost.
Fallbacks everywhere, shallow bugs dried up: the problems now live in combinations, and lineage-driven selection becomes worth the investment.
Experts still matter: LDFI produces the candidate list; experts decide which to run first and when (the split from Chapter 11).

Why it matters / in real systems

This chapter moves chaos engineering from a tool to a search problem: injection is a commodity, selection is the scarce part. Asked in an interview "you have 200 microservices; where do your chaos experiments start?", a strong answer is: use the call graph to find single points with no redundancy (like A in the example), then find paired "main plus backup" dependencies, and rank by how many core requests losing them would hurt. That is LDFI done by hand.

Industry evidence

Netflix: the archetype of random search. Its open-source repository opens with "Chaos Monkey randomly terminates virtual machine instances and containers that run inside of your production environment", which is precisely the random strategy this chapter describes, good at flushing out problems under single-instance failure. Netflix · Chaos Monkey README (github.com/Netflix/chaosmonkey, verified during this run)
Netflix × UC Santa Cruz: LDFI in production. Alvaro, with Netflix's Kolton Andrus, Casey Rosenthal, Lorin Hochstein and others, published "Automating Failure Testing Research at Internet Scale" at SoCC 2016 on wiring LDFI into Netflix's fault-injection platform; its abstract argues that random strategies waste resources on "uninteresting" faults, while programmer-guided approaches scale only with human effort. Alvaro et al. · ACM SoCC 2016 (DOI 10.1145/2987550.2987555)
Molly: the prototype. The project README describes itself as "An implementation of LDFI", corresponding to the paper Lineage-driven Fault Injection (Alvaro, Rosen, Hellerstein, SIGMOD 2015). palvaro/molly (github.com/palvaro/molly, verified during this run)

Pitfalls and debates

"Random is the most objective." Unbiased is not efficient: in a combinatorial space, uniform sampling is close to not sampling at all. Random earns its keep in the shallows, not the depths.
"A lineage graph is just a dependency graph." No. A dependency graph says "A calls B"; a lineage graph also says "B and C are alternatives". Without the redundancy, you cannot compute minimal failure sets.
Tracing's blind spots are LDFI's blind spots. Uninstrumented dependencies, shared underlying resources (the same switch, the same config service) and latency rather than outright failure don't show up in the call tree, so LDFI cannot reason about them.
You need a definition of success. A 200 response is not the same as a correct one; get the check wrong and the loop converges in the wrong place.
High bar, limited adoption. It needs tracing, an injection platform and a solver. Public production case studies are few, with Netflix the best known; most teams still rely on random plus experts.
Minimal is not the same as most important. Which set to run first still needs ranking by business impact, a step the book leaves to people.

Key takeaways

① The problem: the fault space explodes combinatorially (triples of 100 services: 161,700), so choosing experiments is the bottleneck.

② In mature systems the fatal bugs tend to sit in "main path plus backup fail together"; single-fault injection won't find them.

③ Random search is unbiased but shallow; expert guidance is precise but doesn't scale and inherits the experts' blind spots.

④ The flip: study how requests succeed and record supports and redundancy as a lineage graph.

⑤ Turn lineage into a formula and let a SAT solver find minimal failure sets; in the example, 32 subsets shrink to 3.

⑥ The loop: failure after injection = a bug; continued success = unknown redundancy, so extend the graph and solve again.

⑦ Netflix used distributed tracing to approximate lineage and brought LDFI into production (SoCC 2016).

⑧ Blind spots: dependencies tracing can't see, shared resources, latency faults, and a wrong definition of success.