jepsen.tests.cycle.append — jepsen 0.1.14

Detects cycles in histories where operations are transactions over named lists lists, and operations are either appends or reads. Used with jepsen.tests.cycle.

append-index clj

(append-index sorted-values)

Takes a map of keys to observed values (e.g. from sorted-values), and builds a bidirectional index: a map of keys to indexes on those keys, where each index is a map relating appended values on that key to the order in which they were effectively appended by the database.

{:x {:indices {v0 0, v1 1, v2 2} :values [v0 v1 v2]}}

We merge all observed orders on a key using merge-orders.

checker clj

(checker)

(checker opts)

Full checker for append and read histories. Options are:

:additional-graphs A collection of graph analyzers (e.g. realtime) which should be merged with our own dependencies. :anomalies A collection of anomalies which should be reported, if found.

Supported anomalies are:

:G0 Write Cycle. A cycle comprised purely of write-write deps. :G1a Aborted Read. A transaction observes data from a failed txn. :G1b Intermediate Read. A transaction observes a value from the middle of another transaction. :G1c Circular Information Flow. A cycle comprised of write-write and write-read edges. :G1 G1a, G1b, and G1c. :G2 A dependency cycle with at least one anti-dependency edge.

:G2 implies :G1c, and :G1c implies :G0, because if we construct the graph for G2, it'll include all the edges for G1c, and so on. See http://pmg.csail.mit.edu/papers/icde00.pdf for context.

Note that while we can find instances of G0, G1c and G2, we can't (yet) categorize them automatically. These anomalies are grouped under :G0+G1c+G2 in checker results.

cycle-explainer clj

cycle-explanations clj

(cycle-explanations pair-explainer cycle-fn sccs)

Takes a pair explainer, a function taking an scc and possible yielding a cycle, and a series of strongly connected components. Produces a seq (nil if empty) of explanations of cycles.

cycles clj

(cycles opts test history checker-opts)

Performs dependency graph analysis and returns a sequence of anomalies.

Options:

:additional-graphs A collection of graph analyzers (e.g. realtime) which should be merged with our own dependencies. :anomalies A collection of anomalies which should be reported, if found.

Supported anomalies are :G0, :G1c, :G-single, and :G2. G2 implies G-single and G1c, and G1c implies G0.

duplicates clj

(duplicates history)

Given a history, finds operations which have duplicate copies of the same appended element. Since we only append values once, we should never see them more than that--and if we do, it could mess up our whole "total order" thing!

expand-anomalies clj

(expand-anomalies as)

Takes a collection of anomalies, and returns the fully expanded version of those anomalies as a set: e.g. [:G1] -> #{:G0 :G1a :G1b :G1c}

g-single-cases clj

(g-single-cases graph pair-explainer sccs)

Given a graph, an explainer, and a collection of strongly connected components, searches for instances of G-single anomalies within them. Returns nil if none are present.

g0-cases clj

(g0-cases graph pair-explainer sccs)

Given a graph, a pair explainer, and a collection of strongly connected components, searches for instances of G0 anomalies within it. Returns nil if none are present.

g1a-cases clj

(g1a-cases history)

G1a, or aborted read, is an anomaly where a transaction reads data from an aborted transaction. For us, an aborted transaction is one that we know failed. Info transactions may abort, but if they do, the only way for us to TELL they aborted is by observing their writes, and if we observe their writes, we can't conclude they aborted, sooooo...

This function takes a history (which should include :fail events!), and produces a sequence of error objects, each representing an operation which read state written by a failed transaction.

g1b-cases clj

(g1b-cases history)

G1b, or intermediate read, is an anomaly where a transaction T2 reads a state for key k that was written by another transaction, T1, that was not T1's final update to k.

This function takes a history (which should include :fail events!), and produces a sequence of error objects, each representing a read of an intermediate state.

g1c-cases clj

(g1c-cases graph pair-explainer sccs)

Given a graph, an explainer, and a collection of strongly connected components, searches for instances of G1c anomalies within them. Returns nil if none are present.

g1c-graph clj

(g1c-graph history)

Per Adya, Liskov, & O'Neil, phenomenon G1C encompasses any cycle made up of direct dependency edges (but does not include anti-dependencies).

g2-cases clj

(g2-cases graph pair-explainer sccs)

Given a graph, an explainer, and a collection of strongly connected components, searches for instances of G2 anomalies within them. Returns nil if none are present.

graph clj

(graph history)

Some parts of a transaction's dependency graph--for instance, anti-dependency cycles--involve the version order of states for a key. Given two transactions: [[:w :x 1]] and [[:w :x 2]], we can't tell whether T1 or T2 happened first. This makes it hard to identify read-write and write-write edges, because we can't tell what particular transaction should have overwritten the state observed by a previous transaction.

However, if we constrain ourselves to transactions whose only mutation is to append a value to a key's current state...

{:f :txn, :value [[:r :x [1 2]] [:append :x 3] [:r :x [1 2 3]]]} ...

... we can derive the version order for (almost) any pair of operations on the same key because the order of appends is encoded in every read: if we observe [:r :x [3 1 2]], we know the previous states must have been [3] [3 1] [3 1 2].

That is, assuming appends actually work correctly. If the database loses appends or reorders them, it's likely (but not necessarily the case), that we'll observe states like:

[1 2 3] [1 3 4] ; 2 has been lost!

We can verify these in a single O(appends^2) pass by sorting all observed states for a key by size, and verifying that each is a prefix of the next. Assuming we do observe a total order, we can use the longest read value for each key as an order over appends for that key. This order is almost complete in that appends which are never read can't be related, but so long as the DB lets us see most of our appends at least once, this should work.

So then, our strategy here is to compute those orders for each key, then use them to relate successive [w w], [r w], and [w r] pair on that key. [w,w] pairs are a direct write dependency, [w,r] pairs are a direct read-dependency, and [r,w] pairs are direct anti-dependencies.

For more context, see Adya, Liskov, and O'Neil's 'Generalized Isolation Level Definitions', page 8.

incompatible-orders clj

(incompatible-orders sorted-values)

Takes a map of keys to sorted observed values and verifies that for each key the values read are consistent with a total order of appends. For instance, these values are consistent:

{:x [[1] [1 2 3]]}

But these two are not:

{:x [[1 2] [1 3 2]]}

... because the first is not a prefix of the second. Returns a sequence of anomaly maps, nil if none are present.

merge-orders clj

(merge-orders as bs)

(merge-orders merged as bs)

Takes two potentially incompatible read orders (sequences of elements), and computes a total order which is consistent with both of them: where there are conflicts, we drop those elements.

First, we remove duplicates; an order shouldn't have them at all. Yes, this means we fail to compute some dependencies.

In general, the differences between orders fall into some cases:

1. One empty

   _ 1 2 3 4 5

   We simply pick the non-empty order.

2. Same first element

   2 x y 2 z

   Our order is [2] followed by the merged result of [x y] and [z].

3. Different first elements followed by a common element

   3 y 2 3

We drop the smaller element and recur with [3 y] [3]. This isn't... exactly symmetric; we prefer longer and higher elements for tail-end conflicts, but I think that's still a justifiable choice. After all, we DID read both values, and it's sensible to compute a dependency based on any read. Might as well pick longer ones.

Later, we should change the whole structure of append indexes to admit multiple prior txns rather than just one, and get rid of this.

mop-deps clj

(mop-deps append-index write-index read-index op [f :as mop])

A set of dependencies for a mop in an op.

op-deps clj

(op-deps append-index write-index read-index op)

All dependencies for an op.

op-mops clj

(op-mops history)

A lazy sequence of all [op mop] pairs from a history.

prefix? clj

(prefix? a b)

Given two sequences, returns true iff A is a prefix of B.

preprocess clj

(preprocess history)

Before we do any graph computation, we need to preprocess the history, making sure it's well-formed. We return a map of:

{:history The history restricted to :ok and :info ops :append-index An append index :write-index A write index :read-index A read index}

previously-appended-element clj

(previously-appended-element append-index write-index op [f k v])

Given an append mop, finds the element that was appended immediately prior to this append. Returns ::init if this was the first append.

read-index clj

(read-index history)

Takes a history restricted to oks and infos, and constructs a map of keys to append values to the operations which observed the state generated by the append of k. The special append value ::init generates the initial (nil) state.

Note that reads of nil by :info ops don't result in an entry in this index, because those nils denote the default read value, NOT that we actually observed nil.

rw-graph clj

(rw-graph history)

Analyzes read-write anti-dependencies.

rw-mop-deps clj

(rw-mop-deps append-index write-index read-index op [f k v :as mop])

The set of (other) operations which read the value just before this write mop.

sorted-values clj

(sorted-values history)

Takes a history where operation values are transactions, and every micro-op in a transaction is an append or a read. Computes a map of keys to all distinct observed values for that key, ordered by length.

As a special case, if we have a key which only has a single append, we don't need a read: we can infer the sorted values it took on were simply [], [x].

values-from-single-appends clj

(values-from-single-appends history)

As a special case of sorted-values, if we have a key which only has a single append, we don't need a read: we can infer the sorted values it took on were simply [], [x].

verify-mop-types clj

(verify-mop-types history)

Takes a history where operation values are transactions. Verifies that the history contains only reads [:r k v] and appends [:append k v]. Returns nil if the history conforms, or throws an error object otherwise.

verify-total-order clj

(verify-total-order sorted-values)

Takes a map of keys to observed values (e.g. from sorted-values, and verifies that for each key, the values read are consistent with a total order of appends. For instance, these values are consistent:

{:x [[1] [1 2 3]]}

But these two are not:

{:x [[1 2] [1 3 2]]}

... because the first is not a prefix of the second.

Returns nil if the history is OK, or throws otherwise.

verify-unique-appends clj

(verify-unique-appends history)

Takes a history of txns made up of appends and reads, and checks to make sure that every invoke appending a value to a key chose a unique value.

wr-graph clj

(wr-graph history)

Analyzes write-read dependencies.

wr-mop-dep clj

(wr-mop-dep write-index op [f k v])

What (other) operation wrote the value just before this read mop?

write-index clj

(write-index history)

Takes a history restricted to oks and infos, and constructs a map of keys to append values to the operations that appended those values.

ww-graph clj

(ww-graph history)

Analyzes write-write dependencies.

ww-mop-dep clj

(ww-mop-dep append-index write-index op [f k v :as mop])

What (other) operation wrote the value just before this write mop?