After wasting several days trying to come up with a way to make Postgres' lock manager spill to disk, I gave up and ICQed Bruce. This was mainly motivated by the fact that several people complained that the idea of having any process sleep on I/O waiting for the lock manager was a loser. After thinking on it for a while I cannot but agree. I even considered writing some sort of lightweight B-Tree handler on top of SLRU, so we could quickly find lock entries on disk by their LOCKTAG; this is better than using a plain sequential structure, but it's difficult to get right, it's lots of additional code, and it will still need I/O for getting locks :-(
So when I talked to Bruce, he simply said it was a bad idea to use the lock manager to lock tuples; we can't afford to have that many lock entries. In a way it was a disheartening idea. He wondered that maybe we should use some sort of Phantom TransactionIds, an idea on which hearing I almost freeze on terror – I had already heard of Phantom Xids from him, during the nested transactions project, and it was very painful (to me) to code and in the end it was an utter failure. (Althought coding that was a very interesting exercise from which I learned a thing or three – the patches and the disappointing comments from Tom are here.)
So I spent the next day thinking on phantom Ids and felt miserable ;-) because I didn't really see how would they apply to this case.
Turns out it's surprinsingly easy to have it all fit together. Phantom Xids in this case are just a means of indicating a set of TransactionIds; and we store the set on SLRU. So when somebody wants to lock a row, he creates a set; and when somebody needs to lock exclusively, he can sleep on every TransactionId of the set. The only tricky part is how to store variable length content on SLRU, but that is easily solved by using two SLRU areas.
So far I have coded a good deal of the whole thing; though it still doesn't do everything yet, I have now confirmed that the idea is perfectly workable and I'm sure it will have perfect performance.
This means we will have shared row locks for 8.1! I can't help but feel good about that. No more deadlocks in foreign keys. Cool!