Re: Concurrent free-lock - Mailing list pgsql-hackers
From | Jonah H. Harris |
---|---|
Subject | Re: Concurrent free-lock |
Date | |
Msg-id | 41F6D5B0.4060701@tvi.edu Whole thread Raw |
In response to | Re: Concurrent free-lock (Simon Riggs <simon@2ndquadrant.com>) |
List | pgsql-hackers |
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. > > >
pgsql-hackers by date: