jepsen.history — io.jepsen/history 0.1.3

Support functions for working with histories. This provides two things you need for writing efficient checkers:

1. A dedicated Op defrecord which speeds up the most commonly accessed fields and reduces memory footprint.

2. A History datatype which generally works like a vector, but also supports efficient fetching of operations by index, mapping back and forth between invocations and completions, efficient lazy map/filter, fusable concurrent reduce/fold, and a dependency-oriented task executor.

Ops

Create operations with the op function. Unlike most defrecords, we pretty-print these as if they were maps--we print a LOT of them.

(require '[jepsen.history :as h]) (def o (h/op {:process 0, :type :invoke, :f :read, :value [:x nil], :index 0, :time 0})) (pprint o) ; {:process 0, ; :type :invoke, ; :f :read, ; :value [:x nil], ; :index 0, ; :time 0}

We provide a few common functions for interacting with operations:

(invoke? o) ; true (client-op? o) ; true (info? o) ; false

And of course you can use fast field accessors here too:

(.process o) ; 0

Histories

Given a collection of operations, create a history like so:

(def h (h/history [{:process 0, :type :invoke, :f :read} {:process 0, :type :ok, :f :read, :value 5}]))

history automatically lifts maps into Ops if they aren't already, and adds indices (sequential) and times (-1) if you omit them. There are options to control how indices are added; see history for details.

(pprint h) ; [{:process 0, :type :invoke, :f :read, :value nil, :index 0, :time -1} ; {:process 0, :type :ok, :f :read, :value 5, :index 1, :time -1}]

If you need to convert these back to plain-old maps for writing tests, use as-maps.

(h/as-maps h) ; [{:index 0, :time -1, :type :invoke, :process 0, :f :read, :value nil} ; {:index 1, :time -1, :type :ok, :process 0, :f :read, :value 5}]

Histories work almost exactly like vectors (though you can't assoc or conj into them).

(count h) ; 2 (nth h 1) ; {:index 1, :time -1, :type :ok, :process 0, :f :read, :value 5} (map :type h) ; [:invoke :ok]

But they have a few extra powers. You can get the Op with a particular :index regardless of where it is in the collection.

(h/get-index h 0) ; {:index 0, :time -1, :type :invoke, :process 0, :f :read, :value nil}

And you can find the corresponding invocation for a completion, and vice-versa:

(h/invocation h {:index 1, :time -1, :type :ok, :process 0, :f :read, :value 5}) ; {:index 0, :time -1, :type :invoke, :process 0, :f :read, :value nil}

(h/completion h {:index 0, :time -1, :type :invoke, :process 0, :f :read, :value nil}) ; {:index 1, :time -1, :type :ok, :process 0, :f :read, :value 5}

We call histories where the :index fields are 0, 1, 2, ... 'dense', and other histories 'sparse'. With dense histories, get-index is just nth. Sparse histories are common when you're restricting yourself to just a subset of the history, like operations on clients. If you pass sparse indices to (history ops), then ask for an op by index, it'll do a one-time fold over the ops to find their indices, then cache a lookup table to make future lookups fast.

(def h (history [{:index 3, :process 0, :type :invoke, :f :cas, :value [7 8]}])) (h/dense-indices? h) ; false (get-index h 3) ; {:index 3, :time -1, :type :invoke, :process 0, :f :cas, :value [7 8]}

Let's get a slightly more involved history. This one has a concurrent nemesis crashing while process 0 writes 3.

(def h (h/history [{:process 0, :type :invoke, :f :write, :value 3} {:process :nemesis, :type :info, :f :crash} {:process 0, :type :ok, :f :write, :value 3} {:process :nemesis, :type :info, :f :crash}]))

Of course we can filter this to just client operations using regular seq operations...

(filter h/client-op? h) ; [{:process 0, :type :invoke, :f :write, :value 3, :index 0, :time -1} ; {:process 0, :type :ok, :f :write, :value 3, :index 2, :time -1}]

But jepsen.history also exposes a more efficient version:

(h/filter h/client-op? h) ; [{:index 0, :time -1, :type :invoke, :process 0, :f :write, :value 3} ; {:index 2, :time -1, :type :ok, :process 0, :f :write, :value 3}]

There are also shortcuts for common filtering ops: client-ops, invokes, oks, infos, and so on.

(def ch (h/client-ops h)) (type ch) ; jepsen.history.FilteredHistory

Creating a filtered history is O(1), and acts as a lazy view on top of the underlying history. Like clojure.core/filter, it materializes elements as needed. Unlike Clojure's filter, it does not (for most ops) cache results in memory, so we can work with collections bigger than RAM. Instead, each seq/reduce/fold/etc applies the filtering function to the underlying history on-demand.

When you ask for a count, or to fetch operations by index, or to map between invocations and completions, a FilteredHistory computes a small, reduced data structure on the fly, and caches it to make later operations of the same type fast.

(count ch) ; Folds over entire history to count how many match the predicate ; 2 (count ch) ; Cached

; (h/completion ch (first ch)) ; Folds over history to pair up ops, caches {:index 2, :time -1, :type :ok, :process 0, :f :write, :value 3}

; (h/get-index ch 2) ; No fold required; underlying history does get-index {:index 2, :time -1, :type :ok, :process 0, :f :write, :value 3}

Similarly, h/map constructs an O(1) lazy view over another history. These compose just like normal Clojure map/filter, and all share structure with the underlying history.

Folds

All histories support reduce, clojure.core.reducers/fold, Tesser's tesser, and jepsen.history.fold/fold. All four mechanisms are backed by a jepsen.history.fold Folder, which allows concurrent folds to be joined together on-the-fly and executed in fewer passes over the underlying data. Reducers, Tesser, and history folds can also be executed in parallel.

Histories created with map and filter share the folder of their underlying history, which means that two threads analyzing different views of the same underlying history can have their folds joined into a single pass automatically. This should hopefully be invisible to users, other than making things Automatically Faster.

If you filter a history to a small subset of operations, or are comfortable working in-memory, it may be sensible to materialize a history. Just use (vec h) to convert a history a plain-old Clojure vector again.

Tasks

Analyzers often perform several independent reductions over a history, and then compute new values based on those previous reductions. You can of course use future for this, but histories also come with a shared, dependency-aware threadpool executor for executing compute-bound concurrent tasks. All histories derived from the same history share the same executor, which means multiple checkers can launch tasks on it without launching a bazillion threads. For instance, we might need to know if a history includes crashes:

(def first-crash (h/task h find-first-crash [] (->> h (h/filter (comp #{:crash} :f)) first)))

Like futures, deref'ing a task yields its result, or throws.

@first-crash {:index 1, :time -1, :type :info, :process :nemesis, :f :crash, :value nil}

Unlike futures, tasks can express dependencies on other tasks:

(def ops-before-crash (h/task h writes [fc first-crash] (let [i (:index first-crash)] (into [] (take-while #(< (:index %) i)) h))))

This task won't run until first-crash has completed, and receives the result of the first-crash task as its argument.

@ops-before-crash ; [{:index 0, :time -1, :type :invoke, :process 0, :f :write, :value 3}]

See jepsen.history.task for more details.

AbstractHistory clj

add-dense-indices clj

(add-dense-indices ops)

Adds sequential indices to a series of operations. Throws if there are existing indices that wouldn't work with this.

as-maps clj

(as-maps ops)

Turns a collection of Ops back into plain old Clojure maps. Helpful for writing tests.

assert-complete clj

(assert-complete op)

Throws if something is not a completion. Otherwise returns op.

assert-indices clj

(assert-indices ops)

Ensures every op has an :index field. Throws otherwise.

assert-invoke+ clj

(assert-invoke+ op)

Throws if something is not an invocation, or, for non-client operations, an info. Otherwise returns op.

cancel-task clj

(cancel-task this task)

Cancels a task on the this history's task executor. Returns task.

catch-task clj macro

(catch-task history task-name & args)

A helper for launching new catch tasks. Takes a history, a symbol for your catch task's name, optional data, and a binding vector of [arg-name task], followed by a body. Wraps body in a function and submits it as a new catch task to the history's executor.

(catch-task history oh-no [err some-task] (handle err ...))

catch-task-call clj

(catch-task-call this name dep f)

(catch-task-call this name data dep f)

Adds a catch task to this history which handles errors on the given dep. See jepsen.history.task/catch!.

client-op? clj

(client-op? op)

Is this an operation from a client? e.g. does it have an integer process.

client-ops clj

(client-ops history)

Filters a history to just clients.

completion clj

(completion history invocation)

Takes an invocation operation belonging to this history, and returns the operation which invoked it, or nil if none did.

dense-history clj

(dense-history ops)

(dense-history ops {:keys [dense-indices?] :as options})

A dense history has indexes 0, 1, 2, ..., and can encode its pair index in an int array. You can provide a history, or a vector (or any IPersistentVector), or a reducible, in which case the reducible is materialized to a vector. Options are:

:have-indices? If true, these ops already have :index fields. :already-ops? If true, these ops are already Op records. :dense-indices? If true, indices are already dense, and need not be checked.

If given a history without indices, adds them.

dense-history-pair-index clj

(dense-history-pair-index folder)

Given a folder of ops, computes an array mapping indexes back and forth for a dense history of ops. For non-client operations, we map pairs of :info messages back and forth.

dense-indices? clj

(dense-indices? history)

Returns true if indexes in this history are 0, 1, 2, ...

ensure-pair-index clj

(ensure-pair-index history)

Ensures the pair index exists. Helpful when you want to use the pair index during a fold, because loading the pair index itself would require another fold pass. Returns history.

executor clj

(executor this)

Returns the history's task executor. See jepsen.history.task for details. All histories descending from the same history (e.g. via map or filter) share the same task executor.

fail? clj

(fail? op)

Is this op a failure?

fails clj

(fails history)

Filters a history to just :fail ops

filter clj

(filter f history)

Specialized, lazy form of clojure.core/filter which acts on histories and returns histories. Wraps the given history in a new one which only has operations passing (pred op).

A filtered history inherits the task executor of the original.

filter-f clj

(filter-f f-or-fs history)

Filters to a specific :f. Or, given a set, a set of :fs.

filtered-history-indices-fold clj

A fold which computes an int array of all the indexes in a filtered history.

fold clj

(fold history fold)

Executes a fold on this history. See history.fold/fold for details.

get-index clj

(get-index history index)

Returns the operation with the given index in this history, or nil if that operation is not present. For densely indexed histories, this is just like nth. For sparse histories, it may not be the nth op!

has-f? clj

(has-f? f-or-fs)

Constructs a function which takes ops and returns true if the op has the given :f, or, given a set, any of the given :fs.

history clj

(history ops)

(history ops {:keys [dense-indices? have-indices?] :as options})

Just make a history out of something. Figure it out. Options are:

:have-indices? If true, these ops already have :index fields. :already-ops? If true, these ops are already Op records. :dense-indices? If true, indices are already dense.

With :dense-indices?, we'll assume indices are dense and construct a dense history. With have-indices? we'll use existing indices and construct a sparse history. Without either, we examine the first op and guess: if it has no :index, we'll assign sequential ones and construct a dense history. If the first op does have an :index, we'll use the existing indices and construct a sparse history.

Operations with missing :time fields are given :time -1.

index-hash clj

(index-hash this)

Hash by index only. Useful for speeding up large structures of operations.

index= clj

(index= this other)

Equality comparison by index only. Useful for speeding up large structures of operations.

info? clj

(info? op)

Is this op an informational message?

infos clj

(infos history)

Filters a history to just :info ops.

invocation clj

(invocation history completion)

Takes a completion operation and returns the operation which invoked it, or nil if none did.

invoke? clj

(invoke? op)

Is this op an invocation?

invokes clj

(invokes history)

Filters a history to just invocations.

map clj

(map f history)

Specialized, lazy form of clojure.core/map which acts on histories themselves. Wraps the given history in a new one which has its operations transformed by (f op). Applies f on every access to an op. This is faster when you intend to traverse the history only a few times, or when you want to keep memory consumption low.

f is assumed to obey a few laws, but we don't enforce them, in case it turns out to be useful to break these rules later. It should return operations just like its inputs, and with the same :index, so that pairs are preserved. It should also be injective on processes, so that it preserves the concurrency structure of the original. If you violate these rules, get-index, invocation, and completion will likely behave strangely.

A mapped history inherits the same task executor as the original history.

ok? clj

(ok? op)

Is this op OK?

oks clj

(oks history)

Filters a history to just :ok ops

op clj

(op op)

Constructs an operation. With one argument, expects a map, and turns that map into an Op record, which is somewhat faster to work with. If op is already an Op, returns it unchanged.

Ops must have an index. Ops may be missing a :time; if so, we give them time -1.

Op->map clj

(Op->map op)

Turns an Op back into a plain old map

op? clj

(op? op)

Is this op an Op defrecord?

pair-index clj

(pair-index history index)

Given an index, returns the index of that operation's corresponding invocation or completion. -1 means no match.

pair-index-fold clj

A fold which builds a pair index, as an IntMap.

parse-task-args clj

(parse-task-args args)

Helper for task and catch-task which parses varargs and extracts the data, dep names, dep tasks, and body.

possible clj

(possible history)

Filters a history to just :ok or :info ops

pprint-kv clj

(pprint-kv out k v)

(pprint-kv out k v last?)

Helper for pretty-printing op fields.

preprocess-ops clj

(preprocess-ops ops)

(preprocess-ops ops {:keys [have-indices? already-ops?]})

When we prepare a history around some operations, we need to ensure they have indexes, belong to indexed collections, and so on. This takes a collection of ops, and optionally an option map, and returns processed ops. These ops are guaranteed to:

• Have :index fields
• Have :time fields
• Be Op records
• Be in a Clojure Indexed collection

Options are:

:have-indices? If true, these ops already have :index fields. :already-ops? If true, these ops are already Op records.

remove clj

(remove f history)

Inverse of filter

sparse-history clj

(sparse-history ops)

(sparse-history ops options)

Constructs a sparse history backed by the given collection of ops. Options:

:have-indices? If true, these ops already have :index fields. :already-ops? If true, these ops are already Op records.

Adds dense indices if the ops don't already have their own indexes.

sparse-history-by-index-fold clj

A fold which computes the by-index IntMap, taking op indexes to collection indexes.

strip-indices clj

(strip-indices ops)

Strips off indices from a history, returning a sequence of plain maps. Helpful for writing tests.

strip-times clj

(strip-times ops)

Strips off times from a history, returning a sequence of plain maps. Helpful for writing tests.

task clj macro

(task history task-name & args)

A helper macro for launching new tasks. Takes a history, a symbol for your task name, optional data, a binding vector of names to dependency tasks you'd like to depend on, and a single-arity argument vector, and a body. Wraps body in a function and submits it to the task executor.

(task history find-anomalies [] ... go do stuff)

(task history furthermore [as find-anomalies] ... do stuff with as)

(task history data-task {:custom :data} [as anomalies, f furthermore] ... do stuff with as and f)

task-call clj

(task-call this name f)

(task-call this name deps f)

(task-call this name data deps f)

Launches a Task on this history's task executor. Use this to perform parallel, compute-bound processing of a history in a dependency tree--for instance, to perform multiple folds over a history at the same time. See jepsen.history.task/submit! for details.

tesser clj

(tesser history tesser-fold)

Executes a Tesser fold on this history. See history.fold/tesser for details.