jepsen.tests.cycle — jepsen 0.1.14

Tests based on detecting cycles between operations in a history.

First, we define a bunch of ways you can compute a dependency graph over a history. Our graphs use completions (e.g. ok, info) for the canonical representation of an operation. For instance:

realtime-graph relates a->b if operation b begins after operation a completes successfully.

process-graph relates a->b if a and b are performed by the same process, and that process executes a before b.

monotonic-key-graph assumes op :values are maps of keys to observed values, like {:x 1 :y 2}. It relates a->b if b observed a higher value of some key than a did. For instance, {:x 1 :y 2} -> {:x 2 :y 2}, because :x is higher in the second op.

wr-graph assumes op :values are transactions like [[f k v] ...], and relates operations based on transactional reads and writes: a->b if b observes a value that a wrote. This order requires that keys only have a given value written once.

You can also combine graphs using combine, which takes the union of multiple graphs. (combine realtime monotonic-key), for instance, verifies that not only must the values of each key monotonically increase, but that those increases must be observed in real time: stale reads are not allowed.

Given a function which takes a history and produces a dependency graph, the checker runs that function, identifies strongly-connected components in the resulting graph, and decides whether the history is valid based on whether the graph has any strongly connected components--e.g. cycles.

->bset clj

(->bset coll)

(->bset coll s)

Turns any collection into a Bifurcan Set.

check clj

(check analyze-fn history)

Meat of the checker. Takes an analysis function and a history; returns a map of:

{:graph     The computed graph
 :explainer The explainer for that graph
 :cycles    A list of cycles we found
 :sccs      A set of strongly connected components}

checker clj

(checker analyze-fn)

Takes a function which takes a history and returns a [graph, explainer] pair, and returns a checker which uses those graphs to identify cyclic dependencies.

combine clj

(combine & analyzers)

Helpful in composing an analysis function for a checker out of multiple other analysis fns. For example, you might want a checker that looks for per-key monotonicity and real-time precedence---you could use:

(checker (combine monotonic-keys real-time))

cycle-explainer clj

This explainer just provides the step-by-step explanation of the relationships between pairs of operations.

CycleExplainer clj protocol

explain-cycle clj

(explain-cycle _ pair-explainer cycle)

Takes a cycle and constructs a data structure describing it.

render-cycle-explanation clj

(render-cycle-explanation _ pair-explainer explanation)

Takes an explanation of a cycle and renders it to a string.

DataExplainer clj protocol

explain-pair-data clj

(explain-pair-data _ a b)

Given a pair of operations a and b, explains why b depends on a, in the form of a data structure. Returns nil if b does not depend on a.

render-explanation clj

(render-explanation _ explanation a-name b-name)

Given an explanation from explain-pair-data, and short names for a and b, renders a string explaining why a depends on b.

digraph-union clj

(digraph-union)

(digraph-union a)

(digraph-union a b)

(digraph-union a b & more)

Takes the union of n graphs, merging edges with union.

directed-graph clj

(directed-graph)

Constructs a fresh directed graph.

edge clj

(edge g a b)

Returns the edge between two vertices.

edges clj

(edges g)

A lazy seq of all edges.

explain-binding clj

(explain-binding bindings)

Takes a seq of [name op] pairs, and constructs a string naming each op.

explain-cycle-ops clj

(explain-cycle-ops pair-explainer binding steps)

Takes an pair explainer, a binding, and a sequence of steps: each an explanation data structure of one pair. Produces a string explaining why they follow in that order.

explain-cycle-pair-data clj

(explain-cycle-pair-data pair-explainer [a b])

Takes a pair explainer and a pair of ops, and constructs a data structure explaining why a precedes b.

explain-pair clj

(explain-pair explainer a-name a b-name b)

Given a pair of operations, and short names for them, explain why b depends on a, as a string. nil indicates that b does not depend on a.

explain-scc clj

(explain-scc graph cycle-explainer pair-explainer scc)

Takes a graph, a cycle explainer, a pair explainer, and a strongly connected component (a collection of ops) in that graph. Using those graphs, constructs a string explaining the cycle.

ext-index clj

(ext-index ext-fn history)

Given a function that takes a txn and returns a map of external keys to written values for that txn, and a history, computes a map like {k {v [op1, op2, ...]}}, where k is a key, v is a particular value for that key, and op1, op2, ... are operations which externally wrote k=v.

Right now we index only :ok ops. Later we should do :infos too, but we need to think carefully about how to interpret the meaning of their nil reads.

find-cycle clj

(find-cycle graph scc)

Given a graph and a strongly connected component within it, finds a short cycle in that component.

find-cycle-starting-with clj

(find-cycle-starting-with initial-graph remaining-graph scc)

Some anomalies consist of a cycle with exactly, or at least, one edge of a particular type. This fuction works like find-cycle, but allows you to pass two graphs: an initial graph, which is used for the first step, and a remaining graph, which is used for later steps.

forked clj

(forked graph)

Bifurcan's analogue to (persistent! g)

grow-paths clj

(grow-paths g paths)

Given a graph g, and a set of paths (each a sequence like [a b c]), constructs a new set of paths by taking the tip c of each path p, and expanding p to all vertices c can reach: [a b c] => #{[a b c d] [a b c e]}.

in clj

(in g v)

Inbound edges to a graph.

keep-edge-values clj

(keep-edge-values f g)

Transforms a graph by applying a function (f edge-value) to each edge in the graph. Where the function returns nil, removes that edge altogether.

linear clj

(linear graph)

Bifurcan's analogue to (transient g)

link clj

(link graph node succ)

(link graph node succ relationship)

Helper for linking Bifurcan graphs. Optionally takes a relationship, which is added to the value set of the edge.

link-all-to clj

(link-all-to g xs y)

(link-all-to g xs y relationship)

Given a graph g, links all xs to y.

link-all-to-all clj

(link-all-to-all g xs ys)

(link-all-to-all g xs ys rel)

Given a graph g, links all xs to all ys.

link-to-all clj

(link-to-all g x ys)

(link-to-all g x ys rel)

Given a graph g, links x to all ys.

loop? clj

(loop? v)

Does the given vector begin and end with identical elements, and is longer than 1?

map->bdigraph clj

(map->bdigraph m)

Turns a sequence of [node, successors] pairs (e.g. a map) into a bifurcan directed graph

monotonic-key-graph clj

(monotonic-key-graph history)

Analyzes ops where the :value of each op is a map of keys to values. Assumes keys are monotonically increasing, and derives relationships between ops based on those values.

monotonic-key-order clj

(monotonic-key-order k history)

Given a key, and a history where ops are maps of keys to values, constructs a partial order graph over ops reading successive values of key k.

path-shells clj

(path-shells g starting-paths)

Given a graph, and a starting collection of paths, constructs shells outwards from those paths: collections of longer and longer paths.

process-graph clj

(process-graph history)

Analyses histories and relates operations performed sequentially by each process, such that every operation a process performs is ordered (but operations across different processes are not related).

process-order clj

(process-order history process)

Given a history and a process ID, constructs a partial order graph based on all operations that process performed.

project-relationship clj

(project-relationship g rel)

Filters a graph to just those edges with the given relationship.

prune-alternate-paths clj

(prune-alternate-paths paths)

If we have two paths [a b d] and [a c d], we don't need both of them, because both get us from a to d. We collapse a set of paths by filtering out duplicates. Since all paths start at the same place, we can do this efficiently by selecting one from the set of all paths that end in the same place.

prune-longer-paths clj

(prune-longer-paths paths)

We can also completely remove paths whose tips are in a prefix of any other path, because these paths are simply longer versions of paths we've already explored.

realtime-graph clj

(realtime-graph history)

Given a history, produces an singleton order graph {:realtime graph} which encodes the real-time dependencies of transactions: a < b if a ends before b begins.

In general, txn a precedes EVERY txn which begins later in the history, but that's n^2 territory, and for purposes of cycle detection, we only need a transitive reduction of that graph. We compute edges from txn a to subsequent invocations until a new operation b completes.

remove-relationship clj

(remove-relationship g rel)

Filters a graph, removing the given relationship from it.

renumber-graph clj

(renumber-graph g)

Takes a Graph and rewrites each vertex to a unique integer, returning the rewritten Graph, and a vector of the original vertexes for reconstruction.

strongly-connected-components clj

(strongly-connected-components g)

Finds the strongly connected components of a graph, greater than 1 element.

tarjan clj

(tarjan graph)

Returns the strongly connected components of a graph specified by its nodes (ints) and a successor function (succs node) from node to nodes. A iterative verison of Tarjan's Strongly Connected Components.

ToClj clj protocol

->clj clj

(->clj x)

union-edge clj

A binary operator performing set union on the values of edges.

unlink clj

(unlink g a b)

Heper for unlinking Bifurcan graphs.

wr-graph clj

(wr-graph history)

Given a history where ops are txns (e.g. [[:r :x 2] [:w :y 3]]), constructs an order over txns based on the external writes and reads of key k: any txn that reads value v must come after the txn that wrote v.

write-cycles! clj

(write-cycles! test opts cycles)

Writes cycles to a file. Opts:

:subdirectory What subdirectory to write to :filename What to call the file