Hi all,
I'm reading hash_resize recently, and have a few questions regarding
this algorithm. Please take a look if you have time. Any suggestions
are warmly welcomed.
=== Question 1 ===
In hash_resize.c : hashtab_lock_mod
186 if (b > READ_ONCE(htp->ht_resize_cur)) {
187 lsp->hbp[1] = NULL;
188 return;
189 }
190 htp = rcu_dereference(htp->ht_new);
It seems we are missing a barrier (e.g., smp_mb) in between lines 189
and 190, because neither READ_ONCE() nor rcu_dereference() can prevent
compilers and hardware from reordering the two unrelated variables,
ht_resize_cur and ht_new. Is my understanding correct?
=== Question 2 ===
In hash_resize.c, each time an updater wants to access a bucket, the
updater must first acquire the bucket's lock (htb_lock), preventing
other updaters accessing the same bucket concurrently. This approach
is OK if the linked list of a bucket is relatively short, but for a
larger system where linked lists are long enough and the
perftest_resize thread is running simultaneously, it could become a
potential performance bottleneck. One naive solution is to allow
multiple updaters to access the same bucket, only if they don't
operate on the same item of the list of this bucket. I wonder if there
are any existing works or discussions on this topic?
=== Question 3 ===
Chapter Data Structures also discusses other resizable hash tables,
namely "Resizable, scalable, concurrent hash tables via relativistic
programming" from Josh Triplett, which can save memory footprint by
using a single pair of pointers. But my understanding is that
perftest_resize.c is unique in that it allows you to rebuild the hash
table by utilizing a different hash function, which could be very
useful in practice (e.g., to prevent DDoS attack). Other solutions do
not share this property. Is my understanding correct? Did I miss any
discussions on this topic in perfbook?
=== Question 4 ===
In the current implementation of hash_resize.c, the perftest_resize
could block an updater, and vice versa. It seems this is not what we
expected. Ideally, they should be allowed to run concurrently, or at
least the perftest_resize thread should have lower priority and
updaters should never be blocked by the perftest_resize thread. Is
that right? I'm very interested in helping improve. Please let me know
if you have any suggestions.
Thanks,
--Junchang
