Thread: patch: update README-SSI
The attached patch updates README-SSI. In addition to some minor edits, changes include: - add a section at the beginning that more clearly describes the SSI rule and defines "dangerous structure" with a diagram. It describes the optimizations we use about the relative commit times, and the case where one transaction is read-only. It includes a proof for the latter (novel) optimization, per Heikki's request. - note that heap page locks do not lock "gaps" like index pages - be clear about what's been implemented (parts of the README used the future tense, probably because they were written long ago), and remove a couple items from the "R&D Issues" list that have since been addressed. Dan -- Dan R. K. Ports MIT CSAIL http://drkp.net/
Attachment
On 15.06.2011 23:28, Dan Ports wrote: > +SSI is based on the observation [2] that each snapshot isolation > +anomaly corresponds to a cycle that contains a "dangerous structure" > +of two adjacent rw-conflict edges: > + > + Tin ------> Tpivot ------> Tout > + rw rw > + > +SSI works by watching for this dangerous structure, and rolling > +back a transaction when needed to prevent any anomaly. This means it > +only needs to track rw-conflicts between concurrent transactions, not > +wr- and ww-dependencies. It also means there is a risk of false > +positives, because not every dangerous structure corresponds to an > +actual serialization failure. > + > +The PostgreSQL implementation uses two additional optimizations: > + > +* Tout must commit before any other transaction in the cycle > + (see proof of Theorem 2.1 of [2]). We only roll back a transaction > + if Tout commits before Tpivot and Tin. > + > +* if Tin is read-only, there can only be an anomaly if Tout committed > + before Tin takes its snapshot. This optimization is an original > + one. Proof: > + > + - Because there is a cycle, there must be some transaction T0 that > + precedes Tin in the serial order. (T0 might be the same as Tout). > + > + - The dependency between T0 and Tin can't be a rw-conflict, > + because T1 was read-only, so it must be a ww- or wr-dependency. > + Those can only occur if T0 committed before T1 started. There's no mention on what T1 is. I believe it's supposed to be Tin, in the terminology used in the graph. I don't see how there can be a ww-dependency between T0 and Tin. There can't be a rw-conflict because Tin is read-only, so surely there can't be a ww-conflict either? (the proof is still valid, though) > + - Because Tout must commit before any other transaction in the > + cycle, it must commit before T0 commits -- and thus before T1 > + starts. Another reference to T1. Patch looks good otherwise. -- Heikki Linnakangas EnterpriseDB http://www.enterprisedb.com
On Thu, Jun 16, 2011 at 04:39:09PM +0300, Heikki Linnakangas wrote: > There's no mention on what T1 is. I believe it's supposed to be Tin, in > the terminology used in the graph. Yes, I changed the naming after I originally wrote it, and missed a couple spots. T1 should be Tin. > I don't see how there can be a ww-dependency between T0 and Tin. There > can't be a rw-conflict because Tin is read-only, so surely there can't > be a ww-conflict either? Yes, it can only be a wr-conflict. Good catch. Dan -- Dan R. K. Ports MIT CSAIL http://drkp.net/
On 16.06.2011 20:33, Dan Ports wrote: > On Thu, Jun 16, 2011 at 04:39:09PM +0300, Heikki Linnakangas wrote: >> There's no mention on what T1 is. I believe it's supposed to be Tin, in >> the terminology used in the graph. > > Yes, I changed the naming after I originally wrote it, and missed a > couple spots. T1 should be Tin. > >> I don't see how there can be a ww-dependency between T0 and Tin. There >> can't be a rw-conflict because Tin is read-only, so surely there can't >> be a ww-conflict either? > > Yes, it can only be a wr-conflict. Good catch. Ok, I'll commit with those changes. -- Heikki Linnakangas EnterpriseDB http://www.enterprisedb.com