Potential G2-item cycles under serializable isolation

Hello everyone!

First off, I'm sorry for *gestures vaguely* all of this. Second, I think I may 
have found a serializability violation in Postgres 12.3, involving 
anti-dependency cycles around row insertion.

For background, my name is Kyle Kingsbury, and I test distributed database 
safety properties (https://jepsen.io). I started looking at Stolon + PostgreSQL 
this week, encountered this behavior, and managed to narrow it down to a single 
Postgres node without Stolon at all. Normally I test with a variety of faults 
(network partitions, crashes, etc.), but this behavior occurs in healthy 
processes without any faults.

This test uses the Jepsen testing library (https://github.com/jepsen-io/jepsen) 
and the Elle isolation checker (https://github.com/jepsen-io/elle). If you're 
wondering "why would you ever do transactions like this", the Elle paper might 
provide some helpful background: https://arxiv.org/abs/2003.10554. We install 
Postgres 12.3-1.pgdg100+1 on a Debian 10 node, using the official Postgres 
repository at http://apt.postgresql.org/pub/repos/apt/. Each client uses its own 
JDBC connection, on a single thread, in a single JVM process. We use the JDBC 
postgres driver (org.postgresql/postgresql 42.2.12). The JDK is 1.8.0_40-b25.

Logically, the test performs randomly generated transactions over a set of lists 
identified by integer keys. Each operation is either a read, which returns the 
current value of the list for a given key, or an append, which adds a unique 
element to the end of the list for a given key. In Postgres, we store these 
objects in tables like so:

   create table if not exists txn0 (id int not null primary key,
                                    sk int not null,
                                    val text)

id is the key, and text stores comma-separated elements. sk is a secondary key, 
which is unused here. We create three tables like this (txn0, txn1, txn2). 
Records are striped across tables by hashing their key.

We set the session transaction isolation level immediately after opening every 
connection:

   SET SESSION CHARACTERISTICS AS TRANSACTION ISOLATION LEVEL SERIALIZABLE

... and request SERIALIZABLE for each JDBC transaction as well.

Our reads are of the form:

   select (val) from txn0 where id = $1

And our writes are of the form:

   insert into txn1 as t (id, sk, val) values ($1, $2, $3) on conflict (id) do 
update set val = CONCAT(t.val, ',', $4) where t.id = $5

where $1 and $5 are the key, and $2, $3, and $4 are the element we'd like to 
append to the list.

You can try these transactions for yourself using Jepsen f47eb25. You'll need a 
Jepsen environment; see
https://github.com/jepsen-io/jepsen#setting-up-a-jepsen-environment for details.

   cd jepsen/stolon

   lein run test-all -w append --nemesis none --max-writes-per-key 8 --node n1 
--just-postgres --concurrency 50 -r 1000

Which typically produces, after about a minute, anomalies like the following:

G2-item #1
Let:
   T1 = {:type :ok, :f :txn, :value [[:r 7 [1]] [:append 12 1]], :time 95024280, 
:process 5, :index 50}
   T2 = {:type :ok, :f :txn, :value [[:append 7 2] [:r 14 nil] [:append 14 1] 
[:r 12 nil]], :time 98700211, :process 6, :index 70}

Then:
   - T1 < T2, because T1 did not observe T2's append of 2 to 7.
   - However, T2 < T1, because T2 observed the initial (nil) state of 12, which 
T1 created by appending 1: a contradiction!

A dependency graph of this anomaly is attached to this email: lines marked `rw` 
indicate read-write anti-dependencies between specific operations in each 
transaction. Because there are multiple rw edges in this graph, it suggests the 
presence of G2-item. It is also possible, of course, that worse anomalies 
happened (e.g. aborted read) which caused us to incorrectly infer this causal 
graph, but I suspect this is not the case.

You can find a full copy of this particular test run, including a history of 
every transaction, Postgres logs, and a pcap file containing all client-server 
interactions, at 
http://jepsen.io.s3.amazonaws.com/analyses/postgresql-12.3/20200531T215019.000-0400.zip

If you'd like to look at the test code, see 
https://github.com/jepsen-io/jepsen/tree/f47eb25ab32529a7b66f1dfdd3b5ef2fc84ed778/stolon/src/jepsen. 
Specifically, setup code is here:


https://github.com/jepsen-io/jepsen/blob/f47eb25ab32529a7b66f1dfdd3b5ef2fc84ed778/stolon/src/jepsen/stolon/db.clj#L200-L233

... and the workload responsible for constructing and submitting transactions is 
here:


https://github.com/jepsen-io/jepsen/blob/f47eb25ab32529a7b66f1dfdd3b5ef2fc84ed778/stolon/src/jepsen/stolon/append.clj#L31-L107

These anomalies appear limited to G2-item: I haven't seen G-single (read skew), 
cyclic information flow, aborted reads, dirty writes, etc. It also looks as if 
every anomaly involves a *nil* read, which suggests (and I know the bug report 
guidelines say not to speculate, but experience suggests this might be helpful) 
that there is something special about row insertion. In TiDB, for instance, we 
found that G2-item anomalies with `select ... for update` was linked to the fact 
that TiDB's lock manager couldn't lock keys which hadn't been created yet 
(https://jepsen.io/analyses/tidb-2.1.7#select-for-update). I don't know anything 
about Postgres' internals, but I hope this is of some use!

Is this... known behavior? Unexpected? Are there configuration flags or client 
settings I should double-check? I know this is all a bit much, so I'm happy to 
answer any questions you might have. :-)

Sincerely,

--Kyle