Re: WIP: dynahash replacement for buffer table

On Wed, Oct 15, 2014 at 2:03 AM, Andres Freund <andres@2ndquadrant.com> wrote:
> On 2014-10-14 17:53:10 -0400, Robert Haas wrote:
>> On Tue, Oct 14, 2014 at 4:42 PM, Andres Freund <andres@2ndquadrant.com> wrote:
>> >> The code in CHashSearch shows the problem there: you need to STORE the
>> >> hazard pointer before you begin to do the LOAD operations to scan the
>> >> bucket, and you must finish all of those LOADs before you STORE the
>> >> NULL hazard pointer.  A read or write barrier won't provide store/load
>> >> or load/store ordering.
>> >
>> > I'm not sure I understand the problem here - but a read + write barrier
>> > should suffice? To avoid falling back to two full barriers, we'd need a
>> > separate define pg_read_write_barrier(), but that's not a problem. IIUC
>> > that should allow us to avoid emitting any actual code on x86.
>>
>> Well, thinking about x86 specifically, it definitely needs at least
>> one mfence, after setting the hazard pointer and before beginning to
>> read the bucket chain.
>
> Yes, I can see that now. I do wonder if that's not going to prove quite
> expensive... I think I can see some ways around needing that. But I
> think that needs some benchmarking first - no need to build a even more
> complex solution if not needed.
>
> The solution I'm thinking of is to essentially move away from hazard
> pointers and store something like a generation counter per
> backend. Which is updated less often, and in combination with other
> operations. When a backend need to clean up and sees that there's a
> straggler with a old generation it sends that backend a signal to ensure
> it sets the latest generation.

It's possible that might work ... but on the timescale we're talking
about here, that's asking the garbage collecting process to wait for
practically geologic time.

Back when I first wrote this code, I spent a fair amount of time
looking at existing work in the area of lock-free hash tables.
Essentially all of the work I was able to find on this topic assumes a
threaded model - or more precisely, it assumes that shared memory
allocation is cheap and easy and you'll have no problem getting as
much of it as you need whenever you need it.  This assumption often
isn't even spelled out explicitly: it's just assumed that that's the
programming environment you're working in.  Finding highly parallel
algorithms that don't rely on memory allocation as a primitive is
hard.  Hazard pointers are one of the few techniques I found that
seems like it can work in our architecture.  I'm quite reluctant to
leave aside techniques that have been proven to work well in favor of
inventing something entirely novel to PostgreSQL.

That having been said, there is some literature on generation numbers,
and I think something like that could be made to work.  It does have
some significant disadvantages, though.  One is that a single process
which fails to update its generation number prevents all reclamation,
system-wide.    In my algorithm, a process whose execution is
suspended while a hazard pointer is set prevents recycling of only one
of many garbage lists.  A process searching for a reusable element can
mostly likely find some other garbage list to reclaim instead.  Also,
a generation number implies that we update the value periodically,
rather than before and after each critical section.  Anything that
forces garbage collection to be postponed longer than absolutely
necessary seems to me likely to be a loser.  It might be a little
faster as long as we have free elements to allocate, but as soon as
we're out and have to wait longer than we otherwise would for garbage
collection, and all system activity halts as a result, even for a few
milliseconds, it's going to be a whole lot slower.  Or at least, I
think.

That having been said, I don't know what to do about the fact that the
fence is too expensive.  I don't know that we've really established
that that's the true root of the problem rather than some other
pedestrian optimization failure.  But the existing code is using an
atomic operation to acquire a spinlock, then releasing it, walking the
bucket chain, and then using another atomic operation to acquire a
spinlock and then releasing it again.  Surely a pure fence shouldn't
cost more than a spinlock cycle?  Even with arguably one extra cache
line touch, that seems like it ought to be a win.  But my intuitions
in this area are shaky.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company