Horton

Re: Potential G2-item cycles under serializable isolation

Peter Geoghegan <pg@bowt.ie>

View thread View on postgr.es
From: Peter Geoghegan <pg@bowt.ie>
To: Kyle Kingsbury <aphyr@jepsen.io>
Cc: PostgreSQL mailing lists <pgsql-bugs@lists.postgresql.org>
Date: 2020-06-06T22:24:35Z
Lists: pgsql-bugs 
On Sat, Jun 6, 2020 at 5:49 AM Kyle Kingsbury <aphyr@jepsen.io> wrote:
> Here's a quick runthrough of G2-item #0:
>
> Let:
>    T1 = {:type :ok, :f :txn, :value [[:append 1468 3] [:r 1469 nil] [:append
> 1439 2]], :time 22408795244, :process 49, :index 10392}
>    T2 = {:type :ok, :f :txn, :value [[:append 1469 1] [:append 1456 2] [:r 1468
> nil]], :time 22565885165, :process 45, :index 10464}
>
> Then:
>    - T1 < T2, because T1 observed the initial (nil) state of 1469, which T2
> created by appending 1.
>    - However, T2 < T1, because T2 observed the initial (nil) state of 1468,
> which T1 created by appending 3: a contradiction!
>
> Classic G2: two rw-edges, where each transaction failed to observe the other's
> write.

Here is a restatement of the same anomaly with RR event number
annotations, to make it easy for other people to match up each
observation/modification to a query from the log file I made available
yesterday:

G2-item #0
Let:
  T1 = {:type :ok, :f :txn, :value [[:append 1468 3] [:r 1469 nil]
[:append 1439 2]], :time 22408795244, :process 49, :index 10392}
  T2 = {:type :ok, :f :txn, :value [[:append 1469 1] [:append 1456 2]
[:r 1468 nil]], :time 22565885165, :process 45, :index 10464}

Then:
  - T1 < T2, because T1 observed the initial (nil) state of 1469 (at
RR 582419), which T2 created by appending 1 (at RR 581548).
  - However, T2 < T1, because T2 observed the initial (nil) state of
1468 (at RR 582018), which T1 created by appending 3 (at RR 581374):
-- a contradiction!

Possibly silly question: Doesn't "observing the initial (nil) state"
mean that no rows were returned by a SELECT statement? For example,
doesn't that just mean that the following SELECT statement returns no
rows?:

[rr 316514 582419]
1591388175.902-316514-13/403-1680806-SELECT-5edaa7f9.4d462-jepsen
process 49 LOG:  execute <unnamed>: select (val) from txn2 where sk =
$1
 1591388175.902-316514-13/403-1680806-SELECT-5edaa7f9.4d462-jepsen
process 49 DETAIL:  parameters: $1 = '1469'

--
Peter Geoghegan

Commits

  1. Doc: Add references for SI and SSI.

  2. Improve comments for [Heap]CheckForSerializableConflictOut().

  3. Avoid update conflict out serialization anomalies.

  4. Implement genuine serializable isolation level.