Re: WIP: dynahash replacement for buffer table

On 2014-10-14 09:30:58 -0400, Robert Haas wrote:
> A few years ago I started working on a concurrent hash table for
> PostgreSQL. The hash table part of it worked, but I never did
> anything with it, really. Amit mentioned to me earlier this week that
> he was seeing contention inside the dynahash machinery, which inspired
> me to go back and update the patch.

Interestingly I've benchmarked similar loads, even on the same machine
as Amit, and I do seem trememdous time spent in dynahash.c. It's nearly
all cache misses in my tests though.

> I took the basic infrastructure
> from before and used it to replace the buffer table. Patch is
> attached.

That's pretty cool. The algorithm is complex enough that I haven't fully
understood it yet, but it sounds sane on a first glance.

> The key idea here is that lookups are done without any locks, only
> memory barriers; and inserts and deletes are done using atomic ops.

Hm. I quickly looked and I see that you use two full barriers for every
lookup. That's pretty expensive. I think this should be doable using
only read/write barriers on the lookup side? Even on architectures where
read/write memory barriers have to be something but a compiler barrier,
they're still usually a magnitude or so cheaper than full barriers.

> The algorithm is not strictly lock-free for reasons explained in the
> comments in chash.c, but it's a lot less locky than what we have now,
> so in theory you might think that would be a good thing.

I don't see much reason to strive for full lock-free ness. If the locks
aren't noticeable in real world scenarios - who cares?

> I haven't had time to do much performance testing yet, but it looks
> like this may be slower at low client counts and faster at high client
> counts. However, my results weren't real reproducible, and I haven't
> done comprehensive testing yet. What was really bizarre is that I
> couldn't really pin down the cause of the slowness at low client
> counts; a quick perf profile showed overhead concentrated in
> CHashBucketScan, basically memory access latency for walking the
> bucket chain. But the table is built to have a load factor of 1, so I
> can't see why that should amount to much, or why it should be
> significantly worse than for dynahash.

With regard for using a hash table for the buffer mapping lock I'm
doubtful that any form of separate chaining is the right one. We
currently have a quite noticeable problem with the number of cache
misses in the buffer mapping hash (and also the heavyweight lock mgr) -
if we stay with hashes that's only going to be fundamentally lower than
dynahash if we change the type of hashing. I've had good, *preliminary*,
results using an open addressing + linear probing approach.

My guess is that the additional indirection via the arena explains the
difference in cache misses? But I might be completely off here.

It'd be quite interesting to see a perf stat -ddd of dynahash.c/chash
employing builds for some comparable load.

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services