Horton

Re: Potential G2-item cycles under serializable isolation

Kyle Kingsbury <aphyr@jepsen.io>

View thread View on postgr.es
From: Kyle Kingsbury <aphyr@jepsen.io>
To: Peter Geoghegan <pg@bowt.ie>
Cc: PostgreSQL mailing lists <pgsql-bugs@lists.postgresql.org>
Date: 2020-06-05T12:05:23Z
Lists: pgsql-bugs 
On 6/4/20 10:03 PM, Peter Geoghegan wrote:
>> Are you familiar with the paper "Serializable Snapshot Isolation in
>> PostgreSQL"? You might find it helpful:
>>
>> http://vldb.org/pvldb/vol5/p1850_danrkports_vldb2012.pdf
It's been several years since I've read it, and it's worth revisiting. Thanks 
for the recommendation! Yes, I think a good way to understand Elle's G2-item is 
that it might be (and I'm not entirely sure about this--this was only a cursory 
read last night) one of the "dangerous structures" in the Postgres SSI paper. I 
elided this earlier to try and keep things simple, but we actually separate out 
cycles featuring *nonadjacent* rw edges and consider them a separate sort of 
anomaly in Elle, so we can distinguish between snapshot isolation and 
serializability more precisely.
>> Is there a difference between "rw dependencies" as you understand the
>> term, and what the paper calls "rw-antidependencies"?
Yes, my apologies. "anti-dependency" = "rw-antidependency" = "rw dependency" = 
"T1 read state x1, and T2 installed state x2, such that x1 immediately precedes 
x2".
>> "3.2 Serializability Theory" has some stuff about Adya et al, but also
>> talks about the work of Fekete et al -- apparently they built on the
>> Adya paper (both papers share one author). Are you familiar with the
>> Fekete paper?

Yes! Some of Elle's inferences are based in part on Fekete et al.'s work, and 
we've corresponded some during Elle's development. :)

---Kyle

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.