Re: Concurrent free-lock

On Tue, 2005-01-25 at 13:59 +1100, Neil Conway wrote:
> On Mon, 2005-01-24 at 19:36 -0600, Min Xu (Hsu) wrote:
> > In any case, I think only when contention is high the non-blocking
> > algorithms are worth looking at. So can someone shine some light
> > on where the contention might be?
>
> The major point of contention that has been identified in the past is
> over the BufMgrLock, which is an LWLock that protects (1) the buffer
> manager's lookup hash table (2) some aspects of the state of individual
> buffers themselves (e.g. a buffer's flags and shared refcount -- see the
> BufferDesc structure). Amazingly, there *are* lock-free hash table
> algorithms (e.g. [1]), but at first glance they seem pretty complex, and
> I'm not sure how much they would help (we'd still need some form of
> synchronization to protect access to buffer flags etc.) I think the
> better route to fixing this problem is just rethinking how we do locking
> in the bufmgr.
>
> There probably are other points of contention, but I think the
> BufMgrLock has been the one that has stood out in the past -- if/when
> that is resolved it will be easier to see what issues remain.
>
> -Neil
>
> [1] http://www.cs.rug.nl/~wim/mechver/hashtable/
>

This is a very important thread. Many thanks to Jean-Gerard for bringing
the community's attention to this.

Jonah Harris points us to this link:
http://www.cl.cam.ac.uk/Research/SRG/netos/lock-free/
which refers directly to the paper that Jean-Gerard mentions:
http://www.cl.cam.ac.uk/netos/papers/2004-cpwl-submission.pdf
The papers authors are Keir Fraser and Tim Harris

This explains many things of interest.
Jonah's experience with problems at very high contention rates seems to
be associated with a specific technique, rather than lock-free
techniques altogether. Having read the whole damn paper I've now lost
the reference, but will re-read. (I thought that was OSTM, but I may be
wrong).

Most importantly, we should read Conclusion on pp44-46

Min Xu's comments that the algorithms seem complex appears correct, but
I think PostgreSQL should not shy away from that. MVCC is a very complex
algorithm that lies at the heart of the original postgres code - the
purpose was to remove multi-processor contention. It would seem entirely
consistent with its roots that PostgreSQL should adapt the latest
research on contention reducing techniques to improve the code base.
(Which was a root thinking behind the clever spotting and implementation
of the ARC code, AFAICS).

Gao et al's work (Neil's link shown above) on lock-free hash tables is
also interesting. The fact that it has taken two years to prove says
nothing about the complexity of their algorithm and makes me feel pretty
good about it too. Provable theorems make for robust code, eventually.

The one factor which stands out for me from this is that Keir Fraser's
and Tim Harris' algorithms are available as *code*, which additionally
are covered by a licence which appears to be an MIT/BSD variant licence.
On that basis, their recommendations and specific implementations sound
like we should take them seriously.

On Tue, 2005-01-25 at 13:59 +1100, Neil Conway wrote:
> I think the
> better route to fixing this problem is just rethinking how we do locking
> in the bufmgr.

I think this is an easier route, and dare I say one I can personally
understand, but we should not close the door on the lock-free algorithm
route just yet, I think.

--
Best Regards, Simon Riggs