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.
---------------------------(end of broadcast)---------------------------
TIP 3: if posting/reading through Usenet, please send an appropriate
subscribe-nomail command to [EMAIL PROTECTED] so that your
message can get through to the mailing list cleanly
