Re: Concurrent free-lock

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