Skip site navigation (1) Skip section navigation (2)

SSI using rw-conflict lists

From: "Kevin Grittner" <Kevin(dot)Grittner(at)wicourts(dot)gov>
To: <pgsql-hackers(at)postgresql(dot)org>
Cc: <drkp(at)csail(dot)mit(dot)edu>
Subject: SSI using rw-conflict lists
Date: 2010-11-28 21:44:03
Message-ID: 4CF278C30200002500037EC7@gw.wicourts.gov (view raw or flat)
Thread:
Lists: pgsql-hackers
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

Responses

pgsql-hackers by date

Next:From: Tom LaneDate: 2010-11-28 22:03:20
Subject: Re: Rethinking representation of sort/hash semantics in queries and plans
Previous:From: Robert HaasDate: 2010-11-28 21:25:35
Subject: Re: [GENERAL] column-level update privs + lock table

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group