Testing Distributed Systems & Chaos Engineering: Jepsen & Invariants

1. Context & Architecture Reality

SYSTEM ARCHITECTURE BLUEPRINTDISTRIBUTED SYSTEMS

⤢Expand

ARCHITECTURAL FLOW · STEP 1 OF 3

1. Client Workers & Distributed Cluster

Establishes the ingress and structural boundary across Client Workers & Distributed Cluster: invoke(:write, 5) invoke(:read, nil); N1 N2 N3 Split-brain partition!; iptables drop packets.

Architectural Invariant: :invoke :write 1 :ok :write 1 :invoke :read nil :ok :read 1 :invoke :write 2 :fail :write 2 :ok :read 0 <-- Linearizability Violation Detected!.

ARCHITECTURAL FLOW · STEP 2 OF 3

2. Op1: write(x, 1) [OK] & Op2: read(x) → 1 [OK]

Coordinates core data-plane execution and state transitions through Op1: write(x, 1) [OK] & Op2: read(x) → 1 [OK]: Op3 MUST observe Op1 or a newer write! Reading 0 is an illegal stale read; Latency: +250ms with 20ms jitter; Loss: 15% random drop / corrupt.

Architectural Invariant: Stalled fsync writes / disk full.

ARCHITECTURAL FLOW · STEP 3 OF 3

3. Linearizability Model: Real-Time Precedence & Chaos Engineering Fault Categories

Enforces durability, state convergence, and output verification across Linearizability Model: Real-Time Precedence & Chaos Engineering Fault Categories: 1. Entire cluster, network, and disk runs in a single thread; 2. Simulated clock: time jumps instantly to the next discrete event; 3. Pseudorandom seed governs every network packet reorder and crash → If seed 84920 fails on step 4,291, re-running seed 84920 reproduces the EXACT bug down to the microsecond!.

Architectural Invariant: 3. Pseudorandom seed governs every network packet reorder and crash → If seed 84920 fails on step 4,291, re-running seed 84920 reproduces the EXACT bug down to the microsecond!.

In a single-threaded program, verifying correctness is straightforward: given input $X$, the function produces output $Y$. If an exception occurs, a stack trace points directly to the offending line of code.

In distributed systems, traditional testing methodologies (unit tests, mocks, standard end-to-end integration tests) provide a dangerous illusion of safety. The most disastrous bugs—data loss in distributed databases, split-brain write corruption, lost transactions during failover, and deadlocks—do not occur during clean, happy-path execution. They manifest only when:

• A network partition splits a 5-node cluster into a 2-node minority and a 3-node majority.
• A garbage collection (GC) pause freezes the leader for 4 seconds, causing followers to elect a new leader while the old leader still believes it has lease authority.
• An NVMe storage controller acknowledges an fsync() write that was merely buffered in volatile drive cache before power flickers.

To build distributed systems that survive production, software engineers must practice adversarial verification: treating the network and physical hardware as hostile, injecting systematic faults, and mathematically proving that safety invariants hold under chaos.

+--------------------------------------------------------------------------------------------------+
|                            JEPSEN VERIFICATION ARCHITECTURE                                      |
|                                                                                                  |
|   +-------------------+          +-------------------+          +-------------------+            |
|   |  Worker Client 1  |          |  Worker Client 2  |          |  Worker Client 3  |            |
|   +---------+---------+          +---------+---------+          +---------+---------+            |
|             |                              |                              |                      |
|             | Concurrent Read/Write Ops    |                              |                      |
|             v                              v                              v                      |
|   +---------------------------------------------------------------------------------+            |
|   |                        DISTRIBUTED CLUSTER UNDER TEST                           |            |
|   |                                                                                 |            |
|   |       [Node 1] <------------- (iptables drop) ------------> [Node 2]            |            |
|   |          ^                                                     ^                |            |
|   +----------|-----------------------------------------------------|----------------+            |
|              | Fault Injection (SIGSTOP / Clock Skew / Packet Loss)|                             |
|   +----------+----------+                                                                        |
|   |     NEMESIS         |                                                                        |
|   +---------------------+                                                                        |
|              |                                                                                   |
|              v Records execution events (:invoke, :ok, :fail)                                    |
|   +---------------------------------------------------------------------------------+            |
|   |                             OPERATION HISTORY LOG                               |            |
|   +---------------------------------------------------------------------------------+            |
|              |                                                                                   |
|              v Linearizability Verification                                                      |
|   +---------------------------------------------------------------------------------+            |
|   |              PORCUPINE / KNOSSOS INVARIANT CHECKER ENGINE                       |            |
|   |              Validates: Can operations be linearized to a valid state machine?  |            |
|   +---------------------------------------------------------------------------------+            |
+----------------------------------------------------------------------------------+

2. Core Problem & Failure Modes

Adversarial testing targets five classic distributed failure modes:

1. Stale Reads in Quorum Systems ($R+W\le N$): In systems claiming strong consistency, if the read quorum $R$ and write quorum $W$ satisfy $R+W>N$, reads should observe the latest write. However, bugs in version vector comparison or failure to account for uncommitted transactions during node failover frequently allow stale reads to leak through.

2. Split-Brain Dual Leaders: When network partitions occur, if leader election leases rely on wall-clock time rather than monotonic consensus terms or monotonic clock offsets, two nodes may both believe they are the legitimate leader, accepting contradictory writes on either side of the partition.

3. Phantom Writes and Lost Deletions (Tombstone Pruning): Distributed databases use tombstones to record deletions. If a network partition keeps a replica disconnected past the tombstone garbage collection window (gc_grace_seconds), reconnecting the node can cause previously deleted rows to reappear as “phantom” data.

4. Non-Deterministic Race Conditions (Heisenbugs): A race condition that requires a specific sequence of 10 microsecond-level packet arrivals might occur once every 100,000 requests in staging. When running in standard CI/CD, the test passes $99.9\%$ of the time, leading engineers to dismiss intermittent failures as “flaky tests.”

3. Technical Deep Dive

Formal Linearizability Formulation

Linearizability (Herlihy and Wing, 1990) is the gold standard of consistency for single-object concurrent operations.

A concurrent execution history $H$ consists of a set of operations, where each operation $op$ has:

• An invocation event: $\text{inv}(op)$ occurring at real time $t_{\text{start}}(op)$
• A response event: $\text{res}(op)$ occurring at real time $t_{\text{end}}(op)$

We define the Real-Time Precedence Relation ${<}_H$ over operations:

That is, $o{p}_1$ precedes $o{p}_2$ in real time if and only if $o{p}_1$ finished before $o{p}_2$ was invoked.

A concurrent history $H$ is linearizable if and only if there exists a valid sequential history $S$ such that:

1. Equivalence: $S$ contains exactly the same operations with the same arguments and return values as $H$.
2. Sequential Specification: $S$ is legal according to the sequential definition of the data type (e.g., for a register, a read must return the value written by the most recent write preceding it in $S$).
3. Preservation of Real-Time Order: For all $o{p}_1,o{p}_2\in H$, if $o{p}_1{<}_{H}o{p}_2$, then $o{p}_1$ must appear before $o{p}_2$ in $S$:

If two operations overlap in real time (neither finished before the other started), their relative order in $S$ is unconstrained; either order is valid, provided the resulting sequence is legal.

The Linearizability Checking Algorithm (Knossos & Porcupine)

Verifying whether an arbitrary concurrent history $H$ with $n$ operations is linearizable is an NP-complete problem in the general case (equivalent to searching an exponential tree of interleavings).

Modern checkers (like Jepsen’s Knossos or Go’s Porcupine) optimize this search using State-Space Pruning:

1. Construct the partial order DAG defined by ${<}_H$.
2. Maintain a set of reachable legal states $Q$.
3. At step $k$, find all operations $o{p}_i$ that have no unlinearized predecessors in ${<}_H$.
4. For each candidate $o{p}_i$, test if applying $o{p}_i$ to any state $q\in Q$ produces a legal next state $q^{\prime }$.
5. Prune equivalent duplicate states. If all candidate branches fail, backtrack. If no legal sequence exists that accounts for all operations, output the minimal failing history and counterexample DAG.

4. System Design Patterns & Trade-offs

+----------------------------------------------------------------------------------------------------+
| TRADEOFF MATRIX: DISTRIBUTED VERIFICATION METHODOLOGIES                                            |
+--------------------------+------------------------------------+------------------------------------+
| Dimension                | Black-Box Cluster Fuzzing (Jepsen) | Deterministic Simulation (FDB)     |
+--------------------------+------------------------------------+------------------------------------+
| Execution Environment    | Real Linux VMs / Docker containers | Single-threaded simulated event loop|
| Speed                    | Hours to days for complex runs     | Billions of ops in minutes         |
| Reproducibility          | Low (flaky, timing-dependent)      | 100% Deterministic (fixed seed)    |
| Code Changes Required    | Zero (tests black-box network API) | Deep (entire code must use mock I/O)|
+--------------------------+------------------------------------+------------------------------------+
| Dimension                | Staging-Only Chaos Engineering     | Production Chaos (GameDays)        |
+--------------------------+------------------------------------+------------------------------------+
| Safety & Blast Radius    | Zero customer impact               | Potential customer impact          |
| Realism                  | Lacks real traffic distribution    | True production topology & scale   |
+--------------------------+------------------------------------+------------------------------------+

5. Practical Implementation

Below is a complete TypeScript simulation of a Porcupine-style Linearizability Verifier for a concurrent Read/Write register. It constructs real-time intervals and searches for a valid linear sequential permutation.

export interface Operation {
  id: string;
  type: 'WRITE' | 'READ';
  value: number;
  startTime: number; // invocation timestamp
  endTime: number;   // response timestamp
}

export interface VerificationResult {
  isLinearizable: boolean;
  linearizedSequence?: Operation[];
  violationReason?: string;
}

/**
 * Register Linearizability Checker
 * Verifies that concurrent read/write history satisfies real-time atomic register semantics.
 */
export class LinearizabilityVerifier {
  /**
   * Evaluates if a given concurrent history is linearizable
   */
  public verifyRegisterHistory(history: Operation[]): VerificationResult {
    // Sort operations by start time for consistent evaluation
    const ops = [...history].sort((a, b) => a.startTime - b.startTime);

    const result = this.searchLinearization(ops, [], 0);
    if (result) {
      return { isLinearizable: true, linearizedSequence: result };
    }

    return {
      isLinearizable: false,
      violationReason: 'No legal sequential execution order satisfies real-time precedence and register semantics'
    };
  }

  private searchLinearization(
    remainingOps: Operation[],
    linearizedSoFar: Operation[],
    currentRegisterState: number
  ): Operation[] | null {
    if (remainingOps.length === 0) {
      return linearizedSoFar;
    }

    // Identify candidate operations that can be linearized next.
    // An operation can be linearized next if no other unlinearized operation
    // finished strictly before this operation started (preserving <_H).
    const candidates = remainingOps.filter((op) => {
      return !remainingOps.some((other) => other.id !== op.id && other.endTime < op.startTime);
    });

    for (const candidate of candidates) {
      let nextState = currentRegisterState;
      let isValidTransition = false;

      if (candidate.type === 'WRITE') {
        nextState = candidate.value;
        isValidTransition = true;
      } else if (candidate.type === 'READ') {
        // Read is valid if and only if it observes the current state
        if (candidate.value === currentRegisterState) {
          isValidTransition = true;
        }
      }

      if (isValidTransition) {
        const nextRemaining = remainingOps.filter((o) => o.id !== candidate.id);
        const solution = this.searchLinearization(
          nextRemaining,
          [...linearizedSoFar, candidate],
          nextState
        );
        if (solution) return solution;
      }
    }

    return null; // Backtrack
  }
}

function runDemo(): void {
  console.log("=== Chaos Engineering & Linearizability Verifier ===");
  const verifier = new LinearizabilityVerifier();
  const history: Operation[] = [
    { id: "op-1", type: "WRITE", value: 10, startTime: 10, endTime: 20 },
    { id: "op-2", type: "READ", value: 10, startTime: 25, endTime: 30 },
  ];
  const result = verifier.verifyRegisterHistory(history);
  console.log(`Linearizability verification: valid=${result.isLinearizable}, checkedOperations=${history.length}`);
}

runDemo();

6. Failure Scenarios & Edge Cases

1. Clock Desynchronization in Black-Box Test Workers

If Jepsen client workers run on multiple physical host machines whose clocks drift by even $10\text{ ms}$, an operation’s recorded startTime on Worker B might be earlier than Worker A’s recorded endTime, even though Worker B actually started after Worker A finished. This corrupts the ${<}_H$ relation, producing false-positive linearizability failure reports.

• Mitigation: Run all test worker threads inside a single operating system process using a monotonic nanosecond clock (CLOCK_MONOTONIC), eliminating cross-node timestamp skew.

2. Network Chaos Escaping to Kubernetes Control Plane

When injecting packet loss across nodes using a naive NetworkChaos rule (drop: 100%), the rule accidentally matches traffic to the Kubernetes API server on port 6443. The node becomes NotReady, the Chaos Mesh controller loses connection, and the chaos experiment cannot be halted without manually logging into the host console to flush iptables.

• Mitigation: Always enforce explicit negative target selectors for cluster control planes and CIDRs.

7. Production Operations & Observability

Chaos GameDays Protocol

+----------------------------------------------------------------------------------------------------+
| CHAOS GAMEDAY EXECUTION PROTOCOL                                                                   |
+--------------------------+-------------------------------------------------------------------------+
| Phase                    | Checklist Items                                                         |
+--------------------------+-------------------------------------------------------------------------+
| 1. Hypothesis Definition | Formulate exact invariant: "Killing any single Redis replica will not   |
|                          | increase checkout error rate above 0.01% or p99 above 150ms."           |
+--------------------------+-------------------------------------------------------------------------+
| 2. Blast Radius Ceiling  | Scope experiment to 1% of canary production traffic or single AZ.       |
+--------------------------+-------------------------------------------------------------------------+
| 3. Abort Triggers        | Define automated kill-switch: If global 5xx error rate exceeds 0.5%,   |
|                          | cancel chaos experiment and restore networking in < 5 seconds.         |
+--------------------------+-------------------------------------------------------------------------+
| 4. Verification & Audit  | Validate that alerts fired within expected SLO thresholds without false |
|                          | negatives. Log findings into blameless post-drill report.               |
+--------------------------+-------------------------------------------------------------------------+

8. Security & Compliance

1. Restricting Chaos Daemon Privileges: Chaos injection agents (e.g., Chaos Mesh daemon) require privileged Docker access and NET_ADMIN Linux capabilities to manipulate network interfaces and kernel namespaces.
   • Restrict daemon pods using Kubernetes Pod Security Standards (restricted / privileged exceptions only for designated chaos namespaces).
   • Require multi-party authorization (two engineers must approve) before running chaos experiments in production environments subject to SOC2 or PCI-DSS controls.

9. Real-World Case Studies

FoundationDB Deterministic Simulation

FoundationDB’s storage engine was built from day one around deterministic simulation testing. The team wrote an asynchronous C++ runtime (Flow) that compiles to single-threaded coroutines.

• Every system call (disk write, network socket, timer) is simulated.
• During nightly testing runs, clusters of virtual machines execute trillions of transactions while simulated power cuts, disk corruptions, and asymmetric partitions strike.
• Over a 10-year development period, FoundationDB discovered hundreds of critical concurrency bugs that would have required years of production runtime to surface.

10. Technology Comparison Matrix

+----------------------------------------------------------------------------------------------------+
| DISTRIBUTED TESTING & CHAOS FRAMEWORKS                                                             |
+----------------------+--------------------+--------------------+-----------------------------------+
| Tool                 | Primary Focus      | Fault Injection    | Consistency Invariant Checking    |
+----------------------+--------------------+--------------------+-----------------------------------+
| Jepsen               | Distributed DBs    | iptables, SIGSTOP, | Knossos, Elle (Serializability,   |
|                      | & Consensus (Raft) | Clock warp         | Linearizability verification)     |
+----------------------+--------------------+--------------------+-----------------------------------+
| Chaos Mesh           | Cloud-Native       | eBPF, iptables,    | Observability & health probe      |
|                      | Kubernetes (K8s)   | stress-ng, tc      | metrics validation                |
+----------------------+--------------------+--------------------+-----------------------------------+
| FoundationDB Sim     | Deterministic      | Simulated network  | Exact state machine equivalence   |
|                      | Core Simulation    | & disk in 1 thread | with 100% deterministic seed repro|
+----------------------+--------------------+--------------------+-----------------------------------+
| LitmusChaos          | CNCF Workflow      | Container kill,    | Custom health probes & Prometheus |
|                      | Chaos Engine       | Pod network loss   | metric validation                 |
+----------------------+--------------------+--------------------+-----------------------------------+

11. Design Challenge & Exercise

Scenario: Verifying Distributed Leader Lease Invariants

You are tasked with verifying a 5-node distributed lock service based on Raft. The marketing team claims the service is “100% linearizable and partition-tolerant.”

Assignment:

1. Design a Jepsen test suite that runs 10 concurrent client workers acquiring, renewing, and releasing locks.
2. Specify the exact Nemesis failure injections to introduce:
   • Introduce an asymmetric partition where Node 1 (Leader) can send heartbeats to Node 2 and Node 3, but cannot receive responses from them.
   • Inject a 3-second thread freeze on Node 1 using SIGSTOP.
3. Construct a trace history log containing 5 operations and prove mathematically whether the log is linearizable or violates mutual exclusion invariants.

12. Assessment

Review the 4 scenario-based quiz questions at the top of this lesson to test your mastery of linearizability verification, Knossos/Porcupine checking algorithms, and chaos engineering architectures.

13. Summary & Architectural Decision Guide

• Hypothesis First: Never run chaos experiments without defining normal steady-state metrics and an explicit falsifiable hypothesis.
• Automate Blast Breakers: Configure automated metrics monitors (e.g. PromQL error rate triggers) that immediately roll back chaos injections if customer impact exceeds bounds.
• Test Asymmetric Partitions: Simulate one-way packet drops and flapping links; these reveal hidden consensus bugs that symmetric cuts hide.
• Run Jepsen on Storage Engines: Validate distributed transaction invariants under network partitions before declaring a database production-ready.

14. Authoritative References & Version Context

• Casey Rosenthal and Nora Jones (2020), “Chaos Engineering: System Resiliency in Practice”, O’Reilly Media — oreilly.com
• Kyle Kingsbury (2014–2024), “Jepsen: Distributed Systems Safety Verification” — jepsen.io
• Chaos Mesh Official Documentation (CNCF Graduated Project) — chaos-mesh.org/docs/
• Version Context: Chaos engineering frameworks target Kubernetes 1.28+, Chaos Mesh 2.6+, and Linux tc-netem network emulation tools.