Florian Pflug <fgp@phlo.org> wrote:
> Hm, but for there to be an actual problem (and not a false
> positive), an actual dangerous circle has to exist in the
> dependency graph. The existence of a dangerous structure is just a
> necessary (but not sufficient) and easily checked-for condition
> for that, right? Now, if a read-only transaction only ever has
> outgoing edges, it cannot be part of a (dangerous or not) circle,
> and hence any dangerous structure it is part of is a false
> positive.
>
> I guess my line of reasoning is flawed somehow, but I cannot
> figure out why...
Here's why:
We're tracking rw-dependencies, where the "time-arrow" showing
effective order of execution points from the reader to the writer
(since the reader sees a state prior to the write, it effectively
executes before it). These are important because there have to be
two such dependencies, one in to the pivot and one out from the
pivot, for a problem to exist. (See various works by Dr. Alan
Fekete, et al, for details.) But other dependencies can imply an
order of execution. In particular, a wr-dependency, where a
transaction *can* see data committed by another transaction, implies
that the *writer* came first in the order of execution. In this
example, the transaction which lists the receipts successfully reads
the control table update, but is not able to read the receipt
insert. This completes the cycle, making it a real anomaly and not
a false positive.
Note that the wr-dependency can actually exist outside the database,
making it pretty much impossible to accurately tell a false positive
from a true anomaly when the pivot exists and the transaction
writing data which the pivot can't read commits first. For example,
let's say that the update to the control table is committed from an
application which, seeing that its update came back without error,
proceeds to list the receipts for the old date in a subsequent
transaction. You have a wr-dependency which is, in reality, quite
real and solid with no way to notice it within the database engine.
That's why the techniques used in SSI are pretty hard to improve
upon beyond more detailed and accurate tracking of rw-conflicts.
-Kevin
