jepsen.independent

Some tests are expensive to check–for instance, linearizability–which requires we verify only short histories. But if histories are short, we may not be able to sample often or long enough to reveal concurrency errors. This namespace supports splitting a test into independent components–for example taking a test of a single register and lifting it to a map of keys to registers.

checker

(checker checker)

Takes a checker that operates on :values like v, and lifts it to a checker that operates on histories with values of [k v] tuples–like those generated by sequential-generator.

We partition the history into (count (distinct keys)) subhistories. The subhistory for key k contains every element from the original history except those whose values are MapEntries with a different key. This means that every history sees, for example, un-keyed nemesis operations or informational logging.

The checker we build is valid iff the given checker is valid for all subhistories. Under the :results key we store a map of keys to the results from the underlying checker on the subhistory for that key. :failures is the subset of that :results map which were not valid.

concurrent-generator

(concurrent-generator n keys fgen)

Takes a positive integer n, a sequence of keys (k1 k2 …) and a function (fgen k) which, when called with a key, yields a generator. Returns a generator which splits up threads into groups of n threads per key, and has each group work on a key for some time. Once a key’s generator is exhausted, it obtains a new key, constructs a new generator from key, and moves on.

Threads working with this generator are assumed to have contiguous IDs, starting at 0. Violating this assumption results in uneven allocation of threads to groups.

Excludes the nemesis by design; only worker threads run here.

Updates are routed to the generator which that thread is currently executing.

dir

What directory should we write independent results to?

group-threads

(group-threads n ctx)

Given a group size and pure generator context, returns a collection of collections of threads, each per group.

history-keys

(history-keys history)

Takes a history and returns the set of keys in it.

make-group->threads

(make-group->threads n ctx)

Given a group size and pure generator context, returns a vector where each element is the set of threads in the group corresponding to that index.

make-thread->group

(make-thread->group n ctx)

Given a group size and pure generator context, returns a map of threads to groups.

sequential-generator

(sequential-generator keys fgen)

Takes a sequence of keys k1 k2 …, and a function (fgen k) which, when called with a key, yields a generator. Returns a generator which starts with the first key k1 and constructs a generator gen1 via (fgen k1), returns elements from gen1 until it is exhausted, then moves to k2.

The generator wraps each :value in the operations it generates in a k1 value tuple.

fgen must be pure.

subhistories

(subhistories ks history)

Takes a collection of keys and a history. Runs a concurrent fold over the history, breaking it into a map of keys to Histories for those keys. Unwraps tuples. Materializes everything in memory; later if we want to do ginormous histories we should spill to disk.

tuple

(tuple k v)

Constructs a kv tuple

tuple-gen

(tuple-gen k gen)

Wraps a generator so that it returns :value k v tuples for :invoke ops.

tuple?

(tuple? value)

Is the given value generated by an independent generator?