Re: patch: update README-SSI

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