Re: Restructured Shared Buffer Hash Table

On Tue, 7 Jul 2026 at 20:14, Heikki Linnakangas <hlinnaka@iki.fi> wrote:

On 07/07/2026 21:41, Dhruv Aron wrote:

At Databricks, we’ve found that the existing dynahash table structure is
leaving performance gains on the table when it comes to shared buffer
lookups: the multi-level structure (directory, segment, bucket chain,
freelist) appears excessive for the shared buffers and could be
simplified to boost performance and lower memory overhead. As such, we
are proposing a specialized hash table just for this purpose and would
appreciate feedback on this approach.

Yeah, the dynahash has features that we just don't need in the buffer
lookup table...

The indirection with the directory is actually unnecessary for all the
shared memory hash tables, since none of them can be resized. I've
wondered if we should try to eliminate that from dynahash for all shmem
hash tables. But the buffer lookup table is very performance-critical,
so if there are any performance gains to be had, it's indeed probably
worthwhile to have a separate implementation just for it.

bufmgr.c also changed slightly to prevent a race condition.

Hmm, we're now holding the buffer header lock much longer than before,
in InvalidateBuffer(). It's a spinlock, it really should not be held for
more than a few instructions. BufTableDelete() is very fast in the new
implementation, but still. Could we perhaps do some of
BufTableDelete()'s work ahead of time, before we acquire the buffer
header lock? Or maybe it's not a problem, in which case some kind of a
worst case scenario benchmark to show that would be nice. Maybe test how
it behaves when you have a lot of hash collisions, I think that'd make
BufTableDelete() more expensive.

My testing
(helper script also attached) indicates that all three standard hash
table operations (insert, lookup, and delete) generally execute
significantly faster than the existing PG18 dynahash counterparts:

Nice!

I wonder how big the impact is with real world workloads. I've certainly
seen the buffer table lookups consume a fair share of CPU time, so I'd
assume that it shows up.

Another data point:

unpatched master, with shared_buffers='128 MB':

postgres=# select * from pg_shmem_allocations where name like 'Shared
Buffer%' order by name ;
name | off | size | allocated_size
----------------------------+-----------+--------+----------------
Shared Buffer Lookup Table | 141607040 | 926000 | 926108
(1 row)

With this patch:

postgres=# select * from pg_shmem_allocations where name like 'Shared
Buffer%' order by name ;
name | off | size | allocated_size
------------------------------+-----------+--------+----------------
Shared Buffer Lookup Buckets | 141607040 | 65536 | 65644
Shared Buffer Lookup Entries | 141672576 | 393216 | 393216
(2 rows)

So the new hash table takes much less memory. That's nice because you
can then fit more in CPU caches.

Where did this thread come from? I can't see any conversation beyond
this single email, and as such, can't see any patch either.

Thom

On 08/07/2026 00:08, Thom Brown wrote:

Where did this thread come from? I can't see any conversation beyond
this single email, and as such, can't see any patch either.

Huh, maybe it got stuck in moderation? Dhruv CC'd me directly, but
you're right, I don't see it in the archives yet.

- Heikki

On Wed, Jul 8, 2026 at 12:44 AM Heikki Linnakangas <hlinnaka@iki.fi> wrote:

On 07/07/2026 21:41, Dhruv Aron wrote:

At Databricks, we’ve found that the existing dynahash table structure is
leaving performance gains on the table when it comes to shared buffer
lookups: the multi-level structure (directory, segment, bucket chain,
freelist) appears excessive for the shared buffers and could be
simplified to boost performance and lower memory overhead. As such, we
are proposing a specialized hash table just for this purpose and would
appreciate feedback on this approach.

Yeah, the dynahash has features that we just don't need in the buffer
lookup table...

The indirection with the directory is actually unnecessary for all the
shared memory hash tables, since none of them can be resized. I've
wondered if we should try to eliminate that from dynahash for all shmem
hash tables. But the buffer lookup table is very performance-critical,
so if there are any performance gains to be had, it's indeed probably
worthwhile to have a separate implementation just for it.

For very large buffer pools, the buffer lookup table spans multiple
memory pages. With buffer resizing capability it will be good to be
able to resize the buffer lookup table as well. Right now the patch
does not resize buffer look up table because of its memory layout and
complexity involved in that operation. If we are using a different
data structure for buffer lookup, it will be good to consider ease of
resizing as well.

--
Best Wishes,
Ashutosh Bapat

On Tue, 7 Jul 2026 at 20:14, Heikki Linnakangas <hlinnaka@iki.fi> wrote:

Or maybe it's not a problem, in which case some kind of a
worst case scenario benchmark to show that would be nice. Maybe test how
it behaves when you have a lot of hash collisions, I think that'd make
BufTableDelete() more expensive.

My additional benchmarking would suggest that, on average (one entry per
bucket), the spinlock would be held for an extra ~50ns compared to
releasing the header lock earlier for the current dynahash implementation:

Bucket Chain Length

Average Time Under Spinlock for Dynahash Implementation (ns)

Average Time Under Spinlock for New Table, Releasing Lock After Delete (ns)

1

64.4

112.9

2

63.4

118.6

4

63.1

122.3

8

68.8

139.8

16

76.0

159.1

32

77.7

195.0

64

102.0

248.6

On Tue, Jul 7, 2026 at 8:28 PM Ashutosh Bapat <ashutosh.bapat.oss@gmail.com>
wrote:

If we are using a different data structure for buffer lookup,
it will be good to consider ease of resizing as well.

Yes, we have internal functionality to resize (both shrink and expand) this
restructured table without rehashing the entire table, acquiring a global
lock, or introducing new synchronization primitives. Will create and share
a follow-up patch going into more detail soon.

Thanks,
Dhruv Aron

On Tue, Jul 7, 2026 at 8:28 PM Ashutosh Bapat <ashutosh.bapat.oss@gmail.com>
wrote:

Yes, we have internal functionality to resize (both shrink and expand)
this restructured table without rehashing the entire table, acquiring a
global lock, or introducing new synchronization primitives.

Please see the newly attached patch (based on this previously mentioned
patch
</messages/by-id/CAM1e6U5XDwKYZo6Jj3yD3xpCB4qkhRSQn8upauHt=WhEbK9VZA@mail.gmail.com&gt;
on dynamic shared buffers), particularly the changes to buf_table.c and
buf_resize.c, for the dynamic shared buffer table.

The entries array is resized to match the shared buffers: fewer entries
than buffers would result in some pages in the buffer pool not having
corresponding table entries, while more entries than buffers would just
result in unused entry slots and wasted memory. The buckets are resized to
match the entries array and guarantee *O(1)* lookups as much as possible.
As such, we resize the table to maintain a 1:1:1 mapping between shared
buffers, table entries, and buckets: buckets are resized directly after a
successful entries array resize, which occurs directly after a successful
shared buffer resize (see buf_resize.c); we reuse the same madvise()
technique for both cases as with the shared buffer resize and perform both
additional resizes within the critical section protected by the resize
coordinator.

For the bucket resizing process itself, we borrow dynahash’s linear hashing
scheme: it does not require any additional data structures, circumvents the
need for total table rehashing, and already fits with the existing Postgres
systems (allowing us to reuse partition locks for concurrency and
eliminating the need to introduce additional unnecessary complexity into
the codebase). Bucket hashing is thus based on the low/high masks and
number of buckets, with the low mask and the number of buckets (not the
high mask, see below) stored as atomics within shared memory. We continue
enforcing that the number of partitions is a power of 2 greater than one
and that the number of buckets is at least the number of partitions, which
ensures that each bucket and its partner bucket belong to the same
partition. However, we no longer require that the number of buckets is a
multiple of the number of partitions, which allows us to add/remove buckets
individually and generally maintain a 1:1 mapping between entries and
buckets.

During an expansion where *n* buckets are said to be added, the physical
memory is allocated (if necessary) for the new buckets. Afterwards, for
each of the added *n* buckets, the appropriate partition lock is acquired,
the number of buckets and low mask are adjusted appropriately, entries from
the partner bucket are moved if they now hash to the new bucket, and then
the partition lock is released.

During a shrink where *n* buckets are said to be removed, for each of the
*n* buckets being removed, the appropriate partition lock is acquired,
entries are transferred to the partner bucket, the number of buckets and
low mask are adjusted appropriately, and then the partition lock is
released. Only then is the physical memory behind the removed buckets
freed.

Maintaining concurrency during bucket resizes:

- The resize coordinator in buf_resize.c that prevents multiple shared
buffer resizes from occurring simultaneously will also ensure that multiple
bucket resizes cannot occur simultaneously.
- Since the number of buckets and low mask are in shared memory,
multiple backends can concurrently access those variables and continue with
standard hash table operations.
- Acquiring the partition lock for the bucket being added/removed
ensures that race conditions do not occur between the backend performing
the bucket resize process and other backends attempting to perform standard
table operations regarding the same bucket(s).
- Also, notice how we do not utilize any mutexes or barriers for the two
atomic shared variables: the linear hashing scheme guarantees that, as long
as a backend is not attempting to access a bucket currently involved in a
resize (which would be protected by the partition lock), the backend will
still hash to the same bucket regardless of whether it sees old or new
values for the number of buckets and the low mask (even if one is old and
one is new).
- Note: to be explicit, we do not directly store the high mask in order
to avoid torn reads between the low and high masks; we simply store the low
mask and always recompute the high mask based on the low mask.

Hoping that this makes sense and is helpful.

Thanks,
Dhruv Aron

On Fri, Jul 10, 2026 at 11:53 AM Dhruv Aron <dhruv.aron@gmail.com> wrote: