Re: Restructured Shared Buffer Hash Table

>
> 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
<https://www.postgresql.org/message-id/CAM1e6U5XDwKYZo6Jj3yD3xpCB4qkhRSQn8upauHt=WhEbK9VZA@mail.gmail.com>
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(dot)aron(at)gmail(dot)com> wrote:

> On Tue, 7 Jul 2026 at 20:14, Heikki Linnakangas <hlinnaka(at)iki(dot)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(dot)bapat(dot)oss(at)gmail(dot)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(dot)bapat(dot)oss(at)gmail(dot)com> wrote:
>
>> On Wed, Jul 8, 2026 at 12:44 AM Heikki Linnakangas <hlinnaka(at)iki(dot)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
>>
>