PL-2L(monotonic-view) G-monotonic: experiment with adding the anomaly

[nurturenature]

Hi,

I'm working on using Elle as a checker for causal consistency.
Yes, the CRDTs are finally coming in the form of local first sync layers. :)

While testing with :consistency-models [:consistent-view], it seemed like lots of anomalies were not being caught.
Looking at the graphs and cycle-anomalies, consistent-view was:

• missing the process-order graph
• reporting anomalies at higher consistency levels, e.g. strong-session-snapshot-isolation

Looking at how elle.txn used -process, reportable-anomalies, etc lead to looking at Adya's Weak Consistency to see where process order and the expected anomalies were introduced. And in 4.2.2 PL-2L:

G-monotonic: Monotonic Reads. A history H exhibits phenomenon G-monotonic for transaction Ti if there exists a cycle in USG(H, Ti ) containing exactly one anti-dependency edge from a read node ri (xj ) (or ri (P: xj )) to some transaction node Tk (and any number of order or dependency edges).

Which Elle expresses as:

:G-single {:rels        (rels/union ww wwp wr wrp)
           :single-rels (rels/union rw rwp)
           :type        :G-single}

And if we test using G-single-process as additional :anomalies [:G-single-process]:

(def opts
  {:consistency-models [:consistent-view] ; Adya formalism for causal consistency
   :sequential-keys? true                 ; infer version order from elle/process-graph
   :wfr-keys? true                        ; rw/wfr-version-graph within txns
   })

(def mono-writes-anomaly
  (->> [{:process 0 :value [[:w :x 0]]   :type :ok :f :txn}
        {:process 0 :value [[:w :y 0]]   :type :ok :f :txn}
        {:process 1 :value [[:r :y 0]]   :type :ok :f :txn}
        {:process 1 :value [[:r :x nil]] :type :ok :f :txn}]
       h/history))

(rw/check opts mono-writes-anomaly)
{:valid? true}

(rw/check (assoc opts :anomalies [:G-single-process]) mono-writes-anomaly)
{:valid? false,
 :anomaly-types [:G-single-item-process],
 :anomalies {:G-single-item-process [{:cycle [{:index 3, :time -1, :type :ok, :process 1, :f :txn, :value [[:r :x nil]]}
                                              {:index 0, :time -1, :type :ok, :process 0, :f :txn, :value [[:w :x 0]]}
                                              {:index 1, :time -1, :type :ok, :process 0, :f :txn, :value [[:w :y 0]]}
                                              {:index 2, :time -1, :type :ok, :process 1, :f :txn, :value [[:r :y 0]]}
                                              {:index 3, :time -1, :type :ok, :process 1, :f :txn, :value [[:r :x nil]]}],
                                      :steps [{:key :x, :value nil, :value' 0, :type :rw, :a-mop-index 0, :b-mop-index 0}
                                              {:type :process, :process 0}
                                              {:type :wr, :key :y, :value 0, :a-mop-index 0, :b-mop-index 0}
                                              {:type :process, :process 1}], :type :G-single-item-process}]},
 :not #{:strong-session-snapshot-isolation},
 :also-not #{:strong-serializable :strong-session-serializable :strong-snapshot-isolation}}

🎉
It also catches more writes-follow-reads in other tests too.

But if G-single-process is added to the direct-proscribed-anomalies:

:monotonic-view [:G1 :G-monotonic   ; Adya
                 :G-single-process]

We no longer find the G-single-item-process, but only the stronger consistency strong-session-snapshot-isolation-cycle-exists:

(et/reportable-anomaly-types opts)
#{:G-cursor :G-monotonic :G-single :G-single-item :G-single-item-process :G-single-process :G0 :G1 :G1a :G1b :G1c :PL-1-cycle-exists :PL-2-cycle-exists :cycle-search-timeout :cyclic-versions :dirty-update :duplicate-elements :empty-transaction-graph :future-read :incompatible-order :lost-update}

(rw/check opts mono-writes-anomaly)
{:valid? true}

(:anomalies (et/cycles! opts (partial rw/graph opts) mono-writes-anomaly))
{:strong-session-snapshot-isolation-cycle-exists [{:type :strong-session-snapshot-isolation-cycle-exists,
                                                   :not :strong-session-snapshot-isolation,
                                                   :subgraph [:extension [:union :ww :wwp :wr :wrp :process] [:union :rw :rwp]],
                                                   :scc-size 3,
                                                   :scc #{0 1 2}}]}

I've looked at opts :anomalies handling in prohibited-anomaly-types, cycle identification in cycle-explainer, and a few other places and I can't find anything anomalous. :)

I do think that:

• monotonic-view's G-monotonic needs to be expressed, it's currently a no-op
• causal, consistent-view, has to end up with process order
• G-monotonic, as G-single-process, would:
  - more correctly identify what consistency level you are and :not :also-not
  - catch some of the tests labeled not possible to catch at the given consistency level as they are actually writes-follows-reads and/or monotonic-writes anomalies.

Was hoping you would be able to confirm that this is generally a good idea, desired?
And if so, any ideas on where to look to understand and change the behavior?

Thanks!

(P.S. This is my first time really trying to understand DAGs, cycles, etc and Elle is a wonderful teaching tool. I keep thinking, Wow! It's as if Elle was designed for this, then remembering it most certainly was. 😆

[aphyr]

I'm afraid I haven't worked at all on causal or PL-2L yet--nobody's actually asked me to check those properties yet. There's a few definitions in consistency-models.clj, but that's just as a "this can catch occasional anomalies and "having these partial definitions might be useful later if someone takes on these models in more detail" rather than "Elle knows about all forms of anomalies in every consistency model". It'd certainly be nice if it did, haha.

G-single and G-monotonic aren't interchangeable. Elle's G-single is taken directly from Adya's G-single definition, and is defined over DSGs. G-monotonic is defined over USG(H, T_i), which doesn't (presently) exist in Elle. They're not the same graph, which is probably why you're seeing Weird Results here. ;-)

G-single-process is a boundary anomaly for strong-session SI. Pulling it out into a weaker isolation level probably broke the BFS phase of the anomaly search. I imagine something like "the cycle existence pass says there was a strong-session-SI cycle, but also found no cycles that would arise in weaker isolation levels. From this we know that any search for boundary anomalies at levels lower than strong-session-SI are redundant, so we won't bother searching for G-single-process at all".

• monotonic-view's G-monotonic needs to be expressed, it's currently a no-op

Maybe? I don't personally have a need for it yet, but if it's important for your use case you could add it. The naive definition is O(n^2), so you'll want to do Something Clever (TM)--perhaps it could be unified with the internal passes in list-append and rw-register. I could be convinced to take a PR for this, but it needs to be relatively simple and not impose, say, huge performance/memory penalties on the rest of the system. Either that or we put it behind a flag.

causal, consistent-view, has to end up with process order

Maybe. I'm not sure about that one. Would need to look carefully at the formalism's event order and prove it's equivalent to process order plus whatever additional constraints--they're not the same.

G-monotonic, as G-single-process, would more correctly identify what consistency level you are...

I'm afraid not--they're not the same anomaly. I'm not sure exactly all the ways this would cause Elle to be wrong, but it would definitely be wrong in some ways. ;-)

[nurturenature]

Thanks for such an informative response!
Now I can see how dropping an arbitrary anomaly into a model would cause such weirdness, and not be what is really wanted.

I will try creating a USG, use a PL-2L-cycle-exists, etc, and report back.

The naive definition is O(n^2), so you'll want to do Something Clever (TM)
it needs to be relatively simple and not impose, say, huge performance/memory penalties

Thinking comparable to the other cycle-exists in performance and implementation.
If it can't be optimized and/or unified with the existing work being done, it's probably not a good candidate for inclusion.