Thread: SSI using rw-conflict lists

SSI using rw-conflict lists

From
"Kevin Grittner"
Date:
Well, it's been a productive holiday weekend.  I've completed the
switch of the SSI implementation from one conflict pointer in and one
conflict pointer out per transaction to a list of conflicts between
transactions.  This eliminated all false positives in my dtester
suite.  The only test which had still had any was the one based on
the oft-cited receipting example, which had 210 permutations of how
the statements could be interleaved, of which six actually created an
anomaly; but about half the others were false positives because of
the limits of the conflict pointers.
For those following along, the initial (2008 ACM SIGMOD) paper on SSI
used booleans to flag conflicts.  Cahill's 2009 doctoral work
improved the false positive rate by switching these to pointers.  The
obvious next step for anyone competent in the field was to go from
simple pointers to lists.  That was in my mind as a useful
optimization from the beginning, but was brought to a head by Heikki
and Jeff with their concerns about memory management -- I couldn't
see a good way to fix that without first implementing the lists.
Along the way I also implemented more aggressive clean-up of memory
resources, including immediate complete clean-up of a transaction
which is rolled back.  The patch is now also poised to use Andres
Freund's "IDLE IN TRANSACTION cancellation" code in such a way that
SSI can guarantee that even the most pessimal load will not thrash to
the point of no progress -- when this is done, some transaction which
wrote data must successfully commit before transactions concurrent to
it can be cancelled.  These nice features required the conflict list.
I need some advice, though.  I had somehow had it in my head that
fields not declared static had a shared copy among all PostgreSQL
backends.  When things didn't behave properly, I discovered the error
of my ways, and moved them to a shared memory structure used by the
SSI code, just to get things working.  It looks kinda ugly at the
moment, and I'm not sure what would be considered "best practices" to
clean it up.
(1) Should these be moved to ShmemVariableCache, or is it OK to
leave them in this structure as long as I comment it adequately?
(2) Would it be a good idea to create macros for referencing these
fields?  The current references are long and distracting to read, and
would all need to change if the fields are moved to a different
shared memory structure.
The relevant commit diff is here:
http://git.postgresql.org/gitweb?p=users/kgrittn/postgres.git;a=commitdiff;h=bc3aba45e192afcd7776c68e28438991a3406db6
There's another issue involving clarity of code, versus correct
behavior.  When I got to the last few false positives, I found that
they could only be eliminated by tracking one more datum for a
transaction committed with a conflict out to another transaction. 
There was a field which was unused in the particular situations where
we needed this new datum, so I made it work with the dual use of the
existing field.
(3) What would be the cleanest way to conditionally store values
representing different things in one field of a structure, so that
someone reading the code understands what's happening?
The commit diff for this is here:
http://git.postgresql.org/gitweb?p=users/kgrittn/postgres.git;a=commitdiff;h=9425d7fa551a1433bdbec1de5cfb1bfa9f43da22
As always, any other tips or criticisms (or encouragement!) are
welcome.
-Kevin


Re: SSI using rw-conflict lists

From
Heikki Linnakangas
Date:
On 28.11.2010 23:44, Kevin Grittner wrote:
> (1) Should these be moved to ShmemVariableCache, or is it OK to
> leave them in this structure as long as I comment it adequately?

If they're only used by predicate.c, it seems better to leave them where 
they are.

> (2) Would it be a good idea to create macros for referencing these
> fields?  The current references are long and distracting to read, and
> would all need to change if the fields are moved to a different
> shared memory structure.
>
> The relevant commit diff is here:
>
>
http://git.postgresql.org/gitweb?p=users/kgrittn/postgres.git;a=commitdiff;h=bc3aba45e192afcd7776c68e28438991a3406db6

Maybe invent a short name for PredLockTranList and/or the fields? I'm 
not in favor of wrapping those references with macros, it can make it 
harder to understand the code, and unless the macro name is much 
shorter, it doesn't save all that much screen space anyway.

> There's another issue involving clarity of code, versus correct
> behavior.  When I got to the last few false positives, I found that
> they could only be eliminated by tracking one more datum for a
> transaction committed with a conflict out to another transaction.
> There was a field which was unused in the particular situations where
> we needed this new datum, so I made it work with the dual use of the
> existing field.>
> (3) What would be the cleanest way to conditionally store values
> representing different things in one field of a structure, so that
> someone reading the code understands what's happening?
>
> The commit diff for this is here:
>
>
http://git.postgresql.org/gitweb?p=users/kgrittn/postgres.git;a=commitdiff;h=9425d7fa551a1433bdbec1de5cfb1bfa9f43da22

I'd suggest a union field. We've done that e.g. in HeapTupleFields in 
access/htup.h.

--   Heikki Linnakangas  EnterpriseDB   http://www.enterprisedb.com


Re: SSI using rw-conflict lists

From
"Kevin Grittner"
Date:
Heikki Linnakangas <heikki.linnakangas@enterprisedb.com> wrote:
> Maybe invent a short name for PredLockTranList and/or the fields?
Done:
http://git.postgresql.org/gitweb?p=users/kgrittn/postgres.git;a=commitdiff;h=44c8f221100b87fc7c23425f53f2fd38d735b7d2
> I'd suggest a union field.
Done:
http://git.postgresql.org/gitweb?p=users/kgrittn/postgres.git;a=commitdiff;h=c6194da36186f8b13785cf606cda2a77f4422afc
Thanks for the feedback!
By the way, the serializable branch on my git repo is back to stable
now, if anyone wants to play with it.
Before going on to finish the graceful degradation work per previous
discussions, I'll try integrating the "IDLE IN TRANSACTION
cancellation" from the current CF to provide feedback from a
practical use case.  If Andres's patch works in that context, it
will allow SSI to provide a "guarantee of progress" even in the most
contrived and pessimal workloads.
-Kevin