The Scale Ceiling
Jepsen has always treated a test as a history of operations—invocations and completions that checkers later analyze for consistency anomalies and performance metrics. Historically, that history lived in a Clojure vector in memory, serialized to disk only at the end of the run. That design capped practical test sizes at tens of millions of operations. It also meant a crash during a multi-hour test destroyed everything: no partial history to recover, no way to analyze what happened before failure. And the round-trip of saving and loading a large test could take ten minutes or more at each end.
A year of work has addressed all three problems. Generators now run up to ten times faster in many cases, sustaining 50,000 operations per second on realistic workloads. A new Op record type makes individual operations smaller and faster to read. Jepsen now streams histories to disk incrementally as the test runs rather than at the end, which enables histories of up to a billion operations—well beyond available RAM—and allows safe recovery after crashes. Loading is nearly instant because deserialization is lazy. New history types back both dense and sparse index spaces, cache derived indices efficiently, and support lazy disk-backed map and filter. These histories can be folded over linearly or concurrently, which lets checkers analyze real-world data at rates between 250,000 and 900,000 operations per second on multicore hardware.
What a History Holds
A Jepsen history is fundamentally a chronologically ordered list of operation elements. Each logical operation—set a key, read a register, enqueue a value—produces two entries: an :invoke when the operation starts, and a completion (:ok, :fail, or :info) when it ends. That pairing lets checkers distinguish concurrent operations from strictly sequential ones. In practice "operation" is used loosely to mean either a single entry or the whole pair.
[{:type :invoke, :f :txn, :value [[:w 2 1]], :time 3291485317, :process 0, :index 0}
{:type :invoke, :f :txn, :value [[:r 0 nil] [:w 1 1] [:r 2 nil] [:w 1 2]], :time 3296209422, :process 2, :index 1}
{:type :fail, :f :txn, :value [[:r 0 nil] [:w 1 1] [:r 2 nil] [:w 1 2]], :time 3565403674, :process 2, :index 2, :error [:duplicate-key "etcdserver: duplicate key given in txn request"]}
{:type :ok, :f :txn, :value [[:w 2 1]], :time 3767733708, :process 0, :index 3}]
Each operation carries several predictable fields beyond the user-defined :f and :value: :type for the phase, :process to identify the logical thread, and :index, a unique strictly monotonic identifier. In dense histories, indices are consecutive integers starting at zero. Filtering or truncating produces sparse histories—indices like 3, 7, 8, 20—and tests may attach whatever additional fields they need.
A generator decides what operations to issue next. Generators are functional data structures that evolve in response to the operations performed, built from a combinator library that covers sequencing, alternation, mapping, filtering, limits, delays, concurrency bounds, and selective nondeterminism.
Generators, Faster
A major early bottleneck was the generator itself not producing operations quickly enough to tax the database under test. Much of the time went to manipulating the generator context, which tracks which threads are free and what logical process each is running. Contexts are constantly restricted and consulted—a generator that wants to pick a random free process, or partition a context's threads into groups doing different work, pays for that flexibility.
Profiling traced most of the cost to Clojure's persistent maps and sets used for context representation. Jepsen 0.3.0 introduced a new context namespace with specialized structures. A custom translation table maps thread identifiers to integers, allowing the active thread set to be encoded as Java BitSets, which require no pointer chasing and far less memory than hash-set backed collections. To restrict threads to specific subsets, Jepsen precompiles a filter BitSet, converting an expensive set intersection into a single bitwise and. This change alone gave an order-of-magnitude speedup on a realistic 1024-thread generator test, pushing throughput to 26,000 operations per second.
Further tuning based on YourKit profiling added smaller gains: memoized function arity checks for function-based generators, type hints to avoid reflection, careful tracking of which map fields were already read to prevent redundant access, a transducer instead of mapcat, count instead of seq for nil checks, and identical? in a few places that compare symbols. The net result, measured on a list-append generator workload with 100 threads, is 50,000 operations per second.
Memory: The Head Problem
Long-running tests showed a steady linear climb in memory consumption. The culprit was the test map, a ubiquitous structure holding the initial generator reference. Generators behave much like infinite lazy sequences: "retaining the head" kept alive a reference chain that included every operation ever generated.
The test map is accessible throughout the test lifecycle to arbitrary user code, so the fix could not depend on discipline about not storing references. Jepsen now wraps the generator in a Forgettable reference explicitly cleared once execution starts, permitting the garbage collector to reclaim old generator states. Histories of 10⁹ operations now run in a few hundred megabytes of heap.
Records Over Maps
Operations were originally Clojure maps, an array-and-hash-table structure that is memory-hungry, stores only JVM Objects, and has measurable lookup overhead. Since field access is constant and memory efficiency matters at this scale, operations are now Clojure records. The Op datatype stores index and time as primitive longs and type, process, f, and value as direct Object references. That layout is substantially denser and improves cache locality. Field access still reads naturally—(:index some-op)—but compiles to a type-checked direct field read rather than a hash lookup.
Records retain map-like behavior, keeping an internal map that accepts any extra fields tests want to add, so existing tests remain compatible. The one API tightening is that index and time are no longer optional; Jepsen always fills them in production runs, so only internal checker tests had to adapt.
A Streaming Disk Format
Jepsen historically serialized tests—histories and analysis results both—as a single Fressian map. That approach worked for small tests but could take tens of minutes to write large histories. A custom disk format now sits underneath. Files comprise a short header and an append-only log of immutable blocks. Each block carries a type, length, and checksum header followed by its data. Blocks form a persistent tree: changes append new blocks to the file, then a single offset in the header flips to point at the block encoding the tree root.
Blocks hold arbitrary Fressian data, layered lazily-decoded maps, streaming lists, and chunked vectors that point to other vectors “stitched together” into one large vector. The chunked vectors store the index of the first element of each chunk, so any index can jump to its chunk in constant time.
During a test, Jepsen writes each operation into a series of chunks, each a streaming list of Fressian data. When a chunk fills (16384 operations by default), it is sealed, checksummed, and a new chunked vector block records pointers to all chunks in the history, re-using existing chunks. Jepsen then writes a new root block and flips the root pointer. At most the last 16384 operations can be lost on a crash.
Loading a test reads the header, decodes the root block, and constructs a lazy map that decodes results and history only on demand. Results are likewise lazy maps, so large results still load efficiently. This yields millisecond access to test metadata—names, timestamps, validity—instead of minutes-long reads. Existing tests remain drop-in compatible: they look like regular hashmaps, with metadata allowing efficient alteration and re-saving for later re-analysis.
Histories load into a lazy chunked vector with a cached count and a lookup table mapping indices to chunks. Chunks decode lazily on first read and stay in JVM SoftReference caches, reclaimable under memory pressure. To users, the vector behaves exactly like an in-memory vector, preserving compatibility with existing checkers.
Handling Sparse and Transformed Histories
Checkers run repeated operations on histories, needing counts of results, lookups by :index, jumps between invocations and completions, and scheduling for concurrent analysis. The IHistory type adds these facilities to lazy operation vectors: cached invocation-to-completion mapping, a threadpool for analysis, and a stateful execution planner called a folder.
Recorded histories assign each operation a sequential index 0, 1, 2, 3…; these are dense. Lookup by index is then just (nth history idx). Filtering or excerpting a history produces a sparse history, where a lazily-computed map between operation indices and vector positions keeps lookups efficient.
Standard Clojure map and filter would be inappropriate on histories: realized sequences stay in memory permanently and nth needs linear time. So Jepsen ships lazy history-specific map and filter variants that push the operation down into each access, trading cache-ability for low memory. Multiple queries can share the same function, mapped histories keep constant-time nth, and filtered histories get log-time nth.
Concurrent Folds Over Chunks
Because disk files divide into chunks, folds can parallelize naturally. History folds use their own facility, compatible with Tesser, which composes concurrent folds. Though Tesser assumes commutative folds, most operators—map, filter, group-by, fuse, facet—work with ordered reductions too. A concurrent reduction runs independently over each chunk, then combine steps merge results sequentially. On multi-core CPUs this delivers large speedups. Each core scans its chunk linearly from disk, which also plays well with readahead.
Each history pairs with a stateful Folder that schedules and executes folds. A linear fold reduces the first chunk, passes its result to the next, and so on. A concurrent fold schedules reductions over all chunks at once plus a serial chain of combine tasks.
Folders pay close attention to thread locality and memory barriers during inter-thread handoff, so folds can use mutable in-memory accumulators instead of only immutable values. No locks are needed inside reducing or combining functions. This works with mutable reducers in dom-top. Folder interfaces back plain Clojure reduce and reducers/fold, so existing checkers transparently gain the optimizations.
Fusing Folds in One Pass
Jepsen tests can run dozens of checkers, each performing many folds. When the history exceeds memory, chunks evict from cache, and a subsequent fold may re-parse chunks already decoded and dropped. Overlapping folds also destroy locality—each reads operations and chases pointers on different cores at different times, polluting caches. Combining folds into fewer passes would help.
The folder acts as a stateful coordination service. Checkers call fold as usual, and the folder secretly fuses concurrent folds into as few passes as the current state allows. Suppose one thread starts a fold for G1a anomalies on chunk 0, chunks 3, and chunk 5. Another thread then asks for a latency statistics fold. The folder constructs a fused fold that does both in one step, schedules it for the chunks the first fold hasn’t touched, and cancels the redundant planned reductions for those same chunks. New combine tasks merge all results. Fused and independent stages weave together automatically, reusing as much completed work as possible while processing the rest of the history in one pass. Results then go to each caller.
All of this happens transactionally, guaranteeing exactly-once processing and thread safety even with unsynchronized mutable accumulators. A simpler join process fuses linear folds together.
Callers remain unaware of these mechanics—they fold over the history and get results. Early chunks may still see a few independent passes, but those typically stay cached, so the whole history gets processed in a single pass. The payoff is high throughput, reduced I/O, and good cache behavior.
Dependency-Aware Task Scheduling
Modern CPUs offer many cores, so Jepsen's history checker library parallelizes its analyses across threads. But running too many threads imposes heavy context-switching costs. More importantly, tasks that block on the results of other tasks must never launch before their dependencies finish. Doing so would lead to threadpool starvation — and, in the classic Java pattern, deadlock.
Jepsen's history library addresses this with a transactional, dependency-aware task scheduler. Tasks are functions that receive their dependencies' results as arguments and can only start when those dependencies complete, which prevents deadlock. Cancelling a task cancels its dependencies too; an exception in one task propagates to downstream consumers, simplifying error handling. Dereferencing a task returns its result, or throws if an exception occurred.
Behind these semantics sits an immutable executor state tracking the dependency graph, which tasks are ready or running, and the next task ID. A miniature effect system applies a log of side effects derived from changes to that state, enabling arbitrary transactions: any number of tasks can be created or cancelled atomically.
That design leans on deliberate misuse of Java's ExecutorService and BlockingQueue. The "queue" is actually the immutable state's dependency graph, and JVM attempts to enqueue work are ignored in favor of mutating state through transaction channels. When tasks become available, trivial runnables wake up the executor. That may feel wrong, but it works: generative tests stress both the linear and concurrent behavior.
API Surface Changes
The largest API change involves replacing plain vectors of operations with a first-class IHistory type. Code that hand-constructed histories and fed them to checkers — for example by calling regular Clojure map or filter — will now hit a type incompatibility. The fix is straightforward: use jepsen.history/map and friends, or call jepsen.history/history to wrap an existing collection in an IHistory. These wrappers handle both the clean histories Jepsen generates and the incomplete test histories used in Jepsen's own test suites.
Operation :time and :index fields are now mandatory. Jepsen always supplies both, but hand-coded histories in internal test suites may lack them. The history wrapper promotes operations to hashmaps automatically, and indices are validated or assigned for testing as needed.
Otherwise the transition was smooth. Existing code could keep treating operations as hashmaps, continue to pretend histories are vectors, and use standard Clojure collection operations transparently — all now backed by lazily cached on-disk structures. Most core checkers in Jepsen and Elle were incrementally rewritten around the new Op type and fold system, with substantial speedups along the way.
One recent change drops :generator from the test map. Nothing appears to read generator state other than debugging code, but there are always unknowns.
Performance Under Load
Jepsen 0.2.7 could sustain roughly 7,000 ops/sec on an etcd list-append transactional test against a five-node LXC cluster — at which point etcd, not Jepsen, was the bottleneck. That test exhausted a 16 GB heap and crashed after about two hours; a 90-minute run produced a single Fressian object of 2.2 GB containing 38,076,478 operations, which exceeded MAX_INT bytes and crashed Jepsen.
An hour-long run stayed within both the heap and serialization limits: 25,461,508 operations (7.07 kHz) in a 1.5 GB Jepsen file. Analyzing that in-memory history for G1a, G1b, and internal consistency took 202 seconds (126 kHz).
The file itself required 366 seconds and a 58 GB heap just to load — even to read a single operation. The cost comes from persistent map and vector memory footprints, temporary intermediate representations in the Fressian decoder, pointer and object-header overhead, and Fressian's compact primitive encodings and value caching.
By Jepsen 0.3.3, that same hour-long test consumed only a few hundred megabytes of heap until analysis, when it fully exploited the 16 GB heap to cache most of the history and avoid repeated chunk parsing. It produced a 1.9 GB Jepsen file with 40,358,966 elements (11.2 kHz), and analysis finished in 97 seconds (416 kHz). Even though analysis re-parses the whole history from disk, it does so in parallel.
Left running ~25.4 hours, that same suite recorded one billion operations at roughly 11 kHz, producing a 108 GB Jepsen file. Checking for G1a, G1b, and internal anomalies took 1 hour and 6 minutes (249 kHz) on a 100 GB heap, consuming 70–98% of 48 cores. G1a and G1b are global anomalies: they need all failed and intermediate writes computed in an initial pass, then those index structures retained for a second pass. Under memory pressure the analysis reloads evicted chunks more often. Simpler folds — counting ok, failed, and crashed operations — run at upwards of 900 kHz.
The new file format's lazy structure keeps parsing cheap: reading top-level test attributes takes 20–30 milliseconds, and fetching any single history element takes roughly 500 milliseconds — a few disk seeks for the root, test, and history block, plus chunk checksumming and parsing. The history block itself was ~715 KB, containing pointers to 61,000 chunks of 16,384 operations each.
Looking Ahead
Jepsen 0.3.3 generates up to 50,000 operations per second, handles histories of a billion operations, and checks close to a million operations per second — dependent on what the generator, client, and test are doing. Further scaling may prove difficult: many JVM collection APIs cap out at 231 - 1 elements. Many checkers now run as concurrent folds on memory-efficient structures, but only some analyses are fully local; many require O(n) memory and may not scale past a few million operations.
Jepsen 0.3.3 is available now, opening new territory for distributed systems testing.
