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. I took the basic infrastructure
from before and used it to replace the buffer table. Patch is
attached.
The key idea here is that lookups are done without any locks, only
memory barriers; and inserts and deletes are done using atomic ops.
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 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.
This patch contains assorted leftovers and is grotty in various ways,
but I'm sharing it anyway just to get it out there.
git branch also available at:
http://git.postgresql.org/gitweb/?p=users/rhaas/postgres.git;a=shortlog;h=refs/heads/chash2014
--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company