Thread: Concurrent free-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
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 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@postgresql.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@tm.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