Re: Potential G2-item cycles under serializable isolation

On 6/4/20 5:29 PM, Peter Geoghegan wrote:
> I'd appreciate it if you could provide this information, so I can be
> confident I didn't get something wrong. I don't really understand how
> Elle detects this G2-Item anomaly, nor how it works in general.
> PostgreSQL doesn't really use 2PL, even to a limited degree (unlike
> Oracle), so a lot of the definitions from the "Generalized Isolation
> Level Definitions"/Adya paper are not particularly intuitive to me.

Hopefully you shouldn't have to think about 2PL, because the generalized
phenomena are defined independently of locking--though I think the paper talks
about 2PL in order to show equivalency to the locking approaches. The gist of
the generalized definitions is about information flow--the anomalies (well, most
of them) correspond to cycles in the dependency graph between transactions. Elle
works (very loosely) by inferring this dependency graph.

I think you've probably read this already, and I know it's a *lot* to throw out
there all at once, but the Elle readme and paper might be helpful here. In
particular, section 2 of the paper ("The Adya Formalism") gives a brief overview
of what these dependencies are, and section 3 gives an intuition for how we can
infer the dependency graph.

https://github.com/jepsen-io/elle

https://github.com/jepsen-io/elle/blob/master/paper/elle.pdf

> That said, I find it easy to understand why the "G2-item: Item
> Anti-dependency Cycles" example from the paper exhibits behavior that
> would be wrong for Postgres -- even in repeatable read mode.
Yeah! My understanding is that this behavior would be incorrect either under
snapshot serializability or repeatable read, at least using the generalized
definitions. It might be OK to do this under repeatable read given the anomaly
interpretation of the ANSI SQL spec; not entirely sure.
> If
> Postgres exhibits this anomaly (in repeatable read more or
> serializable mode), that would be a case of a transaction reading data
> that isn't visible to its original transaction snapshot. The paper
> supposes that this could happen when another transaction (the one that
> updated the sum-of-salaries from the example) committed.

Yes! It's not always this obvious--G2-item encompasses any dependency cycle
between transactions such that at least one dependency involves a transaction
writing state which was not observed by some (ostensibly prior) transaction's
read. We call these "rw dependencies" in the paper, because they involve a read
which must have occurred before a write. Another way to think of G2-item is "A
transaction failed to see something that happened in its logical past".

A special case of G2-item, G-single, is commonly known as read skew. In Elle, we
tag G-single separately, so all the G2-item anomalies reported actually involve
2+ rw dependencies, not just 1+. I haven't seen G-single yet, which is
good--that means Postgres isn't violating SI, just SSI. Or, of course, the test
itself could be broken--maybe the SQL statements themselves are subtly wrong, or
our inference is incorrect.

> If each Jepsen worker has its own connection for the duration of the
> test (which I guess must happen already), and each connection
> specified an informative and unique "application_name", it would be
> possible to see Jepsen's string from the Postgres logs, next to the
> SQL text.

Give Jepsen a138843d a shot!

1553 jepsen process 27 16 LOG:  execute <unnamed>: select (val) from txn0 where
sk = $1

1553 jepsen process 27 17 DETAIL:  parameters: $1 = '9'

Here, "process 27" is the same as the :process field you'll see in transactions.
I'd like to be able to get a mini log of SQL statements embedded in the
operation itself, so it'd be *right there* in the anomaly explanation, but... I
haven't figured out how to scrape those side effects out of the guts of JDBC yet.

--Kyle