SSI memory mitigation & false positive degradation

To recap, I've had an open question on the Serializable Wiki page[1]
since January about how we should handle long-running transactions.
The algorithm published by Cahill et al requires keeping some
transaction information in memory for all committed transactions
which overlapped a still-running transaction.  Since we need to keep
this in shared memory, and the structures must have a finite
allocation, there's an obvious looming limit, even if the allocation
is relatively generous.
 
The two obvious solutions on resource exhaustion are to roll back the
oldest active serializable transaction or to block or cancel new
serializable transactions.  Neither is particularly appealing. In
September and October Heikki was kind enough to share some insights
and ideas about alternatives.  I've done what I can to pursue this,
but my availability to follow up on it has been limited until now.  I
have blocked out a lot of time between now and the middle of January
to try to resolve the issue, and Dan has been able to devote time to
this lately as well.
 
I've been pursuing the ideas sketched out in a prior post[2] as a way
to work into the approach suggested by Heikki, which amounts to
summarizing old data (at the risk of some false positive
serialization failures) and accessing old data through the SLRU API
(and suffering some performance hit if that data spills to disk).
Pursuing mitigation through more aggressive cleanup seemed important
to me both to reduce the performance impact of the graceful
degradation approach, and to better understand which data are needed
when.
 
Dan and I have now implemented most of the mitigation techniques
described in [2], and I now feel confident I have a good grasp of how
long each type of data is useful.  (By useful I mean that to maintain
data integrity without them it will be necessary to roll back some
transactions which could have been allowed to commit had the data
been available.)  I'll be adding this to the Wiki page, but below are
the results, as I understand them.  I have yet to define exactly what
we will drop at which point, but that should be coming within a few
days.
 
Read only transactions only have one real need to track committed
data, but it is the most complex to state:
 
(1)  An active read only transaction needs to be able to recognize
when it is reading a tuple which was written by an overlapping
transaction which has committed, but only if that read write
transaction has a rw-conflict out to a transaction committed before
the read only transaction acquired its snapshot.
 
A read only transaction which detects such a rw-conflict out must
fail with a serialization conflict.  The multiple conditions required
for this, however, have an up-side -- they allow us to detect when a
read only transaction no longer has any possibility of creating such
a conflict, and therefore entirely removing it from predicate locking
and conflict detection.  This is true whether the read only
transaction is committed, active, or the new DEFERRABLE type of
transaction which will wait for these conditions before it starts.
 
I've found four statements about what committed data are useful for
read write transactions:
 
(2)  An active read write transaction needs to be able to recognize
when it is reading a tuple which was written by an overlapping
transaction which has committed, and to know whether that committed
transaction had any rw-conflict(s) out to previously committed
transaction(s).  This is rather similar to (1).
 
(3)  An active read write transaction needs to be able to detect when
one of its writes conflicts with a predicate lock from an overlapping
transaction which has committed.  There's no need to know which one,
but by the definition of a rw-conflict, it must have overlapped.
 
(4)  An active read write transaction needs to know that it had a
rw-conflict out to a committed transaction.  There's no need to know
which one, but by the definition of a rw-conflict, it must have
overlapped.
 
(5)  An active read write transaction needs to know that it had a
rw-conflict in from a committed transaction.  There's no need to know
which one, but by the definition of a rw-conflict, it must have
overlapped.
 
Since I know some people prefer to look at a patch than to poke
around someone's git repo, I'm attaching a patch reflecting what's in
the repo at the moment.  Consider it WIP.  While I hope to post a
patch as a serious candidate for the release within a couple weeks, I
would sure welcome any feedback before then, so the candidate patch
is in the best shape possible.  (To avoid confusion with Florian's
patch, I'm using ssi instead of serializable in file name and subject
lines.)
 
-Kevin
 
[1] http://wiki.postgresql.org/wiki/Serializable
 
[2] http://archives.postgresql.org/pgsql-hackers/2010-10/msg01754.php