In a Nutshell

Generators tell Jepsen what to do during a test. Generators are purely functional objects which support two functions: op and update. op produces operations for Jepsen to perform: it takes a test and context object, and yields:

• nil if the generator is exhausted
• :pending if the generator doesn’t know what to do yet
• op, gen’, where op’ is the next operation this generator would like to execute, and gen' is the state of the generator that would result if op were evaluated. Ops must be a jepsen.history.Op.

update allows generators to evolve as events occur–for instance, when an operation is invoked or completed. For instance, update allows a generator to emit read operations until at least one succeeds.

Maps, sequences, and functions are all generators, allowing you to write all kinds of generators using existing Clojure tooling. This namespace provides additional transformations and combinators for complex transformations.

Migrating From Classic Generators

The old jepsen.generator namespace used mutable state everywhere, and was plagued by race conditions. jepsen.generator.pure provides a similar API, but its purely functional approach has several advantages:

• Pure generators shouldn’t deadlock or throw weird interrupted exceptions. These issues have plagued classic generators; I’ve done my best to make incremental improvements, but the problems seem unavoidable.

• Pure generators can respond to completion operations, which means you can write things like ‘keep trying x until y occurs’ without sharing complex mutable state with clients.

• Sequences are pure generators out of the box; no more juggling gen/seq wrappers. Use existing Clojure sequence transformations to build complex behaviors.

• Pure generators provide an explicit ‘I don’t know yet’ state, which is useful when you know future operations might come, but don’t know when or what they are.

• Pure generators do not rely on dynamic state; their arguments are all explicit. They are deterministically testable.

• Pure generators allow new combinators like (any gen1 gen2 gen3), which returns the first operation from any of several generators; this approach was impossible in classic generators.

• Pure generators have an explicit, deterministic model of time, rather than relying on thread scheduler constructs like Thread/sleep.

• Certain constructs, like gen/sleep and gen/log in classic generators, could not be composed in sequences readily; pure generators provide a regular composition language.

• Constructs like gen/each, which were fragile in classic generators and relied on macro magic, are now simple functions.

• Pure generators are significantly simpler to implement and test than classic generators, though they do require careful thought.

There are some notable tradeoffs, including:

• Pure generators perform all generator-related computation on a single thread, and create additional garbage due to their pure functional approach. However, realistic generator tests yield rates over 20,000 operations/sec, which seems more than sufficient for Jepsen’s purposes.

• The API is subtly different. In my experience teaching hundreds of engineers to write Jepsen tests, users typically cite the generator API as one of Jepsen’s best features. I’ve tried to preserve as much of its shape as possible, while sanding off rough edges and cleaning up inconsistencies. Some functions have the same shape but different semantics: stagger, for instance, now takes a total rather than a *per-thread* rate. Some infrequently-used generators have not been ported, to keep the API smaller.

• update and contexts are not a full replacement for mutable state. We think they should suffice for most practical uses, and controlled use of mutable shared state is still possible.

• You can (and we encourage!) the use of impure functions, e.g. randomness, as impure generators. However, it’s possible I haven’t fully thought through the implications of this choice; the semantics may evolve over time.

When migrating old to new generators, keep in mind:

• gen/seq and gen/seq-all are unnecessary; any Clojure sequence is already a pure generator. gen/seq didn’t just turn sequences into generators; it also ensured that only one operation was consumed from each. This is now explicit: use (map gen.pure/once coll) instead of (gen/seq coll), andcollinstead of(gen/seq-all coll). Where the sequence is of one-shot generators already, there's no need to wrap elements with gen/once: instead of(gen/seq {:f :read} {:f :write})`), you can write {:f :read} {:f :write} directly.

• Functions return generators, not just operations, which makes it easier to express sequences of operations like ‘pick the current leader, isolate it, then kill that same node, then restart that node.’ Use #(gen/once {:f :write, :value (rand-int 5)) instead of (fn [] {:f :write, :value (rand-int 5)}).

• stagger, delay, etc. now take total rates, rather than the rate per thread.

• delay-til is gone. It should come back; I just haven’t written it yet. Defining what exactly delay-til means is… surprisingly tricky.

• each used to mean ‘on each process’, but in practice what users generally wanted was ‘on each thread’–on each process had a tendency to result in unexpected infinite loops when ops crashed. each-thread is probably what you want instead.

• Instead of using jepsen.generator/threads, etc, use helper functions like some-free-process.

• Functions now take zero args (f) or a test and context map (f test ctx), rather than (f test process).

• Maps are one-shot generators by default, rather than emitting themselves indefinitely. This streamlines the most common use cases:

  • (map (fn x {:f :write, :value x}) (range)) produces a series of distinct, monotonically increasing writes

  • (fn [] {:f :inc, :value (rand-nth 5)}) produces a series of random increments, rather than a series where every value is the same (randomly selected) value.

When migrating, you can drop most uses of gen/once around maps, and introduce (repeat …) where you want to repeat an operation more than once.

In More Detail

A Jepsen history is a list of operations–invocations and completions. A generator’s job is to specify what invocations to perform, and when. In a sense, a generator becomes a history as Jepsen incrementally applies it to a database.

Naively, we might define a history as a fixed sequence of invocations to perform at certain times, but this is impossible: we have only a fixed set of threads, and they may not be free to perform our operations. A thread must be free in order to perform an operation.

Time, too, is a dependency. When we schedule an operation to occur once per second, we mean that only once a certain time has passed can the next operation begin.

There may also be dependencies between threads. Perhaps only after a nemesis has initiated a network partition does our client perform a particular read. We want the ability to hold until a certain operation has begun.

Conceptually, then, a generator is a graph of events, some of which have not yet occurred. Some events are invocations: these are the operations the generator will provide to clients. Some events are completions: these are provided by clients to the generator. Other events are temporal: a certain time has passed.

This graph has some invocations which are ready to perform. When we have a ready invocation, we apply the invocation using the client, obtain a completion, and apply the completion back to the graph, obtaining a new graph.

By Example

Perform a single read

{:f :read}

Perform a single random write:

(fn [] {:f :write, :value (rand-int 5))

Perform 10 random writes. This is regular clojure.core/repeat:

(repeat 10 (fn [] {:f :write, :value (rand-int 5)))

Perform a sequence of 50 unique writes. We use regular Clojure sequence functions here:

(->> (range) (map (fn x {:f :write, :value (rand-int 5)})) (take 50))

Write 3, then (possibly concurrently) read:

{:f :write, :value 3} {:f :read}

Since these might execute concurrently, the read might not observe the write. To wait for the write to complete first:

(gen/phases {:f :write, :value 3} {:f :read})

Have each thread independently perform a single increment, then read:

(gen/each-thread {:f :inc} {:f :read})

Reserve 5 threads for reads, 10 threads for increments, and the remaining threads reset a counter.

(gen/reserve 5 (repeat {:f :read}) 10 (repeat {:f :inc}) (repeat {:f :reset}))

Perform a random mixture of unique writes and reads, randomly timed, at roughly 10 Hz, for 30 seconds:

(->> (gen/mix [(repeat {:f :read}) (map (fn x {:f :write, :value x}) (range))]) (gen/stagger 1/10) (gen/time-limit 30))

While that’s happening, have the nemesis alternate between breaking and repairing something roughly every 5 seconds:

(->> (gen/mix [(repeat {:f :read}) (map (fn x {:f :write, :value x}) (range))]) (gen/stagger 1/10) (gen/nemesis (->> (cycle {:f :break} {:f :repair}) (gen/stagger 5))) (gen/time-limit 30))

Follow this by a single nemesis repair (along with an informational log message), wait 10 seconds for recovery, then have each thread perform reads until that thread sees at least one OK operation.

(gen/phases (->> (gen/mix [(repeat {:f :read}) (map (fn x {:f :write, :value x}) (range))]) (gen/stagger 1/10) (gen/nemesis (->> (cycle {:f :break} {:f :repair}) (gen/stagger 5))) (gen/time-limit 30)) (gen/log “Recovering”) (gen/nemesis {:f :repair}) (gen/sleep 10) (gen/log “Final read”) (gen/clients (gen/each-thread (gen/until-ok {:f :read}))))

Contexts

A context is a map which provides information about the state of the world to generators. For instance, a generator might need to know the number of threads which will ask it for operations. It can get that number from the context. Users can add their own values to the context map, which allows two generators to share state. When one generator calls another, it can pass a modified version of the context, which allows us to write generators that, say, run two independent workloads, each with their own concurrency and thread mappings.

The standard context mappings, which are provided by Jepsen when invoking the top-level generator, and can be expected by every generator, are defined in jepsen.generator.context. They include some stock fields:

:time           The current Jepsen linear time, in nanoseconds

Additional fields (e.g. :threads, :free-threads, etc) are present for bookkeeping, but should not be interfered with or accessed directly: contexts are performance-sensitive and for optimization reasons their internal structure is somewhat complex. Use the functions all-threads, thread->process, some-free-process, etc. See jepsen.generator.context for these functions, which are also imported here in jepsen.generator.

Fetching an operation

We use (op gen test context) to ask the generator for the next invocation that we can process.

The operation can have three forms:

• The generator may return nil, which means the generator is done, and there is nothing more to do. Once a generator does this, it must never return anything other than nil, even if the context changes.
• The generator may return :pending, which means there might be more ops later, but it can’t tell yet.
• The generator may return an operation, in which case:
• If its time is in the past, we can evaluate it now
• If its time is in the future, we wait until either:
  • The time arrives
  • Circumstances change (e.g. we update the generator)

But (op gen test context) returns more than just an operation; it also returns the subsequent state of the generator, if that operation were to be performed. The two are bundled into a tuple.

(op gen test context) => op gen’ ; known op :pending gen ; unsure nil ; exhausted

The analogous operations for sequences are (first) and (next); why do we couple them here? Why not use the update mechanism strictly to evolve state? Because the behavior in sequences is relatively simple: next always moves forward one item, whereas only some updates actually cause systems to move forward. Seqs always do the same thing in response to next, whereas generators may do different things depending on context. Moreover, Jepsen generators are often branched, rather than linearly wrapped, as sequences are, resulting in questions about which branch needs to be updated.

When I tried to strictly separate implementations of (op) and (update), it resulted in every update call attempting to determine whether this particular generator did or did not emit the given invocation event. This is remarkably tricky to do well, and winds up relying on all kinds of non-local assumptions about the behavior of the generators you wrap, and those which wrap you.

Updating a generator

We still want the ability to respond to invocations and completions, e.g. by tracking that information in context variables. Therefore, in addition to (op) returning a new generator, we have a separate function, (update gen test context event), which allows generators to react to changing circumstances.

• We invoke an operation (e.g. one that the generator just gave us)
• We complete an operation

Updates use a context with a specific relationship to the event:

• The context :time is equal to the event :time
• The free processes set reflects the state after the event has taken place; e.g. if the event is an invoke, the thread is listed as no longer free; if the event is a completion, the thread is listed as free.
• The worker map reflects the process which that thread worker was executing at the time the event occurred.

See jepsen.generator.context for more.

Default implementations

Nil is a valid generator; it ignores updates and always yields nil for operations.

IPersistentMaps are generators which ignore updates and return exactly one operation which looks like the map itself, but with default values for time, process, and type provided based on the context. This means you can write a generator like

{:f :write, :value 2}

and it will generate a single op like

{:type :invoke, :process 3, :time 1234, :f :write, :value 2}

To produce an infinite series of ops drawn from the same map, use

(repeat {:f :write, :value 2}).

Sequences are generators which assume the elements of the sequence are themselves generators. They ignore updates, and return all operations from the first generator in the sequence, then all operations from the second, and so on.

Functions are generators which ignore updates and can take either test and context as arguments, or no args. Functions should be mostly pure, but some creative impurity is probably OK. For instance, returning randomized :values for maps is probably all right. I don’t know the laws! What is this, Haskell?

When a function is used as a generator, its return value is used as a generator; that generator is used until exhausted, and then the function is called again to produce a new generator. For instance:

; Produces a series of different random writes, e.g. 1, 5, 2, 3… (fn [] {:f :write, :value (rand-int 5)})

; Alternating write/read ops, e.g. write 2, read, write 5, read, … (fn [](map gen/once {:f :write, :value (rand-int 5)} {:f :read}))

Promises and delays are generators which ignore updates, yield :pending until realized, then are replaced by whatever generator they contain. Delays are not evaluated until they could produce an op, so you can include them in sequences, phases, etc., and they’ll be evaluated only once prior ops have been consumed.