Concurrent wait-lock

Hi,

I read recently a paper
Keir Fraser & Tim Harris, Concurrent Programing without Locks, ACM
Journal Name, vol V, n° N, M 20YY, Page 1-48

About algorithm to manage structure (exemple about red-black tree, skip
list) with dead-lock free property, parallel read, etc.

Does this have been studied for PostgreSQL ?
There is surely some good idea in it.

Cordialement,
Jean-Gérard Pailloncy

Lock free data structures are cool... but not really applicable to
databases. They have a high maintenance overhead, severe complexity,
and will fail when there are many concurrent inserts/deletes to the
structure. I messed with them a year or so ago, and that's what I found
in every implementation.

Pailloncy Jean-Gerard wrote:

> Hi,
>
> I read recently a paper
> Keir Fraser & Tim Harris, Concurrent Programing without Locks, ACM
> Journal Name, vol V, n° N, M 20YY, Page 1-48
>
> About algorithm to manage structure (exemple about red-black tree,
> skip list) with dead-lock free property, parallel read, etc.
>
> Does this have been studied for PostgreSQL ?
> There is surely some good idea in it.
>
> Cordialement,
> Jean-Gérard Pailloncy
>
> ---------------------------(end of broadcast)---------------------------
> TIP 9: the planner will ignore your desire to choose an index scan if
> your
> joining column's datatypes do not matc
> h

On Mon, 2005-01-24 at 08:35 -0700, Jonah H. Harris wrote:
> Lock free data structures are cool... but not really applicable to
> databases. They have a high maintenance overhead, severe complexity,
> and will fail when there are many concurrent inserts/deletes to the
> structure.

Can you elaborate on when they would fail, and why?

It might be worth considering lock-free data structures for certain
parts of the backend, but I'm skeptical they would be much of a win over
locking most of the time.

-Neil

Neil,

Here is some pretty good info on lock-free structures... I'm pretty sure
I tested their code in a multithreaded high-concurrency environment and
experienced the problems I was discussing.

http://www.cl.cam.ac.uk/Research/SRG/netos/lock-free/

Neil Conway wrote:

>On Mon, 2005-01-24 at 08:35 -0700, Jonah H. Harris wrote:
>
>
>>Lock free data structures are cool... but not really applicable to
>>databases. They have a high maintenance overhead, severe complexity,
>>and will fail when there are many concurrent inserts/deletes to the
>>structure.
>>
>>
>
>Can you elaborate on when they would fail, and why?
>
>It might be worth considering lock-free data structures for certain
>parts of the backend, but I'm skeptical they would be much of a win over
>locking most of the time.
>
>-Neil
>
>
>
>

On Mon, 2005-01-24 at 16:50 -0700, Jonah H. Harris wrote:
> Here is some pretty good info on lock-free structures... I'm pretty sure
> I tested their code in a multithreaded high-concurrency environment and
> experienced the problems I was discussing.

Fair enough, but my hope would be that those problems were the result of
bugs in the implementation rather than some fundamental property of
lock-free data structures. A concurrency control mechanism that falls
over under concurrent access sounds a little broken, no?

-Neil

Neil and others,

It might be interesting to look at some of the papers by Michael
Scott et al. I am not an expert on non-blocking data structures,
but the following page seems interesting:

http://www.cs.rochester.edu/u/scott/synchronization/

esp. "(7) nonblocking "dual" data structures, which combine lock freedom
with condition synchronization; and (8) contention management for software
transactional memory"

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?

Cheers!

-Min

On Tue, 25 Jan 2005 Neil Conway wrote :
> On Mon, 2005-01-24 at 16:50 -0700, Jonah H. Harris wrote:
> > Here is some pretty good info on lock-free structures... I'm pretty sure
> > I tested their code in a multithreaded high-concurrency environment and
> > experienced the problems I was discussing.
>
> Fair enough, but my hope would be that those problems were the result of
> bugs in the implementation rather than some fundamental property of
> lock-free data structures. A concurrency control mechanism that falls
> over under concurrent access sounds a little broken, no?
>
> -Neil
>
>
>
> ---------------------------(end of broadcast)---------------------------
> TIP 3: if posting/reading through Usenet, please send an appropriate
> subscribe-nomail command to majordomo(at)postgresql(dot)org so that your
> message can get through to the mailing list cleanly

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/

On Tue, 25 Jan 2005 Neil Conway wrote :
> Amazingly, there *are* lock-free hash table
> algorithms (e.g. [1]), but at first glance they seem pretty complex, and

It is a little scary when I read the lock-free hash table algorithm
needs a theorem prover to prove its correctness. I'd guess maintaining
such code is hard.

> 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.

I completely agree. Ultimately, if a piece of code has "true" contention,
i.e. the contention was not due to coarse-grain locking, then perhaps
redesigning the algorithm is a better solution. I certainly have no
idea what is the code of the bufmgr looks like. May the problem here
be coarse-grain locking?

> Here is some pretty good info on lock-free structures... I'm pretty
> sure I tested their code in a multithreaded high-concurrency
> environment and experienced the problems I was discussing.
I understand.
The algorithm is quite complex.
The old version was not really fast.

In the paper cited, some tests was done with 90 concurrent threads, and
with different density of data inside the structure. I found really
interresting (but I am not expert of this field).

Most of the researcher that work on "concurrent lock free" algorithm
understand the complexity, and to help anyone to use it, they provide
this technology for a whole algorithm.
There are libraries for red-black tree, skip-list, hash-table, etc.

I did not read the detail of the code to know if we may use it as a
direct remplacement.

http://www.cl.cam.ac.uk/Research/SRG/netos/lock-free/
http://www.cl.cam.ac.uk/users/kaf24/lockfree.html
http://www.audiomulch.com/~rossb/code/lockfree/
http://www.cs.rochester.edu/u/scott/synchronization/

Cordialement,
Jean-Gérard Pailloncy

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

Simon,

You are correct. My negative experience with lock-free data structures
has been due to the different implementations I've tried. The theory
sounds good and no doubt, a good implementation could very likely be
developed with some time. I'm in no way against using lock-free data
structures in PostgreSQL as long as significant work is done on the
implementation.

-Jonah

Simon Riggs wrote:

>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.
>
>
>

Simon Riggs wrote:
> 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.

If you're referring to their "Lock-free library", that is licensed under
the GPL.

-Neil

On Wed, 2005-01-26 at 13:30 +1100, Neil Conway wrote:
> Simon Riggs wrote:
> > 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.
>
> If you're referring to their "Lock-free library", that is licensed under
> the GPL.

Maybe, but the one we want is not on the GPL.

This is the code that is recommended in the summary of lock-free
methods:

http://www.cl.cam.ac.uk/Research/SRG/netos/lock-free/

libstm-v1.tar.gz

--
Best Regards, Simon Riggs

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

I was working during my PhD on some parallel algorithm. The computer
was a 32-grid processor in 1995. In this architecture we need to do the
lock on the data, with minimum contention. We can not do a lock on the
code path with mutex, because there was 32 different boards and a sync
across the system was not doable. The data was a mesh graph that
represent the segmentation of some satellite image.

When I see this paper with some good test, I remember this old days and
think that if we have some generic algorithm for type like hash, tree,
list with "lock-free parallel read" property it will be a very good
win.
I think about an other paper I read on the PostgreSQL site about an
algorithm with a global ordering of transaction design for multi-master
database. I do not remember the url.

The third thing that come to my mind, is the next generation of
slony/pgcluster.

Cordialement,
Jean-Gérard Pailloncy

Ühel kenal päeval (kolmapäev, 26. jaanuar 2005, 13:30+1100), kirjutas
Neil Conway:
> Simon Riggs wrote:
> > 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.
>
> If you're referring to their "Lock-free library", that is licensed under
> the GPL.

That's great news, as it removes one of my greatest fears from reading
this thread - namely that there is a submarine patent on their
algorithms waiting to surface.

One of GPL's requirements is free grant of patent use.

But it may be that the free patent grant applies only to GPL code, so we
may be back to the problems we are struggling in ARC vs. LRU ;(

--
Hannu Krosing <hannu(at)tm(dot)ee>

Hi,

There is better than lock-free algorithm, this is wait-free.

A lock-free algorithm guarantees progress regardless of whether some
processes are delayed or even killed and regardless of scheduling
policies. By definition, a lock-free object must be immune to deadlock
and livelock.
A wait-free algorithm guarantees that ALL processes will progress and
FINISH in a finite number of steps.

Wait-Free Reference Counting and Memory Management
http://www.cs.chalmers.se/~phs/TechnicalReports/Sun04_WaitFreeRef.pdf

There are many other paper at
http://www.cs.chalmers.se/~phs/

Cordialement,
Jean-Gérard Pailloncy